專業搜索引擎搜索結果融合算法研究

郝 偉，楊國霞，郝志杰

（1.防災科技學院災害信息工程系，河北三河 065201；2.河北科技大學信息科學與工程學院，河北石家莊 050018；3.滄州職業技術學院信息工程系，河北滄州 061001）

隨著互聯網為代表的信息網絡飛速發展，以光速傳播的信息資源呈爆炸性增長和累積。如何在快速增長的浩如煙海的信息海洋中通過計算快速有效地搜索需要的信息成為人們關注的問題。由于各搜索引擎的算法和機制不同，同一檢索請求在不同搜索引擎中的查詢結果也不盡相同，因此，用戶往往會對多個搜索引擎進行檢索，這就增加了用戶的工作量，元搜索引擎正可以解決這一問題。但是對于專業用戶來說，使用普通的元搜索引擎檢索信息時，得到的多數網頁是沒有用的。因此，建立專業化的元搜索引擎具有通用搜索引擎所不具有的優勢，更符合時代的要求。

1 關鍵技術分析

1.1 元搜索引擎技術分析

元搜索引擎（meta-search engine）是指在統一的用戶查詢界面和信息反饋形式下，共享多個搜索引擎的資源庫為用戶提供信息資源檢索的系統，也就是對多個獨立搜索引擎的整合、調用、控制和優化利用。在用戶檢索時，元搜索可以根據提交的檢索請求，調用各獨立搜索引擎進行搜索，并對檢索結果進行匯集、去重、排列等優化處理后，以統一格式在同一界面集中顯示［1-2］。

根據元搜索引擎工作原理分析，得出其中需要解決的如下問題［3-4］。

1）獨立搜索引擎的選擇 目前存在的獨立搜索引擎很多，元搜索引擎需要選擇哪些獨立搜索引擎直接關系著搜索結果質量的好壞。在搜索引擎的選擇中，需要考慮技術方面的問題包括：在使用獨立搜索引擎時，建立的索引集不可得，而且經常會發生變化；其次，獨立搜索引擎使用的技術也有所區別。因此，建立元搜索引擎需要在搜索結果的質量和網絡資源消耗之間作個權衡。

2）檢索條件轉化 獨立的搜索引擎是直接對用戶的查詢條件進行處理，而元搜索引擎是將收到的檢索請求發送給獨立搜索引擎，并且在發送之前需要將檢索請求轉化成各個搜索引擎能處理的格式。因此，元搜索引擎要考慮針對不同的獨立搜索進行請求轉化處理。

3）結果融合 結果融合是元搜索引擎的最核心問題。獨立搜索引擎檢索的標準和排序算法各不相同，如何將所有搜索引擎的反饋結果整合成一個單一的結果列表，客觀地綜合參考各搜索引擎的相關性評價，在最后結果中精確地體現相關性和重要性，是非常復雜和值得研究的問題［5］。

1.2 PageRank算法

PageRank算法的基本思想主要是來自傳統文獻計量學中的文獻引文分析。PageRank算法認為：如果一個頁面被一個重要鏈接所指向，那么此頁面所指向的其他鏈接的重要性也相對提高。因此，PageRank將頁面的鏈入數加以考慮計算頁面的PageRank值，鏈入數越多的頁面其PageRank值也越高。PageRank算法是建立在隨機沖浪者模型上的。具體來說，假設沖浪者跟隨鏈接進行了若干步的瀏覽后轉向一個隨機的起點網頁又重新跟隨鏈接瀏覽，那么一個網頁的價值程度值就由網頁被這個隨機沖浪者所訪問的頻率所決定。PageRank計算公式如式（1）所示：

其中：PR（u）為頁面u的 PageRank值；u為1個頁面；B（u）為指向頁面u的集合；PR（v）為頁面v的PageRank值；Nv為頁面所指向的外鏈接總數；c為規范化因子，取0.85。

1.3 rtf算法

在信息檢索中，為了實現檢索目標，需要對檢索策略進行修改、擴展和完善。相關反饋是一種自動查詢擴展方法，對于檢索詞也提出了多種排序算法［6］。Harman基于概率模型及Haines和Croft基于推理網絡模型研究了大量檢索詞排序算法，其中rtf算法和rtf＊idf算法還可以用作推理網絡概率模型中的檢索詞權重計算公式。

rtf算法的基本思想為檢索詞在相關文獻的集中出現頻次的均值s（tk）。其計算公式如式（2）所示：

其中：s（tk）為檢索詞出現的頻次均值；R為相關文獻集合；tf為檢索詞在文獻中出現的頻次；為檢索詞在整個文獻集上的總出現頻次。

