Google中的关键词提示=VS中的代码自动补全？

一、引言

我最近用Google以来，不管是客户端Chrome还是手机端Chrome，每次查找资料，都只需要打几个单词就行，后面的在下拉框选就行，像下面这样——

我起初感觉这个提示的实现，是智能算法中的预测功能——通过输入的前几个字符对后面的进行预测。

但是今天看了看专栏后。恍然大悟，也许算法的优化真的有用到预测功能，但是它起初用到的不是，而是我们上次说过的——字符串匹配。

• 匹配的本质是什么？针对于字符串呢？

匹配的本质就是找相同的地方。
针对于字符串，我认为就是在多个字符串中search公共的子串。注意：不是单个字符，而是前缀子串或后缀子串。

那么好，匹配解释完了，大家可以猜一下，这个功能是用了什么数据结构实现的？
其实我们不需要知道这个数据结构的名字，只需要知道它的特点是什么。那么我们来问下自己——

• 这个数据结构需要posses的特点是什么？

特点就是可以在一组字符串集合中快速查找某个字符串。

那么有这种DS吗？有的——Trie树。

二、Trie树的本质

2.1 如何使用trie树解决实际问题？

For example，我们有6个字符串，分别是: how, hi, her, hello, so, see。
既然是应用Trie树，We就把这6个字符串组织成属于它们自己的Trie树，i.e.，查找的时候，在一个树形结构里面查找。

我们来分析一下上图——

• 根节点不包含任何信息
• 每个节点的内容都表示一个字符串的字符
• 从根节点到红色节点的一个path表示一个字符串。

那么我想问大家一个问题：

• 图中的红色节点均是叶子节点吗？

2.2 如何构造Trie树？

我上节有提到一句话，就是针对这6个字符串，构造的是属于它们自己的Trie树，什么意思呢？
构造Trie树的每一个step，都是往Trie里面插入一个字符串。当6个字符串插入finish以后，Trie就build好了。

2.3 如何在构造好的Trie树中查找？

首先问两个questions,

• 在一棵树中查找，我们匹配的载体是什么？

用树来存储数据，数据都放在节点中，所以载体就是节点。

在Trie树中，节点存放的都是单个字符。
So, 如果我们要查找字符串”her”，

• 第一步: 将her分割成h, e, r

• 第二步: 从Trie树的根节点开始match。

  

好，her的最后一个字符r是红色节点，那么如果所查找的字符串的最后一个字符不是红色节点呢？
比如，查找he。

如果出现这种情况，我们就可以believe that这个字符串“he”是某个字符串的前缀子串，但是并不能完全匹配任何字符串。

2.4 如何用代码实现一棵Trie树？

我们在实现Trie树前，先考虑一下，

• We实现的Trie树，都要做什么工作？

在我看来，两个——

1. 将一个又一个字符串插入到Trie树中。2. 在Trie树中查询一个字符串。

那么接下来，

• 如何存储一个Trie树？

Trie树是一棵多叉树。二叉树的存储中，一个节点的左右子节点是通过指针来存储的。
那么对于多叉树呢？我们can借助散列表的思想，通过一个下标与字符一一映射的数组，没错，是数组，来存储子节点的pointer。

假设，字符串中有a-z26个小写字母，也就是26个字符。
We在下标为0的位置，存储指向子节点a的指针，
在下标为1的位置，存储指向子节点b的指针，
…
…
…
在下标为25的位置，存储指向子节点z的指针。
If, 某个字符的子节点不存在，我们就在对应的下标位置存储null。

存储完Trie树后，我们要做的就是查找了。

• 查找的准则：通过待查找字符的ASCII码值减去“a”的ASCII码值，从而快速查找到匹配的子节点的指针。

举个栗子：d 的 ASCII 码减去 a 的 ASCII 码就是 3，那子节点 d 的指针就存储在数组中下标为 3的位置中。

2.5 Trie树的时间复杂度是多少？

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。

每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。

也就是说，Trie树的时度跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

三、Trie树和内存是死敌吗？

是的。

四、如何改善Trie树？

既然，Trie树消耗内存比较严重，那么其本质是why? 猜一下就知道，因为是数组存储的。
我们不用数组存储，换一个。

有序数组、跳表、散列表、红黑树

当然，这四个数据结构的使用，查询效率就会低一些。

假设有序数组入选，数组中的指针按照所指向的子节点中的字符的大小顺序排列。
查询的时候，我们可以通过二分查找的方法，快速查找到某个字符应该匹配的子节点的指针。
但是，在往 Trie 树中插入一个字符串的时候，我们为了维护数组中数据的有序性，插入的操作就会稍微慢了点。

Trie树还有一个变体，which can 解决内存消耗，缩点优化——
就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并。(这样可以节省空间，但却增加了编码难度。)

五、散列表、红黑树可以替代Trie树吗？

Actually，字符串的匹配问题，就是数据的查找问题。

支持动态数据高效操作的数据结构，比如散列表、红黑树、跳表等等。
实际上，这些数据结构也可以实现在一组字符串中查找字符串的功能。

Trie树和红黑树and跳表相比，在处理情景一组字符串中查找字符串中，Trie树对要处理的字符串有4个比较严格的要求——

1. 字符串中包含的字符集不能太大。
   Because如果字符集太大，那存储空间可能就会浪费很多。
   即便可以优化，但也要付出牺牲查询、插入效率的代价。

2. 要求字符串的前缀重合比较多，不然空间消耗会变大很多。

3. 如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。

4. 通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

综合以上4点，针对在一组字符串中查找字符串的问题，更倾向于用散列表或者红黑树。

In fact，Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。
Trie 树比较适合的是查找前缀匹配的字符串，也就是类似Google中的搜索词提示的那种场景。

六、如何利用 Trie 树，实现搜索关键词的提示功能？

We假设关键词库由用户的热门搜索关键词组成，我们将这个词库构建成一个 Trie 树。

当用户输入其中某个单词的时候，把这个词作为一个前缀子串在 Trie 树中匹配。

• We假设词库里只有 hello、her、hi、how、so、see 这 6 个关键词。当用户输入了字母 h 的时候，我们就把以 h 为前缀的 hello、her、hi、how 展示在搜索提示框内。

• 当用户继续键入字母 e 的时候，我们就把以 he 为前缀的 hello、her 展示在搜索提示框内。

以上就是搜索关键词提示的最基本的算法原理。