Автомат Левенштейна - Levenshtein automaton

В Информатика, а Автомат Левенштейна для нить ш и ряд п это конечный автомат который может распознать набор всех строк, чьи Расстояние Левенштейна из ш самое большее п. То есть строка Икс находится в формальный язык распознаваемым автоматом Левенштейна тогда и только тогда, когда Икс может быть преобразован в ш самое большее п односимвольные вставки, удаления и замены.[1]

Приложения

Автоматы Левенштейна можно использовать для исправления орфографии, находя в заданном словаре слова, близкие к слову с ошибкой. В этом приложении, как только слово определяется как написанное с ошибкой, его автомат Левенштейна может быть сконструирован и затем применен ко всем словам в словаре, чтобы определить, какие из них близки к слову с ошибкой. Если словарь хранится в сжатом виде как три время для этого алгоритма (после того, как автомат был построен) пропорционально количеству узлов в дереве, что значительно быстрее, чем при использовании динамическое программирование для вычисления расстояния Левенштейна отдельно для каждого словарного слова.[1]

Также можно найти слова в обычный язык, а не конечный словарь, которые близки к заданному целевому слову, вычисляя автомат Левенштейна для слова, а затем используя Декартово произведение конструкция, объединяющая его с автоматом для обычного языка, давая автомат для языка пересечений. В качестве альтернативы, вместо использования конструкции произведения, как автомат Левенштейна, так и автомат для данного регулярного языка можно пройти одновременно, используя возврат алгоритм.[1]

строительство

Для любой фиксированной постоянной п, автомат Левенштейна для ш и п можно построить за время O (|ш|).[1]

Митанкин изучает вариант этой конструкции, названный универсальный автомат Левенштейна, определяется только числовым параметром п, который может распознавать пары слов (закодированных определенным образом с помощью битовых векторов), которые находятся в пределах расстояния Левенштейна п друг друга.[2] Тузе предлагает эффективный алгоритм построения этого автомата.[3]

Но третья конструкция конечного автомата Левенштейна (или Дамерау – Левенштейн ) расстояния - это преобразователи Левенштейна Хасана и другие., кто показывает преобразователи конечного состояния реализуя расстояние редактирования один, затем скомпонуйте их для реализации расстояний редактирования до некоторой константы.[4]

Смотрите также

  • соглашаться, инструмент (реализован несколько раз) для приблизительного сопоставления регулярных выражений
  • TRE, библиотека для сопоставления регулярных выражений, толерантная к редактированию в стиле Левенштейна

Рекомендации

  1. ^ а б c d Schulz, Klaus U .; Михов, Стоян (2002). «Быстрая коррекция строки с помощью автоматов Левенштейна». Международный журнал анализа и распознавания документов. 5 (1): 67–85. CiteSeerX  10.1.1.16.652. Дои:10.1007 / s10032-002-0082-8.
  2. ^ Митанкин, Петар Н. (2005). Универсальные автоматы Левенштейна. Строительство и недвижимость (PDF) (Тезис). Софийский университет Святого Климента Охридского.
  3. ^ Тузе Х. (2016). "Об автомате Левенштейна и величине окрестности слова" (PDF). Язык и теория автоматов и приложения. 9618. Конспект лекций по информатике. С. 207–218. Дои:10.1007/978-3-319-30000-9_16.
  4. ^ Хасан, Ахмед; Ноеман, Сара; Хасан, Хани (2008). Коррекция текста, не зависящая от языка, с использованием конечных автоматов. IJCNLP.