Levenshtein automaton
Encyclopedia : L : LE : LEV : Levenshtein automaton
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).
References
- Klaus U. Schulz, Stoyan Mihov, [Fast String Correction with Levenshtein-Automata]. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.