Sunday, July 27, 2008
Spellchecker (Levenshtein distance)
Have you ever wondered how the spellchecker suggestions are computed? I had no idea, and found out that the editing distance between words is calculated to come up with a list of words that are "close" to the one you are typed. Those with the fewest number of edits are displayed. The algorithm, known as Levenshtein distance, was devised in 1965. It uses dynamic programming, and it is a very clever and simple solution.