预测自动完成背后的算法/理论是什么？

Question

13

简单的单词自动完成只显示与已输入字符匹配的单词列表。但我想根据先前键入的单词，依靠文本语料库的统计模型，按单词出现的概率对自动完成列表中的单词进行排序。为此，我需要哪些算法和数据结构？您能给我一些好的教程链接吗？

- chiborg

2个回答

6

Peter Norvig撰写了一篇文章如何编写拼写纠正器，解释了Google的您是不是要找...功能是如何使用贝叶斯推断使其有效的。这是一篇非常好的阅读材料，并且应该可以适用于自动完成功能。

- Wernsey

使用贝叶斯定理来进行自动完成可能有些过头了，因为只需提供部分字符串的最常见自动完成通常已经足够好了。 - Fred Foo

1

@larsmans 确实，这可能有些过度了。但是根据自动完成文本匹配单词并按概率排序似乎非常简单 ;) - Wernsey

按频率对它们进行排序要简单得多。 - Fred Foo

2

改进点中的第四点指引我朝着正确的方向前进：使用n-gram进行预测。 - chiborg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fred Foo · Accepted Answer

你不需要概率来完成自动补全。相反，使用语料库中的单词作为键和它们的频率作为值来构建一个前缀树（也称为trie）。当你遇到一个部分字符串时，尽可能地遍历前缀树，然后从你已经到达的点生成所有后缀，并按频率排序。

当用户输入以前未见过的字符串时，只需将其添加到前缀树中并将频率设为1; 当用户输入您曾经看过的字符串（也许是通过从候选列表中选择）时，增加其频率。

[请注意，您无法使用概率模型进行简单的增量；在最坏的情况下，您必须重新计算模型中的所有概率。]

如果您想更深入地了解这种算法，我强烈建议您阅读Jurafsky和Martin的Speech and Language Processing（前几章）。它详细介绍了用于语言处理的离散概率。