基于Web的Lucene全文搜索排序算法的研究?

沙陽陽 吳 陳

（江蘇科技大學(xué)計算機(jī)學(xué)院 鎮(zhèn)江 212000）

1 引言

伴隨著互聯(lián)網(wǎng)發(fā)展水平的提高，企業(yè)在日常的生產(chǎn)過程中產(chǎn)生了大量的電子信息。這些信息以不同的格式分別保存在關(guān)系數(shù)據(jù)庫、企業(yè)內(nèi)部網(wǎng)站上等。企業(yè)正面臨著如何深度挖掘并整合不同類型信息的問題［1］，而目前國內(nèi)企業(yè)搜索引擎的著力點(diǎn)還主要是針對互聯(lián)網(wǎng)市場，針對企業(yè)個性化需求的搜索引擎日趨緊迫。本文在大量研究的基礎(chǔ)之上，采用目前主流的SSM開發(fā)框架以結(jié)合Lucene搜索引擎技術(shù)，設(shè)計出了一種結(jié)合兩者的新的全文搜索引擎框架，同時對其基本的排序算法做了相關(guān)的改進(jìn)與優(yōu)化。結(jié)果表明，與傳統(tǒng)的搜索算法相比，改進(jìn)的排序算法有效提高了系統(tǒng)查詢結(jié)果的準(zhǔn)確度和速度，大大減少了響應(yīng)所需要的時間，滿足了用戶實(shí)際操作中的需求。

2 SSM框架概述

SSM框架整合了struts2、spring和mybatis三個主流的J2EE開源框架。通過對系統(tǒng)的分層管理，降低對各個組成元素之間的耦合程度、提高開發(fā)的效率。struts2作為中央控制器以映射的方式分發(fā)請求；spring動態(tài)地提供注入對象，抽取公共方法進(jìn)行封裝、實(shí)現(xiàn)了業(yè)務(wù)對象管理；MyBatis是一款出色的持久層框架，它支持定制化SQL、存儲過程以及高級映射。SSM框架如圖1所示。

圖1 SSM框架圖

3 Lucene概述

Lucene本身其實(shí)就是全文索引與信息檢索（IR）庫，是基于Java語言編寫實(shí)現(xiàn)的，又因?yàn)镴ava語言的開源性，使其在發(fā)展過程中越來越成熟。Lucene基本上是由建立索引、搜索、管理這三大部分組成的，其索引過程如下:首先系統(tǒng)中要存在大量的被索引文件，這些被索引的文件在經(jīng)過語法分析和語言處理后分解成了一個個單詞（即Term），詞典和反向索引表就是由這些一個個的單詞提供索引創(chuàng)建形成的，接著利用索引的存儲功能將索引讀到系統(tǒng)硬盤中［2～5］。其搜索過程如下:開始時用戶根據(jù)需求在輸入框里輸入自己需要查詢的語句，由于所需要的查詢語句存在語法上的不同，不能直接對該查詢語句進(jìn)行處理，需要對語句進(jìn)行一系列的處理，如詞法分析、語法分析等，經(jīng)過這些過程后得到了一顆查詢樹，然后通過索引的存儲功能將索引文件存放到系統(tǒng)內(nèi)存中，所有詞的文檔鏈表都是根據(jù)查詢樹搜索索引得到的，對這些文檔鏈表做一定的處理得到所需要的結(jié)果文檔，單此時得到的結(jié)果文檔不是我們最終想要看到的，我們想要的結(jié)果是有一定順序的，是與查詢語句有著一定相關(guān)性的，所以我們要針對上面的需求對結(jié)果文檔進(jìn)行處理，使得與查詢語句越相關(guān)的結(jié)果排在前面，最不相關(guān)的排在后面，然后將已經(jīng)處理過且排序好的結(jié)果返回給用戶。

4 Lucene檢索模型與文檔排序算法

目前Lucene采用的評分機(jī)制是基于向量空間模型，通過對文檔相似度的判斷進(jìn)行評分。其核心思想是將文檔分成一系列的詞，且每個詞都有相應(yīng)權(quán)重，文檔中不同的詞可以通過權(quán)重來影響文檔相關(guān)性的分值計算［6～9］。文檔中詞的權(quán)重可以設(shè)為一個向量。此外查詢的關(guān)鍵詞可以看作簡短的文檔，也可以用向量表示。

