第一節(jié) 全文檢索系統(tǒng)與Lucene簡介

一、             什么是全文檢索與全文檢索系統(tǒng)？

全文檢索是指計算機索引程序通過掃描文章中的每一個詞，對每一個詞建立一個索引，指明該詞在文章中出現(xiàn)的次數(shù)和位置，當用戶查詢時，檢索程序就根據(jù)事先建立的索引進行查找，并將查找的結(jié)果反饋給用戶的檢索方式。這個過程類似于通過字典中的檢索字表查字的過程。

全文檢索的方法主要分為按字檢索和按詞檢索兩種。按字檢索是指對于文章中的每一個字都建立索引，檢索時將詞分解為字的組合。對于各種不同的語言而言，字有不同的含義，比如英文中字與詞實際上是合一的，而中文中字與詞有很大分別。按詞檢索指對文章中的詞，即語義單位建立索引，檢索時按詞檢索，并且可以處理同義項等。英文等西方文字由于按照空白切分詞，因此實現(xiàn)上與按字處理類似，添加同義處理也很容易。中文等東方文字則需要切分字詞，以達到按詞索引的目的，關(guān)于這方面的問題，是當前全文檢索技術(shù)尤其是中文全文檢索技術(shù)中的難點，在此不做詳述。

全文檢索系統(tǒng)是按照全文檢索理論建立起來的用于提供全文檢索服務的軟件系統(tǒng)。一般來說，全文檢索需要具備建立索引和提供查詢的基本功能，此外現(xiàn)代的全文檢索系統(tǒng)還需要具有方便的用戶接口、面向WWW^[1]的開發(fā)接口、二次應用開發(fā)接口等等。功能上，全文檢索系統(tǒng)核心具有建立索引、處理查詢返回結(jié)果集、增加索引、優(yōu)化索引結(jié)構(gòu)等等功能，外圍則由各種不同應用具有的功能組成。結(jié)構(gòu)上，全文檢索系統(tǒng)核心具有索引引擎、查詢引擎、文本分析引擎、對外接口等等，加上各種外圍應用系統(tǒng)等等共同構(gòu)成了全文檢索系統(tǒng)。圖1.1展示了上述全文檢索系統(tǒng)的結(jié)構(gòu)與功能。

在上圖中，我們看到：全文檢索系統(tǒng)中最為關(guān)鍵的部分是全文檢索引擎，各種應用程序都需要建立在這個引擎之上。一個全文檢索應用的優(yōu)異程度，根本上由全文檢索引擎來決定。因此提升全文檢索引擎的效率即是我們提升全文檢索應用的根本。另一個方面，一個優(yōu)異的全文檢索引擎，在做到效率優(yōu)化的同時，還需要具有開放的體系結(jié)構(gòu)，以方便程序員對整個系統(tǒng)進行優(yōu)化改造，或者是添加原有系統(tǒng)沒有的功能。比如在當今多語言處理的環(huán)境下，有時需要給全文檢索系統(tǒng)添加處理某種語言或者文本格式的功能，比如在英文系統(tǒng)中添加中文處理功能，在純文本系統(tǒng)中添加XML^[2]或者HTML^[3]格式的文本處理功能，系統(tǒng)的開放性和擴充性就十分的重要。

二、             什么是Lucene？

Lucene是apache軟件基金會^[4] jakarta項目組的一個子項目，是一個開放源代碼^[5]的全文檢索引擎工具包，即它不是一個完整的全文檢索引擎，而是一個全文檢索引擎的架構(gòu)，提供了完整的查詢引擎和索引引擎，部分文本分析引擎（英文與德文兩種西方語言）。Lucene的目的是為軟件開發(fā)人員提供一個簡單易用的工具包，以方便的在目標系統(tǒng)中實現(xiàn)全文檢索的功能，或者是以此為基礎建立起完整的全文檢索引擎。

Lucene的原作者是Doug Cutting，他是一位資深全文索引/檢索專家，曾經(jīng)是V-Twin搜索引擎^[6]的主要開發(fā)者，后在Excite^[7]擔任高級系統(tǒng)架構(gòu)設計師，目前從事于一些Internet底層架構(gòu)的研究。早先發(fā)布在作者自己的http://www.lucene.com/，后來發(fā)布在SourceForge^[8]，2001年年底成為apache軟件基金會jakarta的一個子項目：http://jakarta.apache.org/lucene/。

三、             Lucene的應用、特點及優(yōu)勢

作為一個開放源代碼項目，Lucene從問世之后，引發(fā)了開放源代碼社群的巨大反響，程序員們不僅使用它構(gòu)建具體的全文檢索應用，而且將之集成到各種系統(tǒng)軟件中去，以及構(gòu)建Web應用，甚至某些商業(yè)軟件也采用了Lucene作為其內(nèi)部全文檢索子系統(tǒng)的核心。apache軟件基金會的網(wǎng)站使用了Lucene作為全文檢索的引擎，IBM的開源軟件eclipse^[9]的2.1版本中也采用了Lucene作為幫助子系統(tǒng)的全文索引引擎，相應的IBM的商業(yè)軟件Web Sphere^[10]中也采用了Lucene。Lucene以其開放源代碼的特性、優(yōu)異的索引結(jié)構(gòu)、良好的系統(tǒng)架構(gòu)獲得了越來越多的應用。

Lucene作為一個全文檢索引擎，其具有如下突出的優(yōu)點：

（1）索引文件格式獨立于應用平臺。Lucene定義了一套以8位字節(jié)為基礎的索引文件格式，使得兼容系統(tǒng)或者不同平臺的應用能夠共享建立的索引文件。

（2）在傳統(tǒng)全文檢索引擎的倒排索引的基礎上，實現(xiàn)了分塊索引，能夠針對新的文件建立小文件索引，提升索引速度。然后通過與原有索引的合并，達到優(yōu)化的目的。

（3）優(yōu)秀的面向?qū)ο蟮南到y(tǒng)架構(gòu)，使得對于Lucene擴展的學習難度降低，方便擴充新功能。

（4）設計了獨立于語言和文件格式的文本分析接口，索引器通過接受Token流完成索引文件的創(chuàng)立，用戶擴展新的語言和文件格式，只需要實現(xiàn)文本分析的接口。

