一种基于Java的元搜索引擎的设计与实现_伏汉英

收稿日期:2004-05-17

作者简介:伏汉英(1982-),女,四川南部人,信息工程大学硕士研究生,主要研究方向为分布式对象处理。

一种基于Java 的元搜索引擎的设计与实现

伏汉英,黄永忠,陈　新,杨　凯,郭金庚

(信息工程大学信息工程学院,河南郑州450002)

摘要:随着搜索引擎技术的发展,元搜索引擎已经成为搜索引擎的一个重要的研究方向。文章首先介绍了元搜索引擎的工作原理,接下来分析了影响元搜索引擎性能的各个因素。在此基础上,给出了一种由Java 实现的元搜索引擎的系统框架,以及系统所采用的合成排序算法。关键词:元搜索引擎;搜索引擎;Java ;合成排序算法中图分类号:TP393.092 文献标识码:A

文章编号:1671-0673(2004)04-0042-04

A Design and Implementation of a Meta Search Engine With Java FU Han _ying ,HUANG Yong _zhong ,CHEN Xin ,YANG Kai ,GUO Jin _geng

(Institute of Information En gineering ,Information Engineering University ,Zhengzhou 450002,China )

Abstract :Under the development of search engine technology ,meta search engine is bec oming an impor -tant research .This paper first describes the model of meta search engine ,then analyzes each factor that can influence the meta search engine 's performance .On this condition ,we introduce a framework of a meta search engine with Java ,and the system 's fusion and sort algorithms Key words :meta search engine ;search engine ;Java ;fusion and sort algorithms

1　元搜索引擎的提出

互联网已经成为人类历史上最大的资源和信息库,人们越来越依赖互联网来寻找自己所需要的信息。但是,互联网上的资源的组织非常杂乱无章,需要靠搜索引擎(Search Engine ,简称SE )来将这浩如烟海的资源有机地组织起来,使人们能够方便地在网上搜寻到自己所需的信息。可以说,搜索引擎在用户的上网过程中扮演者一个导航灯的作用。但是,迄今为止,没有一个搜索引擎能够涵盖到整个互联网,并且,搜索引擎不同,它采用的搜索算法,排序算法,后端数据库的大小,提供的服务,以及用户接口的设计都是不同的。对同一个查询请求,不同的搜索引擎返回的结果也不同。这样一来,用户为了查找到自己真正需要的信息,就不得不使用多个搜索引擎,一个一个的链接查找,费时

费力。元搜索引擎(Meta Search Engine ,简称MSE )

就是在这样的需求下产生的。

2　元搜索引擎及其工作原理

元搜索引擎可看作是搜索引擎之上的搜索引擎,它向用户提供一个统一的接口,同时调用多个单独的搜索引擎,返回的结果也以统一的方式来组织(后端的单独搜索引擎叫做源搜索引擎,Source Search Engine ,简称SSE )。这样用户只需输入一次查询请求就能够得到多个搜索引擎的搜索结果。

从上面元搜索引擎的工作原理(见图1)可以看出,元搜索引擎工作过程分成以下几步:

①接受用户的查询条件;

②将用户的查询条件转化为各个SSE 能够辨认的格式;

③将转化后的查询条件发送给各个SSE ;

第5卷　第4期 信息工程大学学报 Vol .5No .4　2004年12月 Journal of Information Engineering University Dec .2004

④收集各个SSE 返回的查询结果;

⑤将查询结果合成排序,形成MSE 的结果集;⑥将MSE 的结果集发送给用户

。

图1　元搜索引擎的工作原理图

与单独搜索引擎相比,元搜索引擎具有以下特点:首先,对同一个查询条目,元搜索引擎能够返回更多的结果,MSE 的结果集是各个SSE 结果集的全集,各个SSE 的结果集只是MSE 的一个子集;第二,MSE 没有自己的索引数据库,它只是单纯收集单独搜索引擎的结果把它们合并,优化后统一返回给用户,即使需要数据库,也只是利用数据库对SSE 返回的结果集进行简单的操作和管理;第三,元搜索引擎不能独立地提供服务,如果后端的搜索引擎发生了变化,它的工作性能就会受到影响。