rtf＊idf算法的基本思想為檢索詞在相關文獻集中出現頻次的均值rtf與檢索詞逆文獻頻率idf相乘。idf部分用于調整同時在相關文獻和不相關文獻中出現的檢索詞的排序權值。其計算公式如式（3）所示。

其中：|D|為文獻集合的大小；|Dtk|為包含檢索詞的文獻數量。

2 專業搜索引擎算法的實現

2.1 重復搜索記錄的去除

元搜索引擎在提取了各個獨立搜索引擎的結果之后，把提取出來的標題、摘要、URL等分別存儲在各個列表中。不同獨立搜索引擎的搜索結果有所重復，因此，去除搜索結果中的重復數據是非常必要的，其算法流程如圖1所示。

圖1中：N為獨立搜索引擎的個數；RecordI為第I個獨立搜索引擎的記錄個數；I為獨立搜索引擎的循環參數；J為獨立搜索引擎記錄個數的循環參數。

2.2 融合后結果排序的算法改進

在對搜索結果進行去重之后，需要對這些搜索結果進行排序，然后顯示給用戶。搜索結果的排列順序直接影響用戶對查詢結果的滿意程度。第1代搜索引擎是根據索引頁面與查詢詞的相似性來排列其返回結果；以Google為代表的第2代搜索引擎開創了基于頁面間鏈接分析的頁面重要性評價方法，其核心內容為PageRank算法［6］。

對于專業搜索引擎來說，具有很強的領域針對性和很強的檢索準確性。PageRank算法只考慮了頁面之間的鏈接關系，沒有考慮查詢詞所出現的位置、次數以及是同義詞或相關詞等。因此，需要對該算法進行進一步的改進。

在改進的算法中，除了考慮頁面之間的鏈接關系，還要考慮根據查詢詞所出現的位置和次數、是否為查詢詞的同義詞或為查詢詞的相關詞［7］。其中查詢詞出現位置和次數的權重值函數如式（4）所示：

圖1 搜索結果去重流程圖Fig.1 Chart of search result about removing redundant

其中：M為查詢主題的集合；N為查詢主題在網頁中出現位置的集合；αql為關鍵詞q在位置l中出現的次數；為關鍵詞q在位置l出現時的權重。

考慮到搜索結果的速度問題，選用rtf算法作為檢索擴充詞的權重值算法，計算公式如式（5）所示：

其中：f（tk）為檢索詞出現的頻次均值；R為相關文獻集合；tf＊ik為檢索詞在文獻中出現的頻次；df′k為檢索詞在整個文獻集上的總出現頻次。

則計算公式可改為

3 算法實驗與分析

3.1 實 驗

采用改進的PageRank算法進行專業搜索引擎的設計，可以改善搜索結果的排列順序，更符合用戶的需求，體現出專業搜索引擎的專業性和準確性。在PentiumⅣ 的CPU，2GB內存；Windows XP操作系統，IE7.0的瀏覽器；100MB局域網的環境下，分別使用獨立搜索引擎和專業搜索引擎對關鍵詞“自燃傾向性、煤的有機顯微組分、煤的顯微構造、煤化作用、巖石組構”進行搜索，其結果如表1、表2所示。

表1 搜索引擎搜索時間比較Tab.1 Comparison of some search engines on search time s

表2 搜索引擎搜索結果個數比較Tab.2 Comparison of some search engines on search result篇

3.2 結果分析

3.2.1 檢索時間的分析

煤地質學搜索引擎的設計采用元搜索引擎與垂直搜索引擎相結合，獨立搜索引擎之間采用并行接口，則在理論上該搜索引擎的反應時間應該滿足式（7）。

其中：T（Sn）為搜索引擎Sn完成搜索的時間；flagn為搜索引擎Sn被用戶選中的狀態，被選中為1，未被選中為0。

在實際情況中，元搜索引擎的反應時間與用戶所選中的獨立搜索引擎的個數成正比，用戶選用的獨立搜索引擎越多，返回的檢索結果就越多，需要整合結果的時間就越長。

通過表1可以看出，煤地質學搜索引擎的檢索速度滿足了式（7）的要求，雖然有一些時間延遲，卻是在用戶的容忍度范圍內的。通過對一些重復結果的去除、整理，相對縮短了用戶查看信息的時間，從某種程度上說，提高了查詢的效率。

3.2.2 信息查全率的分析

查全率是用來評價元搜索引擎的又一重要指標。信息查全率是指系統在進行一次檢索時，查詢到相關文獻的能力［8］。其理論計算公式如式（8）所示：

