百度网站建设的一般要素,电商运营培训课程网站,域名备案网站建设书模板,网络营销是什么时候提出的当我们真正进入到Lucene源代码之中的时候#xff0c;我们会发现:
Lucene的索引过程#xff0c;就是按照全文检索的基本过程#xff0c;将倒排表写成此文件格式的过程。Lucene的搜索过程#xff0c;就是按照此文件格式将索引进去的信息读出来#xff0c;然后计算每篇文档打…当我们真正进入到Lucene源代码之中的时候我们会发现:
Lucene的索引过程就是按照全文检索的基本过程将倒排表写成此文件格式的过程。Lucene的搜索过程就是按照此文件格式将索引进去的信息读出来然后计算每篇文档打分(score)的过程。
一、基本概念
下图就是Lucene生成的索引的一个实例 Lucene的索引结构是有层次结构的主要分以下几个层次
索引(Index) 在Lucene中一个索引是放在一个文件夹中的。如上图同一文件夹中的所有的文件构成一个Lucene索引。段(Segment) 一个索引可以包含多个段段与段之间是独立的添加新文档可以生成新的段不同的段可以合并。如上图具有相同前缀文件的属同一个段图中共两个段 _0 和 _1。segments.gen和segments_5是段的元数据文件也即它们保存了段的属性信息。文档(Document) 文档是我们建索引的基本单位不同的文档是保存在不同的段中的一个段可以包含多篇文档。新添加的文档是单独保存在一个新生成的段中随着段的合并不同的文档合并到同一个段中。域(Field) 一篇文档包含不同类型的信息可以分开索引比如标题时间正文作者等都可以保存在不同的域里。不同域的索引方式可以不同在真正解析域的存储的时候我们会详细解读。词(Term) 词是索引的最小单位是经过词法分析和语言处理后的字符串。 Lucene的索引结构中即保存了正向信息也保存了反向信息。
所谓正向信息
按层次保存了从索引一直到词的包含关系索引(Index) – 段(segment) – 文档(Document) – 域(Field) – 词(Term)也即此索引包含了那些段每个段包含了那些文档每个文档包含了那些域每个域包含了那些词。既然是层次结构则每个层次都保存了本层次的信息以及下一层次的元信息也即属性信息比如一本介绍中国地理的书应该首先介绍中国地理的概况以及中国包含多少个省每个省介绍本省的基本概况及包含多少个市每个市介绍本市的基本概况及包含多少个县每个县具体介绍每个县的具体情况。如上图包含正向信息的文件有 segments_N保存了此索引包含多少个段每个段包含多少篇文档。XXX.fnm保存了此段包含了多少个域每个域的名称及索引方式。XXX.fdxXXX.fdt保存了此段包含的所有文档每篇文档包含了多少域每个域保存了那些信息。XXX.tvxXXX.tvdXXX.tvf保存了此段包含多少文档每篇文档包含了多少域每个域包含了多少词每个词的字符串位置等信息。
所谓反向信息
保存了词典到倒排表的映射词(Term) – 文档(Document)如上图包含反向信息的文件有 XXX.tisXXX.tii保存了词典(Term Dictionary)也即此段包含的所有的词按字典顺序的排序。XXX.frq保存了倒排表也即包含每个词的文档ID列表。XXX.prx保存了倒排表中每个词在包含此词的文档中的位置。
在了解Lucene索引的详细结构之前先看看Lucene索引中的基本数据类型。 二、基本类型
Lucene索引文件中用一下基本类型来保存信息
Byte是最基本的类型长8位(bit)。UInt32由4个Byte组成。UInt64由8个Byte组成。VInt 变长的整数类型它可能包含多个Byte对于每个Byte的8位其中后7位表示数值最高1位表示是否还有另一个Byte0表示没有1表示有。越前面的Byte表示数值的低位越后面的Byte表示数值的高位。例如130化为二进制为 1000, 0010总共需要8位一个Byte表示不了因而需要两个Byte来表示第一个Byte表示后7位并且在最高位置1来表示后面还有一个Byte所以为(1) 0000010第二个Byte表示第8位并且最高位置0来表示后面没有其他的Byte了所以为(0) 0000001。 Chars是UTF-8编码的一系列Byte。String一个字符串首先是一个VInt来表示此字符串包含的字符的个数接着便是UTF-8编码的字符序列Chars。 三、基本规则
Lucene为了使的信息的存储占用的空间更小访问速度更快采取了一些特殊的技巧然而在看Lucene文件格式的时候这些技巧却容易使我们感到困惑所以有必要把这些特殊的技巧规则提取出来介绍一下。
在下不才胡乱给这些规则起了一些名字是为了方便后面应用这些规则的时候能够简单不妥之处请大家谅解。
1. 前缀后缀规则(PrefixSuffix)
Lucene在反向索引中要保存词典(Term Dictionary)的信息所有的词(Term)在词典中是按照字典顺序进行排列的然而词典中包含了文档中的几乎所有的词并且有的词还是非常的长的这样索引文件会非常的大所谓前缀后缀规则即当某个词和前一个词有共同的前缀的时候后面的词仅仅保存前缀在词中的偏移(offset)以及除前缀以外的字符串(称为后缀)。 比如要存储如下词:termtermagancytermagantterminal
如果按照正常方式来存储需要的空间如下
[VInt 4] [t][e][r][m][VInt 10][t][e][r][m][a][g][a][n][c][y][VInt 9][t][e][r][m][a][g][a][n][t][VInt 8][t][e][r][m][i][n][a][l]
共需要35个Byte.
如果应用前缀后缀规则需要的空间如下
[VInt 4] [t][e][r][m][VInt 4 (offset)][VInt 6][a][g][a][n][c][y][VInt 8 (offset)][VInt 1][t][VInt 4(offset)][VInt 4][i][n][a][l]
共需要22个Byte。
大大缩小了存储空间尤其是在按字典顺序排序的情况下前缀的重合率大大提高。
2. 差值规则(Delta)
在Lucene的反向索引中需要保存很多整型数字的信息比如文档ID号比如词(Term)在文档中的位置等等。
由上面介绍我们知道整型数字是以VInt的格式存储的。随着数值的增大每个数字占用的Byte的个数也逐渐的增多。所谓差值规则(Delta)就是先后保存两个整数的时候后面的整数仅仅保存和前面整数的差即可。 比如要存储如下整数16386163871638816389
如果按照正常方式来存储需要的空间如下
[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001][(1) 000, 0011][(1) 000, 0000][(0) 000, 0001][(1) 000, 0100][(1) 000, 0000][(0) 000, 0001][(1) 000, 0101][(1) 000, 0000][(0) 000, 0001]
供需12个Byte。
如果应用差值规则来存储需要的空间如下
[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001][(0) 000, 0001][(0) 000, 0001][(0) 000, 0001]
共需6个Byte。
大大缩小了存储空间而且无论是文档ID还是词在文档中的位置都是按从小到大的顺序逐渐增大的。
3. 或然跟随规则(A, B?)
Lucene的索引结构中存在这样的情况某个值A后面可能存在某个值B也可能不存在需要一个标志来表示后面是否跟随着B。
一般的情况下在A后面放置一个Byte为0则后面不存在B为1则后面存在B或者0则后面存在B1则后面不存在B。
但这样要浪费一个Byte的空间其实一个Bit就可以了。
在Lucene中采取以下的方式A的值左移一位空出最后一位作为标志位来表示后面是否跟随B所以在这种情况下A/2是真正的A原来的值。 如果去读Apache Lucene - Index File Formats这篇文章会发现很多符合这种规则的
.frq文件中的DocDelta[, Freq?]DocSkip,PayloadLength?.prx文件中的PositionDelta,Payload? (但不完全是如下表分析)
当然还有一些带?的但不属于此规则的
.frq文件中的SkipChildLevelPointer?是多层跳跃表中指向下一层表的指针当然如果是最后一层此值就不存在也不需要标志。.tvf文件中的Positions?, Offsets?。 在此类情况下带?的值是否存在并不取决于前面的值的最后一位。而是取决于Lucene的某项配置当然这些配置也是保存在Lucene索引文件中的。如Position和Offset是否存储取决于.fnm文件中对于每个域的配置(TermVector.WITH_POSITIONS和TermVector.WITH_OFFSETS)
为什么会存在以上两种情况其实是可以理解的
对于符合或然跟随规则的是因为对于每一个AB是否存在都不相同当这种情况大量存在的时候从一个Byte到一个Bit如此8倍的空间节约还是很值得的。对于不符合或然跟随规则的是因为某个值的是否存在的配置对于整个域(Field)甚至整个索引都是有效的而非每次的情况都不相同因而可以统一存放一个标志。
文章中对如下格式的描述令人困惑 Positions -- PositionDelta,Payload? Freq Payload -- PayloadLength?,PayloadData PositionDelta和Payload是否适用或然跟随规则呢如何标识PayloadLength是否存在呢 其实PositionDelta和Payload并不符合或然跟随规则Payload是否存在是由.fnm文件中对于每个域的配置中有关Payload的配置决定的(FieldOption.STORES_PAYLOADS) 。 当Payload不存在时PayloadDelta本身不遵从或然跟随原则。 当Payload存在时格式应该变成如下Positions -- PositionDelta,PayloadLength?,PayloadData Freq 从而PositionDelta和PayloadLength一起适用或然跟随规则。 4. 跳跃表规则(Skip list)
为了提高查找的性能Lucene在很多地方采取的跳跃表的数据结构。
跳跃表(Skip List)是如图的一种数据结构有以下几个基本特征
元素是按顺序排列的在Lucene中或是按字典顺序排列或是按从小到大顺序排列。跳跃是有间隔的(Interval)也即每次跳跃的元素数间隔是事先配置好的如图跳跃表的间隔为3。跳跃表是由层次的(level)每一层的每隔指定间隔的元素构成上一层如图跳跃表共有2层。 需要注意一点的是在很多数据结构或算法书中都会有跳跃表的描述原理都是大致相同的但是定义稍有差别
对间隔(Interval)的定义 如图中有的认为间隔为2即两个上层元素之间的元素数不包括两个上层元素有的认为是3即两个上层元素之间的差包括后面上层元素不包括前面的上层元素有的认为是4即除两个上层元素之间的元素外既包括前面也包括后面的上层元素。Lucene是采取的第二种定义。对层次(Level)的定义如图中有的认为应该包括原链表层并从1开始计数则总层次为3为123层有的认为应该包括原链表层并从0计数为012层有的认为不应该包括原链表层且从1开始计数则为12层有的认为不应该包括链表层且从0开始计数则为01层。Lucene采取的是最后一种定义。
跳跃表比顺序查找大大提高了查找速度如查找元素72原来要访问23712233739445072总共10个元素应用跳跃表后只要首先访问第1层的50发现72大于50而第1层无下一个节点然后访问第2层的94发现94大于72然后访问原链表的72找到元素共需要访问3个元素即可。
然而Lucene在具体实现上与理论又有所不同在具体的格式中会详细说明。
