基于社區的問答元搜索引擎設計與實現

摘要:基于社區的問答是近幾年出現并流行的一種有效的信息搜尋網絡應用。文章介紹了針對這種社區的元搜索引擎的工作原理，信息提取、分詞、相關度排序等關鍵技術的實現方法，實驗結果表明元搜索引擎提高了查準率。

關鍵詞:搜索引擎;元搜索引擎;基于社區的問答

中圖分類號:TP393文獻標識碼:A 文章編號:1009-3044(2009)33-9593-04

The Design and Implementation of Community-based Question Answering Meta Search Engine

HUANG Yu1， CHEN Jun2

(1.Jinan Shizhong District Hospital， Ji'nan 250002， China; 2.Network and Information Center， Shandong University， Ji'nan 250100， China)

Abstract: Community-based Question answering sites have emerged as popular and effective means of information seeking on the web in recent years. This paper introduces the principle of meta-search engines oriented community and implementation of key techniques such as information extraction， word segmentation and relevancy ranking. Experimental result demonstrates that meta-search engine has sufficiently improved the precision.

Key words: search engine; meta-search engine; community-based question answering

基于社區的問答(Community-based Question-Answering， CQA)站點是近幾年出現并開始流行的一種新的網絡應用形式，典型的如百度知道、雅虎知識堂等，在CQA站點中，用戶提出自己的問題，回答他人的問題，并對他人給出的對自己問題的解答做出評價。CQA站點中的問題來自于日常生活中各個方面，這些問題的解答日積月累，便形成了一個巨大的百科知識寶庫，比如2009年10月初搜搜問問站點已解決問題有1億多條[1]。為了避免用戶的重復提問，方便用戶檢索、利用已有的知識，CQA站點都提供了搜索引擎功能，對當前知識數據庫中的內容進行檢索。CQA的迅速發展日益引起學者的關注并開始了相關研究，Jiwoon Jeon[2]等人提出一個在CQA中自動發現語義相似問題的方法， Eugene Agichtein[3]等人設計了一種從CQA中識別高質量內容的分類框架，Jiang Bian，Yandong Liu等人[4-5]提出一個按相關性及質量檢索答案的方法和一個預測提問者對答復問題滿意程度的模型， 樊佳怡[6]將圖書館虛擬參考咨詢與CQA做了對比研究。

用過多個CQA站點中搜索引擎的用戶會發現，同一個問題，各CQA站點的搜索引擎返回的搜索結果不盡相同，有的甚至有很大差異。已有學者對google、百度等中外通用搜索引擎搜索結果的重合率進行了研究，得出重合率很低的結論[7-8]，這為元搜索引擎的發展提供了依據。我們對百度知道、搜搜問問、雅虎知識堂、愛問知識人等4 個主要中文CQA站點搜索引擎檢索結果重合情況進行了研究，同樣得出重合率很低的結論[9]，因此，針對CQA站點的元搜索引擎是有必要的。我們設計并實現了一個針對CQA站點的元搜索引擎，具有的功能有:可以按句子或關鍵字檢索;如果有匹配的結果直接顯示其內容，否則顯示最相關的前10個結果。該文介紹了實現該系統的關鍵技術，并通過實驗對該系統的有效性做了驗證。

1 元搜索引擎的工作原理

元搜索引擎可以看作建立在搜索引擎之上的搜索引擎，它相當于一個搜索代理，用戶提交查詢后，元搜索引擎根據預置的規則，將查詢發送到其它搜索引擎上，將各搜索引擎返回的結果匯集處理、排序后呈現給用戶，用戶得到的是處理過的來自多個搜索引擎的搜索結果。

如圖1所示，元搜索引擎的工作過程如下:1) 接收用戶的查詢請求q;2)將q的字符格式轉換成各搜索引擎要求的格式;3) 將轉換后的查詢qi發送到這些搜索引擎i，并接收搜索結果集Ri，i=1..n;4)處理搜索結果集Ri，如轉換格式、消重、排序等，得到最終結果集R;5) 將R做為查詢q的結果輸出給用戶。

2 關鍵技術及實現

由上面工作過程可知，一個CQA元搜索引擎應具有的功能包括:接收用戶提交的查詢請求;轉發查詢請求;接收搜索結果;匯總處理搜索結果并輸出給查詢用戶。其中的關鍵技術在結果的處理上，具體可分為信息提取、分詞和相關度排序三部分。下面詳細介紹其具體實現方法及程序代碼。

2.1 信息提取

