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

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

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

上篇文章 Lucene 倒排索引原理探秘 (1) 详细介绍了 Lucene 索引表的实现,内容涉及关于 Terms Index 以及 Term Dictionary 的剖析。

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

此文将继续剖析 Lucene 倒排索引实现的另一部分核心内容: 倒排表(Postings)。Lucene 的官方文档关于该部分内容的描述非常丰富,所以学习起来也相对轻松。 可思yabo88滚球

Postings 编码

开始之前先介解 Lucene 在 Postings 采用了两个关键的编码格式,PackedBlock 和 VIntBlock。PackedBlock 是在Lucene 4.0引入,带来向量化优化。 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

VIntBlock

VIntBlock 是能够存储复合yabo88滚球类型的yabo88滚球结构,主要通过变长整型(Variable Integer)编码达到压缩的目的。此外 VIntBlock 还能够存储byte[],比如.pay 用 VIntBlock 存储了 payloads yabo88滚球等。 可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

值得一提的是,VIntBlock 可以存储变长yabo88滚球结构,如.doc 用它存储 DocID 和 TermFreq 时,由于在特定条件下 (TermFreq=1),Lucene 会省略 TermFreq 以提高空间占用率。Lucene 用一个 VInt 来表示 DocID,VInt 则用每个 Byte 左边第一个 Bit 来表示是否需要读取顺续到下个 Byte。也就是说一个 VInt 有效位是28bit,这就说明 VInt 头部是有特殊含义的,因此 Lucene 只能在 VInt 最右边的一个 bit 下功夫。让 VInt 的右边第一 Bit 来表示是否有下个yabo88滚球。具体用法会在介绍.doc 文件格式时介绍。 可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

PackedBlock

PackedBlock 只能存储单一整数 (Integer/Long) 数组结构。这里主要介绍 PackedInts:它将一个 int[]打包成一个 Block。PackedBlock 只能存储固定长度的数组(Lucene 规定其长度为 128 个元素),它的压缩方式是将每个元素截断为一个预算的长度(length,单位是 bit),以达到压缩的目的。所以当长度 length 不是 8 的倍数时,会出现一个 byte 被多个元素占用的情形。

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

PackedBlock 需要把整个 int[] 的所有条目指定长度编码,所以 PackedBlock 只能选择 int[] 最大的数来计算长度,否则会让大数失真。反过来,PackedBlock 都选择 64 位,则会浪费空间,不能达到压缩的目的。

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

内容来自可思yabo88滚球

Lucene 预先编译了 64 个 PackedFormat 编码器和解码器,即针对 Long 以内的每种长度都yabo88滚球都有自己的解码和编码器,以提高编解码的性能。 可思yabo88滚球-人工智能资讯平台

PackedPosDeltaBlock、PackedDocDeltaBlock 以及 PackedFreqBlock 都采用了 PackedInts 结构,它能存储的信息实际上是很有限的,只能存储 Int 的数组。所以在 PackedPosDeltaBlock 的时候,只能存储 position 信息,在 VIntBlock 则会存储更多必要信息,减少搜索时的 IO 操作。 可思yabo88滚球-www.sykv.cn,sykv.com

这也是为什么需要将 DocId 和 TermFreq 拆分成 PackedDocDeltaBlock 和 PackedFreqBlock 两个 Block 存储的原因了。

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

定长是指 PackedBlock 限定了一个 Block 仅允许存储长度 128 的整型数组,而不是限定 Block 用多少个 Bytes 来存储编码后的结果。另外 Block 存储占用的大小,是按数组中最大那个数的有效 bits 长度来计算整个 Block 需要占用多大的 Bytes 数组的。也就是 Block 的每个yabo88滚球的长度都是一样,都按最长 bits 来计算。

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

比如:(我们定义一个函数,bit(num) 用来计算 num 占用多少个 bits)

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

1. 数组中最大的是 1,那么 PackedBlock 的长度仅是 16Bytes。bit(1) * 128 / 8 = 16

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

2. 数组中最大的是 128,PackedBlock 长度则是 144 个 Bytes。bit(128) * 128 / 8 = 144

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