3　影响元搜索引擎性能的因素及优化

国内外对元搜索引擎的设计和研究已经有了一段时间,到目前为止,已经出现了近百个可供用户使用的元搜索引擎,比较有代表性的有国外的SavvySearch 、Metacrawler 、Metasearch 、Highway61和中文的搜星,飓风搜索通等。由于中文的编码问题和中文语义理解等方面的问题,中文元搜索引擎在现阶段还是比较少,而且性能也不是很好。

据F .W .Lancaster 的阐述,判定一个检索系统的优劣,主要从质量、费用和时间3方面来衡量。因此,对搜索引擎的效果评价也应该从这3个方面进行。质量标准主要通过查全率与查准率进行评价;费用标准即检索费用是指用户为检索课题所投入的费用;时间标准是指花费时间,包括转化用户输入条目时间、网络传输时间、合成SSE 结果集时间等。质量标准即查全率和查准率是判定检索效果的主要标准,而后两者相对来说次要些。从元搜索引擎的工作机理我们可以看出MSE 的查全率同SSE 相比已经有了很大的提高,那么重点就要放在提高查准率和缩短时间上。

要缩短时间,就要从MSE 的工作过程着手,其中第①、⑥步主要是网络的响应过程,这不受系统

影响。第③、④步牵涉到网络的工作效率,但是发送和接受过程可以采用多线程的机制,对各个SSE 的发送和接收工作同时进行,比一个一个串行发送要快许多。第②步实现起来比较简单,在整个系统的运行过程中只占有很少的部分。系统时间花费最多的是第⑤步,要设计出尽量简洁而高效的合成排序算法。

从理论上来说,查全率和查准率是成反比关系

的,MSE 在提高了查全率的同时,势必会影响到系统的查准率。这就需要设计者从各个方面来改进,在现有的查全率的基础上,尽量提高查准率。经过我们的实验研究发现,可以从以下这几个方面提高MSE 的查准率。

(1)后端单独搜索引擎的选择

元搜索引擎通过链接单独搜索引擎,对其结果进行合成后向用户提供搜索服务,因此,它选择链接哪些搜索引擎会直接影响到它的检索结果。所以在设计MSE 时需要先对各个单独搜索引擎进行深入细致的研究,要对各个SE 的反馈速度、索引数据库容量、更新周期、对布尔操作符的支持、提供的个性化服务、以及综合起来查准率有多高等特征有清楚的了解。如果做中文的元搜索引擎还要考虑这个SE 是否提供对中文的支持。在收集以上的特征以后,再对各个SE 作出综合的评判,择其性能优越者提供后端的服务。

另外要注意的是有的门户网站的搜索引擎其实并没有独立的搜索技术,它只是使用别的专业SE ,因此它的结果集要么同提供服务的SE 的结果集完全相同,要么就是它的一个子集。那么在选择这类搜索引擎的时候只需要挑选其中的一个,重复调用这些搜索引擎是没有意义的。

后端的搜索引擎除了要包括象google 、baidu 这样的通用搜索引擎以外,还应该增加象教育方面的EducationWorld 、法律方面的ILR G 等专业学科或专题检索工具,和天气、航班、电话号码等特殊搜索引擎。这些非通用搜索引擎虽然适用面比较窄,但是在它们各自的领域却能提供更加专业准确的服务。

(2)合成排序算法的设计

在确定由哪些单独搜索引擎作为MSE 的后端搜索引擎后,就要把重心放在整个MSE 最核心的部分—合成排序算法上。从某种意义上说,一个元搜索引擎的优劣最根本是由合成排序算法来决定,它不仅直接影响到系统工作时间,还决定着整个系统的查准率。

43

第4期 伏汉英等:一种基于Java 的元搜索引擎的设计与实现

典型的合成排序算法有以下几种:第1种,也是最简单的,将每个SSE 的查询结果的第一项交叉列出,然后第二项,依此类推;第2种,如果可以得到文档的原始相关性分值,这些分值可以直接比较,就直接按照原始相关性分值的大小来决定最后的排序顺序;如果这些分值不能直接比较,就通过对倒排文档频率(idf )等方法来标准化,根据标准化后的分值进行排序;第3种,对每个SSE 都计算出它相应于查询条件的重要性,并赋以一个权值,将权值乘以文档的相关性分值的结果作为排序的标准。

