如何使用Trie进行拼写检查

Question

我有一个我用词典创建的特里.我想用它来进行拼写检查(并在字典中建议最接近的匹配,也许是对于给定数量的编辑x).我想我会在目标单词和字典中的单词之间使用levenshtein距离,但有没有一种智能的方法可以遍历trie而不会分别在每个单词上运行编辑距离逻辑？我该如何进行遍历和编辑距离匹配？

例如,如果我有单词MAN,MANE,我应该能够在MANE中重用MAN上的编辑距离计算.否则Trie不会用于任何目的

Answer 1

我想你应该尝试一下bk-trees ; 它是一种适合拼写检查的数据结构,因为它可以让你用词典中的单词有效地计算编辑距离.

此链接可以很好地了解应用于拼写检查的BK树

Answer 2

尝试为每个树节点计算一个数组 A，其中 A[x] 是匹配目标单词的前 x 个字母后特里树中该位置的最小编辑距离。

如果数组中的每个元素都大于目标距离，您可以停止检查任何节点。

例如，使用包含 MAN 和 MANE 以及输入 BANE 的 trie：

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] 的最小值是单词“MANE”达到的 1，因此这是最佳匹配。