Levenshtein Automata

Question

我实施了一个levenshtein trie来找到与给定单词相似的单词.我的目标是快速进行拼写纠正.

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

Levenshtein Automata

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

Answer 1

有人可以用简单的词语向我解释levenshtein自动机的想法和基本功能吗？

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

1. 字母表(可能的输入字符集)
2. 一组状态(只是没有特殊属性的抽象对象)
3. 转换函数(给定任何状态和输入字符,它返回一个唯一的状态)
4. 一个杰出的开始状态
5. 一组接受国家.

您可以将DFA绘制为图纸中的图表.通常,圆形节点是状态.每个标有一个字符的定向边是过渡.接受状态标记为双线圆圈.起始状态有一个向内指向的箭头,尾部没有任何东西.

当且仅当您可以将标记从开始状态沿着其连接标签等于W的转换移动到接受状态时,DFA接受字W.也就是说,如果T是转换函数,并且W ="cat",那么T(T(T(开始,'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的维基百科页面也不错.

DFA具有很好的性能.接受/拒绝长度为N的输入需要O(N)时间(只要转换函数在恒定时间内运行).每个DFA都有一个独特的最低版本(在所有接受同一组词的人中)和一个有效的算法来找到最小DFA.在DFA的大小中,很容易比较DFA的时间线性相等性.

用于单词W和Levenshtein距离d的Levenshtein自动机L(W,d)只是一个DFA,它接受所有具有Levenshtein距离的单词,最多d来自W.也就是说,自动机接受W加上一堆其他W的单词.只不过通常意义上的Levenshtein距离的"错误".

本文的贡献是计算Levenshtein DFA的快速算法,然后是一种更先进的算法,可以在不明确计算DFA的情况下完成相同的事情.