阮曙芬

?

基于Lucene的全文搜索排序算法的研究與改進(jìn)

阮曙芬

（中國(guó)地質(zhì)大學(xué) 江城學(xué)院，湖北 武漢 430020）

在文本檢索過(guò)程中，排序算法一定程度上影響到搜索引擎的質(zhì)量。論文首先分析了 Lucene 組織結(jié)構(gòu)，包括建立索引，檢索索引文件以及結(jié)果集排序的工作過(guò)程和原理，著重剖析了Lucene基于向量模型的排序算法，并在原有排序算法基礎(chǔ)上，采用基于關(guān)鍵詞加權(quán)方式改進(jìn)了全文檢索的排序結(jié)果。實(shí)驗(yàn)結(jié)果證明，改進(jìn)后的排序算法提高了系統(tǒng)的結(jié)果精確度，滿足了項(xiàng)目的實(shí)際需求。

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

1 Lucene 搜索技術(shù)

Lucene[1]是 Apache 軟件基金會(huì) Jakarta 項(xiàng)目組的一個(gè)成員項(xiàng)目，它是一個(gè)高性能、可伸縮的信息檢索庫(kù)，但僅是一個(gè)用 Java 語(yǔ)言編寫的全文信息檢索的開(kāi)源工具包Lucene具有開(kāi)放源碼、索引速度快、支持動(dòng)態(tài)增刪索引、內(nèi)存占用小等優(yōu)點(diǎn)，可以方便嵌入到各種實(shí)際應(yīng)用中，實(shí)現(xiàn)全文信息檢索功能。

Lucene 作為一個(gè)優(yōu)秀的全文搜索框架，同時(shí)也是一個(gè)面向?qū)ο笤O(shè)計(jì)(OOP)的成功實(shí)例"首先檢索庫(kù)的功能模塊原子化程度和內(nèi)聚力較高，在重新定義實(shí)現(xiàn)用戶功能時(shí)，只需修改特定功能模塊，而無(wú)需修改其他功能模塊;其次，它定義了一個(gè)與平臺(tái)無(wú)關(guān)的索引文件格式；第三，系統(tǒng)的核心功能和重要組成部分設(shè)計(jì)定義為抽象類，用戶可以通過(guò)繼承等方式重新定義，從而實(shí)現(xiàn)自己的功能目標(biāo)，最后，通過(guò)提供靈活的API 接口，可以讓新用戶很快上手。

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

圖1 檢索與索引過(guò)程

2 Lucene包組織結(jié)構(gòu)

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

表1 Lucene各個(gè)模塊的功能

從面向?qū)ο?OOP)的角度來(lái)觀察，Lucene 采用了一條最基本的程序設(shè)計(jì)準(zhǔn)則即通過(guò)引入額外的抽象層來(lái)降低系統(tǒng)的耦合性。首先，引入數(shù)據(jù)存儲(chǔ)管理功能包完成所有對(duì)文件存儲(chǔ)管理操作的封裝，然后，引入索引功能包完成索引部分操作的封裝，完成對(duì)索引核心的抽象；在索引核心的基礎(chǔ)上設(shè)計(jì)定義對(duì)外的接口語(yǔ)言分析器功能包和檢索功能包，在高度的面向?qū)ο蟪绦蛟O(shè)計(jì)的理論支撐下，使得 Lucene 的整體框架便于理解，易于開(kāi)發(fā)擴(kuò)展。

3 Lucene排序的原理分析

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

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

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

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

圖2 向量相關(guān)性

Lucene的實(shí)際計(jì)算公式如公式（1）[1]：

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

其中，

·t，詞項(xiàng)（term）；也被稱為詞元，是粒度最小的內(nèi)容對(duì)象。

·tf，詞項(xiàng)頻數(shù)（term frequency）；即詞項(xiàng)在文檔中出現(xiàn)的頻數(shù)（次數(shù)）。

·df，文檔頻數(shù)（document frequency）；即整個(gè)數(shù)據(jù)集中出現(xiàn)過(guò)該指定詞項(xiàng)的文檔的頻數(shù)（數(shù)量）。 idf，逆文檔頻數(shù)（invert document frequency）；即與文檔頻數(shù)成反比的值。

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

·queryNorm(q)：計(jì)算每個(gè)查詢條目的方差和，該值不影響排序，僅使得不同的query 之間的分?jǐn)?shù)可以比較，每個(gè)查詢項(xiàng)權(quán)重的平分方和(sumOfSquaredWeights)由 Weight 類完成。

假設(shè): 查詢向量為 V（q）=

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

