如何使用Trie进行拼写检查

Question

我有一个字典中构建的 Trie 树。我想将它用于拼写检查(并为给定编辑次数x建议最接近的单词)。我打算在目标单词和我的字典中的单词之间使用 Levenshtein 距离，但是有没有一种聪明的方法可以在不对每个单词分别运行编辑距离逻辑的情况下遍历 Trie 树？如何进行遍历和编辑距离匹配？

例如，如果我有单词 MAN 和 MANE，我应该能够重复使用 MAN 中的编辑距离计算来匹配 MANE。否则，Trie 树将毫无意义。

- Aks

---

"man/mane" 几乎是微不足道的，试试 "mane/bane"。 - n. m.

我认为这些方法不太适合结合在一起。在我看来，你需要对字典中的每个单词应用“编辑距离”算法，才能提出建议。 - Paulo Bu

真的，但是我该如何重叠编辑距离计算以避免重新计算相同的距离。 - Aks

好的，这里有一个想法：对每个单词运行编辑距离，并在超过一定数量的编辑的单词上进行修剪（这将使大多数情况下不需要搜索整个单词）。如何改进它？由于编辑距离是向后计算的，因此“后缀树”可能会表现得更好。当您超过某个编辑阈值时，可以丢弃整个分支。（这只是一个疯狂的想法 :)） - Paulo Bu

Answer 1

我认为你应该尝试使用bk-trees代替; 它是一种数据结构，非常适合拼写检查，因为它可以让你有效地计算出字典中单词的编辑距离。

这个链接提供了一个很好的关于BK树在拼写检查中的应用的见解。

- pierroz

Answer 2

尝试为每个树节点计算一个数组A，其中A [x]表示在匹配目标单词的前x个字母后，在该位置处得到的最小编辑距离。如果数组中的每个元素都大于您的目标距离，则可以停止检查任何节点。例如，使用包含MAN和MANE的trie和输入BANE的情况：

Node 0 representing '', A=[0,1,2,3,4]
Node 1 representing 'M', A=[1,1,2,3,4]
Node 2 representing 'MA', A=[2,1,1,2,3]
Node 3 representing 'MAN' A=[3,2,2,1,2]
Node 4 representing 'MANE' A=[4,3,2,2,1]

A[end]的最小值为1，对应单词“MANE”，因此这是最佳匹配。

- Peter de Rivaz

Answer 3

有一种聪明的方法可以获取每个元素，这些元素与Levenstein距离不太相同，因为以下算法不包括置换。

假设我们有树形结构，我们可以实现对树的递归搜索。您的递归搜索假定我们从代表删除每个字母的成本行开始。当我们递归搜索树时，我们拥有的信息是

• 您在节点n处，该节点已由字母l在Trie结构中索引。
• 您正在考虑来自单词w的距离
• 您当前的路径假定到目前为止的先前成本行，我们希望更新此以形成此节点n的新成本行。

我们希望根据4种情况更新您正在考虑的字母的成本行； l是单词中的下一个字母（成本行保持不变），需要插入该字母（新成本+1），已删除字母（上一步的成本+1）和字母替换了以前的单词（新成本+1）。

在 Trie 树上继续向下搜索的代价是这些代价中的最小值。如果您到达定义单词的 Trie 结构中的某个点，则将其附加到列表中，然后递归搜索所有子节点以查找更多单词，假设当前成本在定义的最大成本范围内。Python 实现可以在另一篇帖子中找到：

https://stackoverflow.com/a/62823597/8249836

我也有用于管道的C语言版本。由于算法对于高编辑距离（小于单词长度）非常快速，因此可以使用快速高效的Levenstein距离实现来纠正这种方法。

- Chris Ormerod