淺析Web元搜索引擎排序算法

文/桑秀芝

（南京航空航天大學(xué)金城學(xué)院 江蘇·南京）

一、序言

Internet上的信息量已呈爆炸性趨勢(shì)增長(zhǎng)，據(jù)研究報(bào)告顯示，Internet上的網(wǎng)頁(yè)目前已超過(guò)數(shù)百億，如何從浩如煙海的信息中查找需要的信息成為人們最關(guān)心的事情。搜索引擎就是為了幫助人們解決這一問(wèn)題而開(kāi)發(fā)出的一種高效的信息檢索工具，它已經(jīng)成為Internet中最重要的部分。然而，目前還沒(méi)有哪個(gè)獨(dú)立的搜索引擎能夠覆蓋整個(gè)網(wǎng)絡(luò)，而且由于所采用機(jī)制、算法與適用范圍等的不同，導(dǎo)致同一搜索請(qǐng)求在不同搜索引擎中獲得的查詢(xún)結(jié)果的重復(fù)率不足34%，而每一個(gè)搜索引擎的查準(zhǔn)率不到45%。因此，要想獲得一個(gè)比較全面、準(zhǔn)確的結(jié)果，需要同時(shí)使用具有不同數(shù)據(jù)搜索范圍的搜索引擎，在多個(gè)檢索結(jié)果列表之中挑選對(duì)自己有用的內(nèi)容，這就增加了檢索的不便。Web元搜索引擎的出現(xiàn)，在一定程度上解決了這些問(wèn)題。Web元搜索引擎是集成多個(gè)搜索引擎的特殊搜索引擎。用戶(hù)輸入查詢(xún)后，系統(tǒng)將查詢(xún)?cè)~發(fā)送給成員搜索引擎，各成員搜索引擎開(kāi)始檢索。檢索完畢后，系統(tǒng)將各部分結(jié)果集合在一起，整理后采用一定的排序方式返回給用戶(hù)。將多個(gè)搜索引擎的查詢(xún)結(jié)果集合在一起，這樣可以擴(kuò)大檢索面，提高查詢(xún)率。然而，面對(duì)如此海量的結(jié)果數(shù)據(jù)，系統(tǒng)本身就需要提供一套比較適用的排序算法，將用戶(hù)最想要的結(jié)果盡可能地展現(xiàn)在前幾頁(yè)。因此，排序算法是影響元搜索引擎性能的關(guān)鍵技術(shù)之一。

二、Web元搜索引擎搜索流程

Web元搜索引擎（簡(jiǎn)稱(chēng)元搜索）通過(guò)一個(gè)統(tǒng)一用戶(hù)界面幫助用戶(hù)在多個(gè)搜索引擎中選擇和利用合適的搜索引擎來(lái)實(shí)現(xiàn)檢索操作，是對(duì)分布于網(wǎng)絡(luò)的多種檢索工具的全局控制機(jī)制。其搜索流程如圖1所示。（圖1）可以看出，首先用戶(hù)通過(guò)一個(gè)統(tǒng)一界面輸入查詢(xún)?cè)~，任務(wù)分配器將檢索詞分配給合適的多個(gè)獨(dú)立搜索引擎；各獨(dú)立搜索引擎接收到查詢(xún)?cè)~后，立即進(jìn)行相關(guān)文件查詢(xún)，并按照相關(guān)度高低順序?qū)⒔Y(jié)果文件排列，然后反饋到結(jié)果集成中心；結(jié)果集成中心接收到給定的各獨(dú)立搜索引擎發(fā)回的結(jié)果文件序列后，就將按照一定的排序算法對(duì)所有結(jié)果文件匯總重新排序，最后輸出一個(gè)結(jié)果文件序列給用戶(hù)。這期間，針對(duì)不同的獨(dú)立搜索引擎將用戶(hù)的提問(wèn)做不同轉(zhuǎn)換，以適應(yīng)相應(yīng)索引數(shù)據(jù)庫(kù)的調(diào)用；需要強(qiáng)調(diào)的是，元搜索是基于獨(dú)立搜索引擎結(jié)果的二次加工，元搜索引擎的結(jié)果基于獨(dú)立搜索引擎的查詢(xún)結(jié)果，少數(shù)簡(jiǎn)單的直接調(diào)用原始的結(jié)果頁(yè)面，但這都實(shí)現(xiàn)了對(duì)獨(dú)立搜索引擎查詢(xún)結(jié)果的二次加工，如重復(fù)結(jié)果的刪除、結(jié)果的再度排序等。在定制結(jié)果輸出形式的元搜索引擎中，檢索結(jié)果一般都標(biāo)明記錄的來(lái)源搜索引擎及其相關(guān)度。