3. 数组中最大的是 520,PackedBlock 则需要 160Bytes。bit(520) * 128 / 8 = 160 可思yabo88滚球-AI,智能驾驶,人脸识别,区块链,大yabo88滚球

简单总结一下,PackedBlock 相当于实现了向量化优化,Lucene 通常会将整个 PackedBlock 加载到内存,既可以减少 IO 操作数,又能提高解码的性能。相对而言 VIntBlock 则能够更丰富yabo88滚球类型,比较适合存储少量yabo88滚球。

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

Postings 文件格式说明

进入正题,我们知道整个 Postings 被拆成三个文件存储,实际上它们之间也是相对独立的。基本所有的查询都会用.doc,且一般的 Query 仅需要用到.doc 文件就足够了;近似查询则需要用.pox;.pay 则是用于 Payloads 搜索(关于这个之前写一篇博客《Solr 迟到的 Payloads》,介绍了 Payloads 用法和场景 )。 内容来自可思yabo88滚球

?

Frequencies And Skip Data(.doc 文件)

在 Lucene 倒排索引中,只有.doc 是 Postings 必要文件,即它是不能被省略的。除此之外的两个文件通过配置都是可以省略的。那么.doc 到底存储了哪些关键信息呢?直接上图: 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

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

这里画得不够清晰,每个 Term 都有成对的 TermFreqs 和 SkipData 的。换言之,SkipData 是为 TermFreqs 构建的跳表结构,所以它们是成对出现的。

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

?
TermFreqs — Frequencies

TermFreqs 存储了 Postings 最核心的内容,DocID 和 TermFreqs,分别表示文档号和对应的词频,它们是一一对应的,Term 出现在文档上,就会有 Term 在文档中出现次数(TermFreqs)。 可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

Lucene 早期的版本还没有 PackedBlock 结构,所以 DocID 与 TermFreq 是以一个二元组的方式存储的。这个结构简单,有助于理解,但却并不准确。既然是想深入剖析,还是有必要还原真相的。 可思yabo88滚球-AI,人工智能,深度学习,机器学习,神经网络

TermFreqs 采用的是混合存储 ,由 Packed Blocks 和 VInt Blocks 两种结构组成。由于 PackedBlock 是定长的,当前 Lucene 默认是 128 个Integers。所以在不满 128 个值的时候,Lucene 采用 VIntBlocks 结构存储。需要注意的是当用 Packed Blocks 结构时,DocID 和 TermFreq 是分开存储的,各自将 128 个值写入到一个 Block。

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

当用 VIntBlocks 结构时,还是沿用旧版本的存储方式,即上面描述的二元组的方式存储。所以说,将 DocID 和 TermFreq 当成一条yabo88滚球的说法是不完全准确的。 可思yabo88滚球

在 Lucene4.0 之前的版本,还没有引入 PackedBlock 时,DocID 和 TermFreq 确定完全是成对出现,当时只有 VIntBlock 一种结构。

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

Lucene 尽可能优先采用 PackedBlocks,剩余部分(不足 128 部分)则用 VIntBlocks 存储。引入 PackedBlock 之后,PackedDocDeltaBlock 跟 PackedFreqBlock 是成对的,所以它的写出来的示意图应该是如下: 可思yabo88滚球-人工智能资讯平台

内容来自可思yabo88滚球

每个 PackedBlock 由一个 PackedDocDeltaBlock 和一个 PackedFreqBlock 构成,它们都采用 PackedInts 格式。

可思yabo88滚球

例如,在同一个 Segment 里,某一个 Term A 在 259 个文档同一个字段出现,那么 Term A 就需要把这 259 个文档的文档编号和 Term A 在每个文档出现的频率一同记下来存储在.doc。此时,Lucene 需要用到 2 个 PackedBlocks 和 3 个 VIntBlocks 来存储它们。

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

