Levenshtein automaton
From Wikipedia, the free encyclopedia
In computer science, Levenshtein automata are a family of finite state automata that can recognize the set V of all words in a formal language for which the Levenshtein distance to an arbitrary word W does not exceed a particular constant. A Levenshtein automaton for W can be constructed in linear time proportional to the length of W, and can identify V in much less time than would be needed if the Levenshtein distance to W was calculated for each word in the language (a problem with quadratic time complexity).
[edit] References
- Klaus U. Schulz, Stoyan Mihov, Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.