申请专栏作者
您的当前位置:主页 > yabo体育平台注册页 > 正文

Lucene 倒排索引原理探秘 (1)

来源: 时间:2019-07-31
请点击下面的广告后浏览!

在全文检索领域, Lucene 可谓是独领风骚数十年。倒排索引构成全文检索的根基,只有深入理解了倒排索引的实现原理,才能算是入门了全文检索领域。本文将对 Lucene 的倒排索引的实现原理和技术细节进行详细的剖析,这些内容适用于 Lucene 5.x 至 7.x 系列版本。文章整体内容组织如下:

可思yabo88滚球

理论

在学术上,倒排索引结构非常简明易懂,如下:

可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

也许你已接触过倒排索引,下面这张图你或许已经看过很多次了。本文将从你熟悉的部分开始,一步步深入去挖掘这张图的一个个细节。这里先介绍两个重要概念:

可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

_1. 索引,索引词表。倒排索引并不需要扫描整个文档集,而是对文档进行预处理,识别出文档集中每个词。?_

本文来自可思yabo88滚球,转载请联系本站及注明出处

2. 倒排表,倒排表中的每一个条目也可以包含词在文档中的位置信息(如词位置、句子、段落),这样的结构有利于实现邻近搜索。词频和权重信息,用于文档的相关性计算。

本文来自可思yabo88滚球,转载请联系本站及注明出处

倒排索引由两部分组成,所有独立的词列表称为索引,词对应的一系列表统称为倒排表。 —— 来自《信息检索》

可思yabo88滚球-人工智能资讯平台

可思yabo88滚球

如上图所示,整个倒排索引分两部分,左边是 Term Dictionary(索引表,可简称为 Dictionary),是由一系列的 Terms 组成的;右边为 Postings List(倒排表),由所有的 Term 对应的 Postings 组成。 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

实际上 Lucene 所用的信息信息检索方面的术语基本跟 Information Retrieval(《信息检索》原版)保持一致。比如 Term、Dictionary、Postings 等。 内容来自可思yabo88滚球

首先,有必要解释一下,每个 Segment 中的每个字段 (Field) 都有这么一个独立的结构。其次,它是不可改写的,即不能添加或更改。至于为何选择不可改写的设计,简单说有两个方面:一是更新对磁盘来说不够友好;另一方面是写性能的影响,可能会引发各种并发问题。

内容来自可思yabo88滚球

我们可以用一个 HashMap 来简单描述这个结构:Map>,这个 Map 的 Key 的即是Term,那它的 Value 即是Postings。所以它的 Key 的集合即是Dictionary了,这与上图的描述太贴切了。由于 HashMap 的 Key 查找还是用了 HashTable,所以它还解决 Dictionary 的快速查找的问题,一切显得太美好了。这可以说是一个hello world版的倒排索引实现了。 可思yabo88滚球

Lucene 的实现

全文搜索引擎通常是需要存储大量的文本,Postings 可能会占据大量的存储空间,同样 Dictionary 也可能是非常大的,因此上面说的基于 HashMap 的实现方式几乎是不可行的。在海量yabo88滚球背景下,倒排索引的实现都极其复杂,因为它直接关系到存储成本以及搜索性能。为此,Lucene 引入了多种巧妙的yabo88滚球结构和算法。 可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

Lucene 索引文件构成

我们知道 Lucene 将索引文件拆分为了多个文件,这里我们仅讨论倒排索引部分。 可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

Lucene 把用于存储 Term 的索引文件叫 Terms Index,它的后缀是.tip;把 Postings 信息分别存储在.doc.pay.pox,分别记录 Postings 的 DocId 信息和 Term 的词频、Payload 信息、pox 是记录位置信息。Terms Dictionary 的文件后缀称为.tim,它是 Term 与 Postings 的关系纽带,存储了 Term 和其对应的 Postings 文件指针。

内容来自可思yabo88滚球

总体来说,通过 Terms Index(.tip) 能够快速地在 Terms Dictionary(.tim) 中找到你的想要的 Term,以及它对应的 Postings 文件指针与 Term 在 Segment 作用域上的统计信息。

可思yabo88滚球