VIntBlock 结构相对复杂一些,它以一种巧妙的方式存储复杂的多元组结构。在.doc 文件中,用 VIntBlock 存储 DocID 和 TermFreqs 二元组。后面将介绍的 Positions 则用 VIntBlock 存储了 Postition、Payload 和 Offset 多元组, byte[] 和 VInt 多种yabo88滚球类型。 内容来自可思yabo88滚球

这里每一个 PackedBlock 结构都包含了一个PackedDocDeltaBlock和一个PackedFreqBlock,如果没有省略 Frequencies(TermFreq);如果用户配置了不存储词频(TermFreq),此时一个 PackedBlock 仅包含一个 PackedDocDeltaBlock。PackedFreqBlock(TermFreq)的存储方式跟 PackedDocDeltaBlock(DocID)完全一致,包括后面要讲的 pos/pay 也都一样的,都使用 Packed Block 这种编码方式。

可思yabo88滚球

在 VIntBlock 上如何存储 DocDelta 和 TermFreq? 如果设置了不存储 TermFreq 时,Lucene 将所有 DocDelta 以 Variable Integer 的编码方式直接写到文件里。当设置为存储 TermFreq 信息时,实际上,TermFreq 信息会被按需存储。Lucene 做了一个小优化,即当 TermFreq=1 时,TermFreq 将不被存储。那么原本 DocDelta(DocID 的增量)后面紧跟一个 Frequencies 的情况变得不再确定,因为压根无法知道 DocDelta 后面还有没有 TermFreq 信息。那应该如何识别 TermFreq 信息是否存在?Lucene 先把数值向左移动一位,然后用最右的一个 Bit 的标记是否存储 TermFreq。最后右边的一个bit1表示没有存储,0作为有存储 TermFreq。实际上这是 Lucene 的惯用手段。

内容来自可思yabo88滚球

左移一位,实际上等同于X2,当最后一个 bit 是 0,此时是一定是偶数,表示后面还存 储了 TermFreq;左移一位再 +1,相当于偶数 +1,那就是奇数,此时最后一个 bit 是 1,表示 TermFreq=1,所以后面没有存储 TermFreq。

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

DocFreq=1 时,Lucene 做一个叫 Singletion(仅出现在一个文档中)的优化,此时就没有 TermFreq 和 SkipData。因为 TermFreq 等同于 TotalTermFreq(上篇文章介绍过,存储在.tim 的 FieldMetadata 上)。

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

Multi-level SkipList — SkipData

SkipData 是.doc 文件核心部件之一,Lucene 采用的是多层次跳表结构,首先我们先预热一下 SkipList 的逻辑结构图,最后剖析 Lucene 存储 SkipList 的物理结构图。下图 (源自网图) 很好的描述了 SkipList 的结构: 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

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

跳表的原理非常简单,跳表其实就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置,然后再跳到次高级索引继续查找,直到跳到最底层为止,这时候以及十分接近要查找的元素的位置了 (如果查找元素存在的话)。由于根据索引可以一次跳过多个元素,所以跳查找的查找速度也就变快了。 ——— 百度百科

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

将搜索时耗时转嫁给索引时,这就是 Lucene 索引的“空间换时间”的基本思想。为此 Lucene 为 Postings 构建 SkipList ,并把按层级将它系列化存储。第一个 SkipLevel 是最高,拥有最少的索引数。

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

Lucene 在索引时构建了 SkipList,在 Segment 中每个 Term 都有自己唯一的 Postings,每个 Postings 都有需要构建一个 SkipList,这三者是一一对应的。所以画出来结构图如下: 可思yabo88滚球-人工智能资讯平台

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

除了第 0 层之外所有 SkipLevel 的每个跳表yabo88滚球块(SkipDatum)会存储了指向下一个 SkipLevel 的指针。图中 SkipChildLevelFPg 带?的原因是在Level 0时,SkipDatum 没有下一级可以记录。如果 Postings 有存储 positions、payloads 和 offsets 的话,在跳表yabo88滚球块中也会记录它们的 Block 所有文件指针。

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

通过 SkipList 可以找到 DocID 和 TermFreq 之外,还能找到 Positions、Payloads 和 Offsets 这三部分信息。因此,在搜索时通过 SkipList 可以快速定位 Postings 的所有相关信息。

