基于Lucene的全文搜索排序算法的研究與改進

阮曙芬

?

基于Lucene的全文搜索排序算法的研究與改進

阮曙芬

（中國地質大學 江城學院，湖北 武漢 430020）

在文本檢索過程中，排序算法一定程度上影響到搜索引擎的質量。論文首先分析了 Lucene 組織結構，包括建立索引，檢索索引文件以及結果集排序的工作過程和原理，著重剖析了Lucene基于向量模型的排序算法，并在原有排序算法基礎上，采用基于關鍵詞加權方式改進了全文檢索的排序結果。實驗結果證明，改進后的排序算法提高了系統的結果精確度，滿足了項目的實際需求。

Lucene；向量空間模型；TF-IDF；排序算法

1 Lucene 搜索技術

Lucene[1]是 Apache 軟件基金會 Jakarta 項目組的一個成員項目，它是一個高性能、可伸縮的信息檢索庫，但僅是一個用 Java 語言編寫的全文信息檢索的開源工具包Lucene具有開放源碼、索引速度快、支持動態增刪索引、內存占用小等優點，可以方便嵌入到各種實際應用中，實現全文信息檢索功能。

Lucene 作為一個優秀的全文搜索框架，同時也是一個面向對象設計(OOP)的成功實例"首先檢索庫的功能模塊原子化程度和內聚力較高，在重新定義實現用戶功能時，只需修改特定功能模塊，而無需修改其他功能模塊;其次，它定義了一個與平臺無關的索引文件格式；第三，系統的核心功能和重要組成部分設計定義為抽象類，用戶可以通過繼承等方式重新定義，從而實現自己的功能目標，最后，通過提供靈活的API 接口，可以讓新用戶很快上手。

Lucene搜索過程（如圖1中虛線部分所示）首先用戶輸入查詢語句，經過詞法分詞器和語言分詞器分析處理得到一系列詞(Term)，然后通過詞法分析得到一棵查詢樹，通過索引存儲將索引文件讀入內存，利用查詢樹搜索索引，得到每個詞的文檔鏈表，對文檔鏈表進行操作，得到結果文檔集，按查詢的相關性將搜索結果文檔集進行排序，最后將排序后的查詢結果返還給用戶。

圖1 檢索與索引過程

2 Lucene包組織結構

Lucene 將所有源代碼分為7個模塊，各個模塊的功能如表1所示：

表1 Lucene各個模塊的功能

從面向對象(OOP)的角度來觀察，Lucene 采用了一條最基本的程序設計準則即通過引入額外的抽象層來降低系統的耦合性。首先，引入數據存儲管理功能包完成所有對文件存儲管理操作的封裝，然后，引入索引功能包完成索引部分操作的封裝，完成對索引核心的抽象；在索引核心的基礎上設計定義對外的接口語言分析器功能包和檢索功能包，在高度的面向對象程序設計的理論支撐下，使得 Lucene 的整體框架便于理解，易于開發擴展。

3 Lucene排序的原理分析

在搜索引擎的研究中，一個核心問題就是排序算法的確定，較成熟的方法包括向量空間概率模型和統計語言模型等，Lucene 的評分機制采用向量空間模型，那么，我們把文檔或查詢看做一系列的詞(Term)，每個詞都有一個權重(Term Weight)，不同的詞根據自己再文檔或查詢中的權重來影響文檔相關性的評分計算。我們將此文檔或查詢中的所有詞的權重看做一個向量：

Document/ Query ={Term1，Term2，...，Term N}

Document/ Query Vector={Weight1，Weight2，...，Weight N}

我們把所有搜索出的文檔向量及查詢向量放到一個 N 維空間中，每個詞是一維，如果兩個向量間的夾角越小，相關性就越大，所以計算夾角的余弦值作為相關性的評分，夾角越小， 余弦值越大，評分越高，相關性越大[1]。（如圖2）

圖2 向量相關性

Lucene的實際計算公式如公式（1）[1]：

Score=coord(q，d)*queryNorm(q)*∑(tf(tind)*idf(t)2*t.getBoost()*norm(t，d)) （1）

其中，

·t，詞項（term）；也被稱為詞元，是粒度最小的內容對象。

·tf，詞項頻數（term frequency）；即詞項在文檔中出現的頻數（次數）。

·df，文檔頻數（document frequency）；即整個數據集中出現過該指定詞項的文檔的頻數（數量）。 idf，逆文檔頻數（invert document frequency）；即與文檔頻數成反比的值。

·coord(q，d)：一次搜索可能包含多個搜索詞，而一篇文檔中也同時可能包含多個搜索詞，此項則表示，當一篇文檔中包含的搜索詞數量越多，此文檔得分越高。

·queryNorm(q)：計算每個查詢條目的方差和，該值不影響排序，僅使得不同的query 之間的分數可以比較，每個查詢項權重的平分方和(sumOfSquaredWeights)由 Weight 類完成。

假設: 查詢向量為 V（q）=

文檔向量為 V（d）=< w(t1，d)，w(t2，d)，...，w(tn，d)>

向量空間維數位 n，為查詢語句和文檔的并集長度，當某個 Term不在查詢語句中w(tq，)為零，當某個 Term 不在文檔中是 w(t，d，)為零，w 代表 Weight，計算公式為：

