系统设计系列之自动完成的秘密
文本框自动完成是一项十分常见的功能。从表单的自动填充到搜索引擎的智能提示，这个功能极大地提高了用户的输入效率，也有效地防止了手误的可能。
但是，积极进取的你，有没有想过如此快速出现的自动完成是如何实现的呢？
这个看似简单的问题，包子君却用它在面试中却难倒了无数 candidate. 本文就来完整地讲解其原理和实现中的小技巧。
在 Jump into coding 之前，我们还是先来关注下自动完成功能有哪些方面的要求（coding 面试必备技能哦）:
- 很明显，自动完成主要是根据用户的输入作为前缀，找出符合此前缀匹配的可能输入词条，这其中自然少不了前缀匹配高频词条技术。
- 自动完成需要不停与正在输入的用户进行交互，所以对实时性的要求比较高，毕竟没人会希望打字的时候出现卡顿。
- 最好能够照顾到海量词库，在高 QPS 情况下可以横向扩展，这在大数据时代已经算是个基本要求了。
哈希查找
为了达到匹配常见词条的要求，很自然想到在一个很大的高频词条上建立索引，根据用户的输入快速查找所匹配的完整词条作为提示。
嗯，貌似不是很难，有工程经验的同学可能会想到使用数据库+ cache 方案。提醒大家，通用的数据库很难在性能上达到要求；使用 cache 可以提高性能，但为什么我们不能直接把整个词条库全都放入 cache 呢？
很多同学想到使用内存哈希表来进行查找，毕竟哈希表是非常常见的 cache 形式，分布式的哈希表技术也十分成熟。
然而，如果大家仔细想想，每次用户输入的前缀都需要作为哈希表的 Key 来进行匹配查找的话，那同一个词条需要在哈希表中存 n 个 key，其中，n 是词条的长度。这种存储方式虽然简单直接，但是却使用了 O(n) 倍于词条库大小的空间来进行索引，词条库稍一加大的话便有些不太能够承受了。
前缀树
有经验的同学肯定就想到了前缀树 。在这里，适用的字符前缀树又叫 TRIE 树，被广泛地用于基于前缀的快速字符串查找。
如下图中（来源维基百科）所示，TRIE 树将字符串列表 “to”, “tea”, “ted”, “ten”, “A”, “in”, “inn” 按字符展开分布到了树上。每一个字符串，最终都会对应到 TRIE 树上的一个节点，而从根节点到代表字符串节点的路径上便记有该字符串的组成信息。
在前缀查找时，我们根据用户输入的前缀字符，从根节点沿着字符路径一直往下走。比如用户输入 “te” , 我们可以沿路径找到对应的 “te” 节点，而此节点下面的的所有节点都是对用户输入所匹配的词条，其中包括 “tea”, “ted”, “ten”.
我们可以想象到，由于每个词库中的字符串都只在 TRIE 中出现过至多一次，TRIE 的空间复杂度不会超过 O (m), m 表示词条库的大小。而且每一次查找都是耗时 O(n), n 是用户输入的长度。
看到这里，同学们应该能感觉到 TRIE 树是一个省时又省空间的解决方法。
构建最优前缀树
在上文的叙述中，包子君向读者隐藏了一个小小的问题，那便是如何从众多匹配的节点中选取 Top N 的问题。
我们首先来设想一个极端的例子：当用户打了一个字符 “t” 的时候，我们需要从 TRIE 上找出满足 “t” 前缀的节点们。可词库中以 “t” 打头的词条成千上万，不仅用户不能接受如此多的提示词条，而且查找所有词条所需耗费的时间和空间复杂度也变成了 O(m), m 为 t 打头词条的数目。在实时性要求如此之高的应用里，这种时间、空间复杂度不可接受。
于是问题就变成了如何从所有满足要求的词条中快速找到少量对用户最有用的提示词条？
为求简单，在这里我们假设用户仅仅需要我们返回 2 个提示词条。
是如何定义最优？
在不同自动完成的应用中，最优的概念是不同的，比如搜索引擎可能要求频率最高的匹配词条，而填表应用可能要求最近使用的词条。有一个简单的处理方法：我们可以给每一个词条赋一个权重分数，作为优劣的抽象含义。我们希望，对应返回 K 个词条的情况下，时间空间复杂度能大致停留在 O(K*n), 其中 n 表示平均匹配词条的长度。那好，我们就来看看如何在 TRIE 树中实现以上要求。
下图中，我们展现了一个大 TRIE 树的局部小树。此小树的根节点 “t” ，在大 TRIE 树中只是一个中间节点，而此小树中所有带有黑色数字的节点表示的是其节点对应了一个词条；所有带有红色数字的节点则是没有对应任何词条的中间节点。我们假设在匹配完用户匹配后，我们的树节点指针指向了下面的 “t” 节点。我们的任务便是找出 “t” 节点下面，2 个最佳的，对应了词条的节点，并返回。
我们之前讲过，每个对应词条的节点都会有一个分数，分数越高越需要优先返回；显然,找出节点中分数最高的两个便是解决此问题的关键。
为了避免遍历整棵子树来查找分数最高的两个节点，我们采取 A* 的思想来遍历：将所有没有对应词条的中间节点标注上一个“最佳分数”，此最佳分数表示此节点下面所有节点可以达到的最佳的分数。我们用红颜色的数字标注了下图中的树。
在进行 A* 遍历时，站在每一个节点上我们都知道，展开此节点进行搜索可以到达的最高分数的词条的分数。如果我们按照 “best-order” （最佳优先）的顺序进行遍历此树，仅仅需要遍历下图中蓝色的路径，便找到了最大的 “h” 和 “m” 节点。在平均情况下，这种算法所经历的时间和空间复杂度近似于 O (K * n) .
分布式前缀树
最后，包子君再和大家一起来探讨下：如何将 TRIE 树的算法扩展到多台机器上？
首先，一个非常 naïve 的想法便是使用分布式内存。与分布式文件系统类似，业界已有成熟的技术通过类似与 Key-Value pair 的形式将内存检索分布到多台机器的集群中，于是一个简单的想法便是：在集群的分布式内存中建立 TRIE 树，以单机 TRIE 同样的算法来进行构造和查找。
这种想法虽然实现不复杂，但具有很大的性能局限性。由于分布式内存并不会考虑到 TRIE 树搜索时的 “按路径行走” 的局部性，往往每走一步都要访问整个集群中的机器，其网络的延迟很可能是灾难性的。
聪明的同学可能已经想到，可以利用树本身的结构，建立一个树状连接的分布式网络，将 TRIE 树的各个节点均匀分布在树状网络的各个节点上。在极端情况下，此方法将会为每一个 TRIE 节点分配一台计算机结点，以达到最佳分布性能。
这种想法固然比第一种好很多，其将向邻近的 TRIE 树节点放到了同一台机器上，但当算法在 TRIE 树上行走时，仍有可能会跨越计算机的边界，产生多次网络访问延时。那么，到底有没有一种方法可以既有效地横向扩展分布，又能尽量使每个查询保持在同一台机器上以减少延迟呢？
希望大家能开动脑筋自己思考，在此我们也将先抛砖引玉：一种可行的方案便是将词库中所有词条的一定长度的前缀放入路由哈希表中，而此前缀对应下的所有词条也就会被映射到一台机器上。显然，被哈希的词条越长，每台机器上的负载就越小，而集群中的机器的数目也就会越多。这种分布设计的好处是，每个查询请求至多被重定向一次，到一个计算机节点上进行查找。
看看好朋友们还有什么更好的设计么？赶紧将此文分享到朋友圈吧。