改進的BM25F評分算法在文獻檢索系統中的應用

目錄1系統總體架構及數據準備 系統總體架構及數據準備我們改進了BM25F算法，把它用在了論文檢索中，BM25F算法比較適用劃分了區域的文檔，如論文中的區域有標題，摘要，作者等區域，用這個算法來進行論文的檢索就相當的合適。系統總體架構圖1-1系統架構圖以上是我們這個系統的總體架構圖，大致分成兩塊，第一塊就是數據準備，即從網上把我們需要的數據用爬蟲爬下來，從爬下來的html源代碼解析提取出我們想要的字段，然后存儲在數據庫中。第二塊就是當我們有了這些原始數據后，可用它來建立索引、字典等操作，然后再在這個基礎上構建我們的搜索引擎，用我們改進的BM25F算法來對檢索出來的論文進行排序，再把最終的結果返回給用戶。我們在數據庫的設計上做一些小優化，以更好地適應我們的算法，它可以在很大程序上減少計算的開銷。除此之外，我們在原始的BM25F算法上也做了一些優化，詳見后面的章節。數據準備我們項目中的論文數據爬取自萬方，下面是一篇論文示例：圖1-2論文實例在這個頁面中，劃分了很多字段（或者說區域），有標題、摘要、作者、關鍵字等。我們主要爬取了標題、摘要、關鍵字、作者、作者單位這幾個字段。下面是一個爬取過程的示意圖：圖1-3爬蟲過程示意圖最后存儲在數據庫中的結果如下圖所示：圖1-4數據庫表設計示意圖從上圖中可以看到，我們不僅保存了爬取到的這些字段的完整信息，還保存了去除停用詞后的分詞結果，以及一些比較重要的字段的長度，這極大的減小了后續進行BM25F分值計算時的計算開銷。

