`

Lucene学习总结之三:Lucene的索引文件格式 (3)

阅读更多

 本文在csdn中的位置http://blog.csdn.net/forfuture1978/archive/2009/12/10/4976794.aspx

四、具体格式

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来了解文件结构,将更为透彻。

  • 大小: 53.1 KB
  • 大小: 74.4 KB
  • 大小: 44.5 KB
  • 大小: 85.4 KB
  • 大小: 12.3 KB
  • 大小: 42 KB
  • 大小: 73.8 KB
  • 大小: 82.6 KB
  • 大小: 134.2 KB
  • 大小: 151.5 KB
分享到:
评论

相关推荐

    Lucene 3.0 原理与代码分析PDF

    Lucene学习总结之三:Lucene的索引文件格式(3) Lucene学习总结之四:Lucene索引过程分析(1) Lucene学习总结之四:Lucene索引过程分析(2) Lucene学习总结之四:Lucene索引过程分析(3) Lucene学习总结之四:...

    Lucene学习总结之一:全文检索的基本原理[归纳].pdf

    3. **字段信息**:索引可以包含不同字段,如标题、正文、作者等,每个字段可能有不同的权重。 4. **位置信息**:保留术语在文档中的相对位置,用于短语查询和近似搜索。 5. **文档长度信息**:用于调整文档评分,较...

    lucene索引文件格式介绍

    以下是对Lucene索引文件格式的详细说明。 首先,我们要理解Lucene索引的基本结构。一个Lucene索引位于一个文件夹中,这个文件夹包含了多个段(Segment)。每个段是独立的,包含了一组文档,并且可以与其他段合并。...

    Lucene读取索引文件

    一个Lucene索引是由多个文件组成的,包括但不限于 segments文件、.del文件(删除文档标记)、.tii和.tis文件(Term Info Index和Term Info postings)、.frx、.fdx、.fdt、.fdt(Field Data)等。这些文件共同构成了...

    Lucene5学习之增量索引(Zoie)

    总结起来,Lucene5学习之增量索引(Zoie)涉及到的关键技术点包括: 1. 基于Lucene的增量索引解决方案:Zoie系统。 2. 主从复制架构:Index Provider和Index User的角色。 3. 数据变更追踪:通过变更日志实现增量索引...

    Lucene索引文件格式

    《Lucene索引文件格式详解》 Lucene,作为一款强大的全文搜索引擎库,其索引文件格式是实现高效搜索的关键。本文将深入解析Lucene 1.3版本的索引文件结构,帮助读者理解其内部运作机制。 首先,我们要理解Lucene...

    Lucene 索引的简单使用

    以上就是关于“Lucene索引的简单使用”的详细介绍,包括其核心概念、创建和查询索引的步骤以及一些高级特性。希望对你理解和应用Lucene有所帮助。在实际开发中,可以根据需求选择合适的Analyzer,优化索引策略,以...

    Lucene5学习之创建索引入门示例

    **Lucene5学习之创建索引入门示例** 在IT领域,搜索引擎的开发与优化是一项关键技术,而Apache Lucene作为一款高性能、全文本搜索库,是许多开发者进行文本检索的首选工具。本文将深入探讨如何使用Lucene5来创建一...

    Lucene对本地文件多目录创建索引

    - `lukeall-0.8.1.jar`:Luke是一个用于查看和分析Lucene索引的工具,可以帮助开发者调试和理解索引结构。 - `log4j-1.2.12.jar`:日志框架,用于记录程序运行时的信息。 - `commons-httpclient-3.1.jar`:可能是...

    Lucene索引文件查看工具lukeall4.7.1

    《深入理解Lucene索引文件查看工具LukeAll 4.7.1》 在信息检索领域,Lucene作为一款强大的全文搜索引擎库,被广泛应用在各种数据检索系统中。然而,对于开发者来说,理解并调试Lucene创建的索引文件并非易事。此时...

    Lucene3总体图_建索引_查询_数据库索引

    #### 三、Lucene3的查询流程 1. **用户输入查询语句**:用户输入想要搜索的关键词或短语。 2. **查询模块调用**:查询模块(search)接收查询请求。 3. **语法分析**:调用`queryParser`模块对查询语句进行分析。 4. ...

    Lucene3.0创建索引

    ### Lucene3.0创建索引 在Lucene3.0中创建索引是一个关键功能,可以帮助用户快速地检索和管理大量的文本数据。本篇文章将详细介绍如何使用Lucene3.0来创建索引,并通过一个具体的例子来演示整个过程。 #### 一、...

    基于lucene技术的增量索引

    本文将深入探讨如何利用Lucene实现增量索引,这是一种在数据库或文件系统更新时仅对新数据或变化数据进行索引的技术,以降低资源消耗并保持搜索性能。 **1. Lucene基础知识** Lucene首先需要理解的是它的核心概念,...

    lucene 对 xml建立索引

    - 在建立索引之前,需要先将XML文档转换为Lucene能够理解的数据格式。 - 本例中采用SAX解析器来进行XML文档的解析,通过重写SAX处理器类的方法(如`startDocument()`、`endDocument()`、`startElement()`等)来...

    lucene索引查看工具及源码

    通过阅读和学习 Luke 的源码,我们可以了解到如何与 Lucene 索引进行交互,以及索引结构是如何组织和存储的。 在提供的压缩包 "luke-3.3.0" 中,包含了 Luke 工具的旧版本。这个版本可能不支持最新的 Lucene 版本,...

    lucene学习总结

    **Lucene学习总结** 在深入理解Lucene之前,我们首先需要了解什么是全文检索。全文检索是一种从大量文本数据中快速查找所需信息的技术。它通过建立索引来实现高效的搜索,而Lucene正是Java环境下最著名的全文搜索...

    luke源码--查看lucene索引文件

    《深入理解Luke:洞察Lucene索引文件》 在信息技术领域,搜索引擎的高效运作离不开对数据的快速检索,而Lucene作为开源全文检索库,扮演了核心角色。在这个过程中,Luke工具提供了一种直观的方式,让我们能够查看和...

    lucene3源码分析

    #### 三、Lucene的索引文件格式 Lucene的索引文件格式是其高效检索性能的基础,主要包括以下几个方面: - **基本概念**:介绍Lucene索引文件的基本术语和概念。 - **基本类型**:定义了索引文件中使用的数据类型。...

    Lucene之删除索引

    Lucene的索引删除过程并不像传统的文件系统删除那么简单,它涉及到对倒排索引结构的修改。 1. **删除文档**:在Lucene中,删除操作并不是真正地从磁盘上移除文档,而是通过添加一个删除标记到索引中。当你调用`...

Global site tag (gtag.js) - Google Analytics