Levenshtein automaton
Encyclopedia
In computer science
, Levenshtein automata for a formal language
are the family of finite state automata that can recognize the set V of all words in the language for which the Levenshtein distance
to an arbitrary word w does not exceed a particular constant. Levenshtein transducers are extended Levenshtein automata that can in addition generate all strings in V at a fixed Levenshtein distance from a given w.
A Levenshtein automaton for W can be constructed in linear time with respect to the length of W, and can identify V in 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
).
Since Levenshtein automata are finite-state machines, they can be described in (some) regular expression frameworks and finite-state algebra applies to them. In particular, Levenshtein transducers can be composed with other finite-state transducers.
Experimental implementations of the Levenshtein automaton exist in Python and Java
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, Levenshtein automata for a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
are the family of finite state automata that can recognize the set V of all words in the language for which the Levenshtein distance
Levenshtein distance
In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences...
to an arbitrary word w does not exceed a particular constant. Levenshtein transducers are extended Levenshtein automata that can in addition generate all strings in V at a fixed Levenshtein distance from a given w.
A Levenshtein automaton for W can be constructed in linear time with respect to the length of W, and can identify V in 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
Time complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
).
Since Levenshtein automata are finite-state machines, they can be described in (some) regular expression frameworks and finite-state algebra applies to them. In particular, Levenshtein transducers can be composed with other finite-state transducers.
Experimental implementations of the Levenshtein automaton exist in Python and Java
External links
- Ahmed Hassan, Sara Noeman and Hany Hassan (2008). Language Independent Text Correction using Finite State Automata. Proc. IJCNLP.
- Petar N. Mitankin (2005). Universal Levenshtein Automata. Building and Properties. Thesis for the Sofia University St. Kliment Ohridski.
- Klaus U. Schulz and Stoyan Mihov (2002). Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.