开放源代码的全文检索引擎Lucene

    （FSDirectory，FSInputStream，FSOutputStream）的内部实现依托于java语言中的io类库，只是简单的做了一个外部逻辑的包装。这当然要归功于java语言所提供的跨平台特性，同时也带了一些隐患：文件存取的效率提升需要依耐于文件类库的优化。如果需要继续优化文件存取的效率，应该还提供一个文件与目录的抽象，以根据各种文件系统或者文件类型来提供一个优化的机会。当然，这是应用开发者所不需要关系的问题。

    （RAMDirectory，RAMInputStream和RAMOutputStream）的内部实现就比较直接了，直接采用了虚拟的文件RAMFile类（定义于文件RAMDirectory.java中）来表示文件，目录则看作一个String与RAMFile对应的关联数组。RAMFile中采用数组来表示文件的存储空间。在此的基础上，完成各项操作的实现，就形成了基于内存的虚拟文件系统。因为在实际使用时，并不会牵涉到很大字节数量的文件，因此这种设计是简单直接的，也是高效率的。

    这部分的实现在理清楚继承体系后，相当的简单。因此接下来的部分，我们可以通过直接阅读源代码解决。接下来我们看看这个部分的源代码如何在实际中使用的。

    一般来说，我们使用的是抽象类提供的接口而不是实际的实现类本身。在实现类中一般都含有几个静态函数，比如createFile，它能够返回一个OutputStream接口，或者openFile，它能够返回一个InputStream接口，利用这些接口之中的方法，比如writeString，writeByte等等，我们就能够在抽象的层次上处理Lucene定义的数据类型的读写。简单的说，Lucene中存储抽象这部分设计时采用了工厂模式（Factory parttern）^[23]。我们利用静态类的方法也就是工厂来创建对象，返回接口，通过接口来执行操作。

五、             关于cLucene项目

这一部分详细的说明了Lucene系统中所采用的索引文件格式、一些基础类和存储抽象。接下来我们来叙述一下我们在项目cLucene中重新实现这些结构时候的一些考虑。

    cLucene彻底的遵守了Lucene所定义的索引文件格式，这是Lucene对于各个兼容系统的基本要求。在此基础上，cLucene系统和Lucene系统才能够共享索引文件数据。或者说，cLucene生成的索引文件和Lucene生成的索引文件完全等价。

    在基础类问题上，cLucene同样封装了类似的结构。我们同样列表描述，请和前面的表3.2与3.3对照比较。

表 3.4 基础类包cLucene::util

表 3.3 基础类包cLucene::document

    存储抽象的实现上，也同样是类似于java实现。由于我们采用了OpenTop库，因此同样得以借助其中对于文件系统抽象的ot::io包来解决文件系统问题。这部分问题与前面一样，存在优化的可能。在实现的类层次上、对外接口上，均与java版本的一样。

第四节 Lucene索引构建逻辑模块分析

一、             绪论

这一个部分，我们将分析Lucene中的索引构建逻辑模块。它与前面介绍的存储抽象一起构成了Lucene的索引核心部分。无论是对外接口中的查询，还是分析各种文本以进一步生成索引，都需要直接调用这部分来获得对索引文件的访问能力，因此，这部分在系统中至关重要。构建一个高效的、易使用的索引构建逻辑，即是Lucene在这一部分需要达到的目的。

    从面向对象的经典思考方式出发来看，我们只需要使用继承体系来表达图3.1中的各个概念，就可以通过这个继承体系来控制索引文件的结构，然后设计合适的永久化方法，以及接受分析token流的操作，即可将索引构建逻辑完成。原理上就是这样的简单。由于两个关键的概念document和field都已经在org.apache.lucene.document中当作基础类定义过了，因此实际上Lucene在这部分需要完善的概念结构还有segment和term。在此基础上继续编写各个逻辑结构的永久化方法，然后提供一个进入的接口方法，即是宣告完成了这个过程。其中永久化的部分，Lucene使用了另外实现一个代理类的方式来实现，即对于某个类X，存在XWriter类和XReader类来负责写出和读入的功能；用作永久化功能的类是被永久化的类的友元。

    在接下来的分析过程中，我们按照这样一个思路，以UML图和对象体系的描述来叙述这部分的设计和实现，然后通过内部的数据流理清楚调用时序。

二、             对象体系与UML图

1．  项（Term）

这部分主要是分析针对项（Term）这个概念所做的设计，包括概念所实际涉及的类、永久化类。首先，我们从图3.2和阅读参考文献3知道，项（Term）所表示的是一个字符串，它拥有域、频数和位置信息等等属性。因此，Lucene中设计了两个类来表示这个概念，如下图

