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