谷歌的自动补全功能那么快，后台是如何工作的？( 二 ) _谷歌

前缀树实现通常来说，许多词汇都以相同的前缀开头，比如 need、nested 都以 ne 开头，seed、speed 都以 s 开头。要是为每个单词分别存储公共前缀似乎很浪费。

文章插图

前缀树是一种利用公共前缀来加速补全速度的数据结构。前缀树在节点树中排列一组单词，单词沿着从根节点到叶子节点的路径存储，树的层次对应于前缀的字母位置。
前缀的补全是顺着前缀定义的路径来查找的。例如，在上图的前缀树中，前缀 ne 对应于从子节点取左边缘 N 和唯一边缘 E 的路径。然后可以通过继续遍历从 E 节点可以达到的所有叶节点来生成补全列表。在图中，ne 的补全可以是两个分支：-ed 和 -sted 。如果在数中找不到由前缀定义的路径，则说明词汇表中不包含以该前缀开头的单词。
有限状态自动机(DFA)实现前缀树可以有效处理公共前缀，但是，对于其他共享词部分，仍会分别存储在每个分支中。比如，后缀 ed、ing、tion 在英文单词中特别常见。在上一个例子中，e、d 分别存放在了每一个分支上。
有没有一种方法可以更加节省存储空间呢？有的，那就是 DFA 。

文章插图

在上面的例子中，单词 need、nested、seed 和 speed 仅由 9 个节点组成，而上一张图中的前缀树包含了 17 个节点。
可以看出，最小化前缀树 DFA 可以在很大程度上减少数据结构的大小。即使词汇量很大，最小化 DFA 通常也适合在内存中存储，避免昂贵的磁盘访问是实现快速自动补全的关键。
一些扩展上面介绍了如何利用合理的数据结构实现基本的自动补全功能。这些数据结构可以通过多种方式进行扩展，从而改善用户体验。
通常，满足特定前缀的词汇可能很多，而用户界面上能够显示的却不多，我们更希望能显示最常搜索或者最有价值的词汇。这通常可以通过为词汇表中的每个单词增加一个代表单词值的权重 weight，并且按照权重高低来排序自动补全列表。
•对于排序后的词汇表来说，在词汇表每个元素上增加 weight 属性并不难；
•对于前缀树来说，将 weight 存储在叶子节点中，也是很简单的一个实现；
•对于 DFA 来说，则较为复杂。因为一个叶子节点可以通过多条路径到达。一种解决方案是将权重关联到路径而不是叶子节点。
目前有不少开源库都提供了这个功能，比如主流的搜索引擎框架 Elasticsearch[4]、Solr[5]等，基于此，我们可以实现高效而强大的自动补全功能。

【谷歌的自动补全功能那么快，后台是如何工作的？】