Войти
В информатике, автомат Левенштейна для строки w и число n является конечный автомат, который может распознать набор всех строк, для которых расстояние Левенштейна от w не превосходит n. То есть строка x находится на формальном языке, распознаваемом автоматом Левенштейна тогда и только тогда, когда x может быть преобразовано в w с помощью не более n односимвольных вставок, удалений и замен.
Автоматы Левенштейна могут использоваться для исправления орфографии путем поиска слов в данном словаре, которые близки на слово с ошибкой. В этом приложении, как только слово идентифицируется как написанное с ошибкой, его автомат Левенштейна может быть сконструирован, а затем применен ко всем словам в словаре, чтобы определить, какие из них близки к слову с ошибкой. Если словарь хранится в сжатом виде как trie, время для этого алгоритма (после создания автомата) пропорционально количеству узлов в дереве, что значительно быстрее, чем при использовании dynamic программирование для вычисления расстояния Левенштейна отдельно для каждого словарного слова.
Также возможно найти слова в обычном языке, а не в конечном словаре, которые близки к заданного целевого слова, вычислив автомат Левенштейна для этого слова, а затем используя конструкцию Декартово произведение, чтобы объединить его с автоматом для обычного языка, дав автомат для языка пересечений. В качестве альтернативы, вместо использования конструкции произведения, как автомат Левенштейна, так и автомат для данного регулярного языка могут проходить одновременно с использованием алгоритма обратного отслеживания.
Для с любой фиксированной константой n автомат Левенштейна для w и n может быть построен за время O (| w |).
Митанкин изучает вариант этой конструкции, называемый универсальным автоматом Левенштейна, определяемый только числовым параметром n, который может распознавать пары слов (закодированные определенным образом с помощью битовых векторов), которые находятся в пределах расстояния Левенштейна n друг от друга. Тузе предлагает эффективный алгоритм построения этого автомата.
Еще одна конструкция конечного автомата расстояния Левенштейна (или Дамерау – Левенштейна ) - это преобразователи Левенштейна Хасана и др., Которые показывают преобразователи конечного состояния, реализующие редактирование расстояние один, затем скомпонуйте их для реализации расстояний редактирования до некоторой константы.
