algorithm - 创建建议词算法

Question

我正在设计一个很酷的拼写检查器(我知道我知道，现代浏览器已经有了这个)，无论如何，我想知道开发一个相当简单但不错的建议词算法需要什么样的努力。

我的想法是，我会首先查看拼写错误的单词的字符并计算它在字典中每个单词中匹配的字符数量(听起来很耗费资源)，然后选择前 5 个匹配项(因此如果拼写错误的单词匹配字典中最多 7 个单词的字符，它会随机显示其中 5 个单词作为建议拼写)。

显然，为了更高级，我们会查看“常用词”并有一个字典文件，该文件以“该词在英语中使用的频率”排名进行编号。我认为这可能有点过火了。

你怎么看？有人对此有想法吗？

Answer 1

首先，您必须考虑找到与拼写错误的单词“更接近”的单词的复杂性。我看到您正在使用字典，也许是哈希表。但这可能还不够。这里最好和更酷的解决方案是寻求 TRIE数据结构。找到这些所谓的更近单词的复杂性将采用线性顺序计时，并且很容易耗尽树。

一个小例子

以“njce”这个词为例。这是一个 1 级示例，其中一个单词明显拼写错误。预期的明显建议会很好。第一步很明显，就是看这个词是否出现在字典中。使用 TRIE 的搜索功能，这可以在 O(1) 时间内完成，类似于字典。更酷的部分是找到建议。你显然必须穷尽所有以'a'到'z'开头的单词，其中包含像ajce bjce cjce upto zjce这样的单词。现在找到这种类型的出现再次是线性的，具体取决于字符数。你不应该把这个数字乘以 26 个单词的长度。因为随着长度的增加，TRIE 会立即减少。回到问题上来。完成搜索但未找到结果后，您将转到下一个字符。现在您将搜索 nace nbce ncce upto nzce。事实上，您不会探索所有组合，因为 TRIE 数据结构本身不会有中间字符。也许它将有 na ni ne no nu 字符并且搜索空间变得非常简单。进一步的事件也是如此。您可以根据二阶和三阶匹配进一步发展这个概念。希望这对您有所帮助。