三、Web元搜索引擎排序機(jī)制

Web元搜索引擎排序是指對(duì)其調(diào)用的多個(gè)成員搜索引擎所返回的結(jié)果進(jìn)行收集、去重處理，然后按照一定的準(zhǔn)則排序，最終將排序結(jié)果按一定順序展現(xiàn)給用戶(hù)的過(guò)程。由于調(diào)用的成員搜索引擎可以各式各樣，其收集的查詢(xún)結(jié)果組成也形式多樣，歸納起來(lái)其結(jié)果主要是由網(wǎng)址（URL）、網(wǎng)頁(yè)標(biāo)題、內(nèi)容摘要、相關(guān)度等信息組成。因此，元搜索引擎排序可以在利用成員搜索引擎排序的基礎(chǔ)上，從網(wǎng)頁(yè)標(biāo)題、內(nèi)容摘要等方面著手考慮?？偟膩?lái)說(shuō)，其排序方法可以從以下三方面來(lái)闡述：

1、引用排列。指直接采用搜索引擎提交的結(jié)果順序，依次將不同來(lái)源的結(jié)果顯示出來(lái)。這種方式無(wú)需進(jìn)行結(jié)果去重而只需完成格式轉(zhuǎn)換，因此顯得簡(jiǎn)單易行，而且它有利于用戶(hù)了解哪些搜索引擎對(duì)自己所需的信息不能提供或提供很少，以后再查詢(xún)時(shí)可將它們從自己的引擎組合中刪除。但這種方式也很有可能致使一個(gè)搜索引擎的不相關(guān)結(jié)果排在另一個(gè)搜索引擎相關(guān)結(jié)果之前，使用戶(hù)錯(cuò)過(guò)重要信息。

2、重新排列。這種排序的方法比較單一，相當(dāng)于把成員搜索引擎搜索的結(jié)果融合到一起再重新選擇一種方法排序。這種方法僅僅提高了查全率，對(duì)于一些重要的信息，可能會(huì)排在比較靠后的位置而不易被用戶(hù)檢索到，準(zhǔn)確率也不高。早期的元搜索引擎通常使用這種算法思想?；诖祟?lèi)算法思想的方法主要有直接合并、根據(jù)響應(yīng)速度排序、摘要排序等。

圖1 Web元搜索引擎搜索流程圖

3、利用搜索引擎排序信息排序。將各個(gè)成員搜索引擎所返回的結(jié)果集中在一起重新排序，這樣就打亂了原來(lái)搜索引擎的排序信息，而這些信息也是非常重要的排序依據(jù)。盡管有些成員搜索引擎的排序方法未知，但是它肯定是按查詢(xún)結(jié)果與查詢(xún)?cè)~的相關(guān)程度大小排序的，只不過(guò)不同的搜索引擎所側(cè)重的因素不同。若是能充分利用各成員搜索引擎的排序信息，在其基礎(chǔ)上進(jìn)一步地合成，則能夠?qū)⒉闇?zhǔn)率進(jìn)一步提高。輪詢(xún)法、星星排序、Borda排序、貝葉斯概率模型排序、位置排序等方法就是基于此基礎(chǔ)上的。

4、相關(guān)分值融合。相關(guān)分值融合也是充分利用各個(gè)成員搜索引擎的排序信息。針對(duì)某個(gè)查詢(xún)，各成員搜索引擎對(duì)自己搜索的所有結(jié)果均根據(jù)不同的情況分配一定的相關(guān)分值，對(duì)于同一結(jié)果在多個(gè)搜索引擎中出現(xiàn)的，將它們的相關(guān)分值進(jìn)行融合后再排序。相關(guān)分值融合的方法有很多種，其中以Comb融合法（六種）、SDM融合法、MEM融合法、CORINET排序等最為常見(jiàn)。