图 4.1 UML图（－）

上图中，有意的突出了类Term和TermInfo中的数据成员，因为它反映了对于项（Term）这个概念的具体表示。同时上图中也同时列出了用于永久化项（Term）的代理类TermInfosWriter和TermInfosReader，它们完成永久化的功能，需要注意的是，TermInfosReader内部使用了数组indexTerms和indexInfos来存储一系列项；而TermInfosWriter则是一个类似于链表的结构，通过一个other指向下一个TermInfosWriter，每一个TermInfosWriter只负责本身那个lastTerm和lastTi的永久化工作。这是一个设计上的技巧，通过批量读取（或者称为缓冲的方式）来获得读入时候的效率优化；而通过一个链表式的、各负其责的方式，来获得写出时候的设计简化。

项（term）这部分的设计中，还有一些重要的接口和类，我们先介绍如下，同样我们也先展示UML图

图 4.2 UML图（二）

图4.2中，我们看到三个类：TermEnum、TermDocs与TermPositions，第一个是抽象类，后两个都是接口。TermEnum的设计主要用在后面Segment和Document等等的实现中，以提供枚举其中每一个项（Term）的能力。TermDocs是一个接口，用来继承以提供返回<document, frequency>值对的能力，通过这个接口就可以获得某个项（Term）在某个文档中出现的频数。TermPositions则是在TermDocs上的扩展，将项（Term）在文档中的位置信息也表示出来。TermDocs（TermPositions）接口的使用方式类似于java中的Enumration接口，即通过next方法跳转，通过doc，freq等方法获得当前的属性值。

2．  域（Field）

由于Field的基本概念在org.apache.lucene.document中已经做了定义，因此在这部分主要是针对项文件（.fnm文件、.fdx文件、.fdt文件）所需要的信息再来设计一些类。

图 4.3 UML图（三）

图 4.3中展示的，就是表示与域（Field）所关联的属性信息的类。其中isIndexed表示的这个域的值是否被索引过，即值是否被分词然后索引；另外两个属性所表示的意思则很明显：一个是域的名字，一个是域的编号。

接下来我们来看关于域表和存取逻辑的UML图。

图 4.4 UML图（四）

FieldInfos即为域表的概念表示，内部采用了冗余的方式以获取在通过域的编号访问或者通过域的名字来访问时候的高效率。FieldsReader与FieldsWriter则分别是写出和读入的代理类。在功能和实现上，这两个类都比较简单。至于FieldInfos中采用的冗余方式，则是基于域的数目相对比较少而做出的一种折衷处理。

3．  文档（document）

文档（document）同样也是在org.apache.lucene.document中定义过的结构。由于对于这部分比较重要，我们也来看看其UML图。

图 4.5 UML图（五）

在图4.5中我们看到，Document的设计基本上沿用了链表的处理方法。左边的Document类作为一个数据外包类，用来提供对于内部结构DocumentFieldList的增加删除访问操作等等。DocumentFieldList才是实际上的数据存储单位，它用了链表的处理方法，直接指向一个当前的Field对象和下一个DocumentFieldList对象，这个与前面的类似。为了能够逐个访问链表中的节点，还设计了DocumentFieldEnumeration枚举类。

图 4.6 UML图（六）

    实际上定义于org.apache.lucene.index中的有关于Document的就是永久化的代理类。在图4.6中给出了其UML图。需要说明的是为什么没有出现读入的方法：这个方法已经隐含在图4.5中Document类中的add方法中了，结合图2.4中的程序代码段，我们就能够清楚的理解这种设计。

4．  段（segment）

段（Segment）这一部分设计的比较特殊，在实现简单的对象结构之上，还特意的设计了用于段之间合并的类。接下来，我们仍然采取对照UML分析的方式逐个叙述。接下来我们看Lucene中如何表示段这个概念。

图 4.7 UML图（七）

Lucene定义了一个类SegmentInfo用来表示每一个段（Segment）的信息，包括名字（name）、含有的文档的数目（docCount）和段所位于的目录的位置（dir）。根据索引文件中的段的意义，有了这三点，就能唯一确定一个段了。SegmentInfos这个类则是用来表示一个段的链表（从标准的java.util.Vector继承而来），实际上，也就是索引（index）的意思了。需要注意的是，这里并没有在SegmentInfo中安插一个文档（document）的链表。这样做的原因牵涉到Lucene内部对于文档（相当于一个被索引文件）的处理；Lucene内部采用了赋予文档编号，给域赋值的方式来处理文档，即加入的文档顺次编号，以后用文档号表示文档，而路径信息，文件名字等等在以后索引查找需要的属性，都作为域存储下来；因此SegmentInfo中并没有另外存储一个文档（document）的链表，对于这些的写出和读入，则交给了永久化的代理类来做。

