Левенштейн Автоматы

Я реализовал левенштейновую три, чтобы найти похожие слова для данного слова. моя цель состояла в том, чтобы иметь быстрый способ исправить заклинание.

Однако я узнал, что есть еще более быстрый способ сделать это:

Левенштейн Автоматы

У меня просто проблема... Я не понимаю ни слова о том, что здесь написано. Может кто-нибудь объяснить мне идею и основные функции автомата Левенштейна в простых словах?

Источник

2 ответа

Решение

Может кто-нибудь объяснить мне идею и основные функции автомата Левенштейна в простых словах?

Детерминированный конечный автомат (DFA)

  1. алфавит (набор возможных входных символов)
  2. набор состояний (просто абстрактные объекты без специальных свойств)
  3. функция перехода (при любом состоянии и входном символе возвращается уникальное состояние)
  4. отличное начальное состояние
  5. набор принимающих состояний.

Вы можете нарисовать DFA в виде диаграммы, подобной приведенной в статье. Условно круговые узлы являются состояниями. Направленные ребра, каждый из которых помечен одним символом, являются переходами. Принимающие состояния помечены как двойные кружки. Начальное состояние имеет стрелку, указывающую внутрь, и на хвосте ничего нет.

DFA принимает слово W тогда и только тогда, когда вы можете переместить маркер из начального состояния по переходам, конкатенированные метки которых равны W, в принимающее состояние. То есть, если T является функцией перехода, а W = "cat", то T (T(T(T(Start, "c"), "a"), "t") должно быть принимающим состоянием. Циклы в функции перехода позволяют DFA принимать строки произвольной длины, даже если DFA конечен.

В программном обеспечении DFA представляет собой простой цикл и таблицу T(state, char), которая реализует функцию перехода.

current_state = START
while not end-of-input
  c = get character from input
  current_state = T(current_state, c)
end
if current_state is an accepting state return ACCEPT, else REJECT

Страница Википедии о DFA не плохая.

ДФА имеют хорошие свойства. Принятие / отклонение ввода длины N требует времени O(N) (при условии, что функция перехода выполняется в постоянное время). Существует уникальная минимальная версия каждого DFA (среди всех, принимающих один и тот же набор слов) и эффективный алгоритм для поиска этого минимального DFA. Легко сравнить DFA по равенству во времени, линейному по размеру DFA.

Автомат Левенштейна L(W, d) для слова W и расстояния Левенштейна d - это просто DFA, который принимает все слова, имеющие расстояние Левенштейна не более d от W. То есть автомат принимает W плюс кучу других слов, которые W с не более чем "ошибки" в обычном смысле Левенштейна на расстоянии.

Вклад статьи - быстрый алгоритм для вычисления DFA Левенштейна, а затем более продвинутый алгоритм, который выполняет то же самое без явного вычисления DFA.

Источник

Джин предоставил фантастическое высокоуровневое описание автоматов Левенштейна!

С учетом вышесказанного, если вы ищете какой-то код для вашего понимания, вам может пригодиться библиотека Java LevenshteinAutomaton. Он реализует оба алгоритма, описанные в статье, на которую вы наткнулись (среди прочих), и хорошо структурирован, прост в использовании и широко комментируется. Это также поддерживается вашим по-настоящему:) .

Источник
Другие вопросы по тегам