简单的单词自动完成只显示与已经输入的字符匹配的单词列表。但是我想根据单词出现的概率对自动完成列表中的单词进行排序，这取决于之前输入的单词，依赖于文本语料库的统计模型。为此我需要什么算法和数据结构？你能给我一些好的教程的链接吗？
问问题
12233 次
2 回答
14
您不需要自动完成的概率。相反，构建一个前缀树（又名trie），将语料库中的单词作为键，将它们的频率作为值。当你遇到一个部分字符串时，尽可能走远，然后从你到达的点生成所有后缀，并按频率对它们进行排序。
当用户输入一个以前看不见的字符串时，只需将其添加到频率为 1 的 trie 中即可；当用户输入您已经看到的字符串时（可能通过从候选列表中选择它），增加它的频率。
[请注意，您不能使用概率模型进行简单的增量；在最坏的情况下，您必须重新计算模型中的所有概率。]
如果您想深入研究这种算法，我强烈建议您阅读Jurafsky 和 Martin的语音和语言处理（第一章）。它非常详细地处理了语言处理的离散概率。
于 2012-07-12T10:03:05.587 回答
6
Peter norvig 有一篇文章How to Write a Spelling Corrector解释了 Google 的您的意思是...？使用贝叶斯推理使其有效的功能作品。这是一本很好的读物，应该可以适应自动完成功能。
于 2012-07-12T09:48:24.433 回答