其中：p為搜索引擎的查全率；NR為被檢索出來的相關文獻數量；NT為所有相關文獻的總量。

對于獨立搜索引擎來說，由于網頁抓取程序覆蓋范圍和更新頻率的不同以及搜索結果排序算法的不同，導致對于同一個查詢請求，不同的獨立搜索引擎會有不同的搜索結果，這樣導致了只使用一個搜索引擎的用戶將會遺漏許多有用的結果。曾有實驗研究表明，在Google、百度和雅虎3個搜索引擎第1頁結果的重合率為2.54%，前兩頁結果的重合率為2.20%；從漏檢率來看，百度為63.32%，Google為61.85%，雅虎為61.63%［9］。上述數據可以得出元搜索引擎與獨立搜索引擎相比具有很高的查全率。

煤地質學搜索引擎的結果是綜合了多個獨立搜索引擎的返回結果而得，在信息的查準率方面是具有絕對優勢的。但是從搜索用戶體驗的角度考慮，通常情況下，用戶不會將所有的搜索結果一一查看。從CNNIC發布的“2009年中國搜索引擎用戶行為研究報告”中可以了解到：56.6%的用戶只看搜索結果前2頁的內容，查看前3頁的用戶數量下降到10.3%，愿意查看3頁以上內容的用戶只有8.7%，如果搜索結果不是數十頁的話，差不多會有10%的用戶可以看完全部結果［10］。在這種情況下，為了提高用戶查看搜索結果的概率，煤地質學搜索引擎只提取獨立搜索引擎的前100個結果進行整合、排序。但是，為了體現搜索結果的全面性，該系統可以為用戶提供沒有經過處理的各獨立搜索引擎的其他結果。

從實驗結果表2可看出，煤地質學搜索引擎給用戶提交的結果與其他獨立搜索引擎相比，數量大大減少，但是，這些結果的數量是在用戶能夠全部查看的范圍內，所以說搜索結果的查全率相對提高了。

從以上2個方面來看，煤地質學搜索引擎與獨立搜索引擎相比都有很大的提高，從總體設計和出發點來說，都是非常有價值的，但是由于該系統還處于初級開發階段，對于以上提供的量化數據只是初步的實驗結果，只能進行定性的分析，不能作為定量分析之用。

4 結 語

搜索結果的排序是查詢的最直觀結果，原始的PageRank排序算法只考慮了Web頁面之間的超鏈接分析，而忽略了Web頁面的內容，從而導致分析結果出現主題漂移等問題，在此提出了一種基于PageRank算法的改進型結果排序及結果融合算法，提高了搜索結果的準確性。在實際環境測試中，筆者提出的算法比獨立搜索引擎具有更好的搜索結果相關性，為煤地質科學工作者提供了面向煤地質學領域的便捷、準確的專業化信息檢索工具。

［1］ 龔蛟騰.元搜索引擎研究［J］.情報雜志（Journal of Information），2004（10）：77-78，81.

［2］ 吳小蘭，汪 琪.元搜索引擎研究綜述［J］.圖書情報工作（Library and Information Service），2009，53（9）：46-49.

［3］ 李廣建，黃 崑.元搜索引擎及其主要技術［J］.情報科學（Information Science），2002，20（2）：175-179.

［4］ 陳 晶.元搜索引擎實現技術［J］.情報雜志（Journal of Information），2005，24（5）：79-81.

［5］ 張立巖，呂 玲，王井陽.基于最大熵算法的全文檢索研究［J］.河北科技大學學報（Journal of Hebei University of Science and Technology），2009，30（2）：112-115.

［6］ LANGVILLE A N，MEYER C D.Deeper inside PageRank［J］.Internet Mathematics，2003，1（3）：335-380.

［7］ 侯貴賓，曹衛東.一種面向自然語言表達的不確定時態數據的建模方法［J］.河北科技大學學報（Journal of Hebei University of Science and Technology），2010，31（5）：463-467.

［8］ 海 濤，鄭 玲，江 娟.垂直搜索引擎中數據采集的主題相關性算法研究［J］.中國電力教育（China Electric Power Education），2007（S1）：108-109.

［9］ 王益明，劉 菲.中文搜索引擎的搜索結果重合率研究 ［J］.情報學報（Journal of the China Society for Scientific and Technical Information），2009（3）：374-381.

［10］ 中國互聯網絡信息中心.2009年中國搜索引擎用戶行為研究報告［EB／OL］.http：／／research.cnnic.cn／html／1253600840d1370.html，2009-09-22.