一種自反饋式元搜索系統的設計

程傳鵬,王天志

(1.中原工學院,鄭州 450007;2.云南師范大學,昆明 650092)

一種自反饋式元搜索系統的設計

程傳鵬1,王天志2

(1.中原工學院,鄭州 450007;2.云南師范大學,昆明 650092)

分析了常見元搜索系統中普遍存在的問題,對獨立搜索引擎的選擇以及搜索結果的集成提出了改進的方法,并在此基礎上設計出一種自反饋式元搜索系統.實驗結果表明,該元搜索系統提高了用戶的搜索效率.

元搜索;自反饋;獎勵系數;查詢相關度

隨著Internet的迅猛發展,搜索引擎已是人們獲取知識最重要的來源之一.但由于信息量的龐大以及采用的技術不同,大部分的獨立搜索引擎都只涉及到整個WWW資源的30%～50%[1].元搜索引擎的出現,整合了獨立搜索引擎的資源,一定程度上解決了搜索引擎查全率低的問題.元搜索引擎依賴于獨立搜索引擎進行查找,但由于各個獨立搜索引擎的差異性,元搜索引擎在對各個獨立搜索引擎返回的搜索結果的整合上還存在一定的問題.本文對元搜索引擎中的獨立搜索引擎調度以及輸出結果排序兩項關鍵技術進行了研究,在此基礎上提出了一種自反饋式元搜索系統.實驗結果表明,該元搜索系統提高了用戶的搜索效率.

1 關鍵技術

元搜索引擎的主要作用是對獨立搜索引擎的檢索結果作進一步處理.它沒有自己的文檔索引數據庫,其信息來源于獨立搜索引擎的結果輸出[2].從元搜索引擎的工作過程來看,元搜索引擎的關鍵工作主要集中在對獨立搜索引擎的選取以及獨立搜索引擎返回的搜索結果的排序.下面對這兩項技術進行分析.

1.1 獨立搜索引擎返回結果的選擇

對于每個查詢字符串,元搜索引擎通過代理接口向獨立搜索引擎提交查詢請求,一般獨立搜索引擎都將返回成千上萬甚至幾十萬個搜索結果,這其中含有我們需要的結果,然而更多的是干擾信息[3].目前的元搜索引擎一般都事先設置好參數,從各個獨立搜索引擎的搜索結果中提取同等數量的搜索結果.這種方法其實是不妥當的.對于同一個查詢請求,有的獨立搜索引擎查詢精度高,有的獨立搜索引擎查詢精度低,我們應該從搜索精度高的獨立搜索引擎里多取出一些搜索結果.由此本文提出一種可以根據反饋信息自動調整獨立搜索引擎權重的算法.為了便于討論,給出如下幾個定義:

定義1 從獨立搜索引擎的搜索結果中所取回的搜索比例,定義為獨立搜索引擎的權重,用符號Wi表示.

定義2 每個獨立搜索引擎的搜索結果的數量,定義為獨立搜索引擎的基,用符號|Rei|表示.

定義3 元搜索引擎最終向用戶提交的結果集,定義為最終結果集,用符號|R|表示.

定義4 獨立搜索引擎在最終搜索結果集中所占的比例,定義為獨立搜索引擎比重,用符號 Pi表示.

在以上分析的基礎上,形成如下的算法:

(1)對每個獨立搜索引擎 Rei賦以初始權重W0,即Wi=W0=1/n,n為所調用的獨立搜索引擎個數.

(2)計算最初從 Rei中提取的結果的數量Ni:

式中:Rei表示第i個獨立搜索引擎;|Rei|表示集合 Rei的基.

對于一個查詢請求,獨立搜索引擎都會返回很多搜索結果,但用戶一般只會選擇前面的幾頁來瀏覽,實際瀏覽量很少.所以在(1)式的基礎上加一個常數c1,形成公式(2):

式中:c1視對返回結果數量的要求而定,可以取0.01、0.001等,目的是來縮小搜索范圍.

(3)將每個 Rei中前Ni個結果取出,合并形成原始結果集,對結果集用本文所提出的位置/摘要排序法進行排序,取前 n個結果形成最終結果集.其中:

式中:M為獨立搜索引擎個數;c2為常數,用來縮小搜索規模.

(4)計算每個獨立搜索引擎在最終結果集中所占的比例:

pi=ni/n (5)

式中:ni表示第i個獨立搜索引擎中最終入選搜索結果集的搜索結果數量.

對 pi規范化,形成如下公式:

(5)根據獨立搜索引擎比重重新調整每個獨立搜索引擎 Rei的權重:

ωi=c3ω0+c4Pi(6)

式中:c3和 c4為常數,且c3+c4=1.c3和 c4的大小決定了 Pi對ωi的影響力.

對ωi規范化,形成如下公式:

(6)從獨立搜索引擎所返回的搜索結果中提取的數量為:

1.2 位置/摘要排序法的改進

元搜索系統中搜索結果的排序,一般采取的是位置/摘要排序法.它的主要思想是根據用戶查詢串與搜索結果記錄中摘要信息的相關性以及查詢串在摘要中的位置來對搜索結果進行排序.先計算查詢串與每條搜索結果記錄的相關程度,最后將這些搜索結果記錄按照相關度從大到小的順序返回給用戶[4].摘要排序法的計算步驟如下:

(1)對查詢串 Q進行詞條切分,形成詞條 l1,l2,l3,…li,…,lm,其中,m為詞條個數.

(2)計算查詢串Q中每個詞條lj與文摘Abstracti的相關度 Rl(lj,ABstracti):

