如何实现一个搜索自动补全器?

葛霖霖

导语 | 自动补全功能对于使用移动设备的用户来说很友好,用户可以很方便的在难以键入的小屏幕上完成搜索,并能节省用户大量的时间。根据 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/


本文地址:https://www.6aiq.com/article/1599611620992
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出