这篇文章主要给大家介绍了关于如何利用Redis如何实现自动补全功能的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用Redis具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧

忘了redis从哪个版本开启,能够根据输入的部分命令前缀给出提示,即自动补全。接下来笔者介绍基于redis实现这个很酷的功能。

about sorted set

假设结果中有mara,marabel,marcela。现在我们输入mar,就能得到这三个名字,并且输出结果按照字典排序。在实现这个需求之间,我们先简单介绍sorted set。

大家都知道sorted set是按照score排序的:

127.0.0.1:6380> zadd test 85 sida
127.0.0.1:6380> zadd test 80 xiaolang
127.0.0.1:6380> zadd test 60 afei
127.0.0.1:6380> zadd test 90 chenssy
127.0.0.1:6380> zadd test 98 yunaiv
127.0.0.1:6380> zrange test 0 -1
1) "afei"
2) "xiaolang"
3) "sida"
4) "chenssy"
5) "yunaiv"

但是如果score都一样,sorted set是按照什么排序的呢?是按照字典排序的:

127.0.0.1:6380> zadd exam 0 sida
127.0.0.1:6380> zadd exam 0 xiaolang
127.0.0.1:6380> zadd exam 0 chenssy
127.0.0.1:6380> zadd exam 0 yunaiv
127.0.0.1:6380> zadd exam 0 afei
127.0.0.1:6380> zrange exam 0 -1
1) "afei"
2) "chenssy"
3) "sida"
4) "xiaolang"
5) "yunaiv"

这是sorted set一个非常重要的特性,也是我们自动补全需求的一个要点。但是这还不够,离我们的最终需求还有一段路要走。幸运的是sorted set还有另一个很酷的命令:ZRANK。这个命令能知道你要查询的key在sorted set中的位置:

127.0.0.1:6380> zrank exam sida
(integer) 2
127.0.0.1:6380> zrank exam yunaiv
(integer) 4
127.0.0.1:6380> zrange exam 2 4
1) "sida"
2) "xiaolang"
3) "yunaiv"

到这里感觉离我们实现自动补全的第一个版本非常接近了,我们能得到sorted set中按照字典排序后任意一个member及其后面N个member。

简单实现

为了实现最终的自动补全,我们需要付出一些代价:空间。

意思是,对于某个准备添加到sorted set中的member,例如afei,我们不仅要把完整的词(afei)添加到sorted set中,而且还要添加所有可能的前缀(a, af, afe, afei)。这里为了解决某个词是真正的member还是某个member的前缀(例如bar既是一个完整的词,也是某个member例如bark的可能前缀),我们加了一个小把戏,即在真正member的后面增加一个特殊字符,例如"$",那么afei这个member就会添加下列这些词:

a, af, afe, afei, afei$

现在假设我们需要添加三个词:foo, bar, foobar 来进行一些测试, 那么sorted set中就会有如下这些词:

127.0.0.1:6380> zrange autoc 0 -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> zrank autoc fo
(integer) 5
127.0.0.1:6380> zrange autoc 5 -1
1) "fo"
2) "foo"
3) "foo$"
4) "foob"
5) "fooba"
6) "foobar"
7) "foobar$"

更多词的测试

网址http://antirez.com/misc/female-names.txt 提供了近5000个女性名字。按照前面说的规则,将所有名字的所有可能前缀全部添加到sorted set中。假定用户输入member,那么只需要通过如下两个命令,得到字典排序后用户输入的member后面的50个词,然后只取$结尾的词:

127.0.0.1:6380> zrank autoc member
(integer) 8
127.0.0.1:6380> zrange autoc 8 50

时间&空间复杂度

根据官方文档可知,zrank和zrange的事件复杂度都是O(log(N))。因此,即使数据量比较大,这种方案也是可行的。

ZRANK key member
起始版本:2.0.0
时间复杂度:O(log(N))

ZRANGE key start stop [WITHSCORES]
起始版本:1.2.0
时间复杂度:O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.

那么需要多少内存呢?

假设在最糟糕的情况下,一个长度为M的词需要添加M+1个词到sorted set中。那么如果有N个词,总计需要添加N*(Ma+1)个词到sorted set中,Ma是这N个词的平均长度。

幸运的是,实际情况远比这个要好得多,以近5000个女性名字为例,只需要添加大约15000个词到sorted set中,因为这些名词存在大量重复的前缀。以3个名字为例:marci,marcia,marcile。如果按照最糟糕的情况,需要添加3*(6+1)=21个词到sorted set中,然而实际情况呢,只需要添加11个词到sorted set中即可:

m, ma , mar, marc, marci, marci$, marcia, marcia$, marcil, marcile, marcile$。

而且,随着样本越来越大,重复的前缀会越大越多。

所以,需要的内存也还OK。是不是觉得美滋滋?哈

查询预测

