问Google Scribe是如何工作的？

EN

可能的实施建议：

后端:构建和维护NxNxW稀疏矩阵A (例如，作为Hash实现)，其中N是您的词汇表的大小，W是您希望维护的最大上下文(以单词为单位)(例如，W=4可能是OK的)。检查一些样本数据以对A进行种子/初始化，以便A[n1,n2,w]计算单词n2在单词n1之后出现在w位置的次数(注意句子边界)。

前端:当用户输入时，要求后端使用A根据用户在当前句子中完整输入的最后一个W单词来评估(和排名)最可能的后继词；只显示那些以用户正在输入的单词(即用户的“当前”(部分)单词)开头的建议。

有选择地让后端基于用户已经完成键入的单词来更新M，可以是动态地(当用户返回执行更正时具有挑战性)，也可以是随着最终文本的提交(最简单)，或者通过自上次作业运行以来提交的一些定期作业评估文本。

你需要使用马尔可夫链。

您可能希望从查看here开始。sample output也很有趣。

(我对此不是很肯定，如果我错了，请纠正我)

Google Scribe使用的系统(或者至少是一个非常类似的系统)将本质上使用树状数据结构，用于存储所有可能的单词。某种形式的搜索算法，它可以根据已知的词汇表，看到你可以完成单词的所有可能的方式。(可能是存储在数据库中的较旧搜索查询的基础部分)，并根据它们出现的频率对它们进行排序。

例如：

我输入：'a‘

atrocious：'at‘'apple’'atrocious‘

所以：“at”是使用最多的，“apple”其次，“atrocious”是最少的。

就像我说的，我不确定这是不是他们使用的系统，但它应该有类似的结果。

为了检索出现可能性，您可以扫描正在搜索的文档，或者只需逐个查询地存储，以检查过去的搜索。