各搜索引擎的檢索結果是以網頁的形式返回的，網頁信息的抽取方法可分為4類:基于網頁結構的方法、基于模板的方法、基于可視化分塊的方法和基于規則表達式的方法。由于網頁內容、形式各不相同，上述各方法均不具有通用性，不能精確抽取網頁信息。針對搜索引擎返回結果這一特殊情景，返回結果頁面形式固定、格式規范，可用正則表達式進行快速、精確抽取。頁面內容分三各層次:結果列表、結果、結果中主題，該文的元搜索引擎只考慮結果主題，需要用正則表達式精確抽取主題。

結果列表、結果、主題具有包含關系，要取得主題，需要依次進行結果列表、結果、主題提取，對每個搜索引擎返回的結果，根據其頁面特征，設計了三個正則表達式，分別抽取結果列表、結果、主題，正則表達式存為配置文件，當頁面形式改變時重新設計正則表達式，無需改程序代碼。

配置文件格式:

[zhidao]

reg1= (.*?)

reg2=

reg3= target=_blank>(.*?)<\\/a>

reg4=

[yahoo]

…

抽取信息的Perl語言程序代碼(去除了字符集轉換、異常處理代碼)如下，字符變量$wholestr中保存的是抓取的整個網頁內容，提取的主題項及對應的鏈接分別保存在字符數組$result[]和$url[]中。

$wholestr =~ s/\//g;

$wholestr =~ /$reg1/i;#抽取結果列表

if (!defined($1)) { return 0; }

@item = split(/$reg2/i，$1);#抽取各結果

for (my $i =0; $i<@item; $i++) {

$urladdr = $item[$i];

$item[$i] =~ /$reg3/i;#抽取結果中主題

$title = $1;

next if ($title eq '');

$result[$resultnum] = $title;

$urladdr =~ /$reg4/i;

$url[$resultnum] = \"$zhidaourl$1\";

$resultnum++;

}

2.2 分詞

實用性較好的分詞方法有基于詞典的方法和基于統計的方法。因為CQA站點的搜索查詢中常會有新詞、簡稱、縮寫、商品名稱、型號等內容，這些都是詞典里少有的，基于詞典的方法不適合本應用。我們采用的是基于統計的N_gram方法，這里N選2。2_gram的基本方法是以2個字為單位重疊組詞，如字符串“3G手機上網速度快嗎”會切分為“3G手、手機、機上、上網、網速、速度、度快、快嗎”。

分詞函數代碼如下，substr函數用于切詞，哈希表$atoken中保存的是被切字符串中的詞項及出現頻數。

sub tokeniser {

my $rstr = $_[0];

my $tmp = '';

my %atoken;

for (my $i=0; $i

$tmp = substr($rstr，$i，4);#切詞

$atoken{$tmp} ++;#保存切得的詞項，其詞頻數加一

}

return \\%atoken;

}

2.3 相關度排序

搜索結果的相關度排序方法有多種，根據CQA搜索引擎的特點，返回結果的第一頁是與查詢相關度最高的，我們只取第一頁的內容進行排序。我們的排序方法是:在返回結果中搜索是否有與查詢完全匹配的標題項，如果有則直接將標題對應的答案內容取回作為查詢結果發送給用戶;否則對結果按余弦相似度排序，將前10個結果返回給用戶。算法描述如下:

輸入:各CQA搜索引擎返回的查詢結果集R、查詢q

輸出:查詢結果

step1:如果集合R為空，則輸出“無查詢結果”，退出程序。

step2:如果集合R中沒有元素與查詢q字符串相同，轉step5。

step3:獲取與q字符串相同的元素對應的鏈接。

step4:抓取該鏈接對應的網頁，將該頁面作為查詢結果在界面的指定位置顯示，退出程序。

step5:對q分詞，并計算每個詞項的權重w。

step6:遍取集合R中每一元素，對其分詞并計算各詞項權重，計算與q的余弦相似度。

step7:根據余弦相似度將R中元素按從大到小的順序排序。

step8: 將排在前10位的元素及其對應鏈接組合成超文本鏈接在界面的制定位置顯示。

集合中第j個元素rj，與查詢q的余弦相似度計算公式為:

(1)

其中t為詞項數量，wi，j為rj中第i個詞項的權重。wi，j計算公式為:

(2)

ni，j為第i個詞項的在rj中出現的頻數，ni為第i個詞項在所有元素中出現的頻數，N為所有詞項頻數之和。

由于Perl語言具有強大的模式匹配及文本內容處理能力，Redhat Linux系統都帶有Perl語言開發環境，無需額外安裝，我們在Redhat Linux 9.0下用Perl語言實現了該系統。Web界面部分用PHP語言編寫，用于從文本輸入框中接收用戶的查詢請求，驗證安全后再傳遞給后臺的Perl程序。一個有匹配結果的查詢如圖2所示，沒有匹配結果的查詢如圖3所示。

