自动补全¶

自动补全经常出现在搜索引擎或者应用的搜索框中，比如当我们在搜索引擎的搜索框中输入字母“re”的时候，搜索引擎就会通过自动补全提示我们是否要选择“reddit”、“redis”、“react”或者“reuters”等建议的其中一个，而在输入“redis”的时候，搜索引擎则会提示“redis命令”、“redisson”、“redisinsight”或者“redis desktop manager”等建议以供选择。

需求描述¶

你想要使用Redis实现自动补全程序，这种程序能够根据用户的输入提供可选的建议，从而帮助用户更快、更准确地完成输入过程。

解决方案¶

实现自动补全的关键是针对用户输入构建出一系列建议表：表中包含建议项及其权重值，各个建议项按权重从高到低排序，其中权重基于建议项的使用频率或者特定算法计算得出。

以前面的自动补全描述结果为例，对于输入"re"，系统应该构建出一个表 TABLE_RECOMMEND 所示的建议表。

表 TABLE_RECOMMEND 输入"re"对应的建议表

建议项	权重
`"reddit"`	`100.0`
`"redis"`	`90.0`
`"react"`	`75.0`
`"reuters"`	`62.0`
`...`	`...`

要在Redis存储建议表形式的数据，使用有序集合可谓再合适不过了：只要将建议项设置为有序集合成员并将权重设置为成员的分值即可。

此外，为了让自动补全程序能够对输入的每个片段都进行响应，程序必需为输入的每个片段都创建相应的建议表。比方说，对于输入"redis"，程序必须为"r"、"re"、"red"、"redi"和"redis"分别创建建议表。

最后要考虑的就是如何决定建议项的权重了。一般来说，建议项的权重既可以定期基于算法进行更新，也可以根据用户的输入动态进行调整。其中一种特别简单的动态调整权重的方法，就是直接统计用户输入每个单词的次数并将其用作权重。

以上面的表 TABLE_RECOMMEND 为例，在采用输入次数统计方法的情况下，单词"reddit"的权重100就是用户输入该单词100次的结果，而单词"redis"的权重90则是用户输入该单词90次的结果，以此类推。

为了在建议表中实现统计用户输入次数的效果，程序需要在用户每次输入一个单词的时候，在该单词对应的每个建议表中执行以下命令，将单词的统计次数加上一：

ZINCRBY <key> 1.0 <word>

举个例子，如果用户输入的是"redis"，那么程序就需要对"r"、"re"、"red"、"redi"和"redis"对应的建议表分别执行一次针对单词"redis"的权重加一操作，就像这样：

ZINCRBY AutoComplete:r 1.0 "redis"
ZINCRBY AutoComplete:re 1.0 "redis"
ZINCRBY AutoComplete:red 1.0 "redis"
ZINCRBY AutoComplete:redi 1.0 "redis"
ZINCRBY AutoComplete:redis 1.0 "redis"

与此对应，当程序想要根据用户的输入为其提供建议时，只需要执行ZRANGE命令返回相应建议表中的建议项即可。比如说，当用户输入"re"的时候，程序只需要执行以下命令就可以为用户提供最多10个建议项：

ZRANGE AutoComplete:re 0 9 REV

注意，为了返回建议表中权重最高的10个建议项，ZRANGE命令需要用到REV选项，这是不可或缺的。

实现代码¶

基于上一节介绍的原理，代码清单 CODE_AUTO_COMPLETE 展示了自动补全程序的具体实现代码。

代码清单 CODE_AUTO_COMPLETE 自动补全程序 auto_complete.py

DEFAULT_WEIGHT = 1.0
DEFAULT_NUM = 10

def make_ac_key(subject, segment):
    """
    基于给定的主题和输入片段，构建保存建议项的建议表。
    """
    return "AutoComplete:{0}:{1}".format(subject, segment)

def create_segments(content):
    """
    根据输入的字符串为其创建片段。
    例子：对于输入"abc"，将创建输出["a", "ab", "abc"]
    """
    return [content[:i] for i in range(1, len(content)+1)]

class AutoComplete:

    def __init__(self, client, subject):
        self.client = client
        self.subject = subject

    def feed(self, content, weight=DEFAULT_WEIGHT):
        """
        根据输入内容构建自动补全建议表。
        可选的weight参数用于指定需要增加的输入权重。
        """
        tx = self.client.pipeline()
        # 将输入分解为片段，然后对其相应的建议表执行操作
        for seg in create_segments(content):
            # 构建建议表键名
            key = make_ac_key(self.subject, seg)
            # 更新输入在该表中的权重
            tx.zincrby(key, weight, content)
        tx.execute()

    def hint(self, segment, num=DEFAULT_NUM):
        """
        根据给定的片段返回指定数量的补全建议，各个建议项之间按权重从高到低排列。
        """
        # 构建建议表键名
        key = make_ac_key(self.subject, segment)
        # 获取补全建议
        return self.client.zrange(key, 0, num-1, desc=True)

    def set(self, content, weight):
        """
        为输入内容设置指定的权重。
        """
        tx = self.client.pipeline()
        for seg in create_segments(content):
            key = make_ac_key(self.subject, seg)
            # 直接设置权重
            tx.zadd(key, {content: weight})
        tx.execute()

考虑到一个应用里面可能会有多个地方需要用到自动补全功能，所以这个程序使用了subject参数用来区分各种不同主题的自动补全建议表。在使用这个程序的时候，用户需要给定一个subject参数，然后程序就会根据该参数构建相应的键名，并将其用于创建自动补全建议表。

此外，这个程序还提供了set()方法以便用户在有需要的时候可以修改指定内容的权重，又或者根据给定的权重创建建议表。

作为示例，以下代码演示了如何使用这个自动补全程序：