搜索引擎的搭建過程索引的建立我們檢索系統中所用到的是倒排索引，下面給出倒排索引的相關概念，倒排索引（InvertedIndex），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。通過倒排索引，可以根據單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：“單詞詞典”和“倒排文件”。倒排索引有兩種不同的反向索引形式：一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創建?，F代搜索引擎的索引都是基于倒排索引。相比“簽名文件”、“后綴樹”等索引結構，“倒排索引”是實現單詞到文檔映射關系的最佳實現方式和最有效的索引結構。存儲在MySQL數據庫中的每一條記錄都被表示成一個文檔，我們為每一個文檔建立索引。倒排索引的具體建立步驟分為兩步，首先使用中文分詞器對需要建立索引的文檔進行分詞，然后構建倒排索引表，我們還做了一個小小的處理，使得一些原來會被分詞器當成兩個詞而分開的詞，現在當成一個整體而不會被分開，例如機器學習，如果不做處理，會被分為機器、學習，這樣就不符合我們期望的結果。 下圖是一個倒排索引表的示意圖：表2-1索引文件示意表KeyWordsDocumentID[Frequency]PositionsFields機器學習1[2],2[1]2,5,2Abstract????在上圖所示的倒排索引表中，索引的詞是機器學習，它出現的區域是摘要，它在文檔1的摘要中的出現了2次，位置分別是2和5，在文檔2的摘要中出現1次，出現的位置是2。這里所說的位置，都是以分詞后的單詞為距離來計算的，也就是說以分詞后的單詞為最小的單位。中文分詞器的比較與選取當前比較常用的中文分詞器主要有PaodingAnalyzer、ImdictChineseAnalyzer、MMSeg4jAnalyzer以及IKAnalyzer四種，首先分別簡單介紹一下這四種中文分詞器。PaodingAnalyzer中文翻譯為“庖丁解?！?，引入隱喻，采用完全的面向對象設計，構思先進。ImdictChineseAnalyzer是ImdictChineseAnalyzer智能詞典的智能中文分詞模塊，算法基于隱馬爾科夫模型(HiddenMarkovModel,HMM)，是中國科學院計算技術研究所的ictclas中文分詞程序的重新實現（基于Java）。MMSeg4jAnalyzer用Chih-HaoTsai的MMSeg算法實現的中文分詞器，并實現lucene的analyzer和solr的TokenizerFactory以方便在Lucene和Solr中使用。IKAnalyzer是一個開源的，基于java語言開發的輕量級的中文分詞工具包。從2006年12月推出1.0版開始，IKAnalyzer已經推出了4個大版本。接下來將分別從用戶自定義詞庫、效率以及算法和代碼復雜度三個方面對4種分詞器進行比較。（1）用戶自定義詞庫：PaodingAnalyzer：支持不限制個數的用戶自定義詞庫，純文本格式，一行一詞，使用后臺線程檢測詞庫的更新，自動編譯更新過的詞庫到二進制版本，并加載。ImdictChineseAnalyzer：暫時不支持用戶自定義詞庫，但原版ICTCLAS支持用戶自定義stopwords。MMSeg4jAnalyzer：自帶sogou詞庫，支持名為wordsxxx.dic，utf8文本格式的用戶自定義詞庫，一行一詞。不支持自動檢測。IKAnalyzer：支持API級的用戶詞庫加載，和配置級的詞庫文件指定，無BOM的UTF-8編碼，，不支持自動檢測。（2）速度以下數據來源于個分詞器官方介紹。PaodingAnalyzer：在PIII1G內存個人機器上，1秒可準確分詞100萬漢字。ImdictChineseAnalyzer：483.64(字節/秒)，259517(漢字/秒)。MMSeg4jAnalyzer：complex1200kb/s左右，simple1900kb/s左右。IKAnalyzer：具有50萬字/秒的高速處理能力（3）算法和代碼復雜度PaodingAnalyzer：svnsrc目錄一共1.3M，6個properties文件，48個java文件，6895行。使用不同的Knife切不同類型的流，不算很復雜。ImdictChineseAnalyzer：詞庫6.7M（這個詞庫是必須的），src目錄152k，20個java文件，2399行。使用ICTCLASHHMM隱馬爾科夫模型，“利用大量語料庫的訓練來統計漢語詞匯的詞頻和跳轉概率，從而根據這些統計結果對整個漢語句子計算最似然的切分”MMSeg4jAnalyzer：svnsrc目錄一共132k，23個java文件，2089行。MMSeg算法，有點復雜。IKAnalyzer：svnsrc目錄一共6.6M(詞典文件也在里面)，22個java文件，4217行。多子處理器分析，跟PaodingAnalyzer類似，歧義分析算法還沒有弄明白。最終，我們選取了ImdictChineseAnalyzer中文分詞器，并對其中文詞庫進行了處理。處理之后，機器學習、神經網絡、數據挖掘等專業詞語將會被當做一個詞，是查詢結果更符合用戶的原始意愿。評分算法的設計與實現BM25算法在信息檢索中，BM25算法是用來給文檔排序的，具體來說就是當用戶向搜索引擎提交一個查詢時，會查到很多相關的文檔，BM25算法就是給這些文檔做相關度排序的，然后按相關度從大到小把結果返回給用戶。它是把文檔看成是詞袋，忽略語法及詞的順序。給定一個查詢Q，其中Q包含關鍵字q1,,…,qn,，則BM25算法為文檔打的分用下式來計算：其中，f(qi,D)是關鍵字在文檔D中出現的頻率，|D|是文檔D的長度（以詞的個數計算長度），是文檔集中文檔的平均長度，k1和b是可調參數，k1的取值在區間[1.2,2.0]中，b取值在區間[1.2,2.0]中，具體編碼實現時，通過反復時間嘗試，最終取k1=1.2，b=0.75。IDF（InverseDocumentFrequency）為逆向文件頻率，是一個詞語普遍重要性的度量。某一特定詞語的IDF，可以由總文件數目除以包含該詞語之文件的數目，再將得到的商取對數得到，定義如下：其中，N是文檔集中所有文檔的個數，n(qi)是文檔集中包含檢索詞項qi的文檔數。除此之外，IDF權重的計算公式還有一些變體，但最終我們選取了教材中所給出的上述公式。BM25F算法BM25F是一個從BM25算法修改而來的算法，適用于結構化的文檔中，它的主要思想是，結構化文檔是由多個區域組成的，如果HTML網頁有header、body區域等，每個區域的權重應該區別對待。又例如在檢索論文時，認為查詢詞項出現在標題中，比出現在摘要中更重要，那么就會給標題這個區域以更大的權重，比如認為同樣一個詞出現在標題中一次，相當于出現在摘要中10次。BM25F算法就是對不同的區域賦予不同的權重，以此來反映不同區域的重要性不同。它主要就是修改了詞項頻率的計算公式，即修改為下式：f其中，f(qi,D,S)為詞項qi在文檔D的S區域中出現的頻率，l(D,S)是文檔D中區域S的長度，ls是文檔集中所有文檔的區域S的平均長度，bs是一個和區域有關的可調參數，與BM25類似，它的取值從0到1，實際編碼實現時通過反復實踐嘗試，我們取bs=0.75。對這些針對特定區域計算的詞項頻率，或者說是偽頻率，加以整合，可以得到一個針對整個文檔計算的詞項頻率公式，如下所示:f其中，是區域S的權重，例如在論文檢索中，可以取標題區域的權重為=10，摘要區域的權重為=1，這就表示對于一個相同的詞項，它出現在標題中比出現在摘要中更加重要。在BM25公式中的詞項頻率計算公式換為，就得到了BM25F公式，具體如下：QUOTEScoreD,Q=i=1nIDF(在實現了BM25F算法之后，將檢索系統應用于數據集中的查詢結果，我們發現系統再多關鍵字查詢時精度不高，通過分析得出了原因：BM25算法僅僅是考慮到了文檔長度和查詢詞的詞頻，而沒有考慮查詢詞之間的緊鄰距離。事實上，BM25F的評分公式也很好的印證了這一點。關鍵詞緊鄰距離用來衡量多個關鍵詞在同一文檔中是否相鄰。比如用戶搜索“中國足球”這一短語，包含“中國”和“足球”兩個關鍵詞，當這兩個關鍵詞按照同樣順序前后緊挨著出現在一個文檔中時，緊鄰距離為零，如果兩詞中間夾入很多詞則緊鄰距離較大。緊鄰距離是一種衡量文檔和多個關鍵詞相關度的方法。緊鄰距離雖然不應該作為給文檔排序的唯一指標，但在一些情況下通過設定閥值可以過濾掉相當一部分無關的結果。因此，接下來我們將查詢詞項在文檔中的緊鄰距離考慮到評分算法中，得到了新的評分算法，定義如下：算法的編碼實現（1）BM25算法的實現publicBM25BooleanScorer(IndexReaderreader,BooleanTermQuery[]should,BooleanTermQuery[]must,BooleanTermQuery[]not,Similaritysimilarity,String[]fields,float[]boosts,float[]bParams)throwsIOException{ this.ndocs=reader.numDocs(); if(should!=null&&should.length>0){ Scorer[]shouldScorer=newScorer[should.length]; for(inti=0;i<shouldScorer.length;i++){ shouldScorer[i]=newBM25FTermScorer(reader,should[i].termQuery,fields,boosts,bParams,similarity); } this.shouldBooleanScorer=newShouldBooleanScorer(similarity, shouldScorer); }else this.shouldBooleanScorer=newMatchAllBooleanScorer(similarity,this.ndocs); if(must!=null&&must.length>0){ Scorer[]mustScorer=newScorer[must.length]; for(inti=0;i<mustScorer.length;i++){ mustScorer[i]=newBM25FTermScorer(reader,must[i].termQuery,fields,boosts,bParams,similarity); } this.mustBooleanScorer=newMustBooleanScorer(similarity,mustScorer); }else this.mustBooleanScorer=newMatchAllBooleanScorer(similarity,this.ndocs); if(not!=null&¬.length>0){ Scorer[]notScorer=newScorer[not.length]; for(inti=0;i<notScorer.length;i++){ notScorer[i]=newBM25FTermScorer(reader,not[i].termQuery,fields,boosts,bParams,similarity); } this.notBooleanScorer=newNotBooleanScorer(similarity,notScorer,this.ndocs); }else this.notBooleanScorer=newMatchAllBooleanScorer(similarity,this.ndocs); }代碼2-1BM25評分主程序（2）BM25F評分主程序publicList<paper>bm25Seacch(StringqueryStr,intpageNum,intpageSize) throwsCorruptIndexException,IOException,ParseException{ StringindexDir=pathString; String[]fields={"title","author","paperAbstract","keyword","author_dept"}; IndexSearchersearcher=newIndexSearcher(indexDir); StringqueryString=chineseSplit.chineseAnalyze(queryStr); //SetexplicitaverageLengthforeachfield BM25FParameters.setAverageLength("title",AveTitle); BM25FParameters.setAverageLength("author",AveAuthor); BM25FParameters.setAverageLength("paperAbs",AveAbs); BM25FParameters.setAverageLength("author_dept",AveDept); BM25FParameters.setAverageLength("keyword",AveKey;) //Setexplicitk1parameter BM25FParameters.setK1(1.2f); //Usingboostandbdefaultsparameters BM25BooleanQueryqueryF=newBM25BooleanQuery(queryString,fields,newStandardAnalyzer()); //RetrievingNOTnormalizedscorervalues TopDocstop=searcher.search(queryF,null,maxQResultCnt); ScoreDoc[]docs=top.scoreDocs; //Printresults intnumTotalHits=top.scoreDocs.length; List<paper>resultList=newArrayList<paper>(); for(inti=0;i<numTotalHits;i++){ System.out.println(docs[i].doc+":"+docs[i].score); paperpaperItem=newpaper(); Documentdoc=searcher.doc(docs[i].doc); paperItem.setId(Integer.valueOf(doc.get("id"))); paperItem.setAbstract_length(Integer.valueOf(doc .get("abstract_length"))); paperItem.setKeyword_length(Integer.valueOf(doc .get("keyword_length"))); paperItem.setTitle_length(Integer.valueOf(doc.get("title_length"))); paperItem.setFileName(doc.get("fileName")); paperItem.setTitle(doc.get("title")); paperItem.setKeyword(doc.get("keyword")); paperItem.setPaperAbstract(doc.get("paperAbstract")); paperItem.setAuthor(doc.get("author")); resultList.add(paperItem); System.out.println(paperItem.getTitle()); } inttoindex=resultList.size()-1; if(pageNum*pageSize<toindex) toindex=pageNum*pageSize; returnresultList.subList((pageNum-1)*pageSize,toindex); }代碼2-2BM25F查詢主程序publicBM25FTermScorer(IndexReaderreader,TermQueryterm,String[]fields,float[]boosts,float[]bParams,Similaritysimilarity){ super(similarity); this.reader=reader; this.term=term; this.fields=fields; this.boost=boosts; this.bParam=bParams; this.termDocs=newTermDocs[this.fields.length]; this.termDocsNext=newboolean[this.fields.length]; try{ for(inti=0;i<this.fields.length;i++) this.termDocs[i]=reader.termDocs(newTerm(this.fields[i],term.getTerm().text())); this.idf=this.getSimilarity().idf( this.reader.docFreq(newTerm(BM25FParameters.getIdfField(),term.getTerm().text())),this.reader.numDocs()); }catch(IOExceptione){ e.printStackTrace(); } }代碼2-3BM25F評分主程序（3）改進的BM25F距離計算程序publicclassMinDistance{ publicArrayList<Integer>getKeywordPosition(StringstrKeyword){ Listlist=newArrayList<Integer>(); keywordDBkdb=newkeywordDB(); returnkdb.getKeywordPosition(strKeyword); } publicintminDistance(Stringkeyword1,Stringkeyword2){ ListaList=this.getKeywordPosition(keyword1); ListbList=this.getKeywordPosition(keyword2); keywordDBkdb=newkeywordDB(); if(aList==null||bList==null){ returnkdb.getAverageDistance()/2; } intminD=kdb.getAverageDistance(); for(inti=0;i<aList.size();i++){ for(intj=0;j<bList.size();j++){ if(Math.abs((Integer)aList.get(i)-(Integer)bList.get(j))<minD){ minD=Math.abs((Integer)aList.get(i)-(Integer)bList.get(j)); } } } returnminD; } publicintdocMinDistance(ListkeywordsList){ intkeywordsNum=keywordsList.size(); intminDistance=1; if(keywordsNum>1){ for(inti=0;i<keywordsNum-1;i++){ minDistance+=this.minDistance(keywordsList.get(i).toString(),keywordsList.get(i+1).toString()); } minDistance=minDistance/keywordsNum; } returnminDistance; } }代碼2-4改進的BM25F距離計算程序

項目特色考慮查詢關鍵詞之間的距離當用戶提交的一個查詢是一句話時，這句話就會通過分詞分成若干個關鍵字，我們認為如果這些關鍵字在一個文檔中出現的位置離得越近，那么這個文檔就與用戶的查詢意圖越相關，而BM25F公式并未考慮關鍵詞距離這一點，我們在優化過程中力爭把這一點整合到BM25F公式中，并應用于系統中，獲得了一定的效果?？紤]關鍵詞的位置信息，首先就是要能獲取查詢關鍵詞在一篇文檔中所出現的所有位置，再根據查詢時分詞出來的關鍵詞順序，逐一固定關鍵詞以搜索與下一個關鍵詞的距離?？紤]距離因素，需要權衡選擇關鍵詞距離的最小距離，平均距離還是最大距離作為衡量標準，在查閱相關文獻后發現，大多是文獻是基于關鍵詞的最小距離進行的處理和優化，所以我們在實現過程中同樣選擇關鍵詞的最小距離作為衡量標準。實際上在建立索引時，索引表中已經保存了詞項在文檔中出現的位置信息，因此查詢詞項在文檔中的距離也是很容易獲得的。在計算距離時，并不需要確定一個關鍵詞的位置之后再遍歷下一個關鍵詞的所有位置來獲取它們的最小距離。我們采用的方法是：獲取關鍵詞A在文檔D中出現的位置信息，它是一個List，設為AList；獲取關鍵詞B在文檔D中出現的位置信息，它同樣是一個List，設為BList；直接對AList和BList進行處理，計算出AList和BList中最相鄰的兩個數字，它們之間的差值便是關鍵詞A和B的最小距離。此處，沒有考慮AB出現的順序問題，但卻是避免了固定一個關鍵詞的位置再找另一個關鍵詞的位置的開銷，轉而直接對兩個List表進行處理，即使是計算關鍵詞之間的最大距離、平均距離也是比較容易的，同時在時間和資源上的開銷也是很少的。當對查詢語句進行分詞后，只得到兩個關鍵詞時，我們就直接認為它們之間的距離就是這兩個關鍵詞的最小距離。當對查詢語句進行分詞之后，得到兩個以上的關鍵詞時，我們采用的處理方法是：對所有相鄰的兩個關鍵詞的最小距離再進行平均距離的計算，將這個結果作為此查詢語句在該文檔中的距離度量。在實驗中發現，有一種情況是，解析出來的若干個關鍵詞在該文檔中并不一定全部都含有，那么這時就不能為所有的查詢詞項計算它們在文檔中的距離，我們的處理方法是，當一個查詢詞項在一個特定文檔中不存在時，把它和其他查詢詞項的最近距離設為文檔集中所有文檔平均長度的一半，這個值事先已經計算好，作為一個常量進行計算。獲取到查詢語句對文檔的距離度量之后，如何將這個距離度量能夠與BM25F比較合適的結合是一個比較重要的問題。這時需要發現一種情況那就是：關鍵詞越少，關鍵詞的重要性就越大，很多個關鍵詞中丟失一個關鍵詞的影響比兩三個關鍵詞中丟失一個關鍵詞的影響要小很多。BM25F是需要與距離度量成單調遞減的關系，同時需要考慮到關鍵詞丟失的問題，前面已經說明了在丟失關鍵詞之后，處理的方法是將它和其他查詢詞項的最近距離設為文檔集中所有文檔平均長度的一半，這個值在統計學的角度上很大程度上會大于兩個詞出現的最小距離，而造成整個查詢語句在文檔中的距離度量增大。考慮到這一點，需要想到距離小時，距離的變化對整個打分體制的影響較大；距離較大時，對距離的變化對整個打分機制的影響較小。基于以上考慮，我們把距離度量的倒數與BM25F公司相結合，得到一個新的更完善的打分體系，定義如下：實際上在基于距離的BM25F和單純的BM25F在檢索結果上確實存在一定的區別，按照我們對前面兩頁10條數據的人工比對，確實是基于距離的BM25F的檢索結果更加符合我們的預期結果，更能為用戶提供準確的檢索數據。數據庫表設計的優化由于BM25F算法中需要多次使用到文檔長度，在開始階段每次對文檔進行BM25F算法打分的過程中，我們都需要遍歷一遍文檔，以計算出文檔的長度，這種做法開銷太大，對系統的用戶體驗有很大的阻礙。因此在這一塊，我們需要避免多次進行文檔長度的遍歷和計算，減少查詢開銷。考慮到在爬蟲爬取信息的這一階段，信息以及是確定的了，這里只需要將爬去信息的內容進行更詳細的存儲。結合我們的算法要經常用到各字段的長度，而對于一篇已經爬下來的文檔來說，各字段的長度也就定了，我們可以預先計算出各字段的長度，通過在數據庫中增加一些冗余字段，把這些長度存儲在數據庫中，避免重復計算。同時由于對中文詞在存取時已經通過分詞器分詞后再存儲到數據庫中的，所以在數據庫表中對長度的統計引申為對詞數的統計。在數據庫表中針對爬去的標題信息Title字段增加一個title_length作為title字段詞數的計算存儲字段；針對關鍵詞keyword，增加keyword_length字段作為keyword字段字數的計算存儲字段；針對摘要abstract字段，增加abstract_length字段作為abstract字段詞數的計算存儲字段。同樣為了避免掃描整個數據庫中各字段的長度信息來計算整個數據庫文檔中的各字段的平均長度，所以另開辟一塊空間專門來存儲數據庫中所有title、keyword、abstract的平均長度，即平均詞數，該字段同樣存儲計算出此時數據庫中所有文檔各字段的平均長度時，數據庫中已有的記錄總數。圖3-1為數據庫表設計示意圖。圖3-1數據庫表設計示意圖當新的數據進來時，直接取出數據庫中各字段的平均長度與記錄總數，將平均長度與總數相乘以后，加上新數據的各字段的長度，再除以總數加1，得到各字段的新的平均長度，同時更新數據條數，在原來記錄總數上加1后存儲。這樣通過預先對數據分析后，將相應的分析結果進行冗余存儲，這在很大程度上增加了檢索速度，減小了查詢開銷。在實際系統檢索過程中，當輸入檢索關鍵詞，點擊查詢，所提供結果的時間越在1s左右，還可以接受，比未優化之前有很大的改觀，增強了用戶體驗。定時增量索引當第一次創建索引時，數據庫大約有7000條數據，此時創建索引的時間大約在10s左右，當有新的數據存儲進來之后要對新的數據進行索引的創建，一般情況下直接進行索引的創建，掃描整個數據庫，更新整個數據庫的索引，相當于針對所有文件重新做了一次索引，雖然新的索引文件只是比舊的索引文件多了幾條數據，但它的創建確實從頭開始，進行了整個數據庫的索引創建，這個對時間和資源消耗太大。針對此問題，我們通過查閱資料發現，現在已經有了增量索引的機制，也就是每次只針對新數據進行索引文件的創立，再將新的索引文件內容加入到原來的索引文件中去。具體思路如下：在第一次創建索引之后，我們保存創建最后一條索引的記錄的ID，記作lastIndexID；過了一段時間，取出存儲的記錄lastIndexID；遍歷數據庫，找到該記錄，從該記錄的下一條記錄開始進行索引文件的創建；獲取此時創建的最后一條索引的記錄的ID，更新lastIndexID，并進行存儲。將新的索