服务器之家:专注于服务器技术及软件下载分享
分类导航

Mysql|Sql Server|Oracle|Redis|MongoDB|PostgreSQL|Sqlite|DB2|mariadb|Access|数据库技术|

服务器之家 - 数据库 - Redis - 利用Redis如何实现自动补全功能

利用Redis如何实现自动补全功能

2019-11-27 16:04阿飞的博客 Redis

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

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

about sorted set

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

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

?
1
2
3
4
5
6
7
8
9
10
11
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是按照什么排序的呢?是按照字典排序的:

?
1
2
3
4
5
6
7
8
9
10
11
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中的位置:

?
1
2
3
4
5
6
7
8
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就会添加下列这些词:

?
1
a, af, afe, afei, afei$

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
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$就是我们需要的结果,只需要将特殊后缀$去掉即可(其他没有以$结尾的词全部忽略):

?
1
2
3
4
5
6
7
8
9
10
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个词,然后只取$结尾的词:

?
1
2
3
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中即可:

?
1
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

总结

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

原文链接:https://www.jianshu.com/p/b9e7feba2a9c

延伸 · 阅读

精彩推荐
  • RedisRedis 6.X Cluster 集群搭建

    Redis 6.X Cluster 集群搭建

    码哥带大家完成在 CentOS 7 中安装 Redis 6.x 教程。在学习 Redis Cluster 集群之前,我们需要先搭建一套集群环境。机器有限,实现目标是一台机器上搭建 6 个节...

    码哥字节15752021-04-07
  • Redis详解三分钟快速搭建分布式高可用的Redis集群

    详解三分钟快速搭建分布式高可用的Redis集群

    这篇文章主要介绍了详解三分钟快速搭建分布式高可用的Redis集群,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,...

    万猫学社4502021-07-25
  • Redisredis缓存存储Session原理机制

    redis缓存存储Session原理机制

    这篇文章主要为大家介绍了redis缓存存储Session原理机制详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪...

    程序媛张小妍9252021-11-25
  • Redis关于Redis数据库入门详细介绍

    关于Redis数据库入门详细介绍

    大家好,本篇文章主要讲的是关于Redis数据库入门详细介绍,感兴趣的同学赶快来看一看吧,对你有帮助的话记得收藏一下,方便下次浏览...

    沃尔码6982022-01-24
  • Redis如何使用Redis锁处理并发问题详解

    如何使用Redis锁处理并发问题详解

    这篇文章主要给大家介绍了关于如何使用Redis锁处理并发问题的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用Redis具有一定的参考学习...

    haofly4522019-11-26
  • Redis《面试八股文》之 Redis十六卷

    《面试八股文》之 Redis十六卷

    redis 作为我们最常用的内存数据库,很多地方你都能够发现它的身影,比如说登录信息的存储,分布式锁的使用,其经常被我们当做缓存去使用。...

    moon聊技术8182021-07-26
  • RedisRedis Template实现分布式锁的实例代码

    Redis Template实现分布式锁的实例代码

    这篇文章主要介绍了Redis Template实现分布式锁,需要的朋友可以参考下 ...

    晴天小哥哥2592019-11-18
  • RedisRedis集群的5种使用方式,各自优缺点分析

    Redis集群的5种使用方式,各自优缺点分析

    Redis 多副本,采用主从(replication)部署结构,相较于单副本而言最大的特点就是主从实例间数据实时同步,并且提供数据持久化和备份策略。...

    优知学院4082021-08-10