（5）已經(jīng)默認實現(xiàn)了一套強大的查詢引擎，用戶無需自己編寫代碼即使系統(tǒng)可獲得強大的查詢能力，Lucene的查詢實現(xiàn)中默認實現(xiàn)了布爾操作、模糊查詢（Fuzzy Search^[11]）、分組查詢等等。

    面對已經(jīng)存在的商業(yè)全文檢索引擎，Lucene也具有相當?shù)膬?yōu)勢。首先，它的開發(fā)源代碼發(fā)行方式（遵守Apache Software License^[12]），在此基礎上程序員不僅僅可以充分的利用Lucene所提供的強大功能，而且可以深入細致的學習到全文檢索引擎制作技術(shù)和面相對象編程的實踐，進而在此基礎上根據(jù)應用的實際情況編寫出更好的更適合當前應用的全文檢索引擎。在這一點上，商業(yè)軟件的靈活性遠遠不及Lucene。其次，Lucene秉承了開放源代碼一貫的架構(gòu)優(yōu)良的優(yōu)勢，設計了一個合理而極具擴充能力的面向?qū)ο蠹軜?gòu)，程序員可以在Lucene的基礎上擴充各種功能，比如擴充中文處理能力，從文本擴充到HTML、PDF^[13]等等文本格式的處理，編寫這些擴展的功能不僅僅不復雜，而且由于Lucene恰當合理的對系統(tǒng)設備做了程序上的抽象，擴展的功能也能輕易的達到跨平臺的能力。最后，轉(zhuǎn)移到apache軟件基金會后，借助于apache軟件基金會的網(wǎng)絡平臺，程序員可以方便的和開發(fā)者、其它程序員交流，促成資源的共享，甚至直接獲得已經(jīng)編寫完備的擴充功能。最后，雖然Lucene使用Java語言寫成，但是開放源代碼社區(qū)的程序員正在不懈的將之使用各種傳統(tǒng)語言實現(xiàn)（例如.net framework^[14]），在遵守Lucene索引文件格式的基礎上，使得Lucene能夠運行在各種各樣的平臺上，系統(tǒng)管理員可以根據(jù)當前的平臺適合的語言來合理的選擇。

四、             本文的重點問題與cLucene項目

作為中國人民大學信息學院99級本科生的一個畢業(yè)設計項目，我們對Lucene進行了深入的研究，包括系統(tǒng)的結(jié)構(gòu)，索引文件結(jié)構(gòu)，各個部分的實現(xiàn)等等。并且我們啟動了cLucene項目，做為一個Lucene的C++語言的重新實現(xiàn)，以期望帶來更快的速度和更加廣泛的應用范圍。我們先分析了系統(tǒng)結(jié)構(gòu)，文件結(jié)構(gòu)，然后在研究各個部分的具體實現(xiàn)的同時開始進行的cLucene實現(xiàn)。限于時間的限制，到本文完成為止，cLucene項目并沒有完成，對于Lucene的具體實現(xiàn)部分也僅僅完成到了索引引擎部分。

接下來的部分，本文將對Lucene的系統(tǒng)結(jié)構(gòu)、文件結(jié)構(gòu)、索引引擎部分做一個徹底的分析。以期望提供對Lucene全文檢索引擎的系統(tǒng)架構(gòu)和部分程序?qū)崿F(xiàn)的清晰的了解。cLucene項目則作為一個開放源代碼的項目，繼續(xù)進行的開發(fā)。

       有關(guān)cLucene項目的一些信息：

n         開發(fā)語言：ISO C++^[15]，STLport 4.5.3^[16]，OpenTop 1.1^[17]

n         目標平臺：Win32，POSIX

n         授權(quán)協(xié)議：GNU General Public License (GPL)^[18]

第二節(jié) Lucene系統(tǒng)結(jié)構(gòu)分析

一、             系統(tǒng)結(jié)構(gòu)組織

Lucene作為一個優(yōu)秀的全文檢索引擎，其系統(tǒng)結(jié)構(gòu)具有強烈的面向?qū)ο筇卣鳌Ｊ紫仁嵌x了一個與平臺無關(guān)的索引文件格式，其次通過抽象將系統(tǒng)的核心組成部分設計為抽象類，具體的平臺實現(xiàn)部分設計為抽象類的實現(xiàn)，此外與具體平臺相關(guān)的部分比如文件存儲也封裝為類，經(jīng)過層層的面向?qū)ο笫降奶幚恚罱K達成了一個低耦合高效率，容易二次開發(fā)的檢索引擎系統(tǒng)。

以下將討論Lucene系統(tǒng)的結(jié)構(gòu)組織，并給出系統(tǒng)結(jié)構(gòu)與源碼組織圖：

    從圖中我們清楚的看到，Lucene的系統(tǒng)由基礎結(jié)構(gòu)封裝、索引核心、對外接口三大部分組成。其中直接操作索引文件的索引核心又是系統(tǒng)的重點。Lucene的將所有源碼分為了7個模塊（在java語言中以包即package來表示），各個模塊所屬的系統(tǒng)部分也如上圖所示。需要說明的是org.apache.lucene.queryPaser是做為org.apache.lucene.search的語法解析器存在，不被系統(tǒng)之外實際調(diào)用，因此這里沒有當作對外接口看待，而是將之獨立出來。

    從面象對象的觀點來考察，Lucene應用了最基本的一條程序設計準則：引入額外的抽象層以降低耦合性。首先，引入對索引文件的操作org.apache.lucene.store的封裝，然后將索引部分的實現(xiàn)建立在（org.apache.lucene.index）其之上，完成對索引核心的抽象。在索引核心的基礎上開始設計對外的接口org.apache.lucene.search與org.apache.lucene.analysis。在每一個局部細節(jié)上，比如某些常用的數(shù)據(jù)結(jié)構(gòu)與算法上，Lucene也充分的應用了這一條準則。在高度的面向?qū)ο罄碚摰闹蜗拢沟?/span>Lucene的實現(xiàn)容易理解，易于擴展。

    Lucene在系統(tǒng)結(jié)構(gòu)上的另一個特點表現(xiàn)為其引入了傳統(tǒng)的客戶端服務器結(jié)構(gòu)以外的的應用結(jié)構(gòu)。Lucene可以作為一個運行庫被包含進入應用本身中去，而不是做為一個單獨的索引服務器存在。這自然和Lucene開放源代碼的特征分不開，但是也體現(xiàn)了Lucene在編寫上的本來意圖：提供一個全文索引引擎的架構(gòu)，而不是實現(xiàn)。

