检索技术核心20讲
陈东
奇虎360商业产品事业部资深总监
立即订阅
1955 人已学习
课程目录
已完结 29 讲
0/4登录后,你可以任选4讲全文学习。
课前必学 (2讲)
开篇词 | 学会检索,快人一步!
免费
导读 | 三步走策略,轻松搞定检索!
基础技术篇 (8讲)
01 | 线性结构检索:从数组和链表的原理初窥检索本质
02 | 非线性结构检索:数据频繁变化的情况下,如何高效检索?
03 | 哈希检索:如何根据用户ID快速查询用户信息?
04 | 状态检索:如何快速判断一个用户是否存在?
05 | 倒排索引:如何从海量数据中查询同时带有“极”和“客”的唐诗?
测一测 | 检索算法基础,你掌握了多少?
特别加餐 | 倒排检索加速(一):工业界如何利用跳表、哈希表、位图进行加速?
特别加餐 | 倒排检索加速(二):如何对联合查询进行加速?
进阶实战篇 (13讲)
06 | 数据库检索:如何使用B+树对海量磁盘数据建立索引?
07 | NoSQL检索:为什么日志系统主要用LSM树而非B+树?
08 | 索引构建:搜索引擎如何为万亿级别网站生成索引?
09 | 索引更新:刚发布的文章就能被搜到,这是怎么做到的?
10 | 索引拆分:大规模检索系统如何使用分布式技术加速检索?
11|精准Top K检索:搜索结果是怎么进行打分排序的?
12 | 非精准Top K检索:如何给检索结果的排序过程装上“加速器”?
13 | 空间检索(上):如何用Geohash实现“查找附近的人”功能?
14 | 空间检索(下):“查找最近的加油站”和“查找附近的人”有何不同?
15 | 最近邻检索(上):如何用局部敏感哈希快速过滤相似文章?
16 | 最近邻检索(下):如何用乘积量化实现“拍照识花”功能?
特别加餐 | 高性能检索系统中的设计漫谈
测一测 | 高性能检索系统的实战知识,你掌握了多少?
系统案例篇 (4讲)
17 | 存储系统:从检索技术角度剖析LevelDB的架构设计思想
18 | 搜索引擎:输入搜索词以后,搜索引擎是怎么工作的?
19 | 广告系统:广告引擎如何做到在0.1s内返回广告信息?
20 | 推荐引擎:没有搜索词,“头条”怎么找到你感兴趣的文章?
结束语 (2讲)
结束语 | 成长和进化,技术如此,我们亦如此
免费
结课测试 | 这些检索知识,你都掌握了吗?
检索技术核心20讲
15
15
1.0x
00:00/00:00
登录|注册

05 | 倒排索引:如何从海量数据中查询同时带有“极”和“客”的唐诗?

陈东 2020-04-01
你好,我是陈东。
试想这样一个场景:假设你已经熟读唐诗 300 首了。这个时候,如果我给你一首诗的题目,你可以马上背出这首诗的内容吗?相信你一定可以的。但是如果我问你,有哪些诗中同时包含了“极”字和“客”字?你就不见得能立刻回答出来了。你需要在头脑中一首诗一首诗地回忆,并判断每一首诗的内容是否同时包含了“极”字和“客”字。很显然,第二个问题的难度比第一个问题大得多。
那从程序设计的角度来看,这两个问题对应的检索过程又有什么不同呢?今天,我们就一起来聊一聊,两个非常常见又非常重要的检索技术:正排索引和倒排索引。

什么是倒排索引?