在实际的搜索引擎设计中,在上述的典型合成排序算法上进行了一些优化和改进。对于多个SSE 重复出现的结果的处理有两种方法:①是取分值最大的作为结果分值;②是将每次出现的分值相加后的和作为结果分值。②法可以使重复出现的结果条目排在只出现一次的结果条目的前面。

(3)提供对与或等逻辑操作符的支持

用户的查询要求常常不是单独的一个关键词就能够表示的,检索时所用检索词(或检索式)的专指度不够,检索面宽于检索要求是造成查准率不高的一个原因。现在大多数的单独搜索引擎都支持与或等逻辑操作符以提高查准率,这样,就为元搜索引擎引进逻辑操作符提供了很好的后端支持。

4　Java 实现的中文元搜索引擎

正如Sun 公司的“Java 白皮书”中对Java 的定义中所说:Java 是一种简单的、面向对象的、分布式的、健壮的、安全的、结构中立的、可移植的、高效能的、多线程的和动态的语言。Java 有一个很周全的程序库,很容易地与HTTP 和TCP /IP 通信协议相配合。另外,Java 是一种安全的网络编程语言,它拥有数个阶层的互锁保护措施,能够有效地防止病毒的侵入和破坏。同时,Java 语言还具有多个线程,这对于交互回应能力和即时执行行为是有帮助的。正因为Java 有如上的优点,我们选择Java 语言来开发我们的中文元搜索引擎。4.1　系统框架

如图2所示,整个系统由4个模块和一个系统

数据库构成,4个模块分别为:用户接口模块、搜索模块、合成排列模块和陈列模块。系统数据库中主要由两种数据表构成:一种是源搜索引擎结果集表SSETable ,一种是结果表ResultTable ,每个搜索引擎

都对应一个SSETable ,而结果表ResultTable 只有一

图2　Java 实现的元搜索引擎系统框架

个,存放经过合成排序后生成的结果集。这些表的结构相同,有5个字段(id ,urladdr ,url name ,urlin -tro ,weight ),id 是自动生成的索引,代表此条结果条目在结果集中的排序;urladdr 字段记录网页url 地址;urlna me 字段记录网页名;urlintro 字段记录网页的简介;weight 字段记录该条目的权值。用户接口模块完成系统与用户的交互工作,接

收用户提交的查询条件,调用搜索模块进行搜索,并且显示陈列模块返回的结果集。

搜索模块完成搜索工作,它负责与各个搜索引擎的交互,首先把用户的查询条件转化成各个搜索引擎能够辨认的格式,然后发送给各个SSE ,最后将SSE 搜索到的结果存放在系统数据库的SSETable 中。

合成排序模块与系统数据库进行交互,它取出各个SSE Table 中的内容,利用合成排序算法合成,将结果存放到ResultTable 中。

陈列机制将系统数据库ResultTable 中的内容以统一方式陈列,然后发送给用户接口模块去显示。

4.2　系统的核心算法———合成排序算法分析

首先给出算法的相关定义:

　d f :m :代表一条结果条目,如果url 相同的就认为是同一条结果;

i :代表SSE ,i =1,2,…;

m (i ):代表m 在第i 个SSE 的结果集上的位置,如果是第一条结果则m (i )=1,第二条结果则m (i )=2,依此类推,m (i )=1,2,…;

c (i ):根据每个SSE 的查准率和性能给出的每个SSE 的置信度,查准率越高的SSE 的c (i )越大,0≤c (i )≤1;

44

信息工程大学学报 2004年

w (i ,m ):m 在第i 个SSE 的权值, w (i ,m )=c (i )＊(1000-m (i ));I (i ,m ):一个特征函数,表示m 这条结果在第i 个搜索引擎的结果集上是否出现。

I (i ,m )=

1,如果m 在i 的结果集上出现;

0,如果m 在i 的结果集上不出现。W (m ):m 最终的权值, W (m )=∑i

