遍历Trie以检查拼写建议的好算法是什么？

Question

假设构建了一个字典单词的一般Trie,那么在遍历期间检查4种拼写错误 - 替换,删除,转置和插入的最佳方法是什么？

一种方法是找出给定单词的n个编辑距离内的所有单词,然后在Trie中检查它们.这不是一个糟糕的选择,但这里更好的直觉似乎是使用动态编程(或递归等效)方法来确定在遍历期间修改单词后的最佳子尝试.

任何想法都会受到欢迎!

PS,会欣赏实际输入,而不仅仅是答案中的链接.

Answer 1

我实际上写了一些代码来做这件事:

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

它基于Peter Norvig的代码(http://norvig.com/spell-correct.html),但将字典存储在trie中,以便更快地查找给定编辑距离内的单词.

该算法通过消费来自输入词的字母,在每个步骤中递归地应用可能的编辑(或不是).递归调用的参数表示可以进行多少次编辑.trie通过检查从我们给定的前缀实际可以到达哪些字母来帮助缩小搜索空间.例如,在插入字符时,我们只添加可从当前节点访问的字母,而不是添加字母表中的每个字母.不进行编辑等同于从输入字中的当前字母中取出trie中当前节点的分支.如果那个分支不在那里,那么我们可以回溯并避免搜索可能没有找到真正单词的大空间.