Lucene的索引文件格式(3)

四、具体格式

4.2. 反向信息

反向信息是索引文件的核心，也即反向索引。

反向索引包括两部分，左面是词典(Term Dictionary)，右面是倒排表(Posting List)。

在Lucene中，这两部分是分文件存储的，词典是存储在tii，tis中的，倒排表又包括两部分，一部分是文档号及词频，保存在frq中，一部分是词的位置信息，保存在prx中。

• Term Dictionary (tii, tis)
  • > Frequencies (.frq)
  • > Positions (.prx)

    4.2.1. 词典(tis)及词典索引(tii)信息

    

    在词典中，所有的词是按照字典顺序排序的。

    • 词典文件(tis)
      • TermCount：词典中包含的总的词数
      • IndexInterval：为了加快对词的查找速度，也应用类似跳跃表的结构，假设IndexInterval为4，则在词典索引(tii)文件中保存第4个，第8个，第12个词，这样可以加快在词典文件中查找词的速度。
      • SkipInterval：倒排表无论是文档号及词频，还是位置信息，都是以跳跃表的结构存在的，SkipInterval是跳跃的步数。
      • MaxSkipLevels：跳跃表是多层的，这个值指的是跳跃表的最大层数。
      • TermCount个项的数组，每一项代表一个词，对于每一个词，以前缀后缀规则存放词的文本信息(PrefixLength + Suffix)，词属于的域的域号(FieldNum)，有多少篇文档包含此词(DocFreq)，此词的倒排表在frq，prx中的偏移量(FreqDelta, ProxDelta)，此词的倒排表的跳跃表在frq中的偏移量(SkipDelta)，这里之所以用Delta，是应用差值规则。
      • 词典索引文件(tii)
        • 词典索引文件是为了加快对词典文件中词的查找速度，保存每隔IndexInterval个词。
        • 词典索引文件是会被全部加载到内存中去的。
        • IndexTermCount = TermCount / IndexInterval：词典索引文件中包含的词数。
        • IndexInterval同词典文件中的IndexInterval。
        • SkipInterval同词典文件中的SkipInterval。
        • MaxSkipLevels同词典文件中的MaxSkipLevels。
        • IndexTermCount个项的数组，每一项代表一个词，每一项包括两部分，第一部分是词本身(TermInfo)，第二部分是在词典文件中的偏移量(IndexDelta)。假设IndexInterval为4，此数组中保存第4个，第8个，第12个词。。。
        • 读取词典及词典索引文件的代码如下：

          origEnum = new SegmentTermEnum(directory.openInput(segment + "." + IndexFileNames.TERMS_EXTENSION,readBufferSize), fieldInfos, false);//用于读取tis文件

          • int firstInt = input.readInt();
          • size = input.readLong();
          • indexInterval = input.readInt();
          • skipInterval = input.readInt();
          • maxSkipLevels = input.readInt();

            SegmentTermEnum indexEnum = new SegmentTermEnum(directory.openInput(segment + "." + IndexFileNames.TERMS_INDEX_EXTENSION, readBufferSize), fieldInfos, true);//用于读取tii文件

            • indexTerms = new Term[indexSize];
            • indexInfos = new TermInfo[indexSize];
            • indexPointers = new long[indexSize];
            • for (int i = 0; indexEnum.next(); i++)
              • indexTerms[i] = indexEnum.term();
              • indexInfos[i] = indexEnum.termInfo();
              • indexPointers[i] = indexEnum.indexPointer;

                4.2.2. 文档号及词频(frq)信息

                

                文档号及词频文件里面保存的是倒排表，是以跳跃表形式存在的。

                • 此文件包含TermCount个项，每一个词都有一项，因为每一个词都有自己的倒排表。
                • 对于每一个词的倒排表都包括两部分，一部分是倒排表本身，也即一个数组的文档号及词频，另一部分是跳跃表，为了更快的访问和定位倒排表中文档号及词频的位置。
                • 对于文档号和词频的存储应用的是差值规则和或然跟随规则，Lucene的文档本身有以下几句话，比较难以理解，在此解释一下：

                  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

                  首先我们看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就不能按完整信息存了，就应该存放如下：

                  [DocIDDelta = 7, Freq = 1][DocIDDelta = 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，必须要左移一位，且最后一位置一，000 1111 = 15，对于第二个Term，由于Freq大于一，于是放在DocDelta的最后一位置零，DocIDDelta = 4的二进制是0000 0100，必须要左移一位，且最后一位置零，0000 1000 = 8，然后后面跟随真正的Freq = 3。

                  于是得到序列：[DocDleta = 15][DocDelta = 8, Freq = 3]，也即序列，15，8，3。

                  如果omitTf=true，也即我们不在索引中存储一个文档中Term出现的次数，则只存DocID就可以了，因而不存在A+B?规则的应用。

                  [DocID = 7][DocID = 11]，然后应用规则2，Delta规则，于是得到序列[DocDelta = 7][DocDelta = 4 (11 - 7)]，也即序列，7，4.

                  • 对于跳跃表的存储有以下几点需要解释一下：
                    • 跳跃表可根据倒排表本身的长度(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中的偏移量。
                    • 虽然Lucene的文档中有以下的描述，然而实验的结果却不是完全准确的：

                      Example: SkipInterval = 4, MaxSkipLevels = 2, DocFreq = 35. Then skip level 0 has 8 SkipData entries, containing the 3rd, 7th, 11th, 15th, 19th, 23rd, 27th, and 31st?document numbers in TermFreqs. Skip level 1 has 2 SkipData entries, containing the 15th?and 31st?document numbers in TermFreqs.

                      按照描述，当SkipInterval为4，且有35篇文档的时候，Skip level = 0应该包括第3，第7，第11，第15，第19，第23，第27，第31篇文档，Skip level = 1应该包括第15，第31篇文档。

                      然而真正的实现中，跳跃表节点的时候，却向前偏移了，偏移的原因在于下面的代码：

                      • FormatPostingsDocsWriter.addDoc(int docID, int termDocFreq)
                        • final int delta = docID - lastDocID;
                        • if ((++df % skipInterval) == 0)
                          • skipListWriter.setSkipData(lastDocID, storePayloads, posWriter.lastPayloadLength);
                          • skipListWriter.bufferSkip(df);

                            从代码中，我们可以看出，当SkipInterval为4的时候，当docID = 0时，++df为1，1%4不为0，不是跳跃节点，当docID = 3时，++df=4，4%4为0，为跳跃节点，然而skipData里面保存的却是lastDocID为2。

                            所以真正的倒排表和跳跃表中保存一下的信息：

                            

                            4.2.3. 词位置(prx)信息

                            

                            词位置信息也是倒排表，也是以跳跃表形式存在的。

                            • 此文件包含TermCount个项，每一个词都有一项，因为每一个词都有自己的词位置倒排表。
                            • 对于每一个词的都有一个DocFreq大小的数组，每项代表一篇文档，记录此文档中此词出现的位置。这个文档数组也是和frq文件中的跳跃表有关系的，从上面我们知道，在frq的跳跃表节点中有ProxSkip，当SkipInterval为3的时候，frq的跳跃表节点指向prx文件中的此数组中的第1，第4，第7，第10，第13，第16篇文档。
                            • 对于每一篇文档，可能包含一个词多次，因而有一个Freq大小的数组，每一项代表此词在此文档中出现一次，则有一个位置信息。
                            • 每一个位置信息包含：PositionDelta(采用差值规则)，还可以保存payload，应用或然跟随规则。

                              4.3. 其他信息

                              4.3.1. 标准化因子文件(nrm)

                              为什么会有标准化因子呢？从第一章中的描述，我们知道，在搜索过程中，搜索出的文档要按与查询语句的相关性排序，相关性大的打分(score)高，从而排在前面。相关性打分(score)使用向量空间模型(Vector Space Model)，在计算相关性之前，要计算Term Weight，也即某Term相对于某Document的重要性。在计算Term Weight时，主要有两个影响因素，一个是此Term在此文档中出现的次数，一个是此Term的普通程度。显然此Term在此文档中出现的次数越多，此Term在此文档中越重要。

                              这种Term Weight的计算方法是最普通的，然而存在以下几个问题：

                              • 不同的文档重要性不同。有的文档重要些，有的文档相对不重要，比如对于做软件的，在索引书籍的时候，我想让计算机方面的书更容易搜到，而文学方面的书籍搜索时排名靠后。
                              • 不同的域重要性不同。有的域重要一些，如关键字，如标题，有的域不重要一些，如附件等。同样一个词(Term)，出现在关键字中应该比出现在附件中打分要高。
                              • 根据词(Term)在文档中出现的绝对次数来决定此词对文档的重要性，有不合理的地方。比如长的文档词在文档中出现的次数相对较多，这样短的文档比较吃亏。比如一个词在一本砖头书中出现了10次，在另外一篇不足100字的文章中出现了9次，就说明砖头书应该排在前面码？不应该，显然此词在不足100字的文章中能出现9次，可见其对此文章的重要性。

                                由于以上原因，Lucene在计算Term Weight时，都会乘上一个标准化因子(Normalization Factor)，来减少上面三个问题的影响。

                                标准化因子(Normalization Factor)是会影响随后打分(score)的计算的，Lucene的打分计算一部分发生在索引过程中，一般是与查询语句无关的参数如标准化因子，大部分发生在搜索过程中，会在搜索过程的代码分析中详述。

                                标准化因子(Normalization Factor)在索引过程总的计算如下：

                                

                                它包括三个参数：

                                • Document boost：此值越大，说明此文档越重要。
                                • Field boost：此域越大，说明此域越重要。
                                • lengthNorm(field) = (1.0 / Math.sqrt(numTerms))：一个域中包含的Term总数越多，也即文档越长，此值越小，文档越短，此值越大。

                                  从上面的公式，我们知道，一个词(Term)出现在不同的文档或不同的域中，标准化因子不同。比如有两个文档，每个文档有两个域，如果不考虑文档长度，就有四种排列组合，在重要文档的重要域中，在重要文档的非重要域中，在非重要文档的重要域中，在非重要文档的非重要域中，四种组合，每种有不同的标准化因子。

                                  于是在Lucene中，标准化因子共保存了(文档数目乘以域数目)个，格式如下：

                                  

                                  • 标准化因子文件(Normalization Factor File: nrm)：
                                    • NormsHeader：字符串“NRM”外加Version，依Lucene的版本的不同而不同。
                                    • 接着是一个数组，大小为NumFields，每个Field一项，每一项为一个Norms。
                                    • Norms也是一个数组，大小为SegSize，即此段中文档的数量，每一项为一个Byte，表示一个浮点数，其中0~2为尾数，3~8为指数。

                                      4.3.2. 删除文档文件(del)

                                      ?

                                      • 被删除文档文件(Deleted Document File: .del)
                                        • Format：在此文件中，Bits和DGaps只能保存其中之一，-1表示保存DGaps，非负值表示保存Bits。
                                        • ByteCount：此段中有多少文档，就有多少个bit被保存，但是以byte形式计数，也即Bits的大小应该是byte的倍数。
                                        • BitCount：Bits中有多少位被至1，表示此文档已经被删除。
                                        • Bits：一个数组的byte，大小为ByteCount，应用时被认为是byte*8个bit。
                                        • DGaps：如果删除的文档数量很小，则Bits大部分位为0，很浪费空间。DGaps采用以下的方式来保存稀疏数组：比如第十，十二，三十二个文档被删除，于是第十，十二，三十二位设为1，DGaps也是以byte为单位的，仅保存不为0的byte，如第1个byte，第4个byte，第1个byte十进制为20，第4个byte十进制为1。于是保存成DGaps，第1个byte，位置1用不定长正整数保存，值为20用二进制保存，第2个byte，位置4用不定长正整数保存，用差值为3，值为1用二进制保存，二进制数据不用差值表示。

                                          五、总体结构

                                          

                                          ?

                                          ?

                                          ?

                                          ?

                                          • 图示为Lucene索引文件的整体结构：
                                            • 属于整个索引(Index)的segment.gen，segment_N，其保存的是段(segment)的元数据信息，然后分多个segment保存数据信息，同一个segment有相同的前缀文件名。
                                            • 对于每一个段，包含域信息，词信息，以及其他信息(标准化因子，删除文档)
                                            • 域信息也包括域的元数据信息，在fnm中，域的数据信息，在fdx，fdt中。
                                            • 词信息是反向信息，包括词典(tis, tii)，文档号及词频倒排表(frq)，词位置倒排表(prx)。

                                              大家可以通过看源代码，相应的Reader和Writer来了解文件结构，将更为透彻。