I (i ,m )＊w (i ,m )。元搜索引擎返回给用户的结果集中每条结果的排列顺序以W (m )作为判定的标准,W (m )越大的结果条目在结果集中排得越前。注意本算法中w (i ,m )的计算公式中“1000-m (i )”的意思是说对每个搜索引擎都只取其中的前1000条结果,因为在实际的搜索过程中,用户不可能有耐心和时间把所有的结果都链接查看,常常只是查看到前面的几十条,最多几百条而已。我们对每个搜索引擎都取到了前面的1000条,如果后端有10个SSE ,去掉重复的结果数,那么最终我们可以取到5000～10000条结果,这就已经能够充分满足用户的要求。5　结束语

文章讨论了元搜索引擎的原理和影响元搜索引擎工作性能的因素,以及对这些性能优化方法,接着给出了一种由Java 实现的元搜索引擎的系统框架和核心算法。整个系统的瓶颈还是在查准率

的提高上,所以对系统的合成排序算法还需要进一步的优化和研究。

参考文献:

[1]Selberg E W .Towards comprehensive web search [M ].Uni -versity of Was hington ,1999.

[2]Callan J P ,Lu Z ,Croft W B .Searching distributed collection

with inference networks [A ].Proceedings of the 18th Interna -tional Conference on Research and Development in Informa -tion Retrieval [C ].AC M Press ,1995.21-28.

[3]Bruce Eckel .Thinking in Java [M ].北京:机械工业出版

社,2002.

[4]储荷婷.Internet 网络信息检索———原理、工具、技巧

[M ].北京:清华大学出版社,1999.

(上接第11页)

‖f ‖Υ,Q =inf λ>0:1|Q |∫

Q Υ(|f |

λ

)≤1和M Υf (x )=sup x ∈Q

‖f ‖Υ,Q ,我们的结论是

推论2　若局部可积函数f 满足M Υf (x )<∞,a .e .,则有(M Υf (x ))δ

是Α1-权函数,其中

A 1-权常数仅依赖于Υ和δ,0<δ<1。

推论2可由定理2直接得到。事实上,在齐型空间下,由此时测度的双倍性可知,对ρ>1有

‖f ‖Υ,ρ,Q ≤‖f ‖Υ,Q ≤C ‖f ‖Υ,ρ,Q ,其中C 与f 和Q 无关。也就是

M Υ,ρf (x )≤M Υf (x )≤CM Υ,ρf (x )。 由定理2,就有

1 Q ∫Q M Υf (y ) δd y ≤C ess inf x ∈Q (M Υf (x ))δ

。故(M Υf (x ))δ

是A 1-权函数。

参考文献:

[1]Hu G ,Li D .A Cotlar t ype inequality for the multilinear singu -lar integral operators and its applications [J ].J .Math .Anal .

Appl .,2004,290:639-653.[2]

F Nazarov ,S Treil A Volberg .Weak type estimates and Cot -lar 's ineq ualities for Calder ón -Zygmund operators on non -ho -mogeneous spaces [J ].Internat .Math .Res .Notices ,1998,9:463-487.

[3]J Duoandikoetxea .Fourier Analysis [M ].American Mathemat -ic society ,2001.

[4]

J Orobitg and C P érez .A p weights for non doubling measures in and applications [J ].Trans .Amer .Math .Soc .,2002,354:2013-2033.[5]J Verdera .The fall of the doubling condition in Calder ón -Zyg -mund theory [J ].Publ .Mat .,2002,Extra :275-292.[6]M M Rao ,Z D Ren .Theory of Orlicz Spaces [M ].New York :Marcel Dekker ,1991.

[7]X Tolsa .B MO .H 1and Calder ón -Zygmund operators for non doublin g measures [J ].Math .Ann .,2001,319:89-149.[8]

X Tolsa .A proof of the weak (1,1)ineq uality for singular integrals with non doubling measures based on a Calder ón -Zygmund decomposition [J ].Publ .Mat .,2001,45:163-174.[9]

X Tolsa .The space H 1for non doublin g measures in terms of a grand maximal operator [J ].Trans .Amer .Math .Soc .,2003,355:315-348.

45

第4期 伏汉英等:一种基于Java 的元搜索引擎的设计与实现