【Lucene3.0 初窥】索引文件格式(5)：posting数据[.frq/.prx]

★ .frq   词语频率数据 文件    .prx  词语位置数据文件

 

1、frq 保存了 词语所在文档的文档列表(docID)和该词语出现在文档中的频率信息。

 

FreqFile (.frq) --> <TermFreqs, SkipData> ^TermCount       frq文件包含TermCount个项。每一项都代表一个词，按照tis中的term的顺序排列。它分成两个部分：一部分是倒排表本身，也即一串的文档号及词频；另一部分是跳跃表，为了更快的访问和定位倒排表中文档号及词频的位置。

 

TermFreqs --> <TermFreq> ^DocFreq     TermFreq 按文档编号递增的顺序排序。DocFreq表示 出现 该词的文档数量。

 

TermFreq --> DocDelta[, Freq?]   一个TermFreq结构是由一个DocDelta后面或许跟着Freq组成。DocDelta是存储包含此Term的文档的ID号了，Freq是在此文档中出现的次数。

注意：TermFreq的存储数据时比较特别的，其中用到了差值规则和或然跟随规则。我们在下面解释一下TermFreq的存储数据。 (关于差值规则和或然跟随规则，请参见：《索引文件格式(1)：基础知识 》

(http://lucene.apache.org/java/3_0_1/fileformats.html#Frequencies)
Lucene官方网站解析freq文件中我们可以看到这样一段话
For example, the TermFreqs for a term which occurs once in document seven and three times in document eleven, with omitTf false, would be the following sequence of VInts: 15, 8, 3
If omitTf were true it would be this sequence of VInts instead: 7,4
      
(1) 首先我们看omitTf=false的情况，也即我们在索引中会存储一个文档中term出现的次数。
      例子中说了，表示在文档7中出现1次，并且又在文档11中出现3次的文档用以下序列表示：15，8，3.
      那这三个数字是怎么计算出来的呢？
      首先，根据定义TermFreq --> DocDelta[, Freq?]，一个TermFreq结构是由一个DocDelta后面或许跟着Freq组成，也即上面我们说的A+B？结构。
      DocDelta自然是想存储包含此Term的文档的ID号了，Freq是在此文档中出现的次数。
      所以根据例子，应该存储的完整信息为[DocID = 7, Freq = 1] [DocID = 11,  Freq = 3](见全文检索的基本原理章节)。
      然而为了节省空间，Lucene对编号此类的数据都是用差值来表示的，也即上面说的规则2，Delta规则，于是文档ID就不能按完整信息存了，就应该存放如下：
[DocDelta = 7, Freq = 1][DocDelta = 4 (11-7), Freq = 3]
     然而Lucene对于A+B?这种或然跟随的结果，有其特殊的存储方式，见规则3，即A+B?规则，如果DocDelta后面跟随的Freq为1，则用 DocDelta最后一位置1表示。
      如果DocDelta后面跟随的Freq大于1，则DocDelta得最后一位置0，然后后面跟随真正的值，从而对于第一个Term，由于Freq 为1，于是放在
      DocDelta的最后一位表示，DocIDDelta = 7的二进制是000 0111，必须要左移一位，且最后一位置1，000 1111 = 15，对于第二个Term，由于Freq大于1，于是放在DocDelta的最后一位置零，DocIDDelta = 4的二进制是0000 0100，必须要左移一位，且最后一位置零，0000 1000 = 8，然后后面跟随真正的Freq = 3。
      于是得到序列：[DocDleta = 15][DocDelta = 8, Freq = 3]，也即序列，15，8，3。

(2) 如果omitTf=true，也即我们不在索引中存储一个文档中Term出现的次数，则只存DocID就可以了，因而不存在A+B?规则的应用。[DocID = 7][DocID = 11]，然后应用规则2，Delta规则，于是得到序列[DocDelta = 7][DocDelta = 4 (11 - 7)].

  

 

 

SkipData --> <<SkipLevelLength, SkipLevel> ^{NumSkipLevels-1} , SkipLevel> <SkipDatum>  

SkipLevel --> <SkipDatum> ^{DocFreq/(SkipInterval^(Level + 1))}

SkipDatum --> DocSkip,PayloadLength?,FreqSkip,ProxSkip,SkipChildLevelPointer?

 

跳跃表可根据倒排表本身的长度(DocFreq)和跳跃的幅度(SkipInterval)而分不同的层次，层次数为NumSkipLevels = Min(MaxSkipLevels, floor(log(DocFreq/log(SkipInterval)))).

 

第Level层的节点数为DocFreq/(SkipInterval^(Level + 1))，level从零计数。

 

除了最高层之外，其他层都有SkipLevelLength来表示此层的二进制长度(而非节点的个数)，方便读取某一层的跳跃表到缓存里面。

 

低层在前，高层在后，当读完所有的低层后，剩下的就是最后一层，因而最后一层不需要SkipLevelLength。这也是为什么Lucene文 档中的格式描述为 ^{NumSkipLevels-1} , SkipLevel，也即低NumSKipLevels-1层有SkipLevelLength，最后一层只有SkipLevel，没有 SkipLevelLength。

 

除最低层以外，其他层都有SkipChildLevelPointer来指向下一层相应的节点。

 

每一个跳跃节点包含以下信息：文档号，payload的长度，文档号对应的倒排表中的节点在frq中的偏移量，文档号对应的倒排表中的节点在 prx中的偏移量。

 

 

2、 prx文件容纳了每一个term出现在所有文档中的位置的列表。注意如果在fields中的omitTf设置为 true时将不会在此文件中存储任何信息，并且如果索引中所有fields中的omitTf都设置为true，此.prx文件将不会存在

 

ProxFile (.prx) --> <TermPositions> ^TermCount

TermPositions --> <Positions> ^DocFreq

Positions --> <PositionDelta,Payload?> ^Freq

Payload --> <PayloadLength?,PayloadData>

PositionDelta --> VInt

PayloadLength --> VInt

PayloadData --> byte^{PayloadLength}

 

此文件包含TermCount个项，每一个词都有一项，因为每一个词都有自己的词位置倒排表。

 

对于每一个词的 都有一个DocFreq大小的数组，每项代表一篇文档，记录此文档中此词出现的位置。这个文档数组也是和frq文件中的跳跃表有关 系的，从上面我们知道，在frq的跳跃表节点中有ProxSkip，当SkipInterval为3的时候，frq的跳跃表节点指向prx文件中的此数组 中的第1，第4，第7，第10，第13，第16篇文档。

 

而有一个Freq大小的数组，每一项代表此词在此文档中出现 一次，则有一个位置信息。

 

每一个位置信息包含：PositionDelta(采用差值规则)，还可以保存 payload，应用或然跟随规则。

 

 

 

 

 

★  专题用例 ：

 

 关于例子的详细信息参见《索引文件格式 (2)：文件 结构总体框架 》最后的说明。

 

 

(1) 解释一下frq文件的数据

◆   frq文件的数据很显然使用了差值规则和或然跟随规则，比如“term”词语。其存储结构应该为[DocID=0，Freq=1][DocID=1，Freq=2][DocID=2，Freq=3][DocID=3，Freq=1]。

差值规则： [DocCode=0，Freq=1][DocCode=1(1-0)，Freq=2][DocCode=1(2-1)，Freq=2][DocCode=1(3-2)，Freq=2]

或然跟随规则：[DocCode=0，Freq=1] 如果DocCode后面的数据为1，则将DocCode<<1后将最后的bit存储Freq内容。即DocCode=00000000<<1=00000000 再将最后一个bit存储Freq=1，则变成00000001。因此、在文件中本来需要2个byte空间，压缩成1个byte来存储DocCode+Freq。

                     [DocCode=1，Freq=2]如果DocCode后面的数据不为1，则将DocCode<<1得到DocCode=00000001<<1=2后，在用另外一个byte来存储Freq=1。这里没有压缩为什么还要左移呢？为了能够将压缩数据和没有压缩的数据区别开来。

 

(2) 解释一下prx文件的数据

◆   同上，依然使用了差值规则。

 

注意： 这里词频和位置信息并没有使用到跳表结构，是因为所只用的例子中4篇文档内容很少。如果Dictionary非常大，则会向上面叙述的那样使用跳表结构来进行存储。

评论

1 楼 ppm10103 2012-06-27  

差值规则： [DocCode=0，Freq=1][DocCode=1(1-0)，Freq=2][DocCode=1(2-1)，Freq=2][DocCode=1(3-2)，Freq=2]

这个地方是错的，每次增加文档后都会执行
@Override
void finish() throws IOException {
long skipPointer = skipListWriter.writeSkip(out);
// TODO: this is abstraction violation -- we should not
// peek up into parents terms encoding format
termInfo.set(df, parent.freqStart, parent.proxStart,
(int) (skipPointer - parent.freqStart));
// TODO: we could do this incrementally
UnicodeUtil.UTF16toUTF8(parent.currentTerm, parent.currentTermStart,
utf8);
if (df > 0) {
parent.termsOut.add(fieldInfo.number, utf8.result, utf8.length,
termInfo);
}
lastDocID = 0;
df = 0;
}

这样，下一个文档的差值就是 docI-0