algorithm - 拼写检查算法如何优化对建议词的搜索？

Question

据我所知，拼写检查算法通过检查转换次数(交换字母、添加字母、删除字母等)来寻找建议，给定单词需要变成字典中的一个或多个真实单词。我知道他们也会考虑上下文，但我们暂时将其排除在外。

假设我想看看单词 overflw 如果在适当的位置添加 1 个字母，它是否看起来像字典中的单词。我能看到完成的唯一方法是蛮力:检查是否每一个

aoverflw
boverflw
coverflw
.
.
.
overflnw
overflow
overflpw
.
.
overflwy
overflwz

是字典中的一个词。

有更好的方法吗？

Answer 1

您假设拼写检查器有一本字典，它只能告诉您某个词是否存在于字典中。但在大多数拼写检查器中，字典被实现为某种类型的 trie。 , 通常是 directed acyclic word graph (DAWG)。这是一种比具有是/否查找功能的简单字典更通用的数据结构。

实现方式各不相同，但从概念上讲，您可以将字典中的单词搜索视为从单词的第一个字符开始并从 DAWG 的根部获取该节点的搜索。该节点包含以下所有字母等的条目。如果你重复这样做，你最终会得到以下可能性之一:

1. 您在树中遇到一个叶节点，并且您位于单词的末尾。如果这是真的，你就知道这个词存在于字典中。
2. 你遇到了一个叶子节点，但是单词中还剩下字母。想象一下，如果文档中的单词是“fatx”。您已经到达树中的叶节点“t”，但您的单词中仍然有“x”。
3. 您到达了单词的末尾，但您不在叶节点处。比如文档中的单词是“overfl”。
4. 你在一个非叶节点上，你遇到了一个无法识别的字母。例如，单词是“overfdow”。您位于树中的“f”节点，字符“d”不在“f”后面的字母列表中。

在最后三种情况下，您知道您在树中的哪个节点，并且您知道可以生成哪些字母(以及，就此而言，哪些单词)。例如，您有“overflw”。树中的“l”节点表示“l”之后的可能字符是“e”(溢出)、“o”(溢出、溢出等)和“y”(溢出)。如果您想对各种可能性进行详尽搜索以提出建议，则不必尝试字母表中的每个字母。您所要做的就是尝试字典知道“overfl”后面的字母。在这种情况下不需要检查 'q'，因为我们已经知道它不可能匹配。

基本思想是字典数据结构(trie)包括搜索行为。或者，依赖于数据结构的代码非常了解 trie 的实现方式。这使得寻找建议的速度大大加快，尽管我不会说这特别容易。

另一件可以加快搜索速度的事情是创建另一个单词顺序相反的 trie。如果您想为缺少前几个字符的单词找到建议，这会很有帮助。例如，如果有人输入“elpful”，你会想要“helpful”的建议。您可以搜索每个一级节点，寻找“aelpful”、“belpful”等。但是反向 DAWG 将以“l”开头并产生“lufple”...然后看到“h”可以跟随，并建议“有帮助”。当缺少单词的第 2 个或第 3 个字母时，这种类型的东西会非常有用。

基本上，使用 DAWG 查找后缀很容易。寻找前缀在计算上是昂贵的。但是，如果您使用相同的词创建 DAWG，只是向后，那么前缀搜索与后缀搜索一样有效。