>>> from redis import Redis
>>> from auto_complete import AutoComplete
>>> client = Redis(decode_responses=True)
>>> ac = AutoComplete(client, "search")
>>> for i in range(5):  # 模拟用户输入
...   ac.feed("banana")
...
>>> for i in range(2):
...   ac.feed("banquet")
...
>>> for i in range(3):
...   ac.feed("band")
...
>>> ac.hint("ban")  # 模拟用户获取建议
['banana', 'band', 'banquet']

这段代码通过多次调用feed()来模拟用户输入多个单词：其中"banana"输入了五次，"band"输入了三次，而"banquet"只输入了两次，所以在针对输入"ban"获取建议的时候，自动补完程序将按照输入次数从多到少分别获取上述三个单词作为建议项。

正如之前所说，除了根据用户输入生成建议表之外，还可以直接使用set()方法，基于给定的权重值直接创建建议表：

>>> ac.set("reddit", 100)  # 为各个建议项分别设置权重
>>> ac.set("redis", 90)
>>> ac.set("react", 75)
>>> ac.set("reuters", 62)
>>> ac.hint("re")  # 获取建议
['reddit', 'redis', 'react', 'reuters']

set()方法适用于基于算法定期更新建议表的场景，用户只需要根据算法计算出各个建议项的权重，然后定期更新相应的各个建议表即可。

扩展实现：自动移除冷门建议表¶

正如之前所说，我们的自动补全程序可以根据用户输入动态创建对应的建议表。但随着用户输入数量的增加，程序创建的大量建议表可能会产生非常大的内存消耗。为了解决这个问题，可以考虑增加一个排行榜，统计每个输入出现的次数，然后保留热门输入的建议表，删除冷门输入的建议表。

不过有一个更好的方法可以达到类似的效果，而且不需要另外使用排行榜进行记录：

通过在feed()方法的ZINCRBY调用之后增加一个EXPIRE调用，程序可以为每个输入对应的每个建议表设置过期时间。
随着输入不断出现，热门输入对应的建议表将被反复设置过期时间，而基于EXPIRE命令的默认行为，已经存在的过期时间会被新的过期时间覆盖，从而产生一种“续期”效果，使得被设置的键可以一直存在。
这样做最终导致的结果是，热门输入所产生的建议表将一直存在，而少有人问津的冷门输入所产生的建议表将随着时间流逝自动被移除，这是非常巧妙的一种优化内存占用的方法。

举个例子，在采取上述措施时，对于输入"redis"，程序应该产生以下命令序列：

ZINCRBY AutoComplete:r 1.0 "redis"
EXPIRE  AutoComplete:r 300
ZINCRBY AutoComplete:re 1.0 "redis"
EXPIRE  AutoComplete:re 300
ZINCRBY AutoComplete:red 1.0 "redis"
EXPIRE  AutoComplete:red 300
ZINCRBY AutoComplete:redi 1.0 "redis"
EXPIRE  AutoComplete:redi 300
ZINCRBY AutoComplete:redis 1.0 "redis"
EXPIRE  AutoComplete:redis 300

在此之后，只要在接下来的5分钟也即是300秒之内，有至少一个用户输入了同样的单词"redis"，那么上述命令序列就会再执行一次，并将相关建议表的过期时间重新设置为300秒；相反地，如果在300秒之内没有任何人输入"redis"，那么上述命令相关的建议表就会自动被移除。

基于上述原理，代码清单 CODE_FEEDEX 展示了带有自动移除冷门建议表特性的feedex()方法的具体定义。

代码清单 CODE_FEEDEX feedex()方法 auto_complete.py

DEFAULT_WEIGHT = 1.0
DEFAULT_TTL = 300

class AutoComplete:

    def feedex(self, content, weight=DEFAULT_WEIGHT, ttl=DEFAULT_TTL):
        """
        根据输入内容构建自动补全建议表。
        可选的weight参数用于指定需要增加的输入权重。
        可选的ttl参数用于指定建议表的生存时间，默认为300秒（5分钟）。
        """
        tx = self.client.pipeline()
        for seg in create_segments(content):
            key = make_ac_key(self.subject, seg)
            tx.zincrby(key, weight, content)
            # 为建议表设置生存时间
            tx.expire(key, ttl)
        tx.execute()

正如以下代码所示，feedex()的使用方式跟feed()基本相同，它们之间的主要区别在于feedex()创建的建议表必须持续地“续期”才会一直存在，否则它们就会随着键到期而消失，从而导致建议结果也消失：

>>> from redis import Redis
>>> from auto_complete import AutoComplete
>>> client = Redis(decode_responses=True)
>>> ac = AutoComplete(client, "search")
>>> ac.feedex("redis", ttl=10)  # 建议表的有效期为10秒钟
>>> ac.hint("re")  # 10秒内执行
['redis']
>>> ac.hint("re")  # 超过10秒之后执行
[]

重点回顾¶

自动补全能够根据用户的输入提供可选的建议，帮助他们更快、更准确地完成输入过程。
实现自动补全的关键是针对用户输入构建出一系列建议表，而要在Redis存储建议表形式的数据，使用有序集合可谓再合适不过了：只要将建议项设置为有序集合成员并将权重设置为成员的分值即可。：表中包含建议项及其权重值，各个建议项按权重从高到低排序，其中权重基于建议项的使用频率或者特定算法计算得出。
一般来说，建议项的权重既可以定期基于算法进行更新，也可以根据用户的输入动态进行调整。其中一种特别简单的动态调整权重的方法，就是直接统计用户输入每个单词的次数并将其用作权重。
根据用户输入自动创建建议表的做法将产生大量建议表，通过为这些建议表设置过期时间并利用Redis的过期时间更新机制，可以让热门的建议表一直存在，并让冷门的建议表自动被移除。