通过trie检查拼写建议的好算法是什么?

前几天我写了一些代码:

https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py

这是根据彼得·诺维格的密码写的( http://norvig.com/spell-correct.html )但是为了在给定的编辑距离内更快地查找单词,将字典存储在trie中。

该算法通过使用输入字中的字母来递归地遍历trie,在每一步应用可能的编辑(或不应用)。递归调用的参数说明可以进行多少次编辑。trie通过检查从给定的前缀可以访问哪些字母来缩小搜索空间。例如,在插入字符时,我们不添加字母表中的每个字母,而只添加从当前节点可以访问的字母。不进行编辑相当于从trie中的当前节点沿着输入字中的当前字母获取分支。如果分支不在那里,那么我们可以回溯并避免搜索一个可能很大的空间,在那里找不到真正的单词。

我认为你可以在树上直接进行宽度优先搜索:选择一个你要查找的错误数的阈值,简单地运行一次匹配一个单词的字母,生成一组到目前为止匹配前缀的(前缀,子目录)对,当你低于错误阈值时,添加下一个子目标集:

1. 此字符位置无错误:在单词的下一个字符处添加trie的子目标
2. 在这个地方插入、删除或替换的字符:在那里找到适当的trie,并增加错误计数;
3. 不是一个额外的目标,但请注意,换位要么是插入,要么是删除,匹配先前的删除或插入:如果这个测试保持不变,那么不要增加错误计数。

这看起来很幼稚:这有没有导致您想到动态编程的问题?

假定单词中的每个连续字符代表树中的一个级别,然后在每个字符处检查五个事例(匹配、删除、插入、替换和换位)。我假设换位是两个相邻的字符。

您需要一个接受树节点和字符检查的函数(check node)。它将需要返回一组表示匹配项的(子级/子级)节点。

您将需要一个接受单词的函数(checkword)。它根据一组节点依次检查每个字符。它将返回一组表示匹配词的(叶)节点。

其思想是,树中的每一层(孩子、孙子等)都与单词中角色的位置相匹配。如果您调用顶层树节点0级,那么您将拥有1级、2级等。

显然,对于一个没有错误的单词,在字符位置和树中的级别之间有一对一的匹配。

对于删除,需要跳过树中的某个级别。

对于插入,需要跳过单词中的字符。

对于替换,您需要同时跳过级别和字符。

对于换位,您需要(临时)交换单词中的字符。

看看计算 Levenshtein distance 为两个序列之间的距离的确定提供了动态规划解决方案。