Suggested Final Project Topics

Levenshtein Automata

Levenshtein distance is a measure of the difference between two strings as a function of the number of in-

sertions, deletions, and replacements required to turn one string into another. Although most modern

spell-checkers and autocomplete systems are based on machine-learned models, many systems use Leven-

shtein edit distance as a metric for finding similar words. Amazingly, with a small amount of preprocess-

ing, it's possible to build an automaton that will match all words within a given Levenshtein distance of an

input string.