二、             數(shù)據(jù)流分析

理解Lucene系統(tǒng)結(jié)構(gòu)的另一個方式是去探討其中數(shù)據(jù)流的走向，并以此摸清楚Lucene系統(tǒng)內(nèi)部的調(diào)用時序。在此基礎上，我們能夠更加深入的理解Lucene的系統(tǒng)結(jié)構(gòu)組織，以方便以后在Lucene系統(tǒng)上的開發(fā)工作。這部分的分析，是深入Lucene系統(tǒng)的鑰匙，也是進行重寫的基礎。

   我們來看看在Lucene系統(tǒng)中的主要的數(shù)據(jù)流以及它們之間的關(guān)系圖：

索引查找邏輯

索引構(gòu)建邏輯

查詢語句語法分析邏輯

詞法分析邏輯

存儲抽象

    圖2.2很好的表明了Lucene在內(nèi)部的數(shù)據(jù)流組織情況，并且沿著數(shù)據(jù)流的方向我們也可以對與Lucene內(nèi)部的執(zhí)行時序有一個清楚的了解。現(xiàn)在將圖中的涉及到的流的類型與各個邏輯對應系統(tǒng)的相關(guān)部分的關(guān)系說明一下。

    圖中共存在4種數(shù)據(jù)流，分別是文本流、token流、字節(jié)流與查詢語句對象流。文本流表示了對于索引目標和交互控制的抽象，即用文本流表示了將要索引的文件，用文本流向用戶輸出信息；在實際的實現(xiàn)中，Lucene中的文本流采用了UCS-2^[19]作為編碼，以達到適應多種語言文字的處理的目的。Token流是Lucene內(nèi)部所使用的概念，是對傳統(tǒng)文字中的詞的概念的抽象，也是Lucene在建立索引時直接處理的最小單位；簡單的講Token就是一個詞和所在域值的組合，后面在敘述文件格式時也將繼續(xù)涉及到token，這里不詳細展開。字節(jié)流則是對文件抽象的直接操作的體現(xiàn)，通過固定長度的字節(jié)（Lucene定義為8比特位長，后面文件格式將詳細敘述）流的處理，將文件操作解脫出來，也做到了與平臺文件系統(tǒng)的無關(guān)性。查詢語句對象流則是僅僅在查詢語句解析時用到的概念，它對查詢語句抽象，通過類的繼承結(jié)構(gòu)反映查詢語句的結(jié)構(gòu)，將之傳送到查找邏輯來進行查找的操作。

    圖中的涉及到了多種邏輯，基本上直接對應于系統(tǒng)某一模塊，但是也有跨模塊調(diào)用的問題發(fā)生，這是因為Lucene的重用程度非常好，因此很多實現(xiàn)直接調(diào)用了以前的工作成果，這在某種程度上其實是加強了模塊耦合性，但是也是為了避免系統(tǒng)的過于龐大和不必要的重復設計的一種折衷體現(xiàn)。詞法分析邏輯對應于org.apache.lucene.analysis部分。查詢語句語法分析邏輯對應于org.apache.lucene.queryParser部分，并且調(diào)用了org.apache.lucene.analysis的代碼。查詢結(jié)束之后向評分排序邏輯輸出token流，繼而由評分排序邏輯處理之后給出文本流的結(jié)果，這一部分的實現(xiàn)也包含在了org.apache.lucene.search中。索引構(gòu)建邏輯對應于org.apache.lucene.index部分。索引查找邏輯則主要是org.apache.lucene.search，但是也大量的使用了org.apache.lucene.index部分的代碼和接口定義。存儲抽象對應于org.apache.lucene.store。沒有提到的模塊則是做為系統(tǒng)公共基礎設施存在。

三、             基于Lucene的應用開發(fā)

通過以上的系統(tǒng)結(jié)構(gòu)分析和數(shù)據(jù)流分析，我們已經(jīng)很清楚的了解了Lucene的系統(tǒng)的結(jié)構(gòu)特征。在此基礎上，我們可以通過擴充Lucene系統(tǒng)來完成一個完備的全文檢索引擎，緊接著還可以在全文檢索引擎的基礎上構(gòu)建各種應用系統(tǒng)。鑒于本文的目的并不在此，以下我們只是略為敘述一下相關(guān)的步驟，從而給出應用開發(fā)的一些思路。

首先，我們需要的是按照目標語言的詞法結(jié)構(gòu)來構(gòu)建相應的詞法分析邏輯，實現(xiàn)Lucene在org.apache.lucene.analysis中定義的接口，為Lucene提供目標系統(tǒng)所使用的語言處理能力。Lucene默認的已經(jīng)實現(xiàn)了英文和德文的簡單詞法分析邏輯（按照空格分詞，并去除常用的語法詞，如英語中的is，am，are等等）。在這里，主要需要參考實現(xiàn)的接口在org.apache.lucene.analysis中的Analyzer.java和Tokenizer.java中定義，Lucene提供了很多英文規(guī)范的實現(xiàn)樣本，也可以做為實現(xiàn)時候的參考資料。其次，需要按照被索引的文件的格式來提供相應的文本分析邏輯，這里是指除開詞法分析之外的部分，比如HTML文件，通常需要把其中的內(nèi)容按照所屬于域分門別類加入索引，這就需要從org.apache.lucene.document中定義的類document繼承，定義自己的HTMLDocument類，然后就可以將之交給org.apache.lucene.index模塊來寫入索引文件。完成了這兩步之后，Lucene全文檢索引擎就基本上完備了。這個過程可以用下圖表示：

    當然，上面所示的僅僅只是對于Lucene的基本擴充過程，它將Lucene由不完備的變成完備的（尤其是對于非英語的語言檢索）。除此之外我們還可以在很多方面對Lucene進行改造。第一個方面即為按照文檔索引的域，比如標題，作者之類的信息對返回的查詢結(jié)果排序，這即需要改造Lucene的評分排序邏輯。默認的，Lucene采用其內(nèi)部的相關(guān)性方法來處理評分和排序，我們可以根據(jù)需要改變它。遺憾的是，這部分Lucene并沒有做到如同擴充詞法解析和文檔類型那樣的條理清晰，沒有留下很好的接口，因此需要仔細的分析其源代碼的實現(xiàn)，自行擴充等等。其他的方面，比如改進其索引的效率，改進其返回結(jié)果時候的緩沖機制等等，都是加強Lucene系統(tǒng)的方面，在此也不再敘述。

    完成了Lucene系統(tǒng)，之后就可以開始考慮其上的應用系統(tǒng)開發(fā)。如果應用系統(tǒng)也使用java語言開發(fā)，那么Lucene系統(tǒng)能夠方便的嵌入到整個系統(tǒng)中去，作為一個API集來調(diào)用。這個過程十分簡單，以下便是一個示例程序，配合注釋理解起來很容易。

