谷歌抄写是如何工作的？

Question

我想询问新的实验室功能“Google Scribe”。以下是链接：http://scribe.googlelabs.com/ 我对后端和前端都很感兴趣，但主要是后端。我想构建一个类似的东西，使用非常特定的数据集（从我的自己的文档中派生）。我认为前端相当简单，甚至可以使用现有的自动完成插件来完成任务。

- Preston Marshall

Answer 1

可能的实现建议：

后端：构建和维护一个 NxNxW 稀疏矩阵 A（例如实现为 Hash），其中 N 是您词汇量的大小，W 是您希望维护的最大上下文（以单词计）（例如，W=4 可能是可以的）。回顾一些示例数据来初始化 A，使得 A[n1,n2,w] 记录在单词 n1 后第 w 个位置出现单词 n2 的次数（考虑句子边界）。

前端：当用户输入时，请求后端使用 A 来评估（并排名）基于用户在当前句子中完全输入的最后 W 个单词的最可能的后继单词；仅显示以用户正在输入的内容（即用户的“当前”（部分）单词）开头的建议。

可选择让后端根据用户已完成输入的单词更新 M，无论是实时更新（当用户返回执行更正时有挑战性），还是在最终文本提交时更新（最简单），或通过某个定期作业评估自上次作业运行以来提交的文本。

- vladr

---

正如 aleemb 正确指出的那样，上述内容的正式术语应该是 W 阶马尔可夫链。 - vladr

Answer 2

您需要使用马尔可夫链。

您可能想从这里开始查看（链接）。 示例输出也很有趣。

- aleemb

Answer 3

我不确定这一点，如果我错了，请纠正我。

Google Scribe使用的系统（或者至少是非常相似的系统）本质上会使用一种类似树形数据结构的方式来存储所有可能的单词。基于已知的词汇，采用某种搜索算法来查看您可以完成单词的所有可能方式。（可能基于他们数据库中存储的旧搜索查询）并按照它们出现的频率进行排序。

例如：

我输入：“a”

词汇：“at”、“apple”、“atrocious”

因此：“at”被使用最多，“apple”次之，“atrocious”最少。

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

为了检索发生的可能性，您可以扫描要搜索的文档，或者仅在按查询检查过去的搜索时存储。

- TaslemGuy