【Lucene3.0 初窥】索引文件格式(1)：预备知识

注意，本专题内容参见《http://lucene.apache.org/java/3_0_1/fileformats.html 》

 

深入了解Lucene的磁盘索引文件，可以使我们对IR系统底层数据存储结构有一个深刻的认识。在《索引文件格式》这一专题中，我们将详细探讨 Lucene 3.0索引数据在磁盘上的存储格式，并通过一个实例进一步理解这些格式。但首先，我们必须准备点Lucene 索引文件格式的基础知识。

 

 

 

 

★ Lucene 自定义的基本数据类型

 

【Byte】  由8 bits组成的基本数据类型。所有其他的数据类型都是一个byte 串。因此，Lucene的索引文件都可以看成是有序的byte 串

【UInt32】 由4 byte 组成的32位无符号整 型 ，高位优先。UInt32 --> <Byte>⁴

【UInt64】 由8 byte 组成的64位无符号整型，高位优先。 UInt64 --> <Byte>⁸

【VInt】 可变长整型，为正整数定义的可变长格式。其特殊之处在于： 每字节的最高位表明后面还有一个字节，每字节的低七位表明整数的值，高位优先。因此 单个字节能表示的整数范围为0-127，而128到16383必须存储在两个字节中。比如下表：

Value	First byte	Second byte	Third byte
0	00000000
1	00000001
2	00000010
...	...	...	...
127	01111111
128	10000000	00000001
129	10000001	00000001
130	10000010	00000001
...	...	...	...
16,383	11111111	01111111
16,384	10000000	10000000	00000001
16,385	10000001	10000000	00000001

【Chars】 采用UTF-8编码的Unicode字符序列

【String】 由VInt 和 Chars组成的字符串类型，其中VInt表示了Chars的长度，Chars表示了String的值。比如：

字符串"name"在Lucene的存储结构中表示为：4,110,97,109,101。其中4为字符的长度，后面4bytes分别表示四个字 符。

 

 

 

 

 

 

 

★ 空间复杂度的优化 —— Lucene压缩技术

    信息检索领域中一个非常重要的研究课题就是如何将海量的信息存储起来。Lucene建立倒排索引结构，需要将词语、文档号、词频、位置信息写入磁盘文件。需要检索的文本越多，信息量就越大。因此Lucene使用了一些数据压缩技术来尽量减少数据存储所需要的空间。

 

(1) 前缀规则 Prefix

      所谓前缀规则，即当前词和前一个词有共同的前缀的时候，当前词仅仅保存前缀之后的子串。比如“term terminal”这两个词的存储如下所示， 注意：前缀规则只适用于两个相邻的词。

                                                 t e r m 4  i n a l

      我们来看看压缩的效率：假设有term，termagancy，termagant，termina四个词。每个字母需要1byte的空间。常规存储一共需要35byte。而压缩存储之后为："term4agancy8t4inal"。一共需要22byte.

      Lucene倒排索引文件的Dictionary主要就采用了这种压缩技术。其效果非常理想，原因就在于Dictionary中的词语都按照字典序进行排序，两个相邻的词语之间的具有很长的相同前缀。

 

 

(2) 差值规则(Delta)

      所谓差值规则，就是两个连续存储的数据，后一个数据存储的是与前一个数据的差值。比如"1500000 1500001"这两个数据的存储如下所示， 注意：差值规则也必须在两个连续的存储数据之间发生。

                                                    1500000  1

      很显然，如果要存储一个比较大的数据，很有可能需要多个字节的存储空间。如果存储与前一个数据的差值，那么很有可能将数据控制在1byte之内。

      Lucene倒排索引文件中frequence、docID、position都采用了这种压缩技术。其原因就在于这三种信息具有一个相似的特性，就是信息的后一个数据基本上都是前一个数据增1。因此差值总是可以将很大的数用1来存储。

 

 

(3) 或然跟随规则

       或然跟随规则可以在某种特定的情况下将本需要2个空间存储的数据放在压缩成1个空间存储。 比如说某个数据A=1，其后紧跟的一个数据B=1。则可以采用(A<<1) | B 来存储，过程如下：

       A=00000001  B=00000001  --->   (A<<1) | B =00000010 | 00000001=00000011=3

       很显然，本需要2byte存储的A和B，现在只需要1byte就可以全部存储完毕了。

       但要注意，如果后面跟随的B>1怎么办？那么当然不可能将A的最后一个bit来存放B，只能放弃这种规则。但是如何区别使用或然规则压缩的数据和普通数据呢。只能将A进行左移1位而不与B或运算。

 

      Lucene中有很多情况符合这种具有一定条件约束的压缩技术。比如：.frq文件中的DocDelta[, Freq?]、prx文件中的PositionDelta,Payload?等。这些在后面的具体讨论中会详细讲到。

 

 

 

 

 

 

 

 

★ 时间复杂度的优化 —— Lucene 的跳表查询结构(Skip list)

 

    对于搜索引擎而言，查找时最主要的操作。为了提高查找的性能，Lucene在很多地方采取的跳跃表的数据结构。

 

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

• 元素是按顺序排列的，在Lucene中，或是按字典顺序排列，或是按从小到大顺序排列。
• 跳跃是有间隔的(Interval)，也即每次跳跃的元素数，间隔是事先配置好的，如图跳跃表的间隔为3。
• 跳跃表是由层次的(level)，每一层的每隔指定间隔的元素构成上一层，如图跳跃表共有2层。

 

需要注意一点的是，在很多数据结构或算法书中都会有跳跃表的描述，原理都是大致相同的，但是定义稍有差别：

• 对间隔(Interval)的定义： 如图中，有的认为间隔为2，即两个上层元素之间的元素数，不包括两个上层元素；有的认为是3，即两个上层元素之间的差，包括后面上层元素，不包括前面的上 层元素；有的认为是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总共10个元素，应用跳 跃表后，只要首先访问第1层的50，发现72大于50，而第1层无下一个节点，然后访问第2层的94，发现94大于72，然后访问原链表的72，找到元 素，共需要访问3个元素即可。

评论

1 楼 xchd 2013-10-23  

有代码例子吗