Is there a way to search SQL database for similar words (mean not identical words) ?

Question

Hello, Is there a way to search MySQL database for similar words (mean not identical words) . For example : user searches in database for word "abcd" and there is a word "abd" in the database so the search engine or the program Ask the user "Do you mean [abd] ? " as in most of search engines in the web ? Please notice that the search word is not a part of the existing word (can't use "like")

Answer 1

Depends on how far apart they are, you could look into soundex perhaps..

http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#function_soundex

Answer 2

Check out Levenshtein_distance

Answer 3

Have a look at the Damerau-Levenshtein distance algorithm. It calculates the "distance" between two strings and determines how many steps it takes to transform one string into another. The less steps the closer the two strings are.

This article shows the algorithm implemented as a MySQL stored function.

The algorithm is so much better than LIKE or SOUNDEX.

I believe Google uses crowd sourced data rather than an algorithm. ie if a user types in abcd, clicks on the back button and then immediately searches for abd then it establishes a relationship between the two search terms as the user wasn't happy with the results. Once you have a very large community searching then the pattern appears.

Answer 4

Another technique is to create indexes on trigrams.