圖 2.4 Lucene應用代碼示例

    或者，Lucene全文檢索引擎也可作為服務器程序啟動，但是這就需要用戶自行擴充其他應用與Lucene的接口。這個可以通過傳統(tǒng)的包裝方式，比如客戶服務器結(jié)構(gòu)，或者采用現(xiàn)在流行的Web方式。諸如此類的應用方案，本文也不再繼續(xù)敘述。參考Lucene的項目網(wǎng)站中的用戶郵件列表能找到更多的信息。

第三節(jié) Lucene索引文件格式分析

一、             Lucene源碼實現(xiàn)分析的說明

通過以上對Lucene系統(tǒng)結(jié)構(gòu)的分析，我們已經(jīng)大致的清楚了Lucene系統(tǒng)的組成，以及在Lucene系統(tǒng)之上的開發(fā)步驟。接下來，我們試圖來分析Lucene項目（采用Lucene 1.2版本）的源碼實現(xiàn)，考察其實現(xiàn)的細節(jié)。這不僅僅是我們嘗試用C++語言重新實現(xiàn)Lucene的必須工作，也是進一步做Lucene開發(fā)工作的必要準備。因此，這一部分所涉及到的內(nèi)容，對于Lucene上的應用開發(fā)也是有價值的，尤其是本部分所做的文件格式分析。

    由于本文建立在我們的畢設項目之上，且同時我們需要實現(xiàn)cLucene項目，因此很遺憾的我們并沒有完全的完成Lucene的所有源碼實現(xiàn)的分析工作。接下來的部分，我們將涉及的部分為Lucene文件格式分析，Lucene中的存儲抽象模塊分析，以及Lucene中的索引構(gòu)建邏輯模塊分析。這一部分，我們主要涉及到的是文件格式分析與存儲抽象模塊分析。

二、             Lucene索引文件格式

在Lucene的web站點上，有關(guān)于Lucene的文件格式的規(guī)范，其規(guī)定了Lucene的文件格式采取的存儲單位、組織結(jié)構(gòu)、命名規(guī)范等等內(nèi)容，但是它僅僅是一個規(guī)范說明，并沒有從實現(xiàn)者角度來衡量這個規(guī)范的實現(xiàn)。因此，我們以下的內(nèi)容，結(jié)合了我們自己的分析與文件格式的定義規(guī)范，以期望給出一個更加清晰的文件格式說明。具體的文檔規(guī)范可以參考后面的文獻2。

    首先在Lucene的文件格式中，以字節(jié)為基礎，定義了如下的數(shù)據(jù)類型：

表 3.1 Lucene文件格式中定義的數(shù)據(jù)類型

    以上的數(shù)據(jù)類型就是Lucene索引文件格式中用到的全部數(shù)據(jù)類型，由于它們都以字節(jié)為基礎定義而來，因此保證了是平臺無關(guān)，這也是Lucene索引文件格式平臺無關(guān)的主要原因。接下來我們看看Lucene索引文件的概念組成和結(jié)構(gòu)組成。

    以上就是Lucene的索引文件的概念結(jié)構(gòu)。Lucene索引index由若干段(segment)組成，每一段由若干的文檔（document）組成，每一個文檔由若干的域（field）組成，每一個域由若干的項（term）組成。項是最小的索引概念單位，它直接代表了一個字符串以及其在文件中的位置、出現(xiàn)次數(shù)等信息。域是一個關(guān)聯(lián)的元組，由一個域名和一個域值組成，域名是一個字串，域值是一個項，比如將“標題”和實際標題的項組成的域。文檔是提取了某個文件中的所有信息之后的結(jié)果，這些組成了段，或者稱為一個子索引。子索引可以組合為索引，也可以合并為一個新的包含了所有合并項內(nèi)部元素的子索引。我們可以清楚的看出，Lucene的索引結(jié)構(gòu)在概念上即為傳統(tǒng)的倒排索引結(jié)構(gòu)^[21]。

    從概念上映射到結(jié)構(gòu)中，索引被處理為一個目錄（文件夾），其中含有的所有文件即為其內(nèi)容，這些文件按照所屬的段不同分組存放，同組的文件擁有相同的文件名，不同的擴展名。此外還有三個文件，分別用來保存所有的段的記錄、保存已刪除文件的記錄和控制讀寫的同步，它們分別是segments，deletable和lock文件，都沒有擴展名。每個段包含一組文件，它們的文件擴展名不同，但是文件名均為記錄在文件segments中段的名字。讓我們看如下的結(jié)構(gòu)圖3.2。

項集合信息

項位置

項頻數(shù)

被刪除文檔

標準化因子

圖 3.2 Lucene索引文件結(jié)構(gòu)組成

segment1所含文件

項字典

域值存儲表

域集合信息

