Fuzzy Searching (soundex, similar_text, metaphone etc.)

andrewm

I own and operate a review website with a few thousand products. In an attempt to make my website more user friendly I would like people to be able to find a product even if they don't spell the name correctly.

Instead of just automatically selecting products that their search was close to, I would like to try to create something like Google's "Did you mean: XXXX" search correction, so that the user knows they spelled the name incorrectly.

I'm new to fuzzy searching, but this is my plan so far...

Start off by creating a list of unique words taken from product names (they include manufacturer names) and storing them in a table.

This...

Ford Focus
Ford Explorer
Mercedes Benz SLK

Would become...

Ford
Focus
Explorer
Mercedes
Benz
SLK

When a user searches their query will be broken into pieces by spaces or dashes. Each word from the query will be compared against the table with all the words compiled from product names. If the word matches exactly with a word from the table, then it is A-OK, otherwise we will try to find if there is a word it is close to...

Now this is where I am kind of confused as to what to use. I've played around with soundex, similar_text, metaphone, and levenshtein a little bit, but I am not still not sure what would be the best to use in this case. I've even read that people use two of the functions (ie levenshtein and metaphone) together for the best results.

http://www.php.net/similar_text
http://www.php.net/levenshtein
http://www.php.net/metaphone
http://www.php.net/soundex

Any opinions or tips?

Thanks!

ednark

wow hope your server wants a hurting.. if you are going to be doind these searches a lot i would suggest using either metaphon or levenshtein. levenshtein cares not about pronunciation so it would be better at finding just mispellings (i would think) but metaphon would be better at finding horrible similar sounding manglings of code. If you are going to use metaphon please do not recalculate the metaphon string each time.

try making a seperate table
[ PRODUCT_ID | METAPHON_OF_NAME ]
so you need only calculate the mataphon string once upon insertion, and maybe again if the product name gets altered..

then i would use each search term the user inputs, and metaphon each word... then levenshtein that with whats in the DB for a percentile match... then on the matching items... link back to the PRODUCT_ID associated with that...

also read down the meta and lev pages in the php manual.. useful comments there.

andrewm

Thanks for the tips.

For some reason the idea of levenshtein a metaphone didn't click in my head. Thanks. I'll play around with it.

There are going to be around 3k searches a day, but most of them won't even need this because the users will be spelling product names correctly.

andrewm

Wow, I can't believe I missed that first comment on the levenschtein page. Good stuff.