postings: 实际上 Postings 包含的东西并不仅仅是 DocIDs(我们通常把这一个有序文档编号系列叫 DocIDs),它还包括文档编号、以及词频、Term 在文档中的位置信息、还有 Payload yabo88滚球。

可思yabo88滚球-人工智能资讯平台

所以关于倒排索引至少涉及 5 类文件,本文不会全面展开。

内容来自可思yabo88滚球

什么是 Terms Index?

下面引用了一张来自网络上的图,非常直观:

可思yabo88滚球

内容来自可思yabo88滚球

Terms Index 即为上图中.tip 部分,它实际上是由一个或多个FST组成的,Segment 上每个字段都有自己的一个 FST(FSTIndex)记录在.tip上,所以图中 FSTIndex 的个数即是 Segment 拥有字段的个数。另外图中为了方便我们理解把 FST 画成 Trie 结构,然后其叶子节点又指向了 tim 的 Block 的,这实际上是用了一种叫 Burst-Trie 的yabo88滚球结构。 可思yabo88滚球-www.sykv.cn,sykv.com

Burst-Trie

.tip看起来是像一棵 Trie,所以整张图表现出来就是论文上的 Burst-Trie 结构了。上面一棵 Trie,Trie 的叶子节点是 Container(即是 Lucene 中的 Block)。下图就是 Paper 上描述的 Burst-Trie 的结构:

可思yabo88滚球-人工智能资讯平台

来自 Burst-Trie 论文上的一张图 本文来自可思yabo88滚球,转载请联系本站及注明出处

Burst-Trie,关于 Burst-Trie,网上有很多专业资料,这里只做简单介绍。Burst-Trie 可以认为是 Trie 的一种变种,它主要是将后缀进行了压缩,降低了 Trie 的高度,从而获取更好查询性能。

可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

Lucene 工程上的实现方式

可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

Burst-Trie 在 Lucene 是如何应用的? 可思yabo88滚球-人工智能资讯平台

前面提到了 Lucene 是采用Burst-Trie的思想,但在实现上存在一定的出入,Lucene 的 Burst-Trie 被拆成两部分。如果一定把它们对应起来的话,我认为 Burst-Trie 的 AccessTree 的实现是 FST,存在.tip 文件中;Container 的实现是 Block,存在.tim 文件里。Burst-Trie 的 Container 内部是开放性结构,可能是 Binary-Tree,可以也 List。Lucene 的 block 是数组,准确的说,就是把一系列的 Block 系列化写到文件上,这里好像并没有做特殊的处理。 可思yabo88滚球

?

FST

在 Lucene,Terms Dictionary被存储在.tim 文件上。当一个 Segment 的文档数量越来越多的时候 Dictionary 的词汇也会越来越多,那查询效率必然也会逐渐变低。因此需要一个很好的yabo88滚球结构为 Dictionary 建构一个索引,将 Dictionary 的索引进一步压缩,这就是后来的 Terms Index(.tii)。这是在早期的版本中使用的,到 Lucene 4.0 之后做一次重构和升级,同时改名为.tip。

可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

可思yabo88滚球-人工智能资讯平台

FST:Finite-State-Transducer,结构上是。我们知道把一堆字符串放一堆,把它们的同共前缀进行压缩就会变成 Burst-Trie。如果把后缀变成一个一个节点,那么它就是 Trie 结构了。如果将后缀也进行压缩的话,那你就能发现他更变成一张图结构了。 那么我们易知 FST 是压缩字典树后缀的图结构,她拥有 Trie 高效搜索能力,同时还非常小。这样的话我们的搜索时,能把整个 FST 加载到内存。

可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

实际上,FST 的结构非常复杂,我们可以简单的将其理解为一个高效的 K-V 结构,而且空间占用率更高。这里想简单强调一下:Lucene 到底在 FST 里存了什么yabo88滚球??如果你已经了解 FST 在 Lucene 中充当的角色和作用的话,我想你可能会误认为 FST 中存了 Dictionary 中所有的 Terms yabo88滚球,这样可以通过 FST 是找到具体的 Term 的位置,或者通过 FST 可以切实获知一个 Term 是否存在。 内容来自可思yabo88滚球