四、Web元搜索引擎排序算法改進(jìn)建議

鑒于目前元搜索引擎開(kāi)發(fā)技術(shù)不同，且內(nèi)部算法也存在重大差異，很難用統(tǒng)一的標(biāo)準(zhǔn)要求和衡量搜索結(jié)果的優(yōu)劣。但對(duì)于元搜索引擎排序算法方面，其改進(jìn)的方法主要體現(xiàn)在以下幾方面：

1、直接將兩種或者兩種以上的基礎(chǔ)算法進(jìn)行綜合，這是比較常見(jiàn)的改進(jìn)方法。摘要/位置排序法就是將摘要排序法和位置排序法綜合在一起的。元搜索引擎Ixquick、Metor等的結(jié)果排序方式都是基于相關(guān)度與星星評(píng)價(jià)指標(biāo)相結(jié)合排序算法。

2、根據(jù)加權(quán)平均（簡(jiǎn)稱(chēng)WM）算法的原理，針對(duì)成員搜索引擎性能的不同分配一定權(quán)重，權(quán)重值與所引用的搜索引擎名稱(chēng)、個(gè)數(shù)有關(guān)，這樣能夠突出成員搜索引擎之間的差異。加權(quán)輪詢(xún)法、加權(quán)規(guī)范分法、加權(quán)Comb排序等均是在基礎(chǔ)算法的基礎(chǔ)上為搜索引擎分配權(quán)值得到的。

3、依據(jù)信息集結(jié)算子的原理，首先確定所有成員搜索引擎搜索結(jié)果的文件序列；然后確定最終顯示的文件名稱(chēng)和總個(gè)數(shù)，系統(tǒng)會(huì)按照確定的文件名稱(chēng)和文件數(shù)統(tǒng)計(jì)各文件在每個(gè)序列位置出現(xiàn)的次數(shù)；接著系統(tǒng)按從大到小順序排列每個(gè)文件在序列中出現(xiàn)的次數(shù)；最后根據(jù)搜索引擎的個(gè)數(shù)和信息集結(jié)程度，運(yùn)用信息集結(jié)算子計(jì)算每個(gè)位置的權(quán)重，權(quán)重和排序后（降序）的文件在序列中出現(xiàn)的次數(shù)相乘，得到最終集結(jié)結(jié)果，系統(tǒng)把每個(gè)文件最終的集結(jié)結(jié)果按從大到小順序排列，該順序即為元搜索引擎關(guān)于每個(gè)文件最終的順序。針對(duì)成員搜索引擎檢索的每個(gè)文件在序列中每個(gè)位置出現(xiàn)次數(shù)如何確定權(quán)重，目前國(guó)內(nèi)外相關(guān)成熟的算法也比較多，如加權(quán)有序平均（OWA）算子、模糊語(yǔ)言量詞、尤其是規(guī)范單調(diào)遞增（RIM）量詞。

4、綜合2和3算法的原理，首先賦予每個(gè)元搜索引擎一定的權(quán)重，然后再對(duì)最終結(jié)果文件序列每個(gè)位置賦予一定的權(quán)重，當(dāng)然這兩個(gè)權(quán)重值和算法各不相同。然后利用集結(jié)算子原理，計(jì)算每個(gè)文件在所有元搜索引擎中的最終集結(jié)值；再把檢索結(jié)果文件按集結(jié)值降序排列，該順序即為元搜索引擎關(guān)于每個(gè)文件最終的順序。針對(duì)這兩種權(quán)重的確定方法，目前國(guó)內(nèi)外相關(guān)成熟的算法還不是很多，比較成功的算法有加權(quán)有序、加權(quán)平均（簡(jiǎn)稱(chēng)WOWA）算子。

