levenshtein-distance - 编辑器自动机

Question

我实现了一个 levenshtein trie 来查找与给定单词相似的单词。
我的目标是有一种快速的方法来进行拼写纠正。

但是我发现有一种更快的方法可以做到这一点:

莱文斯坦自动机

我只是有一个问题......我不明白写的是什么
here .
有人可以向我解释一个的想法和基本功能吗？
Levenshtein 自动机用简单的话？

Answer 1

Can someone explain me the idea and the basic functionality of a levenshtein automata in easy words?

确定性有限自动机 (DFA) 是

一个字母表(一组可能的输入字符)

一组状态(只是没有特殊属性的抽象对象)

一个转换函数(给定任何状态和一个输入字符，它返回一个唯一的状态)

一个独特的开始状态

一组接受状态。

您可以像论文中那样将 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

The Wikipedia page on DFAs还不错。

DFA 具有很好的属性。接受/拒绝长度为 N 的输入需要 O(N) 时间(只要转换函数在恒定时间内运行)。每个 DFA 都有一个唯一的最小版本(在所有那些接受相同单词集的版本中)和一个找到最小 DFA 的有效算法。比较 DFA 在时间上的相等性很容易与 DFA 的大小成线性关系。

文字 W 和 Levenshtein 距离 d 的 Levenshtein Automaton L(W, d) 只是一个 DFA，它接受所有与 W 的 Levenshtein 距离至多为 d 的词。也就是说，自动机接受 W 加上一堆 W 的其他单词不超过通常意义上的 Levenshtein 距离中的 d 个“错误”。

该论文的贡献是一种用于计算 Levenshtein DFA 的快速算法，然后是一种更高级的算法，该算法无需显式计算 DFA 即可完成相同的任务。