向量空間維數(shù)位 n，為查詢語(yǔ)句和文檔的并集長(zhǎng)度，當(dāng)某個(gè) Term不在查詢語(yǔ)句中w(tq，)為零，當(dāng)某個(gè) Term 不在文檔中是 w(t，d，)為零，w 代表 Weight，計(jì)算公式為：

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)

在查詢一般不輸入同樣的詞，因此假設(shè) tf(t，q)=1。idf 是指 Term 在多少文檔中出現(xiàn)次數(shù)，因此 idf(t，q)和 idf(t，d)值相等，當(dāng)索引中的文檔總數(shù)足夠大時(shí)，查詢語(yǔ)句這篇小文檔可以忽略，因此可以假設(shè) 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）得最終相似度計(jì)算公式：

以上文檔相似度評(píng)分相關(guān)的代碼都位于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)用于為計(jì)算詞項(xiàng)頻數(shù)和相關(guān)平滑提供接口。

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

public abstract void computeNorm(FieldInvertState state，Norm norm)

4 搜索結(jié)果排序的改進(jìn)

Lucene在顯示檢索結(jié)果時(shí)，評(píng)分的基本特點(diǎn)是所查詢的詞在一個(gè)文檔中位置并不重要；若一個(gè)文檔中所含該查詢?cè)~的次數(shù)越多，則其得分越高；一個(gè)命中的文檔中，如果除了該查詢?cè)~之外，其它詞越多，則其得分越少，但是這種排序精確度不高，不能充分體現(xiàn)文檔或者網(wǎng)頁(yè)的重要性。具體來(lái)說(shuō)Lucene默認(rèn)采用向量模型的排序算法得到文檔得分，分?jǐn)?shù)越高、其排名越靠前[4]，而忽略了標(biāo)題、關(guān)鍵字等激勵(lì)因子遠(yuǎn)大于正文的激勵(lì)因子。

本文提出修改文檔標(biāo)題和摘要域的權(quán)重，通過(guò)使用Setboost()方法[5]改變field的權(quán)重，例如，如果term出現(xiàn)在標(biāo)題或摘要中獲取激勵(lì)因子乘以與tf成遞增關(guān)系的倍數(shù)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基礎(chǔ)上加上時(shí)間因子。修改后的打分公式為：L_Score（d）=score*90%+d_time*10%，其中d_time=(當(dāng)前時(shí)間-文檔時(shí)間域)/模。

5 測(cè)試環(huán)境及結(jié)果

實(shí)驗(yàn)測(cè)試以Lucene3.6為開(kāi)發(fā)工具包，開(kāi)發(fā)工具為eclipse7.0，開(kāi)發(fā)平臺(tái)為jdk1.6，測(cè)試文檔分別為doc1、doc2、doc3、doc4，每個(gè)文本文檔包含title、abstract、tex、date四個(gè)域，實(shí)驗(yàn)有兩組結(jié)果，分別為第一組實(shí)驗(yàn)四個(gè)文檔title和abstract不包含索引關(guān)鍵字；第二組修改文檔1、3、4在標(biāo)題和摘要中隨機(jī)添加索引關(guān)鍵詞。對(duì)兩組實(shí)驗(yàn)進(jìn)行索引查詢后的排序得分如圖3。

通過(guò)實(shí)驗(yàn)結(jié)果分析，關(guān)鍵詞的位置激勵(lì)因子起到了排序作用，實(shí)驗(yàn)排序結(jié)果達(dá)到預(yù)期效果，但是在時(shí)間因素影響排序方面還可以改進(jìn)為以月或日或小時(shí)為比較單位。另外根據(jù)應(yīng)用需求，系統(tǒng)還使用Filter 對(duì)搜索結(jié)果進(jìn)行過(guò)濾，可以獲得更小范圍內(nèi)更精確的結(jié)果。

圖3 實(shí)驗(yàn)結(jié)果對(duì)比

[1] 羅剛．解密搜索引擎技術(shù)實(shí)戰(zhàn)[M]. 北京：電子工業(yè)出版，2011．

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

[3] 高凱，郭立煒等．網(wǎng)絡(luò)信息檢索技術(shù)及搜索引擎系統(tǒng)開(kāi)發(fā)[J]. 北京:科學(xué)出版社，2010．

[4] 管建和，甘劍鋒．基于 Lucene 全文檢索引擎的應(yīng)用研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2007, (2).

[5] Lucene官方網(wǎng)站[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-），女，講師，碩士，研究方向：數(shù)學(xué)及信號(hào)處理.