利用Redis如何实现自动补全功能
忘了redis从哪个版本开启，能够根据输入的部分命令前缀给出提示，即自动补全。接下来笔者介绍基于redis实现这个很酷的功能。
aboutsortedset
假设结果中有mara，marabel，marcela。现在我们输入mar，就能得到这三个名字，并且输出结果按照字典排序。在实现这个需求之间，我们先简单介绍sortedset。
大家都知道sortedset是按照score排序的：
127.0.0.1:6380>zaddtest85sida 127.0.0.1:6380>zaddtest80xiaolang 127.0.0.1:6380>zaddtest60afei 127.0.0.1:6380>zaddtest90chenssy 127.0.0.1:6380>zaddtest98yunaiv 127.0.0.1:6380>zrangetest0-1 1)"afei" 2)"xiaolang" 3)"sida" 4)"chenssy" 5)"yunaiv"
但是如果score都一样，sortedset是按照什么排序的呢？是按照字典排序的：
127.0.0.1:6380>zaddexam0sida 127.0.0.1:6380>zaddexam0xiaolang 127.0.0.1:6380>zaddexam0chenssy 127.0.0.1:6380>zaddexam0yunaiv 127.0.0.1:6380>zaddexam0afei 127.0.0.1:6380>zrangeexam0-1 1)"afei" 2)"chenssy" 3)"sida" 4)"xiaolang" 5)"yunaiv"
这是sortedset一个非常重要的特性，也是我们自动补全需求的一个要点。但是这还不够，离我们的最终需求还有一段路要走。幸运的是sortedset还有另一个很酷的命令：ZRANK。这个命令能知道你要查询的key在sortedset中的位置：
127.0.0.1:6380>zrankexamsida (integer)2 127.0.0.1:6380>zrankexamyunaiv (integer)4 127.0.0.1:6380>zrangeexam24 1)"sida" 2)"xiaolang" 3)"yunaiv"
到这里感觉离我们实现自动补全的第一个版本非常接近了，我们能得到sortedset中按照字典排序后任意一个member及其后面N个member。
简单实现
为了实现最终的自动补全，我们需要付出一些代价：空间。
意思是，对于某个准备添加到sortedset中的member，例如afei，我们不仅要把完整的词（afei）添加到sortedset中，而且还要添加所有可能的前缀（a,af,afe,afei）。这里为了解决某个词是真正的member还是某个member的前缀（例如bar既是一个完整的词，也是某个member例如bark的可能前缀），我们加了一个小把戏，即在真正member的后面增加一个特殊字符，例如"$"，那么afei这个member就会添加下列这些词：
a,af,afe,afei,afei$
现在假设我们需要添加三个词：foo,bar,foobar来进行一些测试，那么sortedset中就会有如下这些词：
127.0.0.1:6380>zrangeautoc0-1 1)"b" 2)"ba" 3)"bar" 4)"bar$" 5)"f" 6)"fo" 7)"foo" 8)"foo$" 9)"foob" 10)"fooba" 11)"foobar" 12)"foobar$"
离我们最终的目标又要近了很多。现在假设用户输入"fo"，那么为了实现自动补全，我们需要执行如下命令，仔细查看结果，foo$和foobar$就是我们需要的结果，只需要将特殊后缀$去掉即可（其他没有以$结尾的词全部忽略）：
127.0.0.1:6380>zrankautocfo (integer)5 127.0.0.1:6380>zrangeautoc5-1 1)"fo" 2)"foo" 3)"foo$" 4)"foob" 5)"fooba" 6)"foobar" 7)"foobar$"
更多词的测试
网址http://antirez.com/misc/female-names.txt提供了近5000个女性名字。按照前面说的规则，将所有名字的所有可能前缀全部添加到sortedset中。假定用户输入member，那么只需要通过如下两个命令，得到字典排序后用户输入的member后面的50个词，然后只取$结尾的词：
127.0.0.1:6380>zrankautocmember (integer)8 127.0.0.1:6380>zrangeautoc850
时间&空间复杂度
根据官方文档可知，zrank和zrange的事件复杂度都是O(log(N))。因此，即使数据量比较大，这种方案也是可行的。
ZRANKkeymember
起始版本：2.0.0
时间复杂度：O(log(N))ZRANGEkeystartstop[WITHSCORES]
起始版本：1.2.0
时间复杂度：O(log(N)+M)withNbeingthenumberofelementsinthesortedsetandMthenumberofelementsreturned.
那么需要多少内存呢？
假设在最糟糕的情况下，一个长度为M的词需要添加M+1个词到sortedset中。那么如果有N个词，总计需要添加N*(Ma+1)个词到sortedset中，Ma是这N个词的平均长度。
幸运的是，实际情况远比这个要好得多，以近5000个女性名字为例，只需要添加大约15000个词到sortedset中，因为这些名词存在大量重复的前缀。以3个名字为例：marci，marcia，marcile。如果按照最糟糕的情况，需要添加3*(6+1)=21个词到sortedset中，然而实际情况呢，只需要添加11个词到sortedset中即可：
m,ma,mar,marc,marci,marci$,marcia,marcia$,marcil,marcile,marcile$。
而且，随着样本越来越大，重复的前缀会越大越多。
所以，需要的内存也还OK。是不是觉得美滋滋？哈
查询预测
我们这次的自动补全是按照字典排序，很多时候，这是我们需要的。但是也有一些情况，我们希望按照相似度来排序。例如google搜索那样，搜索结果按照频率和热度等维度进行排序。例如，当用户输入ne，用户应该希望看到Netflix，news，newyorktimes等这些热门关键词。
这样做起来就不那么容易了，如果要能达到根据频率排序，我们需要一个特别的sortedset能以非阻塞的方式实时更新每个前缀的频率：
当用户输入一个例如"foo"这种查询，由于它的所有前缀为："f","fo","foo"。那么对每个前缀都执行命令：ZINCRBY
1foo；如果用户输入"foobar"，那么对每个前缀都执行：ZINCRBY 1foobar；
这种方法还有一个问题，许多自动补全系统只需要展示TOPN个关键词，假设N为10。但是我们这种方法，如果要计算TOP10，我们需要取得关键词远不止10个，理论上我们要这个前缀作为key的sortedset中所有member都取出来。
幸运的是，从统计学上来讲，每个对于sortedset中有300个member的前缀，就能得到TOP5关键词。如果查询越频繁，它的得分越高，它最终被选中的概率也就越高。因此，我们要做的就是对搜索字符串的每个前缀：
- 如果前缀作为key的sortedset中member数量还没有达到300，那么只需要简单的对其zincrby即可；
- 如果前缀作为key的sortedset中member数量已经达到了300，我们将那些得分比较低的member删除，增加新的member进来，从而达到关键词频率不断迭代的效果。
这个方法一下子可能理解不过来，没关系，举个栗子。假设现在用户输入了next，其前缀n为key的sortedset中已经有netflix(100),news(120),newyork(80),near(23),nequ(1)。由于这个前缀对应的sortedset中的member数量还没有300，所以，执行：zincrbyn1next。其中n是前缀，next是用户输入的关键词。假设现在用户输入了next，其前缀n为key的sortedset中已经有netflix(100),news(120),newyork(80),near(23),省略295个score大于1的关键词,nequ(1)。由于这个前缀对应的sortedset中的member数量达到了300，所以，先删除得分比较低的nequ，再执行：zincrbyn1next。
这个方法跟用户输入关键词分布有很大的关联性，如果用户输入的所有关键词频率比较接近，那么这个方法得到的数据并不是很可靠。但是我们知道这不是问题，因为搜索就是绝大部分人在搜索那一小部分关键词集合。
清理阶段
由于上面提到的搜索长尾效应，我们可以讲那些得分为1的member清理掉，因为用户对这些关键词几乎没有任何关注度。清理操作还能够减少使用内存，从而让redis保存更多更有用的数据。
知识总结
- sortedset数据结构中，如果member的score一样，那么按照字典排序。
- zrank命令能得到指定member在结果中的位置，并可以取排在它后面N个member。
- zincrby能给指定的sortedset中的member加分。
参考：http://oldblog.antirez.com/post/autocomplete-with-redis.html
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。