Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: "Fuzzy" text search using n-grams (bigrams) -- speed?

Re: "Fuzzy" text search using n-grams (bigrams) -- speed?

From: crazyhorse <mjbaldwin_at_yahoo.com>
Date: Wed, 24 Oct 2007 21:53:48 -0700
Message-ID: <1193288028.112717.319810@i13g2000prf.googlegroups.com>


On Oct 24, 9:48 pm, Bob Badour <bbad..._at_pei.sympatico.ca> wrote:
> crazyhorse wrote:
> > Hi all,
>
> > Let's suppose I'm writing a website where users search for movie
> > titles, and suppose there are 200,000 movies. The site is in PHP/
> > MySQL.
>
> > I'd like to implement a "fuzzy" text search so that similar movie
> > titles come up in a list no matter if you include all the words or
> > even misspell them.
>
> > MySQL's fulltext-search is a first step, but it doesn't cover mis-
> > spellings.
>
> > My question is this: suppose I broke down every movie title into
> > bigrams (i.e. "Jaws" becomes *j, ja, aw, ws, s*), and store a
> > relationship between every bigram and every movie title that includes
> > it in a separate table, BIGRAMS. (Will have two fields, "bigram" and
> > "movie_id").
>
> > I break down every search string into bigrams. Then, for every search,
> > I retrieve all the rows from BIGRAMS that include any of the bigrams
> > in the search string. I then calculate COUNT(movie_id) ORDER BY DESC
> > and take the top matches.
>
> > Comments? Anybody have experience with this? Does it work? Or would it
> > be far too slow? Is there another better solution I'm missing? We're
> > talking 200,000 movies, which means BIGRAMS might have 4 million rows
> > or so.
>
> > Thanks
> > Michael
>
> http://en.wikipedia.org/wiki/Stemming

That doesn't really help... I'm trying to compensate for spelling errors, not different grammatical forms of words... Received on Wed Oct 24 2007 - 23:53:48 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US