我们先来看比较简单的那个问题:给出一首诗的题目,马上背出内容。这其实就是一个典型的键值查询场景。针对这个场景,我们可以给每首诗一个唯一的编号作为 ID,然后使用哈希表将诗的 ID 作为键(Key),把诗的内容作为键对应的值(Value)。这样,我们就能在 O(1) 的时间代价内,完成对指定 key 的检索。这样一个以对象的唯一 ID 为 key 的哈希索引结构,叫作正排索引(Forward Index)。
哈希表存储所有诗
一般来说,我们会遍历哈希表,遍历的时间代价是 O(n)。在遍历过程中,对于遇到的每一个元素也就是每一首诗,我们需要遍历这首诗中的每一个字符,才能判断是否包含“极”字和“客”字。假设每首诗的平均长度是 k,那遍历一首诗的时间代价就是 O(k)。从这个分析中我们可以发现,这个检索过程全部都是遍历,因此时间代价非常高。对此,有什么优化方法吗?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《检索技术核心20讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(22)

  • 无形
    根据作者查询可以给每首诗打一个作者的标签,再把标签作为关键字,标签对应的文档集合即为这位诗人写的诗的集合,如这种格式
    key=array
    "作者_李白"=["将进酒","凤求凰","静夜思"]
    这里加的前缀"作者_"可以避免有的诗里面有"李白"这两个字,造成检索结果不准确,实际中key可能把key映射成ID,集合里保存的也是诗的ID,这是一种主动打标签的方式,如果还需要按照朝代查询,再打朝代的标签
    对于检索效率的问题,当数据量很大的时候,显然不可能用链表,查询效率太低了,位图相比查询效率就非常高了,每个byte就能表示一个诗的ID,1表示有,0表示没有,因此非常省内存,而且位运算取交集、差集效率非常高,不过普通位图有一个缺点,如果数据稀疏的话比较浪费空间,因此有人研究出了压缩位图,压缩位图的主要思想是把一个int划分为高16位低16位,高16位对应int存储的容器,把低6位放到对应的容器中,容器有三种,有序集合、位图、还有一种忘了名字,会随着数据量的变化选择合适的容器来存储数据,比较节省内存,倒排索引+压缩位图是一个非常强的组合,搜索性能非常高,合适的场景下甚至可以替换ES,提升几十倍搜索性能。快手、华为千亿级用户标签检索系统中也有类似的应用

    作者回复: 非常棒!用不同的key进行区分的确是一个方案。另一个方案是可以在posting list中加域,标明是作者还是内容。
    还有,倒排索引的检索效率优化是一个很重要的问题。你说的压缩位图是roaring bitmap,这的确是最近几年很火的一个应用。剧透一下,加餐会讲到。

    2020-04-01
    2
    18
  • 阿斯蒂芬
    想起了之前看《改变未来的九大算法》(书名比较夸张,但书是好书啊各位),开篇讲到了搜索引擎的「把戏」,就是从单词分词构建单词到网页的链接集合,来实现最「粗糙」的互联网检索冲浪。随后再考虑同时检索到多个满足条件的结果时,如何确定哪一个才更接近我们所需要的。于是在单纯记录单词出现的网页的基础上,加上了单词在这个网页的位置,理论上可以简单认为位置越近,就越符合我们检索条件的输入。
    以上两个知识点其实跟老师讲的倒排索引思路类似。思考题的李白,其实也算是一种:假设作者和内容都命中,我们如何能区分哪个才是更接近我们想要的答案。解决这类问题的思路也是相似的,像单词增多一个在网页出现的位置记录一样,也可以考虑让“李白”多增加一个信息,来让计算机知道它是「出现在什么位置」的,当然这里的位置可能就变成了:内容、作者这样的标签或者类型。

    人类想借助计算机快算处理结构化数据的特点,将人类知识从小条目到全文的检索关系结构化存储到计算机,实现了「正向索引」,但是贪婪的人类并不满足,调皮大脑还有一个特性就是,全文记不住,全文的这一小段那一小段倒是可能记得溜,所以人类又聪明地让计算机以类似的存储结构但是不同的关系方向来实现全文内容到全文方向的查找,于是出来了「倒排索引」。这个角度来看,说检索技术真是是被人类特征的需求来驱动进展的不为过。

    作者回复: 工业社会的一个特点就是追求效率,如何能更快地完成事情是我们一直在追求的一个目标。检索技术可以说是我们在信息时代的加速器,它能帮助我们更快地获取信息,以及让系统更高速地运作。我相信它会持续地演化和影响我们的未来。

    2020-04-17
    1
    3
  • 范闲
    拉链的是倒排索引在数据量不大的情况下应该很好?如果数量上去了,要改成跳表了吧?如果跳表也支撑不下去了呢?

    作者回复: 你的问题我理解有两点:
    1.检索效率问题。
    2.存储空间问题。
    关于检索效率问题,马上会出来两篇热腾腾的加餐,和你聊聊怎么进行倒排索引的检索加速。
    关于存储空间问题,我接下来在进阶篇会开始介绍解决方案。

    2020-04-01
    2
    3
  • fengyi
    有个问题想请教。如果要搜寻‘极客’这个单词的话。有方法可以重复利用‘极’和‘客’的索引吗。还是要对‘极客’单独作索引

    作者回复: 将“极客”作为一个单独的key进行索引是比较高效的。因为它只在检索时只需要直接将posting list取出即可。
    当然,在分词不work的情况下,我们也可以单独对“极”和“客”进行检索,然后在对两个posting list归并时,判断这两个字的位置是否紧邻(在posting list中的每个元素,可以用pos数组记录key出现的所有位置),这样就能判断是否存在“极客”的组合了。这就是搜索引擎会使用的短语查询的方案。你会发现,这种方法会相对耗时一些。

    2020-04-12
    2
  • 明翼
    老师对于邮件中敏感词检测适不适合用倒排索引那,用的话可能每个邮件都只要检测一次,不用直接搜索可能又找不到近义词

    作者回复: 就像你说的,邮件只需要检测一次,因此对邮件做倒排索引并不适用。而且倒排索引也解决不了近义词问题。
    邮件敏感词检测一般是这样的思路:
    1.准备一个敏感词字典。
    2.遍历邮件,提取关键词,去敏感词字典中查找,找到了就说明邮件有敏感词。
    这里的核心问题是如何提取关键词和如何在敏感词字典中查询。
    一种方式是用哈希表存敏感词字典,然后用分词工具从邮件中提取关键字,然后去字典中查。
    另一种方式是trie树来实现敏感词字典,然后逐字扫描邮件,用当前字符在trie树中查找。
    不过,这两种方式都无法解决近义词,或者各种刻意替换字符的场景。要想解决这种问题,要么提供近义词字典,要么得使用大量数据进行训练和学习,用机器学习进行打分,将可疑的高分词找出来。
    其实这种近义词处理方案,和搜索引擎解决近义词和查询纠错的过程很像。我在搜索引擎那篇里面会介绍。

    2020-04-01
    1
    2
  • 时隐时现
    每个留言问的到位,作者回复的也耐心,支持

    作者回复: 讨论区其实是一个思维碰撞的地方。毕竟文章篇幅有限,不可能事无巨细都说一遍。
    因此,如果有什么不清楚的,或者想延展讨论的,都可以在这里交流,相信通过这样的交流,能让更多的人更深入地理解这些知识点。

    2020-05-05
    1
  • gogo
    加餐是6号出的,倒排是1号出的,所以我先把1号的补完哈~

    你可以再思考一些细节:如果有一些诗的内容里也有“李白”这个关键词,比如杜甫的诗。
    那么作者“李白”对应的posting list,和内容中的“李白”对应的posting list是否会冲突?可以怎么处理?

    key_李白 = posting list; 内容中的关键字作为倒排索引
    author_李白 = posting list; 作者的名字作为倒排索引
    为避免 关键字 或 名字 或 朝代 相同时,查询出错,通过给索引加 前缀 或 后缀的形式 来区分内容相同类型不同的索引。

    老师说的给posting list分域有点想不明白?

    看到老师提到进阶会有:压缩位图、磁盘存储、分布式存储。期待老师的进阶篇文章!

    ps: 终于补到6号的了,马上可以去享受加餐课了!
    (✪▽✪)

    作者回复: posting list分域,就是一个元素里加上域标识。举个例子,一篇文章有标题,作者,内容三个域,而“李白”这两个字,可能出现在这三个位置。因此,key和posting list可以这么写:
    key =“李白” -> [id1,标题域:0,作者域:1,内容域:0],[id2,标题域:1,作者域:0,内容域:1]

    2020-04-10
    1
  • Chaos
    在A和B两个链表中查找公共元素,也可以看作判断A中的元素在B中是否存在。那么是不是可以使用上一讲中讲到的布隆过滤器,这样就不需要链表是有序的了。

    作者回复: 你这个想法很棒!的确有这样的方案,用位图来代替链表。我在加餐里会介绍。

    2020-04-02
    1
  • 一步
    倒排索引的核心就是关键词的提取,也就是如何合理的对内容进行分词

    作者回复: 分词是第一步,这样就有了倒排索引的key。至于有了倒排索引以后,如何提高检索效率,马上会有加餐为你揭晓

    2020-04-01
    1
  • 李恒达
    老师,我有个疑问,为了实现根据关键词获取数据的功能,是不是需要在正常的表存储的基础上,再额外维护这样一个倒排索引?那这种在关键词不明确的情况下是不是就不会有这个东西了?

    作者回复: 你的思考很好!的确是这样的。你可以回到开头背唐诗的场景。如果只要求给题目背内容,那么是只需要正排索引就好。不需要倒排索引。
    倒排索引是用在需要根据部分信息或者属性去反查出数据主体的场景中。搜索引擎就是典型的应用场景,因为我们只知道我们想找什么关键字,而不知道哪些网页有这些关键字,因此需要倒排索引。数据库也一样,很多时候,我们去数据库中查找,也不是直接找id,而是用where去限定一些属性和字段。因此,你会发现,根据我们关心的属性去寻找主体,这种需求其实很常见,这些场景就可以用倒排索引了。

    2020-04-01
    1
  • 努力努力再努力Xmn
    老师在文章中提到了在构建倒排索引过程中要记录位置信息,我想可不可以同时检索 李 字和 白 字,然后判断二者的位置是否相邻?希望老师解答。

    作者回复: 很好,你关注到了“李白”的分词问题了!
    对于如何确定一个词,常见的做法是使用分词技术,将“李白”作为一个整体处理。这样检索性能也最好。
    而你提的这个方案,是在分词技术无效的情况下,搜索引擎会采用的方案,它会根据位置信息进行短语查询,查出来的“李”和“白”是有序相邻的,优先级最高,位置越远的,优先级越低。通过描述,你也能体会到这样的效率的确没有直接处理一个整体高。因此,分词也是很重要的技术。

    2020-04-01
    1
  • 范闲
    posting list里面可以增加一个author的信息,word,author,pos,id。这样查完以后只需要做个集合检查即可。

    作者回复: 很正确!posting list是可以根据需要放更多复杂的信息的,从而帮助我们解决更多复杂的需求。
    不过也要注意一个度,如果把所有信息都放posting list中,依赖于集合检查,那就变成了遍历查找的效率了。因此,在合适的场景下,有时候也可以为author独立建一个新索引。

    2020-04-01
    1
  • 感觉老师这个问题有点水到渠成的感觉,既然讲了倒排,一个很明显的答案就是把作者也当检索内容一样处理构建索引,对这种类似kv m 查的问题,这应该是最优的一个手段,具体的方案应该考虑如何压缩表示的问题,不明显的答案想不到哈哈哈。

    既然提到索引给大家分享一个观点,索引是什么,从机器学习的角度上看,它其实是检索信息(比如这边的关键字,作者等等)到数据本身位置信息的一个映射关系,pos =f(x)。这就转变成一个机器学习怎么输入x 预测pos 的问题了!(观点来自jeaf dean组的一篇论文)

    最后老师的口音真牛逼!!!哈哈哈😂

    作者回复: 哈哈,用“口音牛逼”作为我的属性,就可以通过这个标签将我检索出来了。😁
    明显的答案水到渠成,那我们来加入一点细节吧。许多诗的内容里都有李白的名字,比如杜甫就写了许多思念李白的诗。那我们用作者“李白”构建倒排索引,和用内容中的“李白”做倒排索引,会不会有冲突?会不会直接把杜甫的诗给召回了?
    ps:机器学习构建索引就是我们现在在做的事情

    2020-04-01
    2
    1
  • Kǎfκã²⁰²⁰
    在关键字为key所在文档为posting list的基础上,再加以作者名为key,posting list为作者诗集的索引

    作者回复: 很好,你提到了“以关键字为key”和“以作者名为key”,我们是可以用两个不同的key来区分作者“李白”和内容中的“李白”。
    这样就能解决“明明想搜的是李白写的诗,结果出来了杜甫写李白的诗”这样的问题

    2020-04-01
    1
  • 李跃爱学习
    作者看做是文档的一个属性,建立属性倒排索引

    作者回复: 很好。对于属性建立倒排索引是正确的。
    你可以再思考一些细节:如果有一些诗的内容里也有“李白”这个关键词,比如杜甫的诗。
    那么作者“李白”对应的posting list,和内容中的“李白”对应的posting list是否会冲突?可以怎么处理?

    2020-04-01
    1
  • 牛牛
    在创建倒排索引的过程中、作者留下一个小问题: 为什么要先排序文档 ?
    我想下边的内容: 在查找两个集合公共元素的过程中, 若是无序链表, 需要遍历两个集合, 时间复杂度O(m*n); 若是有序链表, 可以归并, 时间复杂度降为 O(m+n) 就是答案了 ?

    课程果然是需要反复读的, 上次看的时候、这篇好像没有很明白~~~

    作者回复: 是的。你找到答案了,这个就是为什么要提前排序的原因。一个有序的posting list,会加快求交集和并集的过程。包括在后面第十二讲中,你也会看到我们是要如何保证posting list有序来加快检索的。
    当然,回到这一讲的这个问题,我也补充一点,要保证posting list有序,我们有许多方法。比如说我们也可以先不对文档排序,而是等所有的posting list都生成了以后,再对每一个posting list都单独排序。只是这样排序代价会比在最开始的时候对文档进行排序要更大。因此我们才使用提前对文档排序的方法。

    2020-05-19
  • aoe
    明白了在多个“有序”链表中查找公共元素的算法,感谢老师通俗易懂的配图!

    作者回复: 你指的是加餐二中的多个有序链表的查找算法么?配图的确画了挺久,不过如果对理解内容有帮助就是值得的。

    2020-04-18
    1
  • 小美
    老师有个当前业务上的疑问,我们有很多商品,从两个维度建立倒排索引:把商品名进行的分词 和 给商品打很多不同的标签。
    检索的时候,将用户查询词进行分词去命中商品名分词,用原始查询词去命中不同的标签,这种情况一般如何设计?
    我的理解每一种标签可以单独建立倒排索引,查询后把多个倒排链做归并,那商品名分词如何建索引?

    作者回复: 听你的描述,你们应该是两种查询需求:标签查询和关键词查询。
    对于“标签查询”,就如你所说的,以标签为key建立倒排索引即可。查询时是直接查询标签。(不过你的问题中说的是“用原始查询词去命中标签”,我的理解是你们有一个“原始查询词转为标签”的功能?)
    而“关键词查询”,就是你说的“商品名分词”了。这种情况,其实就和我们今天文章中介绍的场景很像。你把商品名看做是一首唐诗就好了。具体做法是:将商品名分词,以每个词为key建立倒排索引。查询时,对于查询词分词,然后拿着每个词作为key去查询这个倒排索引,这样就能把对应的商品找出来了。

    2020-04-02
  • 无形
    期待老师热腾腾的加餐😃
    2020-04-01
  • 刘凯
    我能想到的方案是在数据库中建两张表,一张保存唯一索引的分词表,一张保存对应分词的文章id,这样是不是弱爆了。这样变成关系型数据库的查找了,而且外键表行数会暴增。脱离了老师说的hash. 老师你说的hash加链表我也看懂了,但持久话如何实现呢

    作者回复: 其实你已经渐渐掌握了核心原理了!如果你能用数据库那就简单了,因为数据库中的全文索引功能,就是倒排索引的具体实现!
    你只需要建立一张表,一列是文章id,一列是文章内容,然后指定对文章内容这一列建立全文索引,那接下来就可以用sql语句直接检索了。

    2020-04-01
    1
收起评论
22
返回
顶部