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

沙陽(yáng)陽(yáng) 吳 陳

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

1 引言

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

2 SSM框架概述

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

圖1 SSM框架圖

3 Lucene概述

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

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

目前Lucene采用的評(píng)分機(jī)制是基于向量空間模型，通過(guò)對(duì)文檔相似度的判斷進(jìn)行評(píng)分。其核心思想是將文檔分成一系列的詞，且每個(gè)詞都有相應(yīng)權(quán)重，文檔中不同的詞可以通過(guò)權(quán)重來(lái)影響文檔相關(guān)性的分值計(jì)算［6～9］。文檔中詞的權(quán)重可以設(shè)為一個(gè)向量。此外查詢的關(guān)鍵詞可以看作簡(jiǎ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所示，一個(gè)N維空間包含了查詢出的關(guān)鍵詞查詢向量和文檔向量。

圖2 空間向量圖

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

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

表1 文檔權(quán)重

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

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

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

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

5.1 算法介紹

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

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

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

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

5.2 Vector－PageRank算法

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

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

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

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

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

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

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

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

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

7 結(jié)語(yǔ)

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