如何实现一个搜索自动补全器？
葛霖霖
导语 | 自动补全功能对于使用移动设备的用户来说很友好，用户可以很方便的在难以键入的小屏幕上完成搜索，并能节省用户大量的时间。根据 Google 官方报告，自动补全功能可以减少大约 25% 的打字，累积起来预计每天可以节省 200 多年的打字时间。本文将介绍如何实现一个自动补全器，希望与大家一同交流。文章作者：葛霖霖，腾讯运营开发工程师。
一、自动补全
1. 什么是自动补全
自动补全的功能其实很常用，如下图所示：
搜索引擎根据我们输入的关键字进行一些提示，这样用户只需要输入部分内容就可以进行选择。
2. 几种常用的自动补全方式
Google 官方目前并没有公开搜索自动补全的算法实现，但是业界在这方面都有自己的实现。
以下图为例，我们可以看下业界是如何做的：
淘宝、京东、拼多多、百度都有做自动补全器，这里我们可以看到，基本上所有的自动补全器都支持前缀匹配。那么前缀匹配可以如何实现呢？
常用的实现方式可以列成三种：
- MySQL实现；
- Redis实现；
- Elasticsearch实现。
下文将分别介绍这三种实现方式。
二、MySQL实现
MySQL 的实现方式主要是利用 MySQL LIKE 语句来实现。比如：
SELECT * FROM table WHERE keyword LIKE "ssss%" LIMIT 10
使用 MySQL 实现自动补全器，实现简单，但数据量不宜过大。数据量大时，性能较差，并且在做热频词的时候，根据热度查询需要额外处理。
三、Redis实现
使用 Redis 实现时，我们可以利用有序集合，让 score 都为 0，这样就可以按元素值的字典序排序。然后我们可以根据排序号的字符，以添加后缀的方式,找到我们想要的内容。
如下图所示，这里是一个 zset 集合元素：
当所有的数值分值为 0 的时候，zset 会按照字典升序排列。如果我们需要查找上面的 a，就应该能找出 [ a, ab,abcd,abef ] 这四个元素，查找上面的 ab，就应该能找出 [ab,abcd,abef] 这三个元素。
假设我们要匹配 ab，如果我们能知道所有匹配 ab 的 member 在 zset 里的起始位置,那就好办了。那么怎么知道能匹配 ab 的字符都有什么，都在 zset 的什么位置呢?可以参照下面的做法：
- 首先，ASCII 码里小写字母 a 的前面是符号： `，字母 z 的后面是符号：{ ；
- 于是我们查找 ab 匹配的元素，插入 aa{ 和 ab{ ；
- 找到 aa{ 和 ab{ 的下标，通过 Zrange() 得出相关区间的内容；
- 如果是中文，可全部将字符转为 16 进制字符来进行存储，取出的时候再转码。
这里如果需要做热频词的话，可以重新创建一个 zset 专门用来存储每个词对应的热度。最后，将查询结合和这个记录热度的集合做交集，得出按热度排列的结果。
使用 Redis 实现，和 MySQL 一样，如果自动补全器还需要有纠错功能的话，就不太容易实现了。
四、ES实现
如何用 ES 来实现自动补全功能呢，答案就在于 Suggesters API 。ES 设计了 4 种类别的 Suggester 。其中 Completion Suggester 主要针对的场景就是自动补全，它支持按给定的热度排序。
因为自动补全的请求对后端响应速度要求比较苛刻，因此它采用了与其他 Suggester 不同的数据结构，索引并非通过倒排来完成，而是将 analyze 过的数据编码成 FST 和索引一起存放。
对于一个 open 状态的索引，FST 会被 ES 整个装载到内存里的，进行前缀查找且速度极快。但是 FST 只能用于前缀查找，这也是 Completion Suggester 的局限所在。
1. 使用方法
为了使用 Completion Suggester ，字段的类型需要专门定义如下:
PUT /ulink_dict/
{
"mappings": {
"dict" : {
"properties" : {
"suggest" : {
"type" : "completion"
},
}
}
}
}
指定 weight 排序值：
PUT ulink_dict/dict/1
{
"suggest" : {
"input": [ "关键词" ],
"weight" : 80
}
}
查找前缀匹配：
POST /ulink_dict/_search
{
"suggest": {
"song-suggest" : {
"prefix" : "关键词",
"completion" : {
"field" : "suggest"
}
}
}
}
2. FST数据结构
下文将介绍 FST 数据结构，也就是 Completion Suggester 使用的数据结构。
通常来说，许多词汇都以相同的前缀开头，比如 need、nested 都以 ne 开头，seed、speed 都以 s 开头。要是为每个单词分别存储公共前缀似乎很浪费。
Lucene 从 4 以后开始大量使用 FST（Finite State Transducer）的数据结构。FST
有两个优点：
- 空间占用小：通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；
- 查询速度快：O(len(str)) 的查询时间复杂度。
这里可以看下我们是如何对 “cat”、 “deep”、 “do” 这 3 个单词进行插入构建 FST ：
第一步： 插入 "cat"，每个字母形成一条边，其中 t 边指向终点。
第二步： 插入 "deep", 与前一个单词 “cat” 进行最大前缀匹配，发现没有匹配则直接插入，P 边指向终点。
第三步： 插入 "do"，与前一个单词 “deep” 进行最大前缀匹配，发现是 d，则在 d 边后增加新边 o，o 边指向终点。
最终我们得到了如上图所示的一个有向无环图，利用该结构可以很方便的进行查询。如给定一个 “do”，我们可以通过上述结构很方便的查询存不存在，甚至我们在构建过程中可以将单词与某一数字、单词进行关联，从而实现 key-value 的映射。
ES 除了支持使用 Completion Suggester 进行关键词前缀匹配，也支持利用 Term Suggester 来实现纠错补全，在输入错误的情况下补全正确的关键词。
这里的方案可以是先用 Completion Suggester 进行关键词前缀匹配，当随着用户输入的字越来越多，匹配项越来越少，或者没有匹配项的时候，可以用 Term Suggester 来获取推荐可能正常的关键词。
五、结语
本文介绍了自动补全的概念和使用场景，并且介绍了实现自动补全的 3 种方式，即使用 MySQL、Redis、ES 来实现。具体使用还是要看具体的场景，好的自动补全器是需要根据业务场景和数据特性，灵活搭配各种方法和反复调试才能获得理想的补全效果。
参考资料：
https://www.elastic.co/guide/en/elasticsearch/reference/current/search-suggesters.html
https://blog.burntsushi.net/transducers/