内容来自可思yabo88滚球

关于 Lucene 构建 SkipList 的几点细节 (Lucene 规定 SkipList 的层级不超过 10 层):

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

1. 第 0 层,SkipList 为每个 Block 增加索引,所以 VIntBlock 不在 SkipList 上。

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

2. 第 9 层,SkipList 的第一个节点是在第 89?(227)Block。(这个数确实有点大) 内容来自可思yabo88滚球

3. 第 n 层,SkipList 的第 m 个节点的位置是第8^n * m个 Block。

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

跳表的第一层是最密的,越高层越稀疏。按层级从低到高依次系列化为写入.doc 的 SkipData 部分。换言之,SkipDatum 个数越多,SkipLevelLength 则会越大。

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

SkipLevelLength 说明当前层次 Skip 系列化之后的长度,SkipLevel 是包含该层的所有节点的yabo88滚球 SkipDatum。SkipDatum 包含四部分信息,doc_id 和 term_freq、positions、payloads、以及下一层开始的位置(是第 N 层指向第 N-1 层的前一个索引)。

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

SkipList 主要是搜索时的优化,主要是减少集合间取交集时需要比较的次数,比如在 Query 被分词器分成多个关键词时,搜索结果需要同时满足这些关键词的,此时需要将每个 Term 对应的 DocId 集合进行析取操作,通过跳表能够有效有减少比较的次数。 内容来自可思yabo88滚球

?

Postitions(.pos 文件)

.pos 文件存储所有 Terms 出现文档中的位置信息。为了更好的搜索性能,Lucene 还在 VIntBlock 上存储了部分 payloads 和 offsets 信息。实际上只有 VIntBlock 才有能力来存储复杂的yabo88滚球结构,PackedBlock 是不具备这样的能力的。具体请参考下面的示意图:

可思yabo88滚球

可思yabo88滚球

Lucene 把同一个 Term 的所有 position 信息存储在同一个 TermPositions 上,并没有逻辑或者物理上的划分。将在一个文档里出现的所有位置信息,按出现的先后顺序依次写入。 关键在于,position 与 TermFreq 并不是在一维度上,TermFreq 的数值就是 position 的个数。也就是说,通过.pos 文件无法知道每个 position 的具体含义,PostingsReader 通过.doc 文件的 DocID 和 TermFreq 信息才能算出 Postition 的是在哪个文档上的哪个位置。 本文来自可思yabo88滚球,转载请联系本站及注明出处

Payloads and Offsets(.pay 文件)

Payloads,可以理解为 Term 的附加信息,它是与 Term 成对出现的,类似于 Map。在用法上也是如此,Payloads 的信息需要用 byte 数组存储,所以在 TermPayloads 并不能用 PackedBlock 结构来存储。TermOffsets 由 2 个 int 来表示 Offset 的开始位置和长度,可以将它们拆成两个等 size 的 int[],因此可以用 PackedBlock 存储。如下图: 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

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

?

总结

开篇先学习了 Lucene 用于存储 Postings 的两种结构,PackedBlock 和 VIntBlock。PackedBlock 是 Lucene4.0 引用的,它的核心就是一个 int[],为 Postings 提供向量化优化,VIntBlock 也是一种很巧妙且优雅的结构,能存储复杂的类型。

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

而后,在介绍.doc 文件格式的同时,又对上面的两大结构深入剖析,了解这两个结构是理解 postings 的基础。接下来剖析了.doc 文件上采用的 SkipList yabo88滚球结构,主要是搜索时集合间AND操作上的一个优化。至于 postings 中其它两个文件格式,仅做了简单介绍。 可思yabo88滚球-yabo88滚球挖掘,智慧医疗,机器视觉,机器人

Lucene 倒排索引部分内容到这里全部结束,包含很多优雅的设计和巧妙的结构,其中蕴含的 Lucene 设计之美,值得我们反复研读。

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

网友评论:

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

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

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

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

微信公众号

返回顶部
关闭