深入lucene--文件格式(基本压缩规则)

2011-12-28

1.前缀后缀规则(Prefix+Suffix):即当某个词和前一个词有共同的前缀时候,后面的词仅保存前缀在词中的偏移(offset)及前缀后面的词(Suffix)。

lucene数据类型

比如要存储如下词:term,termagancy,termagant,terminal,
如果按照正常方式来存储,需要的空间如下:
[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这种方式还是可以进一步优化整形数据的存储,差值就是先后保存两个整数的时候,后面的仅仅保存和前面的差。

lucene差值规则

3.或然跟随规则(A,B?)

Lucene的索引结构中存在这样的情况,某个值后面可能存在某个值B,也可能不存在,需要一个标志位来表明后面是否跟着B。

一般的情况下,在A后面放置一个Byte,为0则后面不存在B,为1则后面存在B,或者0则后面存在B,1则后面不存在B。

但这样要浪费一个Byte的空间,其实一个Bit就可以了。

在Lucene中,采取以下的方式:A的值左移一位,空出最后一位,作为标志位,来表示后面是否跟随B,所以在这种情况下,A/2是真正的A原来的值。lucene数据结构

Index File Formats下有如下的例子

.frq文件中的DocDelta[,Freq?],DocSkip,PlayloadLength?

.prx文件中的PositionDelta,Playload?(但不完全是,如下表分析)

.frq的SkipChildLevelPointer?,是多层跳跃表中,指向下一层表的指针,当然如果是最后一层,此值就不存在,也不需要标志。

.tvf中的Position?,Offsets?。

    在此类情况下,带?的值是否存在,并不取决于前面的值的最后一位。

    而是取决于Lucene的某项配置,当然这项配置也是保存在Lucene的索引文件中的。

    如Position和Offset是否存储,取决于.fnm文件中对于每个域的配置(TermVector.WITH_POSTIONS和TermVector.WITH_OFFSETS)。

为什么会出现以上两种情况,其实是可以理解的:

    对于符合或然跟随规则的,是因为对于每一个A,B是否存在都不相同,当这种情况大量存在的时候,从Byte到Bit可以节省8倍空间。

    对于不符合或然跟随规则的,是因为某个值的是否存在的配置对于整个域(Filed)甚至整个索引都是有效的,而非每次的情况都不同,因而可以统一存放一个标志。

文章中对如下格式的描述令人困惑:
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.跳跃表规则

为了提高查询性能,Lucene在很多地方采取的跳跃表的数据结构。

跳跃表(Skip List)是如图的一种数据结构,有以下几个基本特征:

    元素是按顺序排列的,在lucene中是按照字典的从小到大的顺序排列的。

    跳跃是有间隔的(Interval),即每次跳跃的元素数,间隔是事先配置好的,如图跳跃表的间隔为3.

    跳跃表是有层次的(Level),每一层的每隔指定间隔的元素构成上一层,如图跳跃表共有两层。

lucene跳跃表

ps:跳跃表在不同的书上描述不太一样,但是原理一样。

对间隔(Interval)的定义:有的认为间隔2,即两个上层元素之间的与素数,不包括两个上层的元素;有的认为是3,即2个上层元素之间的差,包括后面上层元素,不包括前面上层元素;有的认为是4,即除两个上层元素之间的元素,既包括前面,也包括后面的上层元素。Lucene采取的第二种定义。

对层次(Level)的定义:有的认为应该包括原连表层,并从1开始计数,则总层数为3,为1,2,3层;有的认为应该包括原连表层,并从0计数,为0,1,2层;有的认为不应该包括连表层,且从1开始计数,则为1,2层;有的认为不应该包括连表层,切从0开始计数,则为0,1层,Lucene采取的是最后一种定义。

跳跃表比顺序表查找,大大提高了查找速度,如查找元素72,原来要访问元2,3,7,12,23,37,39,44,50,72总共十个元素,应用跳跃表之后,只要首先访问第一层的50,发现72大于50,而第一层无下一个节点,然后访问第二层的94,发现94大于72,然后访问原链表的72,找到元素,总共访问3个元素就可以了。Lucene在具体实现上又有所不同。

作者:robotbird, 分类:关于代码 标签: lucene , 浏览(4854), 评论(1)
上一篇: 深入lucene--文件格式(基本数据类型)
下一篇: 罗马的故事-苏拉

相关文章

(1)条评论 订阅

  1. ${item.nickname} 币安 说:

    前缀的重合率大大提高。

1

发表评论

电子邮件用于回复通知和avatar全球唯一头像 *

*