此外，雖然目前排序算法眾多，但隨著新的搜索引擎的出現(xiàn)、搜索技術(shù)的改進(jìn)及外界環(huán)境的變化，筆者認(rèn)為還需要定期對(duì)元搜索引擎排序結(jié)果進(jìn)行測(cè)評(píng)，主要指標(biāo)包括查全率和查準(zhǔn)率。對(duì)于查全率，由于元搜索引擎作為一種特殊的搜索引擎，對(duì)于一個(gè)固定的查詢(xún)，它的結(jié)果來(lái)自于成員搜索引擎。因此，整體查全率是由成員搜索引擎所確定的；而對(duì)于查準(zhǔn)率，搜索引擎本身提供的排序算法就是將相關(guān)度較大的結(jié)果盡可能排在前面，即提高查準(zhǔn)率，它是衡量元搜索引擎性能的一個(gè)重要尺度。因此，要想使用戶(hù)在最短的時(shí)間內(nèi)檢索到最需要的文件信息，必須不斷優(yōu)化元搜索引擎技術(shù)和元搜索引擎排序算法。

五、元搜索引擎排序算法展望

目前，搜索引擎技術(shù)逐漸趨于成熟階段，尤其是在查全率和查準(zhǔn)率方面都有了較大的改進(jìn)，時(shí)效性也有較大的改善。而元搜索引擎在國(guó)內(nèi)尚處于起步階段，但其還是具有自己獨(dú)特的生存優(yōu)勢(shì)的，因?yàn)樗狭硕鄠€(gè)搜索引擎，具有較高的查全率，這些都是其他搜索引擎不能具備的。但由于不同的搜索引擎在收集信息的數(shù)量、范圍、排序方法等方面有較大的差異，再加上搜索引擎技術(shù)的隱蔽性，設(shè)計(jì)者很難獲取它們的技術(shù)細(xì)節(jié)。對(duì)于元搜索引擎來(lái)說(shuō)，無(wú)論采取哪種排序方式，總不盡如人意。實(shí)際上，對(duì)某元搜索引擎來(lái)說(shuō)（排序方法已定），不同的查詢(xún)，它的查準(zhǔn)率和查全率也有不同；對(duì)于同一個(gè)查詢(xún)，不同的排序方式也會(huì)引起很大的差別，導(dǎo)致這種問(wèn)題的主要是信息重疊率的不同。Wu Sheng-li和McClean經(jīng)過(guò)研究表明，當(dāng)信息重疊率不同時(shí)，各種排序算法差異顯著。所以，要想從排序算法上提高元搜索引擎的查準(zhǔn)率和查全率，除了對(duì)基礎(chǔ)算法進(jìn)行改進(jìn)外，還要根據(jù)不同的查詢(xún)選擇不同的算法。專(zhuān)業(yè)搜索引擎的出現(xiàn)對(duì)元搜索引擎來(lái)說(shuō)可以是一個(gè)借鑒，即將專(zhuān)業(yè)搜索引擎綜合實(shí)現(xiàn)專(zhuān)業(yè)元搜索引擎；或者將元搜索引擎更進(jìn)一步的智能化。針對(duì)用戶(hù)輸入的查詢(xún)串自動(dòng)地進(jìn)行分類(lèi)，然后根據(jù)類(lèi)別選擇最佳的排序方法。當(dāng)然，對(duì)于某個(gè)固定的元搜索引擎，還可以通過(guò)科學(xué)的統(tǒng)計(jì)方法來(lái)檢測(cè)成員搜索引擎的技術(shù)細(xì)節(jié)，盡管檢測(cè)出來(lái)的技術(shù)細(xì)節(jié)不是很精確，但卻能夠在一定程度上反映出該成員搜索引擎的技術(shù)情況。綜合這些技術(shù)給出一個(gè)統(tǒng)一排序方法對(duì)所有結(jié)果進(jìn)行重新排序，這樣勢(shì)必能夠提高用戶(hù)的滿意度。

[1]彭喜化，張林.基于agent的元搜索引擎結(jié)果優(yōu)化技術(shù) [J].計(jì)算機(jī)應(yīng)用，2003.12.

[2]文坤梅，盧正鼎，鄧曦等.元搜索引擎中檢索結(jié)果排序的優(yōu)化方法[J].華中科技大學(xué)學(xué)報(bào)，2003.3.

[3]徐寶文，張衛(wèi)豐.搜索引擎與信息獲取[M].北京：清華大學(xué)出版社，2002.

[4]張強(qiáng)弓，喻國(guó)寶，廖湖聲等.一種元搜索引擎的查詢(xún)結(jié)果處理模型[J].華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2004.32.Z1.