Query=｛term1，term 2，…… ，term N｝

Document=｛term1，term2，…… ，term N｝

Query Vector=｛weight1，weight2，…… ，weight N｝

Document Vector=｛weight1，weight2，…… ，weight N｝

如圖2所示，一個N維空間包含了查詢出的關(guān)鍵詞查詢向量和文檔向量。

圖2 空間向量圖

從圖2中可以看出，如果向量之間的夾角大，則相關(guān)性小。如果兩個向量夾角為0，則說明這兩個向量完全相關(guān)，即完全匹配。所以兩個向量夾角的余弦值來進(jìn)行相關(guān)性打分。然而大部分情況下，查詢關(guān)鍵詞很短，只有一個或兩個詞，這種情況下，查詢關(guān)鍵詞向量維度就很小。計算相關(guān)度是在相同的向量空間，所以維數(shù)相同，維數(shù)如果不同，可以取兩者交集。權(quán)重為0的情況是不含該關(guān)鍵詞。相關(guān)性打分公式（1）［10］如下:

舉例說明，用戶搜索語句包含11個關(guān)鍵詞，搜索結(jié)果為3篇文檔。各自權(quán)重如表1所示。

表1 文檔權(quán)重

計算3篇文檔與查詢語句的相關(guān)性分值，過程 如下:

計算結(jié)果是D2相關(guān)性最高，D3其次，D1相關(guān)性最低。所以返回結(jié)果的順序是，D2，D3，D1。在實(shí)際計算中Lucene常采用式（5）對文檔進(jìn)行排序［11］:

其中t為詞項(xiàng)（term），是粒度最小的內(nèi)容對象也被叫做詞元。tf為詞項(xiàng)頻數(shù)（term frequency），表示文檔中詞元出現(xiàn)的次數(shù)。df為文檔頻數(shù)（document frequency），表示對于某一詞項(xiàng)出現(xiàn)過的文檔數(shù)目。idf為逆文檔頻數(shù)（invert document frequency），其值與文檔頻數(shù)成反比。coord（q，d）:在每次搜索時，我們可能需要搜索多個搜索詞，而一篇文檔里往往不可能僅有一個搜索詞，而是有很多個，所以此項(xiàng)代表了搜索的詞數(shù)越多，打分越高的關(guān)系［12］。queryNorm（q）:通過計算每個查詢條目的方差和，比較查詢項(xiàng)不影響最終結(jié)果。

5 Lucene文檔排序算法優(yōu)化

5.1 算法介紹

Direct Hit算法由Ask Jeeves公司提出，通過用戶的點(diǎn)擊行為來判斷網(wǎng)頁的重要性。其基本原理是對于檢索出來的結(jié)果，如果用戶瀏覽的時間較長，說明檢索結(jié)果是基本符合用戶的需求，那么系統(tǒng)會增加此網(wǎng)頁的相關(guān)度。反之對于瀏覽時間較長的網(wǎng)頁，則會增加其相關(guān)度。Direct Hit算法實(shí)際上對檢索結(jié)果集提供了一種動態(tài)排序的功能，且只適合檢索關(guān)鍵字較少的情況下。目前在很多搜索引擎中都將Direct Hit算法作為輔助排序算法［13］。

Page Rank 算法［13～17］思想起源于文獻(xiàn)引文索引機(jī)制，若經(jīng)過論文經(jīng)過索引后的得分越高，那么則表明這篇論文的被引用次數(shù)一定越多。Page Rank算法體現(xiàn)了一種回歸的思想，如果網(wǎng)頁A導(dǎo)向到了網(wǎng)頁B，說明網(wǎng)頁A對網(wǎng)頁B投了支持票，通過多個得票數(shù)的綜合，就可以得出網(wǎng)頁的重要性。當(dāng)然除了考慮得票數(shù)之外還要考慮投票者的權(quán)威性，投票者的權(quán)威性越高，網(wǎng)頁的價值、重要性就越大。