圖2 有匹配結果的查詢輸出圖3 沒有匹配結果的查詢輸出

3 實驗及結果

為了驗證該元搜索引擎的效果，我們從網上隨機選取了500個查詢進行試驗，方法如下。

將“嗎、呢、啥、哪里、哪些、哪個、哪兒、哪去、哪樣、咋樣、怎樣、如何、何時、時候、幾點、哪天、哪年、哪個月、什么、誰、誰知道、誰有、誰是、誰說、誰清楚、誰明白、睡去、多少、為什么、為何”等中文常用疑問詞作為關鍵詞依次向google提交查詢，將google返回結果的前20頁保存下來，用正則表達式將這些網頁中結果標題提取出來，人工對消重后剩余的5300多條逐項檢查，去除了其中的不良信息和陳述句、刪除各句子首尾的欄目名、作者名、網站名等無用文字，再次消重，從剩余的4000個標題中隨機選取500個作為查詢問句。將這500條問句依次向元搜索引擎提交，元搜索引擎將查詢同時提交給百度知道(用zhidao表示)、騰訊搜搜問問(用soso表示)、雅虎知識堂(用yahoo表示)、新浪愛問(用iask表示)，將它們返回結果的第一頁分別保存下來，并提取結果標題，如果查詢問句與某結果標題相同，則認為有一個匹配結果，該結果所屬的搜索引擎匹配計數器加1。最終結果列于表1、 表2。

該文中定義搜索引擎的查準率precision為有匹配結果的查詢數與全部查詢數的比值;根據上節的排序算法，元搜索引擎的查準率precision為: (3)

其中n為CQA站點搜索引擎的個數，Qi為第i個搜索引擎中有匹配結果的查詢集合，Q為全部查詢的集合。

表1中，zhidao、soso、yahoo、iask列依次為百度知道、騰訊搜搜問問、雅虎知識堂、新浪愛問四個單一CQA站點搜索引擎的匹配數和查準率，Mzsy為搜索zhidao、soso、yahoo的元搜索引擎的匹配數和查準率、Mzsi為搜索zhidao、soso、iask的元搜索引擎的匹配數和查準率，以此類推，Mzsyi是搜索zhidao、soso、yahoo、iask的元搜索引擎的匹配數和查準率。表2是zhidao、soso、yahoo、iask任意兩個組合的元搜索引擎的結果。從表1、表2中可以看出，元搜索引擎的查準率明顯好于單一CQA搜索引擎，使用的CQA搜索引擎數量越多，查準率越高。

4 結束語

該文詳細介紹了CQA元搜索引擎的工作原理和實現方法，實驗表明元搜索引擎提高了查準率，元搜索引擎使用的CQA站點越多，查準率越高。針對CQA站點的元搜索引擎可以提高使用者的查詢效率、縮短檢索問題的時間，同時也能提高各CQA站點知識庫的利用率。

參考文獻:

[1] 搜搜問問網[EB/OL].[2009-10-06].http://wenwen.soso.com.

[2] JEON J，CROFT W B，LEE J H.Finding Semantically Similar Questions Based on Their Answers[C]//Salvador，Brazil: Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval，ACM，2005:617-618.

[3] AGICHTEIN E，CASTILLO C，DONATO D，et al.Finding High-quality Content in Social Media[C]//Palo Alto，California，USA:Proceedings of the international conference on Web search and web data mining，CM，2008:183-194.

[4] BIAN J，LIU Y D，AGICHTEIN E，et al.Finding the Right Facts in the Crowd:factoid question answering over social medie[C]//Proceeding of the 17th international conference on World Wide Web.2008，Beijing，China:ACM，2008:467-476.

[5] LIU Y D，BIAN J，AGICHTEIN E.Predicting Information Seeker Satisfaction in Community Question Answering[C]//Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval，2008.Singapore，Singapore:ACM，2008:483-490.

[6] 樊佳怡.圖書館虛擬參考咨詢與互動問答咨詢的比較與啟示[J].圖書館研究與工作，2007(4):37-40.

[7] SPINK A，JANSEN B J，BLAKELY C，et al.A Study of Results Overlap and Uniqueness among Major Web Xearch Engine[J].Information Processing and Management，2006，42(5):1379-1391.

[8] 王益明，劉菲.中文搜索引擎搜索結果重合率研究報告2007[R/OL].[2009-04-03].http://www.searchlab.com.cn/thesis.php.

[9] 黃玉，陳軍.基于社區的問答搜索引擎搜索結果重合率研究[J].山東科學，2009，22(8):59-63.