index

    關(guān)于圖3.2中的各個文件具體的內(nèi)部格式，在參考文獻3中，均可以找到詳細的說明。接下來我們從宏觀關(guān)系上說明一下這些文件組成。在這些宏觀上的關(guān)系理清楚之后，仔細閱讀參考文獻3，即可清楚的明白具體的Lucene文件格式。

    每個段的文件中，主要記錄了兩大類的信息：域集合與項集合。這兩個集合中所含有的文件在圖3.2中均有表明。由于索引信息是靜態(tài)存儲的，域集合與項集合中的文件組采用了一種類似的存儲辦法：一個小型的索引文件，運行時載入內(nèi)存；一個對應于索引文件的實際信息文件，可以按照索引中指示的偏移量隨機訪問；索引文件與信息文件在記錄的排列順序上存在隱式的對應關(guān)系，即索引文件中按照“索引項1、索引項2…”排列，則信息文件則也按照“信息項1、信息項2…”排列。比如在圖3.2所示文件中，segment1.fdx與segment1.fdt之間，segment1.tii與segment1.tis、segment1.prx、segment1.frq之間，都存在這樣的組織關(guān)系。而域集合與項集合之間則通過域的在域記錄文件（比如segment1.fnm）中所記錄的域記錄號維持對應關(guān)系，在圖3.2中segment1.fdx與segment1.tii中就是通過這種方式保持聯(lián)系。這樣，域集合和項集合不僅僅聯(lián)系起來，而且其中的文件之間也相互聯(lián)系起來。此外，標準化因子文件和被刪除文檔文件則提供了一些程序內(nèi)部的輔助設施（標準化因子用在評分排序機制中，被刪除文檔是一種偽刪除手段）。這樣，整個段的索引信息就通過這些文檔有機的組成。

    以上所闡述的，就是Lucene所采用的索引文件格式。基本上而言，它是一個倒排索引，但是Lucene在文件的安排上做了一些努力，比如使用索引/信息文件的方式，從文件安排的形式上提高查找的效率。這是一種數(shù)據(jù)庫之外的處理方法，其有其優(yōu)點（格式平臺獨立、速度快），也有其缺點（獨立性帶來的共享訪問接口問題等等），具體如何衡量兩種方法之間的利弊，本文這里就不討論了。

三、             一些公用的基礎類

分析完索引文件格式，我們接下來應該著手對存儲抽象也就是org.apache.lucenestore中的源碼做一些分析。我們先不著急分析這部分，而是分析圖2.1中基礎結(jié)構(gòu)封裝那一部分，因為這是整個系統(tǒng)的基石，然后我們在下一部分再來分析存儲抽象。

    基礎結(jié)構(gòu)封裝，或者基礎類，由org.apache.lucene.util和org.apache.lucene.document兩個包組成，前者定義了一些常量和優(yōu)化過的常用的數(shù)據(jù)結(jié)構(gòu)和算法，后者則是對于文檔（document）和域（field）概念的一個類定義。以下我們用列表的方式來分析這些封裝類，指出其要點。

表 3.2 基礎類包org.apache.lucene.util

表 3.3 基礎類包org.apache.lucene.document

總的來說，這兩個基礎類包中含有的類都比較簡單，通過閱讀源代碼，可以很容易的理解，因此這里不作過多的展開。

四、             存儲抽象

有了上面的知識，我們接下來來分析存儲抽象部分，也就是org.apache.lucene.store包。存儲抽象是唯一能夠直接對索引文件存取的包，因此其主要目的是抽象出和平臺文件系統(tǒng)無關(guān)的存儲抽象，提供諸如目錄服務（增、刪文件）、輸入流和輸出流。在分析其實現(xiàn)之前，首先我們看一下UML^[22]圖。

圖 3.3 存儲抽象實現(xiàn)UML圖（一）

圖 3.4 存儲抽象實現(xiàn)UML圖（二）

圖 3.4 存儲抽象實現(xiàn)UML圖（三）

    圖3.2到3.4展示了整個org.apache.lucene.store中主要的繼承體系。共有三個抽象類定義：Directory、InputStream和OutputStrem，構(gòu)成了一個完整的基于抽象文件系統(tǒng)的存取體系結(jié)構(gòu)，在此基礎上，實作出了兩個實現(xiàn)品：（FSDirectory，FSInputStream，FSOutputStream）和（RAMDirectory，RAMInputStream和RAMOutputStream）。前者是以實際的文件系統(tǒng)做為基礎實現(xiàn)的，后者則是建立在內(nèi)存中的虛擬文件系統(tǒng)。前者主要用來永久的保存索引文件，后者的作用則在于索引操作時是在內(nèi)存中建立小的索引，然后一次性的輸出合并到文件中去，這一點我們在后面的索引邏輯部分能夠看到。此外，還定以了org.apache.lucene.store.lock和org.apache.lucene.store.with兩個輔助內(nèi)部實現(xiàn)的類用在實現(xiàn)Directory方法的makeLock的時候，以在鎖定索引讀寫之前來讓客戶程序做一些準備工作。

    （FSDirectory，FSInputStream，FSOutputStream）的內(nèi)部實現(xiàn)依托于java語言中的io類庫，只是簡單的做了一個外部邏輯的包裝。這當然要歸功于java語言所提供的跨平臺特性，同時也帶了一些隱患：文件存取的效率提升需要依耐于文件類庫的優(yōu)化。如果需要繼續(xù)優(yōu)化文件存取的效率，應該還提供一個文件與目錄的抽象，以根據(jù)各種文件系統(tǒng)或者文件類型來提供一個優(yōu)化的機會。當然，這是應用開發(fā)者所不需要關(guān)系的問題。

    （RAMDirectory，RAMInputStream和RAMOutputStream）的內(nèi)部實現(xiàn)就比較直接了，直接采用了虛擬的文件RAMFile類（定義于文件RAMDirectory.java中）來表示文件，目錄則看作一個String與RAMFile對應的關(guān)聯(lián)數(shù)組。RAMFile中采用數(shù)組來表示文件的存儲空間。在此的基礎上，完成各項操作的實現(xiàn)，就形成了基于內(nèi)存的虛擬文件系統(tǒng)。因為在實際使用時，并不會牽涉到很大字節(jié)數(shù)量的文件，因此這種設計是簡單直接的，也是高效率的。

    這部分的實現(xiàn)在理清楚繼承體系后，相當?shù)暮唵巍Ｒ虼私酉聛淼牟糠郑覀兛梢酝ㄟ^直接閱讀源代碼解決。接下來我們看看這個部分的源代碼如何在實際中使用的。

    一般來說，我們使用的是抽象類提供的接口而不是實際的實現(xiàn)類本身。在實現(xiàn)類中一般都含有幾個靜態(tài)函數(shù)，比如createFile，它能夠返回一個OutputStream接口，或者openFile，它能夠返回一個InputStream接口，利用這些接口之中的方法，比如writeString，writeByte等等，我們就能夠在抽象的層次上處理Lucene定義的數(shù)據(jù)類型的讀寫。簡單的說，Lucene中存儲抽象這部分設計時采用了工廠模式（Factory parttern）^[23]。我們利用靜態(tài)類的方法也就是工廠來創(chuàng)建對象，返回接口，通過接口來執(zhí)行操作。

