基于社区的问答元搜索引擎设计与实现

摘要:基于社区的问答是近几年出现并流行的一种有效的信息搜寻网络应用。文章介绍了针对这种社区的元搜索引擎的工作原理,信息提取、分词、相关度排序等关键技术的实现方法,实验结果表明元搜索引擎提高了查准率。

关键词:搜索引擎;元搜索引擎;基于社区的问答

中图分类号: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; work 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>(.*?)

reg4=

[yahoo]

…

抽取信息的Perl语言程序代码(去除了字符集转换、异常处理代码)如下,字符变量$wholestr中保存的是抓取的整个网页内容,提取的主题项及对应的链接分别保存在字符数组$result[]和$url[]中。

$wholestr =~ s/\n//g;

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

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

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

for (my $i =0; $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]..

[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]..cn/thesis.php.

[9] 黄玉,陈军.基于社区的问答搜索引擎搜索结果重合率研究[J].山东科学,2009,22(8):59-63.