图 4.8 UML图（八）

图4.8给出了负责段（segment）的读入操作的代理类，而负责段（segment）的写出操作也同样没有定义，这些操作都直接实现在了类IndexWriter类中（后面会详细分析）。段的操作同样采用了之前的数组或者说是缓冲的处理方式，相关的细节也不在这里详细叙述了。

然后，针对前面项（term）那部分定义的几个接口，段（segment）这部分也需要做相应的接口实现，因为提供直接遍历访问段中的各个项的能力对于检索来说，无疑是十分重要的。即这部分的设计，实际上都是在为了检索在服务。

图 4.9 UML图（九）

图 4.10 UML图（十）

图4.9和图4.10分别展示了前面项（term）那里定义的接口是如何在这里通过继承实现的。Lucene在处理这部分的时候，也是分成两部分（Segment与Segments开头的类）来实现，而且很合理的运用了数组的技法，以及注意了继承重用。但是细化到局部，终归是比较简单的按照语义来获得结果而已了，因此关于更多的也就不多做分析了，我们完全可以通过阅读源代码来解决。

接下来所介绍的，就是在Lucene的设计过程中比较特殊的一个部分：段合并类（SegmentMerger）。这首先需要介绍Lucene中的建立索引时的段合并策略。

Lucene为了兼顾建立索引时的效率和读取索引查找的速度，引入了分小段建立索引的方式，即每一次批量建立索引时，先在内存中的虚拟文件系统中为每一个文档单独建立一个段，然后在输出的时候将这些段合并之后输出成为索引文件，这时仅仅存在一个段。多次建立的索引后，如果想优化索引文件，也可采取合并段的方法，将索引中的段合并成为一个段。我们来看一下在IndexWriter类中相应的方法的实现，来了解一下这中建立索引的实现。

    对于上面的代码，我们不做过多注释了，结合源码中的注解应该很容易理解。在最后那个mergeSegments函数中，将用到几个重要的类结构，它们记录了合并时候的一些重要信息，完成合并时候的工作。接下来，我们来看这几个类的UML图。

图 4.12 UML图（十一）

从图4.12中，我们看到Lucene设计一个类SegmentMergeInfo用来保存每一个被合并的段的信息，也保存能够访问其内部的接口句柄，也就是说合并时的操作使用这个类作为对被合并的段的操作代理。类SegmentMergeQueue则设计为org.apache.lucene.util.PriorityQueue的子类，做为SegmentMergeInfo的容器类，而且附带能够自动排序。SegmentMerger是主要进行操作的类，里面各个方法环环相扣，分别完成合并各个数据项的问题。

5．  IndexReader类与IndexWirter类

最后剩下的，就是整个索引逻辑部分的使用接口类了。外界通过这两个类以及文档（document）类的构造函数调用之，比如图2.4中的代码示例所示。下面我们来看一下这部分最后两个类的UML图。

图 4.13 UML图（十二）

    IndexWriter的设计与IndexReader的设计很不相同，前者是一个实现类，而后者是一个抽象类，带有没有实现的接口。IndexWriter的主要作用就是接收新加入的文档（document），然后在内部为之生成相应的小段，最后再合并并向索引文件中输出，图4.11中已经给出了一些实现的代码。由于Lucene在面向对象上封装的努力，通过各个构造函数就已经完成了对于各个概念的构造过程，剩下部分的代码主要是依据各个数组或者是链表中的信息，逐个逐个的将信息写出到相应的文件中去了。IndexReader部分则只是做了接口设计，没有具体的实现，这个和本部分所完成的主要功能有关：索引构建逻辑。设计这个抽象类的目的是，预先完成一些函数，为以后的检索（search）部分的各种形式的IndexReader铺平道路，也是利用了在同一个包内可以方便访问其它类的保护变量这个java语言的限制。

    到此，在索引构建逻辑部分出现的类我们就分析完毕了，需要说明主要是做的一个宏观上的组成结构上的分析，并指出一些实现上的要点。具体的实现，由于Lucene的开放源码而显得并不是非常的重要，因为Lucene在做到良好的面相对象设计之后，实际带来的是局部复杂性的减小，因此某一些单独的函数或者实现就比较容易编写，也容易让人阅读。本文不再继续叙述这方面的细节，作为一个总结，下一个部分我们通过索引构建逻辑的数据流图的方式，再来理清楚一下索引构建逻辑这部分的调用时序。