五、             關(guān)于cLucene項目

這一部分詳細的說明了Lucene系統(tǒng)中所采用的索引文件格式、一些基礎類和存儲抽象。接下來我們來敘述一下我們在項目cLucene中重新實現(xiàn)這些結(jié)構(gòu)時候的一些考慮。

    cLucene徹底的遵守了Lucene所定義的索引文件格式，這是Lucene對于各個兼容系統(tǒng)的基本要求。在此基礎上，cLucene系統(tǒng)和Lucene系統(tǒng)才能夠共享索引文件數(shù)據(jù)。或者說，cLucene生成的索引文件和Lucene生成的索引文件完全等價。

    在基礎類問題上，cLucene同樣封裝了類似的結(jié)構(gòu)。我們同樣列表描述，請和前面的表3.2與3.3對照比較。

表 3.4 基礎類包cLucene::util

表 3.3 基礎類包cLucene::document

    存儲抽象的實現(xiàn)上，也同樣是類似于java實現(xiàn)。由于我們采用了OpenTop庫，因此同樣得以借助其中對于文件系統(tǒng)抽象的ot::io包來解決文件系統(tǒng)問題。這部分問題與前面一樣，存在優(yōu)化的可能。在實現(xiàn)的類層次上、對外接口上，均與java版本的一樣。

第四節(jié) Lucene索引構(gòu)建邏輯模塊分析

一、             緒論

這一個部分，我們將分析Lucene中的索引構(gòu)建邏輯模塊。它與前面介紹的存儲抽象一起構(gòu)成了Lucene的索引核心部分。無論是對外接口中的查詢，還是分析各種文本以進一步生成索引，都需要直接調(diào)用這部分來獲得對索引文件的訪問能力，因此，這部分在系統(tǒng)中至關(guān)重要。構(gòu)建一個高效的、易使用的索引構(gòu)建邏輯，即是Lucene在這一部分需要達到的目的。

    從面向?qū)ο蟮慕?jīng)典思考方式出發(fā)來看，我們只需要使用繼承體系來表達圖3.1中的各個概念，就可以通過這個繼承體系來控制索引文件的結(jié)構(gòu)，然后設計合適的永久化方法，以及接受分析token流的操作，即可將索引構(gòu)建邏輯完成。原理上就是這樣的簡單。由于兩個關(guān)鍵的概念document和field都已經(jīng)在org.apache.lucene.document中當作基礎類定義過了，因此實際上Lucene在這部分需要完善的概念結(jié)構(gòu)還有segment和term。在此基礎上繼續(xù)編寫各個邏輯結(jié)構(gòu)的永久化方法，然后提供一個進入的接口方法，即是宣告完成了這個過程。其中永久化的部分，Lucene使用了另外實現(xiàn)一個代理類的方式來實現(xiàn)，即對于某個類X，存在XWriter類和XReader類來負責寫出和讀入的功能；用作永久化功能的類是被永久化的類的友元。

    在接下來的分析過程中，我們按照這樣一個思路，以UML圖和對象體系的描述來敘述這部分的設計和實現(xiàn)，然后通過內(nèi)部的數(shù)據(jù)流理清楚調(diào)用時序。

二、             對象體系與UML圖

1．  項（Term）

這部分主要是分析針對項（Term）這個概念所做的設計，包括概念所實際涉及的類、永久化類。首先，我們從圖3.2和閱讀參考文獻3知道，項（Term）所表示的是一個字符串，它擁有域、頻數(shù)和位置信息等等屬性。因此，Lucene中設計了兩個類來表示這個概念，如下圖

圖 4.1 UML圖（－）

上圖中，有意的突出了類Term和TermInfo中的數(shù)據(jù)成員，因為它反映了對于項（Term）這個概念的具體表示。同時上圖中也同時列出了用于永久化項（Term）的代理類TermInfosWriter和TermInfosReader，它們完成永久化的功能，需要注意的是，TermInfosReader內(nèi)部使用了數(shù)組indexTerms和indexInfos來存儲一系列項；而TermInfosWriter則是一個類似于鏈表的結(jié)構(gòu)，通過一個other指向下一個TermInfosWriter，每一個TermInfosWriter只負責本身那個lastTerm和lastTi的永久化工作。這是一個設計上的技巧，通過批量讀取（或者稱為緩沖的方式）來獲得讀入時候的效率優(yōu)化；而通過一個鏈表式的、各負其責的方式，來獲得寫出時候的設計簡化。

項（term）這部分的設計中，還有一些重要的接口和類，我們先介紹如下，同樣我們也先展示UML圖

圖 4.2 UML圖（二）

圖4.2中，我們看到三個類：TermEnum、TermDocs與TermPositions，第一個是抽象類，后兩個都是接口。TermEnum的設計主要用在后面Segment和Document等等的實現(xiàn)中，以提供枚舉其中每一個項（Term）的能力。TermDocs是一個接口，用來繼承以提供返回<document, frequency>值對的能力，通過這個接口就可以獲得某個項（Term）在某個文檔中出現(xiàn)的頻數(shù)。TermPositions則是在TermDocs上的擴展，將項（Term）在文檔中的位置信息也表示出來。TermDocs（TermPositions）接口的使用方式類似于java中的Enumration接口，即通過next方法跳轉(zhuǎn)，通過doc，freq等方法獲得當前的屬性值。

2．  域（Field）

由于Field的基本概念在org.apache.lucene.document中已經(jīng)做了定義，因此在這部分主要是針對項文件（.fnm文件、.fdx文件、.fdt文件）所需要的信息再來設計一些類。

圖 4.3 UML圖（三）

圖 4.3中展示的，就是表示與域（Field）所關(guān)聯(lián)的屬性信息的類。其中isIndexed表示的這個域的值是否被索引過，即值是否被分詞然后索引；另外兩個屬性所表示的意思則很明顯：一個是域的名字，一個是域的編號。

接下來我們來看關(guān)于域表和存取邏輯的UML圖。

圖 4.4 UML圖（四）

FieldInfos即為域表的概念表示，內(nèi)部采用了冗余的方式以獲取在通過域的編號訪問或者通過域的名字來訪問時候的高效率。FieldsReader與FieldsWriter則分別是寫出和讀入的代理類。在功能和實現(xiàn)上，這兩個類都比較簡單。至于FieldInfos中采用的冗余方式，則是基于域的數(shù)目相對比較少而做出的一種折衷處理。

