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 的。首先先介绍一下这个算法的思路，这个算法的搜索列表并不是原始的列表，例如假设我们原始的列表是：

aida
cori

那么，这个算法是这样存储搜索列表的：

a
ai
aid
aida
aida*
c
co
cor
cori
cori*

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

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

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

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 的话，我们可以设一个保存热度的 sortedset，然后关联出来的结果与热度set 求一个交集，然后按照 score 排序即可。
• 如果是给应用的话，那么我们可以设置一个保存热度的 hash，然后对关联出来的结果去除每个结果的热度，使用排序算法排个序。

这里以给 redis 为例，给一个代码实现：

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 也能搜索出来，这个时候前缀匹配的方法好像不起作用了。这个时候我们就要想一些新的策略了，我这里给出两个方式，这两种分别是时间和空间的选择：

• 时间型：对每一个输入都进行正则匹配，例如将 pple 转为正则 p.*p.*l.*e，然后对每个词都进行正则匹配，找出匹配的，这种方式是需要耗费计算时间的。
• 空间型：对于每个词，我们都讲可能匹配的子串都在 redis 上设置一个键，例如 eat，那么我们就需要设键：e/a/t/ea/at/eat，然后每次搜索的时候只需要 Θ(1) 的时间就找出所有匹配的词了，但是这种方式很耗空间。

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

Reference

• Auto Complete with Redis
• Fast Algorithms for Sorting and Searching Strings
• 使用 Redis 实现自动补全功能
• 10 行 Python 代码写的模糊查询
• autocomplete-redis