Levenshtein automaton

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, " [http://citeseer.ist.psu.edu/schulz02fast.html Fast String Correction with Levenshtein-Automata] ". International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Levenshtein distance — In information theory and computer science, the Levenshtein distance is a string metric for measuring the amount of difference between two sequences. The term edit distance is often used to refer specifically to Levenshtein distance. The… …   Wikipedia

  • List of Russian IT developers — This list of Russian IT developers includes the famous hardware engineers, computer scientists and programmers from the Russian Empire, the Soviet Union and the Russian Federation. See also the Category:Russian computer scientists and… …   Wikipedia

  • List of Russian mathematicians — Andrey Kolmogorov, a preeminent 20th century mathematician. This list of Russian mathematicians includes the famous mathematicians from the Russian Empire, the Soviet Union and the Russian Federation. This list is incomplete; you can help by …   Wikipedia

  • List of Russian people — The Millennium of Russia monument in Veliky Novgorod, featuring the statues and reliefs of the most celebrated people in the first 1000 years of Russian history …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”