然而,事实并非如此。?FST 即不能知道某个 Term 在 Dictionary(.tim) 文件上具体的位置,也不能仅通过 FST 就能确切的知道 Term 是否真实存在。它只能告诉你,查询的 Term 可能在这些 Blocks 上,到底存不存在 FST 并不能给出确切的答案,因为 FST 是通过 Dictionary 的每个 Block 的前缀构成,所以通过 FST 只可以直接找到这个 Block 在.tim 文件上具体的 File Pointer,并无法直接找到 Terms。关于 FST 的详细细节,后面将以一篇独立的文章来讲解,这里暂时不展开过多细节。 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

下面会详细的介绍 Dictionary 的文件结构,这里先提一下。每个 Block 都有前缀的,Block 的每个 Term 实际不记录共同前缀的。只有通过 Block 的共同的前缀,这是整个 Block 的每个 Term 共同的,所以每个 Term 仅需要记录后缀可以通过计算得到,这可以减少在 Block 内查找 Term 时的字符串比较的长度。 内容来自可思yabo88滚球

简单理解的话,你可以把它当成一个高级的 BloomFilter,我们 BloomFilter 是有一定的错误率的;同时 BloomFilter 是通过 HashCode 实现的,只能用它来测试是否存在,并无法快速定位。在 FST 中,并无错误率且能快速定位。但是 BloomFilter 有更高的性能。

内容来自可思yabo88滚球

说了这么一大半天,Terms Index 到底带来哪些实质性的功能呢??Terms Index 是 Dictionary 的索引,它采用 了 FST 结构。上面已经提及了,FST 提供两个基本功能分别是:

可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

1. 快速试错,即是在 FST 上找不到可以直接跳出不需要遍历整个 Dictionary。类似于 BloomFilter 的作用。 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

2. 快速定位 Block 的位置,通过 FST 是可以直接计算出 Block 的在文件中位置(offset,FP)。

可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

上面已经介绍了 FST 的一种功能,此外,FST 还有别的功能,因为 FST 也是一个 Automation(自动状态机)。这是正则表达式的一种实现方式,所以 FST 能提供正则表达式的能力。通过 FST 能够极大的提高近似查询的性能,包括通配符查询、SpanQuery、PrefixQuery 等,甚至包括近期社区正在做的基于正则表达式的查询。

可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

?

什么是 Terms Dictionary?

前面我们已经介绍了Terms Dictionary的索引,Terms Index。已经频频提到的 Terms Dictionary 到底是什么东东?Terms Dictionary 是 Segment 的字典,索引表。它能够让你知道你的查询的这个 Term 的统计信息,如tf-idfdf(doc_freq)Total Term Frequence(Term 在整个 Segment 出现频率);还能让你知道 Postings 的元yabo88滚球,这里是指 Term 的 docids、tf 以及 offset 等信息在 Postings 各个文件的文件指针 FP。

可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

Block 并不记录这个 Block 的起始和结束的范围,所以当 FST 最终指向多个 Block 时,就会退化为线性搜索。那什么时候会出现 FST 最终指向多个 Block 呢?最简单的一种情况是,超过 48 个的 Term,且出现首字母相同的 term 的个数不超过 25 个。这种情况下由于没有每个 Block 都没有共同前缀,所以构建出来的 FST 只有一个结束节点记录每个 Block 的文件寻址的偏移增量。

可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

Lucene 规定,每个 Block 的大小在 25-48 范围内 可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

说这么多,还是觉得太抽象了,我们来看一下.tim文件结构示意图:

可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

可思yabo88滚球-www.sykv.cn,sykv.com

主要是大两部分信息,1. Block 信息,包含所有 Term 的详情;2. Field 的自有属性和统计信息。接下来我们将展开来介绍这两部分内容。

可思yabo88滚球-www.sykv.cn,sykv.com

?

Block 信息 - NodeBlock

在整个.tim 文件上,我觉得比较复杂且值得拎出来讲的只有 NodeBlock。那么,Block 又是什么东东?它是如何被构建的?这部分代码,还是比较晦涩难懂得,我每次读时也都会产生一些新的疑问。 可思yabo88滚球-www.sykv.cn,sykv.com

