元搜索引擎排序技術綜述
2009-01-01 00:00:00曹林韓立新吳勝利
計算機應用研究 2009年2期
（1.河海大學 計算機及信息工程學院， 南京 210098；2.阿爾斯特大學 計算機與數學學院， 英國 貝爾法斯特）
摘 要：如何排序是實現元搜索引擎的一項關鍵技術，排序算法的好壞直接決定著元搜索引擎的性能。對元搜索引擎常用的排序算法根據其發展先后順序作了介紹，對一些經典的算法進行了分析和評價，歸納出元搜索引擎排序算法適用的不同環境，最后對元搜索引擎排序算法未來發展方向作了技術展望。
關鍵詞：元搜索引擎；結果集成；排序算法；相關性
中圖分類號：TP391 文獻標志碼：A
文章編號：10013695(2009)02041104
Ranking algorithms for metasearch engine
CAO Lin1，HAN Lixin1，WU Shengli2
(1.College of Computer Information Engineering， Hohai University， Nanjing 210098， China；2.School of Computing Mathematics， University of Ulster， Northern Ireland， Belfast，UK)
Abstract:Ranking is a key technology to carry out meta search engine. Whether the ranking algorithm is good or not will derectly decide the function of the meta search engine.Provided a survey of the study in the common use ranking algorithms for metasearch engine，analysed and evaluated some classical algorithms.Summmed up the suitable different environment，viewed some future directions in ranking algorithms for metasearch engine.
Key words:metasearch engine; result merging; ranking algorithms; relevancy
0 引言
搜索引擎是一種基于關鍵字查詢的信息檢索工具，近十年來隨著因特網的普及而得到迅速發展，為用戶在網絡上查找信息提供了一套極為便利的工具。目前搜索引擎的種類較多，品牌也越來越多，服務也越來越豐富，其采取的技術、算法、適用范圍等也各不相同。但是目前還沒有哪個搜索引擎返回的結果能夠覆蓋所有的相關資源，大部分搜索引擎返回的結果只是涉及到整個相關資源的一小部分，如AltaVista、HotBot、Excite和Infosee所標引的網頁不到所有搜索引擎搜索網頁的1%[1]；另外對于某個查詢，不同搜索引擎查詢結果的重疊率不足34%[1，2]。因此要想獲得一個比較全面、準確的結果，就需要將多個搜索引擎綜合在一起。1995年，華盛頓大學碩士生Eric Selberg和Oren Etzioni推出了第一個元搜索引擎MetaCrawler，此后這一新型的網絡檢索工具迅速發展起來。盡管它在諸多技術上還存在一定局限性，但是它具有覆蓋面大、查準率高、易維護等優點，它的出現在一定程度上解決了搜索引擎查全率和查準率低的問題。
元搜索引擎是一種建立在搜索引擎基礎上，調用多個成員搜索引擎的搜索引擎，亦稱“搜索引擎之母（the mother of search engines)”。這里的“元”有總的、超越之意。對于某個給定的查詢，元搜索引擎將其發送到其調用的幾個成員搜索引擎，待成員搜索引擎完成查詢后，收集各個搜索引擎查詢的所有結果，去重整理后按照一定的排序方法最終顯示給用戶。由于元搜索引擎的結果規模比較龐大，而用戶又往往缺乏足夠的耐心去遍歷這些海量信息，他們一般只會檢索前面幾條或者幾十條信息，如何將用戶想要的信息盡可能地排在前面（結果排序）顯得尤為重要，同時它也是影響元搜索引擎性能的關鍵技術。
1 元搜索引擎排序的基礎算法
元搜索引擎排序是指對其調用的多個成員搜索引擎所返回的結果進行收集、去重處理，然后按照一定的準則排序，最終將排序結果按一定順序展現給用戶的過程。由于調用的成員搜索引擎可以各式各樣，其收集的查詢結果組成也形式多樣，歸納起來其結果主要是由網址（URL）、網頁標題、內容摘要、相關度等信息組成。因此元搜索引擎排序可以在利用成員搜索引擎排序的基礎上，從網頁標題、內容摘要等方面著手考慮。總的來說，其排序方法可以從以下三方面來闡述。
1.1 收集結果重新排序
這種排序的方法比較單一，相當于把成員搜索引擎搜索的結果融合到一起再重新選擇一種方法排序。這種方法僅僅提高了查全率，對于一些重要的信息，可能會排在比較靠后的位置而不易被用戶檢索到，準確率也不高。早期的元搜索引擎通常使用這種算法思想。基于此類算法思想的方法主要有直接合并、根據響應速度排序、摘要排序。
1）直接合并
直接合并[1]是一種元搜索引擎最原始的一種排序方式，它直接將不同搜索引擎的結果合并，然后返回給用戶。由于用戶一般只對排列在前幾頁的信息感興趣，而排在后面的搜索引擎的許多結果信息被無形地忽略掉了。對于用戶來說，這種結果顯示方式和一般的搜索引擎差別不大，對于某個查詢，其查詢速度也比較慢，現在已經很少使用該方法。
2）根據響應速度排序
對于某個查詢來說，每個成員搜索引擎查詢結果的速度是不一樣的，為了減少用戶的等待時間，按照搜索引擎搜索結果出現的時間先后順序排序返回給用戶。它是針對直接合并速度比較慢的問題的一種簡單改進，排序的結果也不能夠提高用戶的滿意度。
3）摘要排序法
摘要排序法[1]是基于相關度排序算法的一種，其主要思想是根據用戶輸入的查詢串與各個成員搜索引擎搜索的結果記錄摘要信息之間的相關性來進行排序，相關性大的結果排在前面。摘要排序法的優點是實現簡單、速度快；缺點是返回的摘要過于簡單，而且各個獨立搜索引擎的用戶接口不同，導致同一個結果在不同的獨立搜索引擎返回的摘要不同。摘要排序法往往導致返回摘要信息多的搜索引擎的搜索結果排名靠前，而不是與結果詞條相關度高的搜索結果排名靠前。
4）按照某種成員搜索引擎排序方法排序
在知道某種搜索引擎的排序方法后，可以將結果收集在一起利用該搜索引擎的排序算法排序，這種方法比較直觀，思路也比較清晰。但是某個搜索引擎的排序算法越好，涉及的結果內容因素越多。這些結果是通過不同的搜索引擎搜索得到的，有些結果信息很單一，不能滿足該排序算法的諸多因素需求。另外，搜索引擎的排序算法一般是不公開的，很難獲取這些技術細節，所以該方法實現起來比較困難。
1.2 利用搜索引擎排序信息排序
將各個成員搜索引擎所返回的結果集中在一起重新排序，這樣就打亂了原來搜索引擎的排序信息，而這些信息也是非常重要的排序依據。盡管有些成員搜索引擎的排序方法未知，但是它肯定是按查詢結果與查詢串的相關程度大小排序的，只不過不同的搜索引擎所側重的因素不同。若是能充分利用各成員搜索引擎的排序信息，在其基礎上進一步地合成，則能夠將查準率進一步提高。輪詢法、星星排序、Borda排序、貝葉斯概率模型排序、位置排序等方法就是基于此基礎上的。
1）輪詢法（roundrobin）
輪詢法的思想也比較簡單，首先把成員搜索引擎根據其性能按照一定次序排列好，然后按照這些次序將每個查詢結果中的第一項依次列出，再把每個查詢結果中的第二項依次列出，依此類推。一個結果出現在多個搜索引擎中的以第一次出現該結果的為基準，后面出現的不再參加排序。中途出現某搜索引擎的結果已經取完時，則跳轉到下一個搜索引擎。輪詢法最初雖然按照搜索引擎的性能給予排序，但沒有充分考慮到成員搜索引擎之間的差異，當相同的結果記錄在多個成員搜索引擎中同時出現并且位置不一樣時，處理得也不是很好，但它是后來發展的諸多排序算法的基礎。現在一些元搜索引擎使用的都是對其改進后的算法，如加權輪詢法等。
2）星星排序
星星排序[1]是建立在各個成員搜索引擎排序信息基礎上的一種信息融合方法，它首先統計某個搜索結果記錄在多少個成員搜索引擎的前面幾條信息中出現，以此作為相關度評價指標。對于某個查詢結果，若其在一個成員搜索引擎的前幾條中出現，就得到一個“星”，得到的“星”越多，則該記錄就越重要；然后對所有結果都進行統計；最后比較每個結果所得的“星”的個數，將所有結果按照所得“星”個數多少進行排序。星星排序比較適合于調用多個成員搜索引擎的情況，對于成員搜索引擎個數比較少的情況，則容易出現多個結果“星”個數相同的情況，不易排序。元搜索引擎Ixquick和Metor都是基于相關度結合“星星”評價指標排序的。
3）Borda排序
Borda排序[3]最初是用于民主政治選舉，選民對各候選人進行投票后，對于每個候選人進行統計票數，最后按照得票數多少進行排序，票數最高的排在最前面。后來有人將此法改進后用于元搜索引擎結果排序，對于某個查詢，它被幾個成員搜索引擎檢索到，則該結果記錄就得幾票，最后統計各個結果記錄的票數，按照票數多少排序。很明顯，被多個成員搜索引擎檢索到的結果記錄更有可能排在前面。為了更好地利用原來成員搜索引擎的排序信息，對每個成員搜索引擎的結果按照從前到后的順序分配一定的權值，統計結果時乘以相應的權值。這樣就能夠將每個結果所得票數細化，排序就方便多了。通過比較可以發現，Borda排序與星星排序也有相似之處。同樣，Borda排序也比較適用于調用成員搜索引擎個數較多的情況，它給每個成員搜索引擎的結果分配權值的情況對星星排序也同樣適用。但是Borda排序僅僅考慮到了同一個結果文檔被多個搜索引擎檢索的重要性，卻忽視了某些文檔被少數搜索引擎檢索到的重要性，而這些文檔確有可能是相關性比較大的。所以Borda排序在成員搜索引擎查詢結果重疊率較高的情況下才適用。
4）位置排序
位置排序[4]的基本思想也是充分利用各獨立搜索引擎返回的結果記錄集合中原來的排序信息，同時給每個成員搜索引擎分配了優先級。不同的搜索引擎對于相同的查詢可能會得到一些相同的結果，但是相同的幾個搜索結果在不同的成員搜索引擎中返回的次序可能不一樣。位置排序法就是專門為了調和這種矛盾而設計的排序方法。
對于某個元搜索引擎來說，假設其調用的成員搜索引擎個數為n，成員搜索引擎si(i=1，2，…，n)的優先度為pi(i=1，2，…，n)。對于某個搜索結果，令其在搜索引擎si中的排序位置為qi（若不在該搜索引擎中出現，則qi為無窮大），那么該搜索結果的相關度計算公式為score(q)=ni=1pn-i+1/q。通過此公式計算所有搜索結果的相關度，然后按照相關度大小的順序排序。
5）概念可信度排序
概念可信度排序[5]與Borda排序法有點相似，對于某個查詢，將每個搜索引擎的前1 000項按照位置前后順序分配相關分值，第一項賦值為1 000，第二項賦值為999，依此類推，最后一項賦值為1；然后將每個結果在各個成員搜索引擎中的相關分值相加（沒有在其他搜索引擎中出現的則在該搜索引擎中的相關分值為0）；最后將結果按照相關分值和的大小順序排序分頁返回給用戶。元搜索引擎MetaCrawler的就是使用該方法來進行排序的。概念可信度排序給每個成員搜索引擎的結果按照先后順序分配了一定的分值，這些分值與其位置呈線性遞減關系。實際上，相關分值與位置之間并不一定是線性關系，更多的是呈一定的曲線遞減關系。若是每個成員搜索引擎對其結果都分配了相關分值，則利用相關分值與其位置之間的關系擬定函數則比較好。但是比較優秀的幾個成員搜索引擎如Google、百度等都不顯示相關分值，這樣要使概念可信度排序方法獲得較好的排序結果，實現起來就有一定的難度。
6）貝葉斯概率模型排序
貝葉斯概率模型排序[5]也是基于成員搜索引擎排序基礎之上的一種概率模型排序方法。對于某個查詢，元搜索引擎可以得到各個成員搜索引擎的查詢結果文件排序列表。假設ri(d)表示成員搜索引擎si賦值為搜索結果d的相關度（如果文件d沒有被系統i檢索到，那么它的相關度為∞），各個成員搜索引擎對于該文檔評價的相關度提供給原搜索引擎。假定Qre=Qr[r1，r2，…，rn]re;Qir=Qr[r1，r2，…，rn]ir。其中：Qre是給定的文件相關的概率值；Qir是給定的文件不相關的概率值。給定序列r1，r2，…，rn，規定如果Qre＞Qir則文檔是相關的；反之則不相關。這樣就可以計算出Ore=Qre/Qir，即相關度的幾率，然后根據這一價值尺度來排序。
1.3 相關分值融合
相關分值融合[6]也是充分利用各個成員搜索引擎的排序信息。針對某個查詢，各成員搜索引擎對自己搜索的所有結果均根據不同的情況分配一定的相關分值，對于同一結果在多個搜索引擎中出現的，將它們的相關分值進行融合后再排序。相關分值融合的方法有很多種，其中以Comb融合法（六種）、SDM融合法、MEM融合法、CORINET排序等最為常見。
1）Comb排序
Comb排序[6，7]是基于規范化賦值的多種排序合稱，對于某一查詢，若某一文檔被各成員搜索引擎檢索到(還有其他一些成員搜索引擎雖然被元搜索引擎調用，但沒有檢索到該文檔)，并根據不同位置給出了n個不同的相關分值。元搜索引擎首先將該相關分值歸一化后變換到[0 ，1]區間，排名靠前的分值大一些，靠后的分值小一點；然后對每個文檔在這n個成員搜索引擎中的相關值進行綜合處理，將處理后的值作為該文檔的相關度；最后對所有結果文檔按照此相關度大小排序。常見的處理方法有六種分別描述如下：
a）CombMIN。對于某文檔，取該文檔在n個成員搜索引擎中最小的相關值作為該文檔的CombMIN值。
b）CombMAX。對于某個文檔，取該文檔在n個成員搜索引擎中最大的相關值作為該文檔的CombMAX值。
c）CombSUM。對于某個文檔，將其在這n個成員搜索引擎中的n個相關分值相加作為該文檔的CombSUM值。
d）CombMNZ。它是建立在CombSUM基礎上的，將該文檔的CombSUM值乘以n便得到該文檔的CombMNZ值。
e）CombANZ。對于某文檔，其在這n個成員搜索引擎中的n個相關分值的平均值作為該文檔的CombANZ值。
f）CombMED。對于某文檔，其在這n個成員搜索引擎中的n個相關分值的相似中位數作為該文檔的CombMED值。
以上六種相關分值融合中，對于不同的搜索結果文檔其n取值可能不同。Comb排序具有簡單、直觀的優勢，但是它在使用上卻具有一定的限制。在假定各個成員搜索引擎具有相同的檢索數據庫前提下，Comb排序的優勢才比較明顯，然而這樣的假定前提對于不同的成員搜索引擎來說卻是不能夠成立的。尤其是調用的成員搜索引擎個數較多時，該方法就會顯得“頭重腳輕”，所以Comb排序只適合成員搜索引擎個數較少的情況。SDM法就是為解決這樣問題而采取的一種相關分值合成法。
2）SDM法
SDM法（shadow document method）[8，9]是一種基于相關分值的合并方法，算法描述如下：假設元搜索引擎調用了n個成員搜索引擎，對于某一查詢q，包含某個記錄結果d的搜索引擎對于記錄結果d分別賦予了一定的相關分值Si(1≤i≤m≤n)，那么可以計算出d的總相關分值score(d)。計算公式如下：
score(d)=mi=1Si+[k(n-m)/m]mi=1Si
其中k是權重系數，對于不含記錄結果d的成員搜索引擎，分配d與m個相關的成員搜索引擎的均值，并將其值乘以權重系數k以便更好地區分成員搜索引擎之間的相關值。最后將每個記錄結果按照總相關分值從大到小的順序依次排序展現給用戶。相對Comb排序，SDM法則不需要求各個成員搜索引擎具有相同的數據庫，適用范圍更加廣泛。
3）MEM排序（multievidence method）
MEM排序[2 ，7]是在規范化分值的基礎上引入數學函數，首先令記錄結果d在m個成員搜索引擎結果中均出現，針對d在m個成員搜索引擎結果記錄中的不同位置分配不同的分值，排名靠前的分值相應大一些，排名靠后的分值小一些。為便于計算，將這些分值全部規范化后分別為Si(1≤i≤m)，同時引進函數f(m)，那么記錄結果d的總相關分值為
F(d)=f(m)×avg_score
其中avg_score=（1/m）mi=1Si。最后按照F(d)值的大小排序，最終分頁返還給用戶。如何確定f(m)的值是MEM算法的關鍵，目前對函數f(m)的確定僅僅停留在嘗試方面，即取不同的函數值代入，然后比較這些排序結果，找出相對的最優函數。盡管也取得了一些較滿意的排序結果，但仍不能確定它是最優的。
4）CORINET排序
CORINET排序[10]主要是利用一定的規則對其調用的成員搜索引擎給予分配權重，再結合搜索結果在該成員搜索引擎結果中的位置信息來進行排序。對于某個元搜索引擎所調用的成員搜索引擎D來說，假設其優先度系數為s，令為所有成員搜索引擎優先度分值的均值，N為成員搜索引擎的個數，那么成員搜索引擎D的權重可以表示為w=1+N×[(s-）/]。很明顯，在N固定時，當s＞時，w的值大于1，并且s與之間的差距越多，則w的值就越大；反之，當s＜時，w的值小于1，并且s與之間的差距越多，w的值就越小。確定權重以后，對于查詢結果d在搜索引擎D中的相關性系數用x表示，那么d在D中的相關分值就可以表示為w×x。很明顯，被優先度高的搜索引擎檢索到的結果更有可能排在前面。但是如何對成員搜索引擎確定其優先度系數還需要一系列復雜的計算過程，如果僅僅依靠人為的規定，勢必會影響用戶對其排序結果的滿意度。
1.4 算法的改進
對于元搜索引擎排序方面，其改進的方法主要體現在兩個方面：a）直接將兩種或者兩種以上的基礎算法進行綜合，這也是比較常見的改進方法。摘要/位置排序法[10，11]就是將摘要排序法和位置排序法綜合在一起的。元搜索引擎Ixquick、Metor結果排序方式都是基于相關度與星星評價指標相結合的排序算法[1，5]。 b)針對成員搜索引擎性能的不同分配一定的權重，權值與所引用的搜索引擎名稱、個數有關，這樣能夠突出成員搜索引擎之間的差異。加權輪詢法[12]、加權規范分值法[12]、加權Comb排序[7]等均是在基礎算法的基礎上為成員搜索引擎分配權值得到的。
2 元搜索引擎排序算法技術展望
由于不同的搜索引擎在收集信息的數量、范圍、排序方法等方面有較大的差異，再加上搜索引擎技術的隱蔽性，設計者很難獲取它們的技術細節。對于元搜索引擎來說，無論采取哪種排序方式，總不能盡如人意。實際上，對某元搜索引擎來說（排序方法已定），不同的查詢，它的查準率和查全率也有不同；對于同一個查詢，不同的排序方式也會引起很大的差別，導致這種問題的主要是信息重疊率[2]的不同。Wu Shengli和McClean經過研究表明，當信息重疊率不同時，各種排序算法差異顯著。所以，要想從排序算法上提高元搜索引擎的查準率和查全率，除了對基礎算法進行改進外，還要根據不同的查詢選擇不同的算法。專業搜索引擎的出現對元搜索引擎來說可以是一個借鑒，即將專業搜索引擎綜合實現專業元搜索引擎；或者將元搜索引擎更進一步的智能化。針對用戶輸入的查詢串自動地進行分類，然后根據類別選擇最佳的排序方法。
當然，對于某個固定的元搜索引擎，還可以通過科學的統計方法來檢測成員搜索引擎的技術細節，盡管檢測出來的技術細節不是很精確，但卻能夠在一定程度上反映出該成員搜索引擎的技術情況。綜合這些技術給出一個統一排序方法對所有結果進行重新排序，這樣勢必能夠提高用戶的滿意度。
參考文獻：
[1]徐寶文，張衛豐.搜索引擎與信息獲取[M].北京：清華大學出版社，2002.
[2]WU Shengli，McCLEAN M.Result merging methods in distributed information retrieval with overlapping databases[J].Information Retrieval，2007，10(3):297319.
[3]FRANCIS N.Voting as a method for rank aggregation and spam reduction on the Web[D].New Howen:Yale University，2005:2338.
[4]張強弓，喻國寶，廖湖聲，等.一種元搜索引擎的查詢結果處理模型[J].華南理工大學學報：自然科學版，2004，32(Z1):4751.
[5]文坤梅，盧正鼎，鄧曦，等.元搜索引擎中檢索結果排序的優化方法[J].華中科技大學學報，2003，31(3):4951.
[6]JIJKOUN V，RIJKE M D.Answer selection in a multistream open domain question answering system[EB/OL].(20080401)[20080430].http://staff.science.uva.nl/~jijkoun/papers/ecir04.pdf.
[7]WU Shengli，McCLEAN S.Performance prediction of data fusion for information retrieval[J].Information Processing Management，2006，42(4): 899915.
[8]WU Shengli，CRESTANI F.Shadow document methods of resutls merging[C]//Proc of ACM Symposium on Applied Computing.New York:ACM Press，2004:1417.
[9]WU Shengli，McCLEAN S.High accuracy retrieval by eliminating the uneven correlation effect in data fusion[J].Journal of the American Society for Information Science and Technology，2006，57(14):19621973.
[10]MENG Weiyi，YU C.Building efficient and effective metasearch engines[J].ACM Computer Surveys，2002，34(1):4889.
[11]BAEZAYATES R，RIBEIRONETO B.Modern information retrieval[M].王知津，賈福新，等譯.北京：機械工業出版社，2005.
[12]彭喜化，張林.基于agent的元搜索引擎結果優化技術[J].計算機應用，2003，23(12):6872.［13］WU Shengli，CRESTANI F，GIBB F.New methods of results merging for distributed information retrieval[C]//Proc of Workshop on Distributed Multimedia Information Retrieval.Berlin:Springer，2004:84100.
[14]WU Shengli，McCLEAN S.Data fusion with correlation weights[C]//Proc of the 17th International Conference on Information and Knowledge Management.Berlin:Springer，2002:648651.
[15]WU Shengli，CRESTANI F.Methods for ranking information retrieval systems without relevance judgments[C]//Proc of the 18th ACM Symposium on Applied Computing.New York:ACM Press，2003：811816.
[16]BEITZEL S M，JENSEN E C，CHOWDHURY A，et al.Fusion of effective retrieval strategies in the same information retrieval system[J].Journal of the American Society for Information Science Technology，2004，55（10）：859868.
[17]CALLAN J P，LU Z，CROFT W B.Searching distributed collections with inference networks[C]//Proc of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM Press，1995:2128.
[18]KHOUSSAINOV R，KUSHMERICK N.Distributed Web search as a stochastic game[EB/OL].(20080501)[20080530].http://boston.lti.cs.cmu.edu/callan/Workshops/dir03/PapersPublished/khoussainov.pdf.
[19]SELBERG E W.Towards comprehensive Web search[D].Washington DC：University of Washington，1999.
[20]HSU D F，TAKSA I.Comparing rank and score combination，methods for data fusion in information retrieval[J].Information Retrieval，2005，8(3):449480.
