Введение
Математическая модель для сравнения строк. В информатике, автомат Левенштейна для строки w и числа n — это конечный автомат, способный распознавать множество всех строк, расстояние Левенштейна от которых до w не превышает n. То есть, строка x принадлежит формальному языку, распознаваемому автоматом Левенштейна, тогда и только тогда, когда строку x можно преобразовать в строку w не более чем n односимвольными вставками, удалениями и заменами.
In computer science, a Levenshtein automaton for a string w and a number n is a finite state automaton that can recognize the set of all strings whose Levenshtein distance from w is at most n. That is, a string x is in the formal language recognized by the Levenshtein automaton if and only if x can be transformed into w by at most n single character insertions, deletions, and substitutions.
Приложения
Автоматы Левенштейна могут использоваться для коррекции орфографических ошибок путем поиска в заданном словаре слов, близких к ошибочно написанному слову. В этом случае, после того как слово определено как содержащее ошибку, для него строится автомат Левенштейна, который затем применяется ко всем словам словаря, чтобы определить, какие из них находятся на близком расстоянии от ошибочного слова. Если словарь хранится в сжатом виде в виде три, то время работы этого алгоритма (после построения автомата) пропорционально количеству узлов в три, что значительно быстрее, чем вычисление расстояния Левенштейна с помощью динамического программирования для каждого слова словаря по отдельности.
Строительство
Для любой фиксированной константы n автомат Левенштейна для w и n может быть построен за время O(|w|). Тузе предложил эффективный алгоритм для построения этого автомата. Еще одним способом построения конечного автомата для вычисления расстояния Левенштейна (или Дамерау–Левенштейна) являются преобразователи Левенштейна, предложенные Хассаном и др., которые демонстрируют конечные автоматы, реализующие расстояние редактирования, равное 1, а затем компонуют их для реализации расстояний редактирования до некоторой константы.