我们前面所有说的 Block 即是 NodeBlock 的一个 Entry。 由上图可以知道,Block 中有两种 OuterNode 和 InnerNode。这里我想引用代码上两个类名来辅助我们接下来的剖析:PendingTerm/PendingBlock,我们暂且把它们叫作待写的Term子Block的指针吧。 可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

NodeBlock 从构建逻辑上来讲是它是树型结构,所以它由叶子节点和非叶子节点两种节点组成。叶子节点就叫 OutterNode,非叶子节点就叫 InnerNode。一个 Block 可能含有一堆的 Term(PendingTerm)和 PendingBlock(当它是非叶子节点时),实际上 PendingBlock 也是不可能出现在叶子节点上的。如果是 PendingBlock,那么这个 Entry 只记录两个信息:后缀 (这个 Block 的共同后缀) 以及子 Block 的文件指针,此时就不必再记上所说的统计信息和 postings 信息了。

可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

如图所示,一个 Block 记录的信息非常多,首先是 Block 的类型和 Entry 的条数等元yabo88滚球信息,而后是该 Block 拥有的所有 Entry。

可思yabo88滚球

本文来自可思yabo88滚球,转载请联系本站及注明出处

这里每个 Entry 含有后缀、统计信息 (对应为前面据说的权重,它含有 ttf 和 df)、Postings 的位置信息 (这就是反复提及 postings 相关的文件指针,postings 是拆分多文件存储的)。 关于 Postings 更多细节,放到下个章节来讨论。

可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

?

Field 信息 - FieldMetadata

相对来说FieldMetadata组织结构就简单多了,纯粹的线性写入即可。但 Field 信息记录的内容还是挺多的,包括字段本身的属性,如字段编号、Terms 的个数、最大和最小的 Terms;此外还记录了 Segment 级别的一些统计信息,包括 tdf、拥有该字段的文档总数(如果文档没有该字段,或者该字段为空就不计了)。 可思yabo88滚球-人工智能资讯平台

1. RootCode 实际上指向该字段第一个 Block 的文件指针。 可思yabo88滚球-www.sykv.cn,sykv.com

2. LongsSize 这个名字有点隐晦,它是说该字段的字段存储哪些 Postings 信息。因为我们是可以指定 Postings 存储或者不存储诸如位置信息和 Payload 信息的,存与不存将被表现在这里了。

内容来自可思yabo88滚球

从搜索流程来看,Lucene 先读到 FieldMetadata 的信息,然后判断 Query 上 Terms 是否落在这里字段的 MinTerm 和 MaxTerm 之间。如果不在的话,完全不需要去读 NodeBlock 的。MinTerm 和 MaxTerm 可以有效的避免读取不必要的.tip 文件。

本文来自可思yabo88滚球,转载请联系本站及注明出处

结束语

到这里,关于倒排索引结构中第一部分内容已经介绍完了,限于篇幅的原因,还有更多有趣的小细节没有呈现出来。简单总结一下:我们先从 _Information Retrieve_ 开始了解学术上倒排索引结构,接着我们又对 Luecne 的实现做了深入剖析。Lucene 对索引词表也做了索引(叫 Terms Index,文件后缀是.tip),索引词表的索引采用 Finite-State Transducer 这种yabo88滚球结构。由于这种结构占用空间极小,所以它完成可以被加载到内存加速 Terms Dictionary 的查找过程。而后又介绍了 Terms Dictionary,Terms Dictionary 以 Terms Index 共同构成与 Burst-Trie 类似的yabo88滚球结构,Terms Dictionary 含两部分信息:1. NodeBlock 记录 Dictionary 的所有 Terms;2. FieldMetadata 存储了 FieldInfos 信息和 Segment 的统计信息。 内容来自可思yabo88滚球

关于倒排索引还有 Postings List,这部分内容将在下篇文章中介绍。

本文来自可思yabo88滚球,转载请联系本站及注明出处

网友评论:

发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片 匿名?

Copyright?2005-2019 Sykv.com 可思yabo88滚球 版权所有 ?? 网站地图?? 联系我们?? 京ICP备14056871号

人工智能资讯?? 人工智能资讯?? 人工智能资讯?? 人工智能资讯

?扫码入群
咨询反馈
扫码关注

微信公众号

返回顶部
关闭