Redis 自动补全

自动补全和自动关联是有区别的,我差点将自动关联当做自动补全来讨论了,必须说自动关联这个话题的范围有点大,做得简单些,就是自动补全,也就是这里讨论的前缀匹配,就是说我只能支持搜索特定开头的词,例如假设我要搜索 apple,那么我只能对 "a"/"ap"/"app"/"appl" 进行自动关联,如果你输入 "ale" 我是识别不出来你想要的是 "apple" 的。

如果做得复杂些,不仅要能支持 "ale" 识别出 "apple",还要能自动纠错,例如我即使输入的是 "abble" 你也能联想 "apple" 出来;此外可能还能联想相关搜索,例如我输入 "apple" 会联想出 "orange"/"lenovo"(免费打广告了),如果再智能一些,那都不会出现不同种类了,只会出现 "lenove",如果我真的是想搜 "apple" 这家公司的话。

当然,本文由于水平以及知识限制,本文讨论的只是自动补全,我将会介绍通用的匹配以及与热度相关的补全顺序的实现思路,希望对读者有所帮助。

为了后面的实践方便,我将会给出一份我实践使用到的数据,这是一份人名的列表,将会在后面的实践中拿来做为实践数据使用。如果有需要,可以点此下载

原始版本

我将第一个要解决的问题定义为前缀匹配,对于这个问题,比较原始的做法就是穷举法,我们可以遍历列表,然后找出符合我们要求的,这样的话可以找到符合条件的搜索结果,我给的一个 Python 实现是:

## BF
def search(prefix):
    result = []
    with open('female-names.txt', 'r') as f:
        for line in f:
            if line.strip().startswith(prefix):
                result.append(line.strip())
    return result

这种方法的短板很明显,那就是每次都要全部搜索一遍,很费时间,所以我们需要对他进行改进。

改进版本

原始版本的问题其实就是做了太多无必要的搜索,例如这段名字我们要搜索 "ad" 开头的名字,那很明显搜索完 "adrienne" 之后,后面的 "aeriel" 就没必要搜索了,可以直接跳出返回了。这样的话就省了 90% 以上的时间。但是,这样也有问题啊,假如搜索的是 "za" 开头的,那么我从 "a" 开头到 "y" 期间的所有也要白搜索一遍。

那么这些无谓的损耗能不能避免呢?其实我们分析一下前面的问题,关键有两个问题:

  1. 从哪开始匹配,肯定不能从头开始,太浪费
  2. 到哪算匹配完,也肯定不能到最后,也是很浪费

在查阅了好多的资料之后,我选择了一种比较通俗的做法,这个做法是基于 Redis 的。首先先介绍一下这个算法的思路,这个算法的搜索列表并不是原始的列表,例如假设我们原始的列表是:

1
2
aida
cori

那么,这个算法是这样存储搜索列表的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
a
ai
aid
aida
aida*
c
co
cor
cori
cori*

这样的存储结构的好处就是我们可以很简单得解决两个问题:

  1. 如果找到开始搜索的位置,因为是基于前缀匹配,所以我们可以在列表中找到我们的任何前缀,例如,我输入的是 'ai' 那么,我可以很快找到 'ai' 的 index,然后就从此开始搜索
  2. 当搜索到包含 '*' 号的名字时,这个名字就算匹配上了。
  3. 当我们发现需要匹配的词的前缀已经不是我们的搜索关键词的时候,那么就可以停止搜索了。

基于这个算法,我给出一个简单的 python 实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
SUGGESTION_NAME = 'prefix:suggestion:test'

# gen word's predix list
def gen_words(suggestion):
    words = []
    length = len(suggestion)
    for i in range(1, length):
        words.append(suggestion[0:i])
    words.append(suggestion)
    words.append(suggestion + '*')
    return words

# build new search list
with open('female-names.txt', 'r') as f:
    for line in f:
        words = gen_words(line.strip())
        for word in words:
            rds.zadd(SUGGESTION_NAME, word, 0)

def search(kw):
    max_size = 50
    page_size = 600
    # find begin index
    start = idx = rds.zrank(SUGGESTION_NAME, kw)
    if not idx:
        return []
    keywords = []
    end = start + page_size
    words = rds.zrange(SUGGESTION_NAME, start, end)
    for word in words:
        if word[-1] == '*':
                 # finish
            if not word.startswith(kw):
                break
            keywords.append(word[:-1])
        if len(keywords) >= max_size:
            break
    return keywords

这样的话这个前缀匹配就算是可以完了,因为这里的查找开始的地点的复杂度是 Θ(n),然后搜索的长度是可控的,所以总的复杂度应该是 Θ(n)

热度排行

目前为止,也只是实现了自动关联,但是,我们希望能够做得更好,我们希望能够按照搜索的热度来排序,也就是热门的词拍在前面一些,冷门的词可以放在后面,实现的方式有很多,这里有一个取舍,是将排序的计算量给应用服务器还是给 redis:

这里以给 redis 为例,给一个代码实现:

1
2
3
4
5
6
7
8
def suggestion_with_hot(prefix):
    results = suggestion(prefix)
    for result in results:
        # 确保热度里面每个key 都有记录
        rds.zincrby('hot', result, 0)
        rds.zadd("{}_score".format(prefix), result, 0)
    rds.zinterstore("{}_result".format(prefix), ['hot', "{}_score".format(prefix)])
    return rds.zrevrange("{}_result".format(prefix), 0, -1)

非前缀匹配

到目前为止,我们的自动补全都是针对的前缀匹配,那么假如要任意匹配该怎么实现呢?例如apple 这个词,我希望是搜索 pple 也能搜索出来,这个时候前缀匹配的方法好像不起作用了。这个时候我们就要想一些新的策略了,我这里给出两个方式,这两种分别是时间和空间的选择:

参考文献中的 10 行 Python 代码写的模糊查询 使用的就是时间型方式,而autocomplete-redis 项目使用的是空间型方式。需要注意的是 autocomplete-redis 使用了中文的分词来匹配,这在一定程度上节省了空间,但是也在一定程度上减少了正确度。

Reference