3．  文檔（document）

文檔（document）同樣也是在org.apache.lucene.document中定義過的結(jié)構(gòu)。由于對于這部分比較重要，我們也來看看其UML圖。

圖 4.5 UML圖（五）

在圖4.5中我們看到，Document的設計基本上沿用了鏈表的處理方法。左邊的Document類作為一個數(shù)據(jù)外包類，用來提供對于內(nèi)部結(jié)構(gòu)DocumentFieldList的增加刪除訪問操作等等。DocumentFieldList才是實際上的數(shù)據(jù)存儲單位，它用了鏈表的處理方法，直接指向一個當前的Field對象和下一個DocumentFieldList對象，這個與前面的類似。為了能夠逐個訪問鏈表中的節(jié)點，還設計了DocumentFieldEnumeration枚舉類。

圖 4.6 UML圖（六）

    實際上定義于org.apache.lucene.index中的有關(guān)于Document的就是永久化的代理類。在圖4.6中給出了其UML圖。需要說明的是為什么沒有出現(xiàn)讀入的方法：這個方法已經(jīng)隱含在圖4.5中Document類中的add方法中了，結(jié)合圖2.4中的程序代碼段，我們就能夠清楚的理解這種設計。

4．  段（segment）

段（Segment）這一部分設計的比較特殊，在實現(xiàn)簡單的對象結(jié)構(gòu)之上，還特意的設計了用于段之間合并的類。接下來，我們?nèi)匀徊扇φ?/span>UML分析的方式逐個敘述。接下來我們看Lucene中如何表示段這個概念。

圖 4.7 UML圖（七）

Lucene定義了一個類SegmentInfo用來表示每一個段（Segment）的信息，包括名字（name）、含有的文檔的數(shù)目（docCount）和段所位于的目錄的位置（dir）。根據(jù)索引文件中的段的意義，有了這三點，就能唯一確定一個段了。SegmentInfos這個類則是用來表示一個段的鏈表（從標準的java.util.Vector繼承而來），實際上，也就是索引（index）的意思了。需要注意的是，這里并沒有在SegmentInfo中安插一個文檔（document）的鏈表。這樣做的原因牽涉到Lucene內(nèi)部對于文檔（相當于一個被索引文件）的處理；Lucene內(nèi)部采用了賦予文檔編號，給域賦值的方式來處理文檔，即加入的文檔順次編號，以后用文檔號表示文檔，而路徑信息，文件名字等等在以后索引查找需要的屬性，都作為域存儲下來；因此SegmentInfo中并沒有另外存儲一個文檔（document）的鏈表，對于這些的寫出和讀入，則交給了永久化的代理類來做。

圖 4.8 UML圖（八）

圖4.8給出了負責段（segment）的讀入操作的代理類，而負責段（segment）的寫出操作也同樣沒有定義，這些操作都直接實現(xiàn)在了類IndexWriter類中（后面會詳細分析）。段的操作同樣采用了之前的數(shù)組或者說是緩沖的處理方式，相關(guān)的細節(jié)也不在這里詳細敘述了。

然后，針對前面項（term）那部分定義的幾個接口，段（segment）這部分也需要做相應的接口實現(xiàn)，因為提供直接遍歷訪問段中的各個項的能力對于檢索來說，無疑是十分重要的。即這部分的設計，實際上都是在為了檢索在服務。

圖 4.9 UML圖（九）

圖 4.10 UML圖（十）

圖4.9和圖4.10分別展示了前面項（term）那里定義的接口是如何在這里通過繼承實現(xiàn)的。Lucene在處理這部分的時候，也是分成兩部分（Segment與Segments開頭的類）來實現(xiàn)，而且很合理的運用了數(shù)組的技法，以及注意了繼承重用。但是細化到局部，終歸是比較簡單的按照語義來獲得結(jié)果而已了，因此關(guān)于更多的也就不多做分析了，我們完全可以通過閱讀源代碼來解決。

接下來所介紹的，就是在Lucene的設計過程中比較特殊的一個部分：段合并類（SegmentMerger）。這首先需要介紹Lucene中的建立索引時的段合并策略。

Lucene為了兼顧建立索引時的效率和讀取索引查找的速度，引入了分小段建立索引的方式，即每一次批量建立索引時，先在內(nèi)存中的虛擬文件系統(tǒng)中為每一個文檔單獨建立一個段，然后在輸出的時候?qū)⑦@些段合并之后輸出成為索引文件，這時僅僅存在一個段。多次建立的索引后，如果想優(yōu)化索引文件，也可采取合并段的方法，將索引中的段合并成為一個段。我們來看一下在IndexWriter類中相應的方法的實現(xiàn)，來了解一下這中建立索引的實現(xiàn)。

    對于上面的代碼，我們不做過多注釋了，結(jié)合源碼中的注解應該很容易理解。在最后那個mergeSegments函數(shù)中，將用到幾個重要的類結(jié)構(gòu)，它們記錄了合并時候的一些重要信息，完成合并時候的工作。接下來，我們來看這幾個類的UML圖。

圖 4.12 UML圖（十一）

從圖4.12中，我們看到Lucene設計一個類SegmentMergeInfo用來保存每一個被合并的段的信息，也保存能夠訪問其內(nèi)部的接口句柄，也就是說合并時的操作使用這個類作為對被合并的段的操作代理。類SegmentMergeQueue則設計為org.apache.lucene.util.PriorityQueue的子類，做為SegmentMergeInfo的容器類，而且附帶能夠自動排序。SegmentMerger是主要進行操作的類，里面各個方法環(huán)環(huán)相扣，分別完成合并各個數(shù)據(jù)項的問題。

5．  IndexReader類與IndexWirter類

最后剩下的，就是整個索引邏輯部分的使用接口類了。外界通過這兩個類以及文檔（document）類的構(gòu)造函數(shù)調(diào)用之，比如圖2.4中的代碼示例所示。下面我們來看一下這部分最后兩個類的UML圖。

