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

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）包含搜索行为。或者，另一方面，依赖于数据结构的代码深入了解如何实现该特里结构。这使得更快地寻找建议，但我不会说这很容易。

您可以通过另一种方法来加速搜索，创建另一个具有相反顺序的单词。如果您想查找缺少前几个字符的单词的建议，这很有帮助。例如，如果有人输入“elpful”，你会想要“有帮助”的建议。你可以搜索每个第一级节点，寻找“有用的”，“漂亮的”等等。但是反向DAWG将以'l'开始并产生“lufple”...然后看到'h'可以跟随，并且建议“有用”。当一个单词的第二个或第三个字母丢失时，这种类型的东西可能非常有用。

基本上，使用DAWG寻找后缀很容易。寻找前缀的计算成本很高。但是，如果您使用相同的单词创建DAWG，只能向后搜索，则前缀搜索与后缀搜索一样有效。