三、             数据流逻辑

从宏观上明白一个系统的设计，理清楚其中的运行规律，最好的方式应该是通过数据流图。在分析了各个位于索引构建逻辑部分的类的设计之后，我们接下来就通过分析数据流图的方式来总结一下。但是由于之前提到的原因：索引读入部分在这一部分并没有完全实现，所以我们在数据流图中主要给出的是索引构建的数据流图。

图 4.14 索引构建部分的数据流逻辑

合并输出

字节流输入

内存文件系统

writeNorms写出标准化因子

sortPostingTable排序位置信息

writePostings写出索引信息

invertDocument分析文档

addDocument生成小段

加入document对象

以document对象方式传入

调用

生成field对象，根据对象性质不同，为值赋予String值，或者是Reader值

生成document对象，调用add方法加入field对象

通过java语言的io类以输入流方式传入

对于图4.14中所描述的内容，结合Lucene源代码中的一些文件看，能够加深理解。准备阶段可以参考demo文件夹中的org.apache.lucene.demo.IndexFiles类和java文件夹中的org.apache.lucene.document文件包。索引构建阶段的主要源码位于java文件夹中org.apache.lucene.index.IndexWriter类，因此这部分可以结合这个类的实现来看。至于内存文件系统，比较复杂，但是这时的逻辑相对简单，因此也不难理解。

    上面的数据流图十分清楚的勾画除了整个索引构建逻辑这部分的设计：通过层层嵌套的类结构，在构建时候即分步骤有计划的生成了索引结构，将之存储到内存中的文件系统中，然后通过对内存中的文件系统优化合并输出到实际的文件系统中。

四、             关于cLucene项目

前面的三个部分，已经完成了分析索引构建逻辑的任务，这里我们还是有针对性的谈谈我们这次的毕业设计项目cLucene在这一部分的情况。

在实现这部分的时候，为了将一些java语法中比较特殊的部分，比如内隐类、同步函数、同步对象等等，我们不得不采用了一些比较晦涩和艰深的C++语法，在OpenTop这个类库所提供的类似于java语言的设施上来实现。这个尤其体现在实现Segment相关类时，为了处理原来java源代码中用内隐类实现的Lock文件创建机制的时候，我们不得不定义了大量的cLucene::store::With的子类，并为之传入调用类的指针，设置它为调用类的友元，才得以精确的模拟了原有的语义。陷于我们这次的重写以移植为主，系统结构基本上没有大的变化，不得不产生这种重复而且大量的工作。如果需要改进这中状况，我们应该考虑按照C++语言的特点来设计索引构建部分的类库继承结构，但是很可惜在本文成文之前，时间不允许我们这样做。

来自java语法的特殊性只是我们解决问题的一个方面，我们还需要处理引用的调用方式。由于java语言拥有了垃圾收集机制，因此得以将一切的参数形式看作为引用，而不考虑其分配与消亡的问题。C++语言并不具备这种机制，它需要程序员自行管理分配空间与销毁对象的问题。在这里，我们使用的是来自OpenTop中所引入的计数指针RefPtr<>模板，它能够模拟指针的语义，并且计算指针被引用的次数，在引用次数为0时就自动释放资源：这是一种类似于java语言中引用的方式，不过它显得更加高效率。我们在cLucene的实现中大量的使用了计数指针模板。

    除此之外，我们没有改变Lucene所定义的索引构建逻辑的结构和语义，我们实现的是一个完全和java版本Lucene兼容的版本。

结论

本文深入细致的分析了开放源代码全文检索系统Lucene的系统结构、索引文件格式和源码的部分实现，介绍了在Lucene系统下面的应用和一个用C++语言重写的全文检索系统cLucene。全文通过图表和文字说明结合的方式，理清了Lucene的系统结构关系，揭示了其运行时的数据流程，总结了其索引文件格式，并且从有助于理解源代码的角度宏观的分析了索引核心部分的源代码实现。

在分析Lucene系统的同时，本文作者及同在项目组的同学共同进行了cLucene系统的开发工作，以C++语言实现了一个兼容Lucene索引文件格式的新的全文检索系统。这个系统的目的旨在通过C++语言使之能够在更多范围内应用以及提高其运行的效率。由于时间的关系，这个项目并没有完成，还需要继续的开发。

注解：

[1] WWW ：Word Wide Web的缩写词，但是此处指应用程序具有被web访问的能力。

[2] XML ：Extensible Markup Language（可扩展标记语言）的缩写，这里指一种文件的存储结构，关于XML的更多信息见http://www.w3c.org/xml

