3 ms·

In PHP, you can use the levenshtein() function. http://php.net/manual/en/function.levenshtein.php http://php.net/manual/en/function.levenshtein.php

• l0nwlf 16y ago
  Levenshtein Distance ( http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance ) is a standard algorithm taught in algorithm courses as a standard example of Dynamic Programming. Some discussion here : http://stackoverflow.com/questions/1564184/edit-distance-algorithm http://stackoverflow.com/questions/1564184/edit-distance-alg...
• cloudkj 16y ago
  Levenshtein/edit distance isn't too useful for spell checking though. Edit distance can yield you the absolute difference between two words, but your goal is to find the words that have the smallest such distance with the word in question. Simply calculating the edit distance between the word in question and all other dictionary words isn't good enough - you'll have to be a bit more clever.
• adamzochowski 16y ago
  Levenshtein is good for many languages. However, for English nothing beats soundex type algo. I believe major SQLs and php do soundex. Soundex is an old algorithm, century old, designed to find immigrants by their last name, no matter how they converted it from their native language to english. For example: if one came and had name Szczybliewski or had it Shcheeblevsky , then soundex should return close match. Metaphone is improved version of soundex (available in php). And if you are careful, you can find double-metaphone out there. Kind regards
  • Terretta 16y ago
    I dropped by to say this. The examples in Future Work 2 would all have been resolved by checking results against Soundex, a simple check with significant improvement. There are two classes of errors: misspellings and typos. Edit distance (Levenshtein) is reasonable for typos, while the examples in Future Work 2 are misspellings. Another trivial improvement is to weight edit distance by typo distance.