一種元搜索引擎的查詢結果處理模型(

1、一種元搜索引擎的一種元搜索引擎的查詢結查詢結果果處處理模型理模型(張強弓1，喻國寶2，廖湖聲3，隋樹林4(1,2,3 北京工業(yè)大學 計算機學院，北京 100022)(4 青島科技大學 四方學院，山東青島 266042)摘要：為改進元搜索引擎查詢速度慢、獨立性差的缺點，本文設計了一個元搜索引擎的結果處理模型。該模型結合元搜索引擎的特點設計了一種 4 級結果集的結構，提高了元搜索引擎結果處理的效率。在結果提取部分提出了根據(jù)反饋信息自動調整權重的算法（FBWM），在沒有人工干預的情況下自動監(jiān)視各獨立搜索引擎的性能變化并隨之動態(tài)調整其權重。在結果排序部分，提出了改進的位置/全文排序法（IPFTS），在

2、算法中引入了詞條匹配等級的概念，不但能提高搜索結果和查詢串相關度的精度，還能保證排名在前的搜索結果的 URL 的有效性。關鍵詞：元搜索引擎；結果處理；FBWM 算法；IPFTS 算法；詞條匹配等級 本文得到北京市優(yōu)秀人才培養(yǎng)專項經(jīng)費資助。1 張弓強（1982-），男，漢族，山東人，碩士研究生，主要從事網(wǎng)絡信息檢索和 Web 信息集成等方面的研究。E-mail: .1. 引言搜索引擎按其工作原理可分為目錄式搜索引擎、機器人搜索引擎和元搜索引擎三大類。其中元搜索引擎具有無需人工干預、無需維護龐大的數(shù)據(jù)庫以及搜索的查全率高等優(yōu)點，但也具有查詢處理速度慢，搜索性能過于依賴所調用的獨立搜索引擎等缺點。為

3、了克服這些缺點，本文對元搜索引擎的結果處理部分提出了一種新的處理模型及相關算法。論文第2節(jié)簡要介紹元搜索引擎的體系結構；第3節(jié)介紹本模型的結構和一些算法的思想和實現(xiàn)步驟；第4節(jié)是全文總結。2. 元搜索引擎的體系結構一個元搜索引擎就是一個“高層”的搜索引擎它是調用其他搜索引擎的搜索引擎。元搜索引擎接收用戶的查詢串并把它提交給多個下層搜索引擎，再把下層搜索引擎返回的結果合并成一個統(tǒng)一的結果返回給用戶。一個元搜索引擎一般包括用戶接口、分發(fā)器、結果提取和結果排序 4 個模塊，如圖 1 所示。圖 1 元搜索引擎德體系結構用戶接口接收用戶的輸入并向用戶輸出搜索的結果。分發(fā)器以用戶接口傳送的查詢串為依據(jù)，根

4、據(jù)所調用的獨立搜索引擎的特點產生不同的查詢語句，以適應各個不同的獨立搜索引擎的特定要求。例如在 Google 中把“OK_HERE”作為一個詞來看待，而在其他一些搜索引擎中會被看成是“OK”和“HERE”兩個詞。結果提取模塊負責從多個獨立搜索引擎返回的結果中提取部分或全部結果，再把這些結果交給結果排序模塊。它要解決的是怎樣從獨立搜索引擎中提取結果和提取多少等問題。目前的處理方法主要有“系統(tǒng)預定法”、 “權重分配法1”和“信息獲取的訓練集策略”等2。結果排序模塊負責把結果提取模塊提交的結果按照一定的策略排序，再交給用戶接口。元搜索引擎的結果排序模塊工作用戶接口分發(fā)器結果排序模塊結果提取模塊SE1

5、SE2.SEnwww的原則是在保證效率的基礎上盡可能利用一切可用信息提高結果排序的質量。目前的處理方法有“將響應最快的搜索引擎的搜索結果先返回”、 “星星體系”、 “位置排序法”、 “摘要排序法”、 “位置/摘要排序法”等2。3. 一種元搜索引擎的結果處理模型結果處理模型涉及圖 1 中的結果提取模塊和結果排序模塊。它的工作過程是對各個獨立搜索引擎搜索到的結果進行提取，并將這些結果進行排序后再提交給用戶接口。3.1 模型的 4 級結果集結構各個獨立搜索引擎把各自的搜索結果提交給結果提取模塊，結果提取模塊以此為 1 級結果集；利用 FBWM（Feedback Based Weight Modify

6、ing）方法，根據(jù)各個獨立搜索引擎的權重從 1 級結果集中提取一部分結果形成 2 級結果集；對 2 級結果集的結果用位置排序法排序，取其排位在前的一部分，得到 3 級結果集；根據(jù)各個獨立搜索引擎對 3 級結果集的貢獻比率（定義 1）重新調整各個獨立搜索引擎的權重；提取 3 級結果集中排在前邊的一些結果形成 4 級結果集，再對 4 級結果集中的結果應用改進的位置/全文排序法（IPFTS）排序。完畢后，將 4級結果集的結果和剩余的 3 級結果集的結果提交給用戶接口。圖 2 4 級結果集示意圖這樣的結果集結構設計是出于這樣一種思想：每個獨立搜索引擎都會返回上百萬結果，但是據(jù)調查，最終用戶可能瀏覽到的

7、網(wǎng)頁少于 100 個。所以一般情況下，返回 1,000,000 個結果和返回 100 個結果，對用戶來說幾乎是一樣的。為了提高性能，我們在龐大的較低級結果集中用低級快速的算法挑選出一部分網(wǎng)頁構成較高級的結果集，在新結果集中應用更高級的，精度更高但時間復雜度也更高的算法。從新結果集中再提取新的子集，應用更加復雜的排序算法，最終目的是達到搜索精度和效率的平衡。3.2 搜索結果的提取這里的提取是指從各個獨立搜索引擎各自的搜索結果集中提取部分搜索結果，作為元搜索引擎進一步處理的結果集。搜索結果的提取方法有系統(tǒng)預定法、權重分配法和訓練集方法等。系統(tǒng)預定法過于死板，它限制從各個獨立搜索引擎的結果集中提取結

8、果的數(shù)量，也限制了最終結果集的上限。權重分配法可以更改所取結果的總數(shù)量，并利用權重使從各個搜索引擎的結果集取得結果各占一定比例。然而獨立搜索引擎發(fā)展的速度很快，其性能隨時變化，如果等這些搜索引擎公布這些變化或明顯地感到其性能發(fā)生變化時再調整它們的權重，就不能及時、合理、有效地利用獨立搜索引擎的最新成果。訓練集方法則要維護一個龐大的訓練集，削弱了元搜索引擎無須維護大量數(shù)據(jù)這一優(yōu)點。3.2.1 FBWM 算法的思想由此本文提出一種可以根據(jù)反饋信息自動調整權重的算法，簡稱 FBWM 方法，它實際上也是基于學習的方法，但是與訓練集方法相比它有自己的特點。FBWM 算法不固定每次查詢所返回結果的數(shù)量的總

9、數(shù)（2 級結果集的基數(shù)）。因為對于不同的查詢串，搜索引擎返回的結果的數(shù)量相差懸殊。我們對每個獨立搜索引擎規(guī)定一個比率，從每個獨立搜索引擎的結果集中，按照這個比率提取排名在前的一部分結果（這個比率與各個獨立搜索引擎的權重相關）。從各個獨立搜索引擎的結果集提取出來的結果合到一起，就形成了 2 級結果集。然后對 2 級結果集中的結果用位置排序法進行排序，形成 3 級結果集。根據(jù)各個獨立搜索引擎的搜索結果對 3 級結果集的貢獻比率（并不僅僅是在 3 級結果集中占有率）來調整它們的權重。對 3 級結果集的貢獻比率越大，說明這個獨立搜索引擎返回結果的質量越高，所以應該從它的結果集中多取一些結果。3.2.2

10、 符號的約定1 級結果集（全部結果）2 級結果集（實施排序的初始結果集）3 級結果集（最終顯示的結果集）4 級結果集（實施高精度排序算法的結果集） Si表示元搜索引擎調用的第 i 個獨立搜索引擎，假設共調用 M 個獨立搜索引擎； Ri表示第 i 個獨立搜索引擎返回結果的結果集； Wi為 Si的權重； Ni表示從 Ri中根據(jù) Wi提取結果的數(shù)量； ni表示在 3 級結果集中，屬于 Ri中結果的數(shù)量。3.2.3 FBWM 算法的描述FBWM 算法的步驟如下： 首先對每個獨立搜索引擎 Si賦以權重 W0，即 Wi = W0。 計算從 Ri中提取的結果的數(shù)量 Ni： （1）MiiiiiwwRcN11其

11、中，|Ri|表示集合 Ri的基數(shù)。c1是常數(shù)，可以取 0.1,0.01 等等，視對返回結果的數(shù)量的要求而定。我們規(guī)定搜索引擎的權重以百分數(shù)表示，即令。所以（1）可表示為：1M1iiw （2）iiiwRcN1 將每個 Ri中前 Ni個結果取出，并合并形成 2 級結果集，對 2 級結果集用位置排序法進行排序，取出前 n 個結果形成 3 級結果集。其中： （3）MiiNcn12c2為常數(shù)，它的作用和 c1一樣，用來控制 3 級結果集中結果的數(shù)量。n 不宜太多或太少，可以定義 n的上下限。如果通過 c2的調節(jié)不能使 n 落在這個范圍內，那就應該強迫 n 屬于這個范圍。 每個獨立搜索引擎，我們可以根據(jù)占

12、有率來調整的權重，但是在算法分析部分Miiinn1iS我們會看到這樣做有不妥之處。于是本文提出了貢貢獻比率這個概念：定義 1： Si對 3 級結果集的貢獻比率 pi表示為 Si對 3 級結果集貢獻的結果數(shù) ni除以 Si 在 2 級結果集中的個數(shù)。公式表示為：pi = ni / Ni （4）再定義規(guī)范化的貢獻比率調節(jié)系數(shù)iP （5）MiiiippP1 重新調整每個 Si的權重 Wi： （6）iiiPcwcw43其中 c3和 c4為常數(shù)， 且 c3+c4 =1 。c3和 c4的大小決定了 Pi對 Wi的影響力。對每個 Wi重新計算完畢后，將每個 Wi重新化成百分比形式（化為百分比形式還可以保證每

13、次 Pi對 Wi的影響力是一樣的）： （7）niiiiwww1 對每次查詢，都重復步驟到步驟。3.2.4 FBWM 算法的分析 對搜索結果總數(shù)量的適應性為了簡單，我們假設只有兩個獨立搜索引擎S1，S2。對于查詢串 q1, S1返回 100000 個結果，S2返回 150000 個結果，總結果數(shù)為 250000；對于查詢串 q2，S1返回 1000 個結果，S2返回 1500 個結果，總結果數(shù)為 2500。顯然最終我們需要的 2 級結果集的結果數(shù)應該與上述總結果數(shù)近似成正比，F(xiàn)BWM方法通過以百分比的形式提取結果確保了這一點，而系統(tǒng)預定法和普通的權重分配法就不具有這種靈活性。所以說 FBWM 方

14、法避免了人為的設定取回數(shù)量帶來的不合理之處，很好的適應了 Si對不同的查詢串返回結果的不可預測性以及返回結果的數(shù)量差別太大。 對獨立搜索引擎性能變化的適應每次查詢都會對各個獨立搜索引擎的權重作調整，當此元搜索引擎的使用頻率較高時，完全可以及時地適應獨立搜索引擎性能的變化。實際的元搜索引擎大都是設計了一個統(tǒng)計模型，來監(jiān)視各個獨立搜索引擎的性能變化，而不是僅僅參照相對滯后的獨立搜索引擎公布的技術信息。 對獨立搜索引擎的搜索精度的差別的適應為什么用貢獻比率而不用占有率？舉例來說，假設對某個查詢串 q，S1返回了 200 個搜索結果，S2返回了 800 個搜索結果，S1和 S2初始的權重分別為 W1=

15、0.5 和 W2=0.5。則提取到 2 級結果集的數(shù)量分別為 N1=200*0.5=100，N2=800*0.5=400。假設最終 S1的 100 個搜索結果有 50 個入選了 3 級結果集，而 S2的 400 個搜索結果也只有 50 個入選。顯然，S1的搜索質量比 S2高，應該從 S1的結果集中多取，但是 S1和 S2的結果在 3 級結果集中的占有率都是 50/（50+50）=0.5。根據(jù)公式（6），沒有起到調整權重的作用。而 S1的貢獻比率 p1=50/100=0.5，S2的貢獻比率 p2=50/400=0.125；S1的貢獻比率調節(jié)系數(shù) P1=0.5/(0.5+0.125)=0.8，S2

16、的P2=0.125/（0.5+0.125）=0.2。可以看到 S1的權重必定會有所提高，S2的必定會下降。這才能適應不同的獨立搜索引擎在搜索精度上的差別。 與訓練集方法的不同之處雖然都是根據(jù)各個獨立搜索引擎的結果集在高質量的結果集中占有情況來調整權重，但是FBWM 算法根據(jù)的是貢獻比率，訓練集方法根據(jù)的是占有率；訓練集方法中的權重決定的是各個獨立搜索引擎的搜索結果在總結果集中占有的比例，而 FBWM 方法中的權重決定的是從各個獨立搜索引擎的結果中選取結果的比例；因為沒有維護查詢結果集，所以 FBWM 方法的效率和資源占用方面比訓練集策略有明顯優(yōu)勢，但是也失去了對獨立搜索引擎針對不同查詢串的搜索

17、性能差異的處理能力。3.3 搜索結果的排序這一部分要把搜索結果按規(guī)則評分，把得分最高的結果放在最前。在本文講述的模型里，搜索結果的排序過程先是把第 2 結果集里的結果用位置排序法排序，選出其中前 N 個結果形成第 3 結果集，選出前 K 個結果形成第 4 結果集（一般的，KN）。對第 4 結果集的結果應用改進的位置/全文排序法（IPFTS 算法）進行排序。最后，把排好序的第 4 結果集和第 3 結果集的結果提交給用戶接口。這一部分提出了一個“改進的位置/全文排序法”，簡稱 IPFTS（Improved Place & Full-Text Sorting）方法。在這個方法中，提出了一個概

18、念：詞條匹配等級。應用詞條匹配等級可以使排序結果更加準確。這里需要注意的是，全文排序法，詞條匹配等級這些概念在擁有數(shù)據(jù)庫的機器人搜索引擎中是很自然的被應用的，但是對元搜索引擎來說，它的操作對象是文本而不是數(shù)據(jù)庫，所以在應用這些概念時就要費一些周折了。3.3.1 IPFTS 算法的思想IPFTS 算法在排序時綜合考慮了位置信息和全文信息與查詢串的相關度兩個因素。由于位置信息已經(jīng)在 3 級結果集的形成過程中應用了，所以IPFTS 算法要處理的第 4 結果集里的結果的順序已經(jīng)是按照位置信息排序后的順序，所以這里 IPFTS算法的重點是全文排序，只不過最后在全文排序的結果中加入位置信息的影響。IPFT

19、S 算法是在對摘要排序法的改進的基礎上提出的。摘要排序法的優(yōu)點是實現(xiàn)簡單，速度快。缺點是返回的摘要過于簡單，而且各個獨立搜索引擎的用戶接口不同，導致同一個結果在不同的獨立搜索引擎返回的摘要不同。摘要排序法往往導致返回摘要信息多的搜索引擎的搜索結果排名靠前，而不是與詞條相關度高的搜索結果排名靠前。因此IPFTS 算法決定提取搜索結果的全部文本內容（文檔）作為判別相關性的依據(jù)。這樣做的最大問題是效率。但在后文的算法分析部分，我們將會看到此模型的 4 級結果集結構緩解了這一問題。在計算查詢串與文檔的相關度時，我們引入了詞條匹配等級這個概念。它的提出出于這樣一種思想：假設一個查詢串 q 有 m 個詞條

20、 l1，l2，lm，如果在文檔 D1中，l1出現(xiàn)了 m 次, l2到 lm一次也沒出現(xiàn)，而在與文檔 D1長度相同的文檔 D2中，l1,lm各出現(xiàn)一次。則按照先前的算法，D1與 q的相關度和 D2與 q 的相關度都是 m 。但是，顯然，D2是比 D1更好的結果。 （例如：查詢串 q=“信息 獲取 技術”，則詞條“信息”出現(xiàn)很多次而“獲取”和“技術”沒有出現(xiàn)的文檔，與“信息”， “獲取”， “技術”都出現(xiàn)的文檔相比，自然是后者具有更高的相關度）于是，我們考慮給詞條匹配全面的文檔獎勵：更高的詞條匹配等級。定義 2： 設查詢串 q 有 X 個詞條，文檔 D 中包含有這 X 個詞條的 N 個（N=X）,

21、則文檔 D 與查詢串q 的詞條匹配等級為 N。3.3.2 符號的約定ri表示第 4 結果集中第 i 個結果;Di表示 ri對應的全部文本信息，即文檔;q 表示用戶輸入的查詢串;lj表示 q 中第 j 個詞條。X 為查詢串 q 中的詞條數(shù)。3.3.3 IPFTS 算法的描述對每個 ri： 仿照摘要排序法，計算 Di與 q 的普通相關度（是指沒有詞條匹配等級影響的相關度）。先計算q中每個詞條lj與文檔Di的相關度Rl(lj, Di)：),(ijDlRl（8）),(1) ),()(ln(ijDlOccurencekijiDklLocationDLength其中 Length(Di)為 Di的長度；O

22、ccurrence(lj, Di)為 lj在 Di中出現(xiàn)的次數(shù)；Location(lj, k, Di)為詞條 lj在 Di中第 k 次出現(xiàn)的位置。再計算 Di與 q 的相關度 Rq(q, Di)： （9）XjijiDlRlDqRq),(),(其中，X 為查詢串 q 中的詞條數(shù)。 計算文檔 Di與查詢串 q 的詞條匹配等級。定義詞條 lj與文檔 Di的詞條匹配等級系數(shù)mg(lj, Di)： （10）計算查詢串 q 與文檔 Di的詞條匹配等級MG(q, Di)：= （11）),(iDqMGXjijDlmg1),(其中 X 為 q 中詞條的個數(shù)。 計算查詢串 q 與文檔 Di的相關度 R(q, Di

23、)： （12）),(),(),(iiiDqRqDqMGDqR 計算位置信息的得分 P(ri)：P(ri) = 1/i （13）公式(13)表示第 4 結果集中第 i 個結果的位置信息得分是它所在的位置的倒數(shù)。 綜合位置信息和相關度信息先將相關度和位置信息得分分別標準化，再乘以各自的權重，相加，得到最終排序分數(shù) Rank(ri)： )(irRank（14）KiiiKiiirPrPcDqRDqRc1615)()(),(),(其中 c5，c6是常數(shù)，它們的大小決定了位置信息和相關度信息對最終排序的影響力。K 為第 4 結果集中結果的個數(shù)（第 4 結果集的基數(shù)）。最后，將第 4 結果集中的 ri按照

24、Rank(ri)的值從大到小排列。3.3.4 IPFTS 算法的分析IPFTS 算法就是一種加入了詞條匹配等級的全文相關度計算方法與位置排序法的融合。除了位置排序法本身的特點外，還有以下特點： 對獨立搜索引擎用戶接口的差異的適應IPFTS 算法是根據(jù)搜索結果的網(wǎng)頁全文來計算相關度，不管各個獨立搜索引擎的用戶接口以什么形式返回結果，都不影響 IPFTS 算法的最后結果。 對返回結果的有效性的保證對第 4 結果集的結果來說，因為要獲取它的全文，所以要鏈接它的 URL，并將它的全文下載到本地。這無形當中檢測了 URL 的有效性。這是目前很多搜索引擎沒有做的。例如，經(jīng)常會在 Google 和Baidu

25、 等搜索引擎的搜索結果中發(fā)現(xiàn)無效鏈接（死鏈接）。這多半是出于時間效率上的考慮。在稍后的分析中會看到，由于本模型的第 4 結果集較小，所以時間上的代價可以接受。 時間代價問題本模型假設第 4 結果集的結果數(shù)為幾百。普通的元搜索引擎提取摘要時，處理的結果往往是幾千、幾萬甚至更多，所以要下載的網(wǎng)頁數(shù)也達到幾百到幾千。以 Google 為例，它每頁顯示 10 個搜索結果，也就是說每獲取 10 個搜索結果的摘要信息，就要下載一個網(wǎng)頁。而 IPFTS 算法略掉了從較為龐大的結果集中提取摘要的步驟，所以在獲取網(wǎng)頁方面，本模型的 IPFTS 算法并沒有花費更多的時間。當然，這是以參加精確排序的結果數(shù)減少為代價

26、的。3.4 模型的特色 4 級結果集結構使最有用的搜索結果接受最多最精確的處理，使那些不太有用的結果浪費很少時間。在一定程度上解決了元搜索引擎響應速度慢的缺點。另外它使一些時間代價大的算法得以實施。 根據(jù)反饋信息自動調整權重的算法能根據(jù)每次查詢的反饋信息自動調整獨立搜索引擎的權重。做到了在沒有人工干預的情況下，自動的監(jiān)視獨立搜索引擎的性能變化，并根據(jù)變化作相應的調整。而且，F(xiàn)BWM 算法對不同的查詢串返回結果的數(shù)量的巨大差別，對各個搜索引擎精度的差別作了相應的處理。 詞條匹配等級詞條匹配等級的引入，使得含有查詢串中多數(shù)詞條的文檔從只含有較少詞條但詞條出現(xiàn)次數(shù)較多的文檔中脫穎而出。 改進的位置/

27、全文排序法較位置/摘要排序法，能更精確的判別結果與查詢串的相關度；對獨立搜索引擎用戶接口的差異有很好的適應性，還能保證第 4 結果集中結果的有效性。4. 結束語用戶接口、分發(fā)器、結果提取模塊和結果排序模塊構成了元搜索引擎。本文對元搜索引擎中的結果提取模塊和結果排序模塊提出了一種新的查詢結果處理模型，該模型利用 4 級結果集的結構、根據(jù)反饋信息自動調整權重的算法、詞條匹配等級的概念和改進的位置/全文排序法等技術，有利于克服元搜索引擎查詢速度慢，獨立性差的缺點。將來如果能結合用戶接口模塊和分發(fā)器模塊的新技術共同應用，將會使元搜索引擎更具威力。參考文獻：1 Eric J. Glover，Using

28、Extra-Topical User Preferences To Improve Web-Based Metasearch., PhD thesis. University of Michigan 2001.2 Yuwono B, Lee D. Server ranking for distributed text database systems on Internet. Proceedings of 5th International Conference on Database Systems for Advanced Applications.，Melbourne ,Australi

29、a: World Scientific Pub Co Inc，April, 1997. pp. 391-400.3 徐寶文，張衛(wèi)峰.搜索引擎與信息獲取技術.北京：清華大學出版社，2003. pp.146-147，153.4 Sergey Brin, Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine，Computer Networks and ISDN Systems, 1998, Volume 30, issues 1-7.A Novel Processing Model for the Que

30、ry Results of Meta-search EnginesZHANG Qiang-Gong1, YU Guo-Bao2, LIAO Hu-Sheng3, SUI Shu-Lin4(1,2,3 College of Computer Science and Technology, Beijing University of Technology, Beijing 100022，China)( 4 Sifang College, Qingdao University of Science and Technology, Qingdao, Shandong 266042, China)Abstract： ：This paper presents a novel processing mo