algorithm - 什么是遍历 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 通过检查我们给定的前缀实际上可以到达哪些字母来帮助缩小搜索空间。例如，当插入一个字符时，我们不会添加字母表中的每个字母，而是只添加从当前节点可达的字母。不进行编辑等同于从 trie 中的当前节点沿着输入单词的当前字母获取分支。如果该分支不存在，那么我们可以回溯并避免搜索可能找不到真正单词的大空间。