[3] HTML ：Hypertext Markup Language（超文本标记语言）的缩写，这里也是指一种文件的存储结构，关于HTML的更多信息见http://www.w3c.org/MarkUp

[4] apache软件基金会 ：著名的开放源代码组织，开发了Apache Web服务器、Ant编译工具等等著名程序，jakarta项目组是其下面一个大的子项目组，主要用java语言开发开放源代码软件，更多信息可见http://www.apache.org，http://jakarta.apache.org

[5] 开放源代码 ：英文为Open Source，自70年代开始由自由软件基金会（Free Software Foundation）倡导而迅速流行于互联网络的软件开发和授权方式，最大的特点是在用户遵守一定协议的情况下软件源代码开放，更多信息可见http://www.opensource.org/

[6] V-Twin搜索引擎 ：Apple的Copland操作系统的成就之一，作为Apple操作系统内建的检索引擎存在

[7] Excite ：这里指搜索引擎提供商Excite公司，互联网上的最早的搜索引擎之一，更多信息可见http://www.excite.com/

[8] SourceForge ： 互联网上最大的网上开发平台，提供CVS等各种开发者服务，是大量开放源代码软件的发布地，更多信息可见http://www.sourcefoege.net

[9] eclipse ：IBM公司所主创地一个开放源代码的集成开发工具，用java实现，在2.1版本中开始使用Lucene作为索引引擎，更多信息可见http://www.eclipse.org

[10] Web Sphere ：IBM公司的软件开发套件，主要是基于eclipse改进而来

[11] Fuzzy Search ：模糊查询，指可以按照相似度或者各种转义字符查找，比如查找“roam~”就可能查找到foam或者roams

[12] Apache Software License ：apache软件基金会所制定的用户协议，基本要点是软件开放源代码，保留apache软件基金会在源码中的声明，但是不强制要求修改过的软件也开放源代码。更多信息可见http://www.opensource.org/licenses/apachepl.php

[13] PDF ：可移植文档格式文件，由Adobe公司提出，已经成为标准的文档交换格式。

[14] .net framework ：微软公司所推出的软件开发平台，面向下一代的Web开发与应用程序开发，与java有一定的相似之处。更多信息可见http://www.microsoft.com/net/

[15] ISO C++ ：经过国际标准化组织（ISO）所标准化之后的C++语言版本，这里指开发语言只使用标准化之后的特性

[16] STLport 4.5.3 ：C++语言的标准模板库（STL）的一个实现版本，由SGI STL版本改进而来，特点是能够适应多个平台与多个编译器。更多信息可见http://www.stlport.org

[17] OpenTop 1.1 ：一套C++语言库，提供了类似于java语言的多种封装，比如文件系统，容器等等。更多信息可见http://www.sourceforge.net/projects/opentop

[18] GNU General Public License (GPL) ：一个软件许可协议，特点是不仅仅开放源代码，而且要求修改者也开放源代码。更多信息可见http://www.opensource.org/licenses/gpl-license.php

[19] UCS-2 ：Unicode编码方式的一种，对于文字使用定长的两字节编码，可以最多容纳65535个字符的编码方案。更多信息可见http://www.unicode.org/

[20] UTF-8 ： Unicode编码方式的一种，特点是采用不定长字节编码，适合做为文件存储的编码方案。更多信息可见http://www.unicode.org

[21] 倒排索引结构 ：经典索引结构的一种，特点是存储的是字串与所在位置信息的一个配对，刚好与文章中位置与字串的关系相反，是一种普遍采用得建立索引方式。

[22] UML ：Unified Modeling Language（统一建模语言）的缩写，其定义了一套共通的软件建模的标准语言，用于描述软件的构造、模型等等。更多信息可见http://www.uml.org/

参考文献：

1．   车东，《在应用中加入全文检索功能 — 基于Java的全文索引引擎Lucene简介》，http://www.chedong.com/tech/lucene.html

2．   Brian Goetz，《The Lucene search engine: Powerful, flexible, and free》，http://www.javaworld.com/javaworld/jw-09-2000/jw-0915-lucene.html

3．   Apache软件基金会Lucne项目文档，《Index File Formats》，http://jakarta.apache.org/lucene/docs/fileformats.html

4．   Bruce Exkel著，侯捷译，《Java编程思想（第二版）》，机械工业出版社（北京），2002，ISBN-7-111-10441-2

5．   Erich Gamma，Richard Helm，Ralph Johnson，John Vlissides著，李英军，马晓星等译，《设计模式 可复用面相对象软件的基础》，机械工业出版社（北京），2000，ISBN 7-111-07575-7

文章来源：http://liyu2000.nease.net/article/Lucene/bachelor-paper.htm