假設(shè)有若干個不同的網(wǎng)頁鏈接t1…tn，指向了網(wǎng)頁A，設(shè)阻尼系數(shù)為d（0＜d＜1），同Google一樣，本次試驗(yàn)中取d=0.85。網(wǎng)頁A的出鏈數(shù)量為C（A），其計算如式（6）所示［18］:

PageRank算法一個顯著的優(yōu)點(diǎn)是通過離線計算網(wǎng)頁的PR值，大大降低了在線計算的工作量，提高了查詢響應(yīng)時間。但是由于并未將主題相關(guān)性影響考慮在內(nèi)，使得準(zhǔn)確度受到影響；而且從公式中我們可以看出PageRank算法偏重舊網(wǎng)頁，對于一個新的網(wǎng)頁被投入Internet后，由于有較少的網(wǎng)頁指向它，PR值也會偏低。

5.2 Vector－PageRank算法

Lucene的排序算法與PageRank排序算法相結(jié)合，雖然一定程度上提高了查詢的精度，但由于其各自缺陷效果并不理想。為了在海量的搜尋信息中返回更加切合用戶關(guān)注度的結(jié)果集，本文提出了綜合網(wǎng)頁排序算法，即充分考慮標(biāo)題、關(guān)鍵字激勵因子以及網(wǎng)頁關(guān)于更新日期的時間權(quán)重、檢索來源權(quán)威性因子對排序結(jié)果的影響。

針對Lucene在排序時并未對標(biāo)題、關(guān)鍵字與正文的激勵因子做區(qū)分的不足［19～20］，系統(tǒng)設(shè)計時通過使用Document類的setBoost（）方法修改文檔標(biāo)題和摘要域的權(quán)重，即如果term出現(xiàn)在標(biāo)題或摘要中，那么我們通過激勵因子乘以與詞項(xiàng)頻數(shù)tf成遞增關(guān)系的倍數(shù)X提高得分，經(jīng)過改進(jìn)后標(biāo)題、關(guān)鍵字等激勵因子將大于正文的激勵因子。改進(jìn)后的Lucene的實(shí)際計算公式（7）如下:

針對PageRank的排序算法的不足，通過引入時間權(quán)重以及網(wǎng)站權(quán)威性因子參數(shù)，使其算法更為全面、合理，結(jié)果查詢率更為準(zhǔn)確，改進(jìn)后的PageR-ank的計算公式（8）如下:

結(jié)合改進(jìn)的PageRank算法改進(jìn)Lucene的排序算法得出最終本系統(tǒng)采用的Vector－PageRank算法的計算公式（9）:

其中，newscore（d）表示用改進(jìn)后算法求得的文檔d的得分，score代表由Lucene基礎(chǔ)排序算法改進(jìn)后計算出的記錄d的得分；prscore對應(yīng)改進(jìn)的PageR-ank算法算出的d的得分，k1、k2為系統(tǒng)選取合適的權(quán)重系數(shù)并且其總和為1。

6 測試環(huán)境及結(jié)果

系統(tǒng)在以開發(fā)平臺為jdk1.8，采用Lucene5.3為基礎(chǔ)jar具包，使用Eclipse4.4開發(fā)完成。通過對關(guān)鍵詞“智慧園區(qū)”進(jìn)行搜索，將本系統(tǒng)與搜索引擎Google返回結(jié)果集的前80個頁面進(jìn)行相關(guān)度評價。數(shù)據(jù)結(jié)果對比如表2所示。

表2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)數(shù)據(jù)顯示，本系統(tǒng)優(yōu)化后的排序算法在搜索引擎內(nèi)部起到了良好的作用，效率和準(zhǔn)確度都得到了改善。

7 結(jié)語

本文主要通過采用Lucene排序算法與PageR-ank算法相結(jié)合的方式，研究企業(yè)全文搜索引擎的設(shè)計。對兩種算法結(jié)合后進(jìn)行優(yōu)化、重構(gòu)提出Vector－PageRank新型算法。通過選取關(guān)鍵詞對比優(yōu)化前后搜索引擎的性能，證明了改進(jìn)后排序算法在搜索引擎應(yīng)用中的優(yōu)越性。