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.
Subscribe to:
Post Comments (Atom)
1 comments:
dynamic programming is quite powerful but sometimes the generic solution is not enough. The blast algorithm is a good example of that...
Post a Comment