学术堂首页 | 文献求助论文范文 | 论文题目 | 参考文献 | 开题报告 | 论文格式 | 摘要提纲 | 论文致谢 | 论文查重 | 论文答辩 | 论文发表 | 期刊杂志 | 论文写作 | 论文PPT
学术堂专业论文学习平台您当前的位置:学术堂 > 图书档案学论文 > 搜索引擎论文

Lucence索引的内部结构探析

来源:学术堂 作者:姚老师
发布于:2015-07-31 共4544字
摘要

  1 引言(Introduction)

  在Lucence中包括了几个基础的概念,分别是索引、段、文档、域和项。其中索引由段构成,段由文档构成,因此索引可以理解为包含了多个文档的序列。文档由域构成,域由项构成,项是索引中最小构成单位,其本质是一个字符串。段是索引数据存储的基本单元,多个段之间彼此独立,当添加新的文档时将生成新的段,且段可以合并。

  充分理解Lucence索引的内部结构,对于在当前互联网大数据、云存储应用环境下较好使用Lucence进行具有重要意义。

  2 索引文件结构(Index file structure)

  2.1 倒排索引

  对文本信息进行检查的系统索引可以分为包括正排索引和倒排索引[1].在实际使用中根据属性值查找记录的过程称为倒排索引。倒排表中存储了文档中包含的单词,文档编号差值、单词出现次数等,这些信息即组成了倒排索引项term.倒排索引入口为索引项term,通过倒排索引可以找到包含每个term的文档集合称为记录表,记录表中包含文档号及term在该文档中的出现频率。

  Lucene为了使得基于term的检索效率更高,索引存储terms的统计数据。Lucene的索引采用了倒排索引。它可以列举,包含一个term的所有文档。这与自然关联规则相反,即由documents列举它所包含的terms.

  2.2 域Fields

  Lucene在存储域数据时,域中文本被逐字的以非倒转方式进行转换,这些被倒排存储的域数据可以被索引[2].每个域的文本被拆分为多个索引项以便被高效索引,另一种方式为域中文本作为一个索引项进行索引。

  2.3 片断

  Lucene索引可以由多个复合的子索引或片段构成。每个段是一个完全独立的索引,它可以分离提取进行检索。检索过程如下:(1)当添加新的文档时创建新的段;(2)对现有段进行合并。在索引检索时,会涉及多个索引或段,因此每一个索引都隐含包括了一组段。段及文档关系如图1所示。

  2.4 文档编号

  在Lucene的内部对于每个文档使用一个整数编号进行标识。初始情况下,第一个被加进来的文档其文档编号为0,之后加进来的文档其编号自动递增,采用自动递增方式对文档进行编号,编号不会出现重复。但需注意的是,文档编号可以被手动更改。因此在维护时若出现更改情况,需特别考虑此编号是否在更大的范围内被使用。通常的做法是为每个段空间设置文档编号的范围,以保证段之间的文档编号不重复。

  综上所述,文档编号若发生修改可能导致错误,因此文档编号应先进行设计,在应用时不轻易、不频繁修改文档编号,只有当出现文档在某段空间是统一的,且需要在整个系统中使用时必须修改情况下才进行修改。

  3 索引文件(Index file)

  3.1 索引文件

  Lucene索引文件包含多种,其使用不同的文件扩展名来进行标识。同时文件名称可以标识不同的版本。常见的文件扩展名有:fnm文件存储域名和域属性、fdt文件存储域数据、fdx文件存储在fdt文件中的偏移位置、frq存储文件中项的位置数据等。对于段文件命名通常为segments_x,其中x即为最新修改版本,文件segments.gen存储当前版本值。以下文件存在于每个索引index中,并且只有一份。

  (1)Segments文件

  索引中活动的Segments被存储在segment info文件中,segments_N,在索引中可能会包含一个或多个segments_N文件。然而,最大一代的那个文件是活动的片断文件(这时更旧的segments_N文件依然存在是因为它们暂时还不能被删除,或者,一个writer正在处理提交请求,或者一个用户定义的IndexDeletionPolicy正被使用。这个文件按照名称列举每一个片断,详细描述分离的标准和要删除的文件,并且还包含了每一个片断的大小。

  (2)Lock文件

  写锁文件名为"write.lock",存储在默认的索引目录中。如果锁目录和索引目录不一致的,写锁将被命名为"XXXX-write.lock",其中"XXXX"是一个特殊唯一的前缀,来源于索引目录的路径。

  (3)Deletable文件

  Lucene的删除机制类似于操作系统回收站,在执行删除操作时,相当于对索引进行了"删除标记"并未真实删除,当索引下次优化或合并时再从索引中真正删除。

  (4)Compound文件

  Compound文件格式成一个简单的容器,其用来服务所有Segment包含的文件(除了。del文件)。

  3.2 Segment

  每个段中的文件是由后缀名来区分的。

  (1)域集合信息

  域的信息以集合形式存储,域集合文件后缀为。fnm.在当前的情况下,fieldbits仅用于低位,索引的域值是1,未索引的域值为0,文件中各域根据次序进行编号,即认为值0是第一个域文件,值1是下一个域文件等。Fields将使用它们在这个文件中的顺序来编号。需要注意的是,就像文档编号一样,field编号与片断是相关的。

  (2)域索引和域值

  域值存储表使用两种文件存储 , 分别为 : 域索引表(。fdx文件)文件,这个文件包含指向域值的指针FieldvaluesPosition,类型为UInt64类型,此指针指向了某域值在域文件中的位置。因为域值文件包括定长的数据信息,较易随机访问;域值(。fdt文件)文件,每个文档的域值信息包括了字段FieldData、DocFieldData、FieldCount、FieldNum、Bits和value.

  (3)项字典

  项Term字典使用如下两种文件存储,第一种是存储term信息(TermInfoFile)的文件,即。tis文件,另一种是存储term信息索引的文件,即。tii文件。TermInfoFile文件按照Term来排序,排序方法首先按照Term的field名称(按照UTF-16字符编码)排序,然后按照Term的Text字符串(UTF-16编码)排序。项的命名上前缀通常上是相同的,然后以字的后缀组成。

  (4)项频率数据

  Term频率数据文件(。frq文件)存储容纳了每一个term的文档列表,以及该term出现在该文档中的频率(出现次数frequency,如果omitTf设置为fals时才存储)。

  关 于 skiplevels , 每一个 term 可以有多个skip levels.一个term的skip levels的数目等于NumSkipLevels=Min(MaxSkipLevels,floor(log(DocFreq/log(SkipInterval))))。对一个skip level来说SkipData记录的数目等于DocFreq/(SkipInterval^(Level+1))。然而最低的skip level等于Level=0.例如假设SkipInterval=4,MaxSkipLevels=2,DocFreq=35,则skip level 0有8个SkipData记录,在TermFreqs序列中包含第3、7、11、15、19、23、27和31个文档的编号。Skip level 1则有两个SkipData记录,在TermFreqs中包含了第15和第31个文档的编号。在所有level>0之上的SkipData记录中包含一个SkipChildLevelPointer,指向(referencing)level-1中相应)的SkipData记录。在这个例子中,level 1中的记录15有一个指针指向level 0中的记录15,level 1中的记录31有一个指针指向level 0中的记录31.

  (5)项位置

  Positions位置信息数据文件(。prx文件)容纳了每一个term出现在所有文档中的位置的列表,可以利用这些信息来参与对索引结果的排序。如果在fields中的omitTf设置为true时将不会在此文件中存储任何信息,并且如果索引中所有fields中的omitTf都设置为true,此。prx文件将不会存在。

  (6)标准化因子文件

  在Lucene 2.1版本之前,每一个索引都有一个norm文件给每一个文档都保存了一个字节。对每一个文档来说,那些。f[0-9]包含了一个字节容纳一个被编码的分数,值为对hits结果集来说在那个field中被相乘得出的分数。每一个分离的norm文件在适当的时候为复合的和非复合的segment片断创建。在Lucene 2.1及以上版本,只有一个norm文件容纳了所有norms数据:一个分离的norm文件在一个存在的segment的norm数据被更改的时候被创建,当field N被修改时,一个分离的norm文件。sN被创建,用来维护该field的norm数据。

  (7)项向量文件

  Term向量的支持是field基本组成中对一个field来说的可选项,它包含如下三种文件:a.文档索引或。tvx文件:对每个文档来说,它把偏移存储进文档数据(。tvd)文件和域field数据(。tvf)文件。b.文档或。tvd文件:对每个文档来说,它包含fields的数目,有term向量的fields的列表,还有指向term向量域文件(。tvf)中的域信息的指针列表。该文件用于映射出那些存储了term向量的fields,以及这些field信息在。tvf文件中的位置。c.域field或。tvf文件:对每个存储了term向量的field来说,该文件包含了一个term的列表,及它们的频率,还有可选的位置和偏移信息。

  (8)删除的文档

  删除的文档(。del)文件是可选的,而且仅当一个segment存在有被删除的文档时才存在。即使对每一单个segment,它也是维护复合segment的外部数据。

  4 索引创建过程(The index creation process)

  为了使用Lucene的索引数据,必须先将其转换为文本标记的数据流,并用它来创建一个文档对象,其中包含的域成员来容纳这些文本数据[3,4].一旦你准备的文档对象,可以调用IndexWriter类的adddocument方法传递对象到Lucene写索引。当这样做时Lucene进行分析数据,以便更适合索引。

  文档的索引过程是通过DocumentsWriter的内部数据处理链完成的,DocumentsWriter可以实现同时添加多个文档并将它们写入一个临时的segment中,完成后再由IndexWriter和SegmentMerger合并到统一的segment中去。

  DocumentsWriter支持多线程处理,即多个线程同时添加文档,它会为每个请求分配一个DocumentsWriterThreadState对象来监控此处理过程。处理时通过DocumentsWriter初始化时建立的DocFieldProcessor管理的索引处理链来完成的,依次处理为DocFieldConsumers、DocInverter、TermsHash、FreqProxTermsWriter、TermVectorsTermsWriter、NormsWriter以及StoredFieldsWriter等。

  DocFieldProcessorPerThread.processDocument()方法是处理一个文档的调度函数,负责整理文档的各个fields数据,并创建相应的DocFieldProcessorPerField对象来依次处理每一个field.该方法首先调用索引链表的startDocument()来初始化各项数据,然后依次遍历每一个fields,将它们建立一个以field名字计算的hash值为key的hash表,值为DocFieldProcessorPerField类型。如果hash表中已存在该field,则更新该FieldInfo(调用FieldInfo.update()方法),如果不存在则创建一个新的DocFieldProcessorPerField来加入hash表中。该hash表会存储包括当前添加文档的所有文档的fields信息,并根据FieldInfo.update()来合并相同field名字的域设置信息。

  建立hash表的同时,生成针对该文档的fields[]数组(只包含该文档的fields,但会共用相同的fields数组,通过lastGen来控制当前文档),如果field名字相同,则将Field添加到DocFieldProcessorPerField中的fields数组中。建立完fields后再将此fields数组按field名字排序,使得写入的vectors等数据也按此顺序排序。之后开始正式的文档处理,通过遍历fields数组依次调用DocFieldProcessorPerField的processFields()方法进行,完成后调用finishDocument()完成后序工作,如写入FieldInfos等。

  5 结论(Conclusion)

  Lucene自发布至今已有近15年时间,近几年互联网的快速发展更使得产生的数据呈指数级增长,Lucene面对海量数据进行处理,因此在检索时针对索引的优化至关重要。牢固掌握Lucene索引原理对于解决当前大数据环境下数据检索以及提高检索效率打下良好基础。

  参考文献(References):
  [1] 王冬。一种增量倒排索引结构的设计与实现[J].吉林大学学报,2007,45(06):953-958.
  [2] 黄轶文。搜索引擎原理与快速开发应用[J].科技信息,2010,(36):570-571.
  [3] 何伟,等。基于Lucene的全文搜索引擎的设计与实现[J].2006,25(9):88-90.
  [4] 李晓丽,杜振龙。基于Lucence的个性化搜索引擎研究[J].计算机工程,2010,36(19):258-260.

相关标签:
  • 报警平台
  • 网络监察
  • 备案信息
  • 举报中心
  • 传播文明
  • 诚信网站