w=tf*idf

V(q)* V(d)= w(t1，q)* w(t1，d)+……w(tn，q)* w(tn，d)

=tf((t1，q)*idf((t1，q)* tf((t1，d)*idf((t1，d)+…tf((tm，q)*idf((tm，q)* tf((tm，d)*idf((tm，d)

在查詢一般不輸入同樣的詞，因此假設 tf(t，q)=1。idf 是指 Term 在多少文檔中出現次數，因此 idf(t，q)和 idf(t，d)值相等，當索引中的文檔總數足夠大時，查詢語句這篇小文檔可以忽略，因此可以假設 idf(t，q)=idf(t，d)=idf(t)，因此：

V(q) V(d)= idf((t1)* tf((t1，d)*idf((t1)+……idf((tm)* tf((tm，d)*idf((tm) （2）

將公式（2）帶入（1）得

cos(q，d)=∑tf((t，d) idf((t)2/( |V(q)|| V(d)|) （3）

將公式（4），（5）帶入（3）得最終相似度計算公式：

以上文檔相似度評分相關的代碼都位于org.apache.Lucene.search.similarities包下，TFIDFSimilarity類中，該類主要提供了以下的功能[3]：

public abstract float coord(int overlap，int maxOverlap)

public abstract float queryNorm(float sumOfSquaredWeights)

public abstract float tf(float freq)用于為計算詞項頻數和相關平滑提供接口。

public abstract float idf(long docFreq，long numDocs)計算文檔頻率提供接口。

public abstract void computeNorm(FieldInvertState state，Norm norm)

4 搜索結果排序的改進

Lucene在顯示檢索結果時，評分的基本特點是所查詢的詞在一個文檔中位置并不重要；若一個文檔中所含該查詢詞的次數越多，則其得分越高；一個命中的文檔中，如果除了該查詢詞之外，其它詞越多，則其得分越少，但是這種排序精確度不高，不能充分體現文檔或者網頁的重要性。具體來說Lucene默認采用向量模型的排序算法得到文檔得分，分數越高、其排名越靠前[4]，而忽略了標題、關鍵字等激勵因子遠大于正文的激勵因子。

本文提出修改文檔標題和摘要域的權重，通過使用Setboost()方法[5]改變field的權重，例如，如果term出現在標題或摘要中獲取激勵因子乘以與tf成遞增關系的倍數X，提高得分，修改后的打分公式如下，field_flag為命中bool變量0或者1。

Score=coord(q，d)*queryNorm(q)*∑(tf(tind)*idf(t)2*t.getBoost()*(field_flag*X+1)norm(t，d))

其次，在文檔打分相同條件下，查詢用戶往往希望看到最近的文檔，本文提出在原有的score基礎上加上時間因子。修改后的打分公式為：L_Score（d）=score*90%+d_time*10%，其中d_time=(當前時間-文檔時間域)/模。

5 測試環境及結果

實驗測試以Lucene3.6為開發工具包，開發工具為eclipse7.0，開發平臺為jdk1.6，測試文檔分別為doc1、doc2、doc3、doc4，每個文本文檔包含title、abstract、tex、date四個域，實驗有兩組結果，分別為第一組實驗四個文檔title和abstract不包含索引關鍵字；第二組修改文檔1、3、4在標題和摘要中隨機添加索引關鍵詞。對兩組實驗進行索引查詢后的排序得分如圖3。

通過實驗結果分析，關鍵詞的位置激勵因子起到了排序作用，實驗排序結果達到預期效果，但是在時間因素影響排序方面還可以改進為以月或日或小時為比較單位。另外根據應用需求，系統還使用Filter 對搜索結果進行過濾，可以獲得更小范圍內更精確的結果。

圖3 實驗結果對比

[1] 羅剛．解密搜索引擎技術實戰[M]. 北京：電子工業出版，2011．

[2] 李剛，宋偉，邱哲．Ajax+Lucene構建搜索引擎[M]. 北京:人民郵電出版社，2006．

[3] 高凱，郭立煒等．網絡信息檢索技術及搜索引擎系統開發[J]. 北京:科學出版社，2010．

[4] 管建和，甘劍鋒．基于 Lucene 全文檢索引擎的應用研究與實現[J]. 計算機工程與設計，2007, (2).

[5] Lucene官方網站[EB/OL]. http://Lucene.apache.org/.2013-09-01.

Research and Improvement of Full-text Retrieval Sorting Algorithm Based on Lucene

RUAN Shu-fen

(Jiangcheng College, China University of Geosciences, Wuhan Hubei 430020, China)

In the process of text retrieval, the sort algorithm affects the quality of search engine to a certain. This paper analyzes the structure of Lucene, to be familiar with the course and theory of creating index files, searching index files, sorting the results and discussing the improved presentation of sorting algorithm of Lucene. On the foundation of the sorting algorithm, the sorting result is improved by weighting major descriptor. Experimental results show that the improved sorting algorithm increase accuracy of the search system, and meet with the real needs of the project.

Lucene; VSM; TF-IDF; Sorting Algorithm

TP311.13

A

2095－414X(2013)06－0084－04

阮曙芬（1980-），女，講師，碩士，研究方向：數學及信號處理.