我们这次的自动补全是按照字典排序,很多时候,这是我们需要的。但是也有一些情况,我们希望按照相似度来排序。例如google搜索那样,搜索结果按照频率和热度等维度进行排序。例如,当用户输入ne,用户应该希望看到Netflix,news,new york times等这些热门关键词。

这样做起来就不那么容易了,如果要能达到根据频率排序,我们需要一个特别的sorted set能以非阻塞的方式实时更新每个前缀的频率:

当用户输入一个例如"foo"这种查询,由于它的所有前缀为:"f", "fo", "foo"。那么对每个前缀都执行命令:ZINCRBY <prefix> 1 foo ;如果用户输入"foobar",那么对每个前缀都执行:ZINCRBY <prefix> 1 foobar;

这种方法还有一个问题,许多自动补全系统只需要展示TOP N个关键词,假设N为10。但是我们这种方法,如果要计算TOP 10,我们需要取得关键词远不止10个,理论上我们要这个前缀作为key的sorted set中所有member都取出来。

幸运的是,从统计学上来讲,每个对于sorted set中有300个member的前缀,就能得到TOP 5关键词。如果查询越频繁,它的得分越高,它最终被选中的概率也就越高。因此,我们要做的就是对搜索字符串的每个前缀:

    如果前缀作为key的sorted set中member数量还没有达到300,那么只需要简单的对其zincrby即可; 如果前缀作为key的sorted set中member数量已经达到了300,我们将那些得分比较低的member删除,增加新的member进来,从而达到关键词频率不断迭代的效果。

这个方法一下子可能理解不过来,没关系,举个栗子。假设现在用户输入了next,其前缀n为key的sorted set中已经有netflix(100), news(120), new york(80), near(23), nequ(1)。由于这个前缀对应的sorted set中的member数量还没有300,所以,执行:zincrby n 1 next。其中n是前缀,next是用户输入的关键词。假设现在用户输入了next,其前缀n为key的sorted set中已经有netflix(100), news(120), new york(80), near(23), 省略295个score大于1的关键词, nequ(1)。由于这个前缀对应的sorted set中的member数量达到了300,所以,先删除得分比较低的nequ,再执行:zincrby n 1 next。

这个方法跟用户输入关键词分布有很大的关联性,如果用户输入的所有关键词频率比较接近,那么这个方法得到的数据并不是很可靠。但是我们知道这不是问题,因为搜索就是绝大部分人在搜索那一小部分关键词集合。

清理阶段

由于上面提到的搜索长尾效应,我们可以讲那些得分为1的member清理掉,因为用户对这些关键词几乎没有任何关注度。清理操作还能够使用内存,从而让redis保存更多更有用的数据。

知识总结

    sorted set数据结构中,如果member的score一样,那么按照字典排序。 zrank命令能得到指定member在结果中的位置,并可以取排在它后面N个member。 zincrby能给指定的sorted set中的member加分。

参考:http://oldblog.antirez.com/post/autocomplete-with-redis.html

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对爱安网的支持。

最新资讯
那颗星星,突然消失了

那颗星星,突然消失了

一颗恒星突然消失了。这一奇怪的事件发生在一个距离我
特斯拉在中国启动电动皮卡Cybertruck预订 订金1000元

特斯拉在中国启动电动

特斯拉共提供三款CyberTruck,分别是单电机后轮驱动、双
滴滴未有轻松时刻:短中长周期面临三大问题

滴滴未有轻松时刻:短中

滴滴,百度,以及智能汽车车企在这个赛道角逐,谁跑得快就夺
阅文新合同一个月:谁在逃离,谁在回归?

阅文新合同一个月:谁在

阅文合同风波一个月后,作者群体分化,平台战略意图愈加明
5G第一个演进版本标准完成:3GPP宣布R16标准冻结

5G第一个演进版本标准

国际通信标准组织3GPP宣布R16标准冻结,标志5G第一个演
保价5万寄古董遭损引赔偿纠纷 律师建议完善保价制度

保价5万寄古董遭损引

王永康建议,快递公司应当尽快改进完善保价制度,在客户进
最新文章
从一个小需求感受Redis的独特魅力(需求设计)

从一个小需求感受Redi

Redis在实际应用中使用的非常广泛,本篇文章就从一个简
详解redis desktop manager安装及连接方式

详解redis desktop ma

这篇文章主要介绍了redis desktop manager安装及连接
Redis集群下过期key监听的实现代码

Redis集群下过期key监

这篇文章主要介绍了Redis集群下过期key监听的实现代码
Redis集群增加节点与删除节点的方法详解

Redis集群增加节点与

这篇文章主要给大家介绍了关于Redis集群增加节点与删
Linux 下redis5.0.0安装教程详解

Linux 下redis5.0.0安

这篇文章主要介绍了Linux 下redis5.0.0安装教程,本文图
Redis 实现“附近的人”功能

Redis 实现“附近的人

Redis基于geohash和有序集合提供了地理位置相关功能。