How to implement the 'did-you-mean' feature?

[mPeror]

I'm basically trying to implement a did-you-mean feature like google. See for example when you search for 'sitepppoint', the results will show 'Did you mean: sitepoint' regardless if it had any results or not.

So, how can this be done? (i'm not looking for code, i just need the concept explained in either a small example or clear text).


Your help is much appreciated

[babyboy808]

Well not sure about this one, but i once made a small version of this, I had a few keywords relating to food, pasta, pizza, burger etc. and each food item eg => burger had an array relating to it (buurger, buger, bugger etc). and if a user entered in a value of the array, it would output burger...

[mPeror]

Well that'd be a good idea for a very small database or few keywords, but the database i'm working on is always expanding, and i can't make up typos of each entry. I'm trying to make some sort of "smart" script, but i don't have any idea how this is approached.

[Eugene Bond]

Try to take a look here: http://php.net/pspell

[stereofrog]

So, how can this be done? (i'm not looking for code, i just need the concept explained in either a small example or clear text).

Start here
http://en.wikipedia.org/wiki/Fuzzy_string_searching

[trib4lmaniac]

soundex
levenshtein
metaphone

A combination of the three is almost scary

[momos]

Most of the time levenshtein is sufficient for this kind of search.

[trib4lmaniac]

Most of the time levenshtein is sufficient for this kind of search.

It's a bit dodgy with string lengths though. It sometimes says two words are similar even when one of them is, say 5x bigger. Using a combination of the above functions can fix this.

[stereofrog]

Most of the time levenshtein is sufficient for this kind of search.

Can you tell us how would you use levenshtein() for searching in a database of, say, 100,000 words?

[trib4lmaniac]

Thankfully MySQL has the soundex function built in, which should reduce the result set dramatically.

SELECT * FROM `words` WHERE SOUNDEX(`word`) = SOUNDEX('$search')

Store these into an array and then (why is there no recursive array sort function?):

for($i = 0; $i < (count($words) - 1); $i++)
    if(levenshtein($words[$i], $search) > levenshtein($words[$i + 1], $search)) {
        $temp = $words[$i];
        $words[$i] = $words[$i + 1];
        $words[$i + 1] = $temp;
    } 

I'm only guessing here though as I've never attempted fuzzy searching before

[F4nat1c]

The PSpell suggestion by Eugene is the best. The others require a manually produced database of 'keywords' where as with pspell you already have a spelling library.

[stereofrog]

Thankfully MySQL has the soundex function built in, which should reduce the result set dramatically.

SELECT * FROM `words` WHERE SOUNDEX(`word`) = SOUNDEX('$search')

This makes sense, however soundex is far from accurate, especially if first letters don't match (try sitepoint/citepoint). metaphone() is better, but in that case you have to index dict tables in php (or switch to postgres ).