DevOps Articles

Spell Autocorrect With Edit Distance and Trie

For most spell checkers, a candidate word is considered to be spelled correctly if it is found in a long list of valid words called a dictionary.

The following rules define how a word is determined to be most similar: If there is more than one word in the dictionary that is an edit distance of 1 from the input string, return the one that appears the greatest number of times in the original text file.

If there is no word at an edit distance of 1 from the input string then the most “similar” word in the dictionary (if it exists) will have an edit distance of 2.

If there is no word in the dictionary that has an edit distance of 1 or 2, there is no word in the dictionary “similar” to the input string.