问题预测自动完成背后的算法/理论？

简单单词自动完成只显示与已键入的字符匹配的单词列表。但是我想根据出现的单词的概率，在自动完成列表中排序单词，这取决于之前输入的单词，依赖于文本语料库的统计模型。我需要什么算法和数据结构？你能给我一些好的教程链接吗？

11934

2017-07-12 09:43

起源

彼得诺维格有一篇文章如何编写拼写校正器这解释了谷歌的方式 你的意思是...？ 功能使用贝叶斯推理使其有效。这是一个非常好的阅读，应该适应自动完成功能。

2017-07-12 09:48

然而，使用贝叶斯定律对于自动完成将是过度的，因为;只给出最常见的部分字符串自动完成通常就足够了。 - Fred Foo

@larsmans真的，这可能是矫枉过正。但是找到与自动完成文本匹配的单词并根据概率对它们进行排序所以简单;） - Wernsey

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

＃4的改进使我指向正确的方向：使用n-gram进行预测。 - chiborg

2017-07-12 09:48

然而，使用贝叶斯定律对于自动完成将是过度的，因为;只给出最常见的部分字符串自动完成通常就足够了。 - Fred Foo

@larsmans真的，这可能是矫枉过正。但是找到与自动完成文本匹配的单词并根据概率对它们进行排序所以简单;） - Wernsey

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

＃4的改进使我指向正确的方向：使用n-gram进行预测。 - chiborg

您不需要自动完成的概率。相反，建立一个前缀树（又名a 特里）将语料库中的单词作为键，将其频率作为值。当你遇到一个部分字符串时，尽可能地走trie，然后从你到达的点生成所有后缀并按频率对它们进行排序。

当用户输入以前看不见的字符串时，只需将其添加到频率为1的trie中;当用户输入您看到的字符串时（可能通过从候选列表中选择它），增加其频率。

[注意，你不能用概率模型进行简单的增量;在最坏的情况下，你必须重新计算模型中的所有概率。

如果你想深入研究这种算法，我强烈建议你阅读（第一章） 语音和语言处理 由Jurafsky和Martin。它非常详细地处理语言处理的离散概率。

2017-07-12 10:03

虽然这是一种直接的方法，但该解决方案没有考虑来自语料库的n-gram语言模型的信息。即单词历史 - swami

@swami：没错，但这是一个问题吗？如果需要，可以使用指数方案对频率进行加权，以便用户的输入将超过语料库，反之亦然。 - Fred Foo

问题 预测自动完成背后的算法/理论？