圖 4.13 UML圖（十二）

    IndexWriter的設計與IndexReader的設計很不相同，前者是一個實現(xiàn)類，而后者是一個抽象類，帶有沒有實現(xiàn)的接口。IndexWriter的主要作用就是接收新加入的文檔（document），然后在內(nèi)部為之生成相應的小段，最后再合并并向索引文件中輸出，圖4.11中已經(jīng)給出了一些實現(xiàn)的代碼。由于Lucene在面向?qū)ο笊戏庋b的努力，通過各個構(gòu)造函數(shù)就已經(jīng)完成了對于各個概念的構(gòu)造過程，剩下部分的代碼主要是依據(jù)各個數(shù)組或者是鏈表中的信息，逐個逐個的將信息寫出到相應的文件中去了。IndexReader部分則只是做了接口設計，沒有具體的實現(xiàn)，這個和本部分所完成的主要功能有關(guān)：索引構(gòu)建邏輯。設計這個抽象類的目的是，預先完成一些函數(shù)，為以后的檢索（search）部分的各種形式的IndexReader鋪平道路，也是利用了在同一個包內(nèi)可以方便訪問其它類的保護變量這個java語言的限制。

    到此，在索引構(gòu)建邏輯部分出現(xiàn)的類我們就分析完畢了，需要說明主要是做的一個宏觀上的組成結(jié)構(gòu)上的分析，并指出一些實現(xiàn)上的要點。具體的實現(xiàn)，由于Lucene的開放源碼而顯得并不是非常的重要，因為Lucene在做到良好的面相對象設計之后，實際帶來的是局部復雜性的減小，因此某一些單獨的函數(shù)或者實現(xiàn)就比較容易編寫，也容易讓人閱讀。本文不再繼續(xù)敘述這方面的細節(jié)，作為一個總結(jié)，下一個部分我們通過索引構(gòu)建邏輯的數(shù)據(jù)流圖的方式，再來理清楚一下索引構(gòu)建邏輯這部分的調(diào)用時序。

三、             數(shù)據(jù)流邏輯

從宏觀上明白一個系統(tǒng)的設計，理清楚其中的運行規(guī)律，最好的方式應該是通過數(shù)據(jù)流圖。在分析了各個位于索引構(gòu)建邏輯部分的類的設計之后，我們接下來就通過分析數(shù)據(jù)流圖的方式來總結(jié)一下。但是由于之前提到的原因：索引讀入部分在這一部分并沒有完全實現(xiàn)，所以我們在數(shù)據(jù)流圖中主要給出的是索引構(gòu)建的數(shù)據(jù)流圖。

圖 4.14 索引構(gòu)建部分的數(shù)據(jù)流邏輯

合并輸出

字節(jié)流輸入

內(nèi)存文件系統(tǒng)

writeNorms寫出標準化因子

sortPostingTable排序位置信息

writePostings寫出索引信息

invertDocument分析文檔

addDocument生成小段

加入document對象

以document對象方式傳入

調(diào)用

生成field對象，根據(jù)對象性質(zhì)不同，為值賦予String值，或者是Reader值

生成document對象，調(diào)用add方法加入field對象

通過java語言的io類以輸入流方式傳入

對于圖4.14中所描述的內(nèi)容，結(jié)合Lucene源代碼中的一些文件看，能夠加深理解。準備階段可以參考demo文件夾中的org.apache.lucene.demo.IndexFiles類和java文件夾中的org.apache.lucene.document文件包。索引構(gòu)建階段的主要源碼位于java文件夾中org.apache.lucene.index.IndexWriter類，因此這部分可以結(jié)合這個類的實現(xiàn)來看。至于內(nèi)存文件系統(tǒng)，比較復雜，但是這時的邏輯相對簡單，因此也不難理解。

    上面的數(shù)據(jù)流圖十分清楚的勾畫除了整個索引構(gòu)建邏輯這部分的設計：通過層層嵌套的類結(jié)構(gòu)，在構(gòu)建時候即分步驟有計劃的生成了索引結(jié)構(gòu)，將之存儲到內(nèi)存中的文件系統(tǒng)中，然后通過對內(nèi)存中的文件系統(tǒng)優(yōu)化合并輸出到實際的文件系統(tǒng)中。

四、             關(guān)于cLucene項目

前面的三個部分，已經(jīng)完成了分析索引構(gòu)建邏輯的任務，這里我們還是有針對性的談談我們這次的畢業(yè)設計項目cLucene在這一部分的情況。

在實現(xiàn)這部分的時候，為了將一些java語法中比較特殊的部分，比如內(nèi)隱類、同步函數(shù)、同步對象等等，我們不得不采用了一些比較晦澀和艱深的C++語法，在OpenTop這個類庫所提供的類似于java語言的設施上來實現(xiàn)。這個尤其體現(xiàn)在實現(xiàn)Segment相關(guān)類時，為了處理原來java源代碼中用內(nèi)隱類實現(xiàn)的Lock文件創(chuàng)建機制的時候，我們不得不定義了大量的cLucene::store::With的子類，并為之傳入調(diào)用類的指針，設置它為調(diào)用類的友元，才得以精確的模擬了原有的語義。陷于我們這次的重寫以移植為主，系統(tǒng)結(jié)構(gòu)基本上沒有大的變化，不得不產(chǎn)生這種重復而且大量的工作。如果需要改進這中狀況，我們應該考慮按照C++語言的特點來設計索引構(gòu)建部分的類庫繼承結(jié)構(gòu)，但是很可惜在本文成文之前，時間不允許我們這樣做。

來自java語法的特殊性只是我們解決問題的一個方面，我們還需要處理引用的調(diào)用方式。由于java語言擁有了垃圾收集機制，因此得以將一切的參數(shù)形式看作為引用，而不考慮其分配與消亡的問題。C++語言并不具備這種機制，它需要程序員自行管理分配空間與銷毀對象的問題。在這里，我們使用的是來自OpenTop中所引入的計數(shù)指針RefPtr<>模板，它能夠模擬指針的語義，并且計算指針被引用的次數(shù)，在引用次數(shù)為0時就自動釋放資源：這是一種類似于java語言中引用的方式，不過它顯得更加高效率。我們在cLucene的實現(xiàn)中大量的使用了計數(shù)指針模板。

    除此之外，我們沒有改變Lucene所定義的索引構(gòu)建邏輯的結(jié)構(gòu)和語義，我們實現(xiàn)的是一個完全和java版本Lucene兼容的版本。