式中:Length(Abstracti)為 Abstracti的長度;Occurence(lj,Abstracti)為 lj在Abstractj中出現的次數;L ocation(lj,k,Abstracti)為詞條 lj在 Abstracti中第k次出現的位置.

(3)計算 Abstracti與Q的相關度 Rq(Q,Abstracti) :

式中:m為查詢串Q中的詞條數.

下面我們通過一個例子,來說明此方法的不足之處.假設查詢串“搜索引擎的設計與實現”,通過分詞,該查詢串被切分為“搜索引擎”、“設計”、“實現”3個詞條.“搜索引擎”字串在 Abstract1中出現了3次,而在Abstract2中3個詞條各出現了1次,如果按照式(10)來計算,那么 Rq(Q,Abstract1)=Rq(Q,Abstract2),也就是說,Q相對于Abstract1的查詢相關度與 Q相對于Abstract2的查詢相關度一樣.但直觀上來看,Abstract2更符合查詢的要求,理應得到更多關注,基于此,我們考慮給詞條匹配全面的文檔獎勵.

定義5 定義元搜索引擎最后提交給用戶的搜索結果集為最終結果集.

定義6 假設查詢串Q經過詞條切分后,有 M個詞條在文摘Abstracti中出現,則定義 Abstracti獎勵系數為M T(Q,Abstracti).

定義7 定義詞條 lj與文摘Abstracti的詞條匹配系數為mt(lj,abstracti):

在以上分析的基礎上,本文提出的搜索結果的排序算法如下:

(1)計算文摘 Abstracti的獎勵系數M T(Q,Abstracti):

式中:X為查詢串Q中詞條的個數.

(2)計算查詢串 Q與文摘Abstracti的相關度R(Q,Abstracti):

(3)計算最終結果集中第 i個搜索結果的位置信息得分Pos(ri):

(4)綜合位置信息和相關度信息,得到最終排序分數Rank(ri):

式中:c5、c6是常數,它們的大小決定了位置信息和相關度信息對最終排序的影響力;K為最終選擇的搜索結果個數.

(5)將最終結果集中的 r1按照 Rank(ri)的值從大到小排列.

2 自反饋式元搜索系統的結構

元搜索引擎又稱作搜索引擎之上的搜索引擎,它沒有自己的網頁數據庫和索引庫.用戶通過元搜索引擎接口向獨立搜索引擎提交查詢請求,獨立搜索引擎返回的結果再通過元搜索引擎進一步整合后,提交給用戶.在以上分析的基礎上,設計出一個元搜索引擎模型,其中包含有用戶接口、元搜索接口、搜索結果提取和搜索結果排序4個模塊.整個系統的結構如圖1所示.

圖1 自反饋式元搜索系統結構圖

自反饋式元搜索系統的流程如下:

(1)用戶通過元搜索接口提出搜索請求;

(2)元搜索接口將查詢短語整理后,發送到獨立搜索引擎,并獲取搜索引擎的搜索結果,形成原始網頁集;

(3)由元搜索接口返回的搜索結果集,通過本文所提出的選擇方法進行二次選擇;

(4)經過二次選擇的搜索結果集,按照本文所提出的相關度排序方法進行排序;

(5)經過查詢相關度排序后,最終提交給用戶一定數量的搜索結果.

3 實驗結果及分析

在搜索引擎返回的結果中,符合用戶查詢意圖的結果數量所占的百分比,稱作搜索引擎的查準率.查準率是衡量搜索引擎搜索質量的一個重要指標,但目前還沒有很好的方法對這一指標作出量化.本文中查準率可通過多個人工專家分別打分,取得分的平均值來確定.這里假設人工專家的查準率為100%,以百度和搜狗2個搜索引擎作比較,以不同的關鍵詞進行搜索,百度和搜狗的返回結果只取前面10頁.經過實驗,得到如表1所示的結果.

表1 實驗結果

從表1中的實驗數據可以看出,本文中的方法雖然在時間上劣于其他搜索引擎的搜索時間,但大大提高了查準率.

4 結 語

搜索引擎的選擇和查詢結果的排序是元搜索引擎需要重點解決的關鍵技術.本文在分析了常見元搜索系統結果集成的基礎上,根據每次查詢的反饋信息自動調整獨立搜索引擎的權重,做到了依據查詢串動態地調整從每個獨立搜索引擎中返回的結果,并且對傳統的位置/摘要排序方法進行了分析,指出了其不足之處,提出了相應的改進措施.

[1] 李永平,文坤梅.集成搜索引擎中結果排序的優化分析[J].華中科技大學學報(自然科學版)2001,31(11):28-30.

[2] 王敏,楊炳儒.基于主題的個性化元搜索引擎的設計與實現[J].情報檢索2005,31(11):57-58.

[3] 肖建華,蔣明,何瑗,等.二次搜索系統的設計與實現[J].計算機應用研究2003,20(9):28-30.

[4] 張衛豐,徐寶文,周曉宇,等.元搜索引擎結果生成技術研究[J].小型微型計算機系統,2003,24(1):123-126.

Design of Self-response Meta Search System

CHENG Chuan-peng1,WANG Tian-zhi2
(1.Zhongyuan University of Technology,Zhengzhou 450007;2.Yunnan Normal University,Kunming 650092,China)

This paper analyzes the common question in meta-search system,and proposes improvement method for selection of independent search and integration of search result.On this basis,a response metasearch system is designed.Experiments show that the meta search system has improved efficiency of search

meta-search engines;self-response;incentive factor;query relevance

TP391

A

10.3969/j.issn.1671-6906.2011.04.015

1671-6906(2011)04-0068-04

2011-06-13

程傳鵬(1977-),男,河南鄭州人,講師,碩士.