一种元搜索引擎的查询结果处理模型(

1、一种元搜索引擎的一种元搜索引擎的查询结查询结果果处处理模型理模型(张强弓1，喻国宝2，廖湖声3，隋树林4(1,2,3 北京工业大学 计算机学院，北京 100022)(4 青岛科技大学 四方学院，山东青岛 266042)摘要：为改进元搜索引擎查询速度慢、独立性差的缺点，本文设计了一个元搜索引擎的结果处理模型。该模型结合元搜索引擎的特点设计了一种 4 级结果集的结构，提高了元搜索引擎结果处理的效率。在结果提取部分提出了根据反馈信息自动调整权重的算法（FBWM），在没有人工干预的情况下自动监视各独立搜索引擎的性能变化并随之动态调整其权重。在结果排序部分，提出了改进的位置/全文排序法（IPFTS），在

2、算法中引入了词条匹配等级的概念，不但能提高搜索结果和查询串相关度的精度，还能保证排名在前的搜索结果的 URL 的有效性。关键词：元搜索引擎；结果处理；FBWM 算法；IPFTS 算法；词条匹配等级 本文得到北京市优秀人才培养专项经费资助。1 张弓强（1982-），男，汉族，山东人，硕士研究生，主要从事网络信息检索和 Web 信息集成等方面的研究。E-mail: .1. 引言搜索引擎按其工作原理可分为目录式搜索引擎、机器人搜索引擎和元搜索引擎三大类。其中元搜索引擎具有无需人工干预、无需维护庞大的数据库以及搜索的查全率高等优点，但也具有查询处理速度慢，搜索性能过于依赖所调用的独立搜索引擎等缺点。为

3、了克服这些缺点，本文对元搜索引擎的结果处理部分提出了一种新的处理模型及相关算法。论文第2节简要介绍元搜索引擎的体系结构；第3节介绍本模型的结构和一些算法的思想和实现步骤；第4节是全文总结。2. 元搜索引擎的体系结构一个元搜索引擎就是一个“高层”的搜索引擎它是调用其他搜索引擎的搜索引擎。元搜索引擎接收用户的查询串并把它提交给多个下层搜索引擎，再把下层搜索引擎返回的结果合并成一个统一的结果返回给用户。一个元搜索引擎一般包括用户接口、分发器、结果提取和结果排序 4 个模块，如图 1 所示。图 1 元搜索引擎德体系结构用户接口接收用户的输入并向用户输出搜索的结果。分发器以用户接口传送的查询串为依据，根

4、据所调用的独立搜索引擎的特点产生不同的查询语句，以适应各个不同的独立搜索引擎的特定要求。例如在 Google 中把“OK_HERE”作为一个词来看待，而在其他一些搜索引擎中会被看成是“OK”和“HERE”两个词。结果提取模块负责从多个独立搜索引擎返回的结果中提取部分或全部结果，再把这些结果交给结果排序模块。它要解决的是怎样从独立搜索引擎中提取结果和提取多少等问题。目前的处理方法主要有“系统预定法”、 “权重分配法1”和“信息获取的训练集策略”等2。结果排序模块负责把结果提取模块提交的结果按照一定的策略排序，再交给用户接口。元搜索引擎的结果排序模块工作用户接口分发器结果排序模块结果提取模块SE1

5、SE2.SEnwww的原则是在保证效率的基础上尽可能利用一切可用信息提高结果排序的质量。目前的处理方法有“将响应最快的搜索引擎的搜索结果先返回”、 “星星体系”、 “位置排序法”、 “摘要排序法”、 “位置/摘要排序法”等2。3. 一种元搜索引擎的结果处理模型结果处理模型涉及图 1 中的结果提取模块和结果排序模块。它的工作过程是对各个独立搜索引擎搜索到的结果进行提取，并将这些结果进行排序后再提交给用户接口。3.1 模型的 4 级结果集结构各个独立搜索引擎把各自的搜索结果提交给结果提取模块，结果提取模块以此为 1 级结果集；利用 FBWM（Feedback Based Weight Modify

6、ing）方法，根据各个独立搜索引擎的权重从 1 级结果集中提取一部分结果形成 2 级结果集；对 2 级结果集的结果用位置排序法排序，取其排位在前的一部分，得到 3 级结果集；根据各个独立搜索引擎对 3 级结果集的贡献比率（定义 1）重新调整各个独立搜索引擎的权重；提取 3 级结果集中排在前边的一些结果形成 4 级结果集，再对 4 级结果集中的结果应用改进的位置/全文排序法（IPFTS）排序。完毕后，将 4级结果集的结果和剩余的 3 级结果集的结果提交给用户接口。图 2 4 级结果集示意图这样的结果集结构设计是出于这样一种思想：每个独立搜索引擎都会返回上百万结果，但是据调查，最终用户可能浏览到的

7、网页少于 100 个。所以一般情况下，返回 1,000,000 个结果和返回 100 个结果，对用户来说几乎是一样的。为了提高性能，我们在庞大的较低级结果集中用低级快速的算法挑选出一部分网页构成较高级的结果集，在新结果集中应用更高级的，精度更高但时间复杂度也更高的算法。从新结果集中再提取新的子集，应用更加复杂的排序算法，最终目的是达到搜索精度和效率的平衡。3.2 搜索结果的提取这里的提取是指从各个独立搜索引擎各自的搜索结果集中提取部分搜索结果，作为元搜索引擎进一步处理的结果集。搜索结果的提取方法有系统预定法、权重分配法和训练集方法等。系统预定法过于死板，它限制从各个独立搜索引擎的结果集中提取结

8、果的数量，也限制了最终结果集的上限。权重分配法可以更改所取结果的总数量，并利用权重使从各个搜索引擎的结果集取得结果各占一定比例。然而独立搜索引擎发展的速度很快，其性能随时变化，如果等这些搜索引擎公布这些变化或明显地感到其性能发生变化时再调整它们的权重，就不能及时、合理、有效地利用独立搜索引擎的最新成果。训练集方法则要维护一个庞大的训练集，削弱了元搜索引擎无须维护大量数据这一优点。由此本文提出一种可以根据反馈信息自动调整权重的算法，简称 FBWM 方法，它实际上也是基于学习的方法，但是与训练集方法相比它有自己的特点。FBWM 算法不固定每次查询所返回结果的数量的总数（2 级结果集的基数）。因为对

9、于不同的查询串，搜索引擎返回的结果的数量相差悬殊。我们对每个独立搜索引擎规定一个比率，从每个独立搜索引擎的结果集中，按照这个比率提取排名在前的一部分结果（这个比率与各个独立搜索引擎的权重相关）。从各个独立搜索引擎的结果集提取出来的结果合到一起，就形成了 2 级结果集。然后对 2 级结果集中的结果用位置排序法进行排序，形成 3 级结果集。根据各个独立搜索引擎的搜索结果对 3 级结果集的贡献比率（并不仅仅是在 3 级结果集中占有率）来调整它们的权重。对 3 级结果集的贡献比率越大，说明这个独立搜索引擎返回结果的质量越高，所以应该从它的结果集中多取一些结果。1 级结果集（全部结果）2 级结果集（实施

10、排序的初始结果集）3 级结果集（最终显示的结果集）4 级结果集（实施高精度排序算法的结果集） Si表示元搜索引擎调用的第 i 个独立搜索引擎，假设共调用 M 个独立搜索引擎； Ri表示第 i 个独立搜索引擎返回结果的结果集； Wi为 Si的权重； Ni表示从 Ri中根据 Wi提取结果的数量； ni表示在 3 级结果集中，属于 Ri中结果的数量。FBWM 算法的步骤如下： 首先对每个独立搜索引擎 Si赋以权重 W0，即 Wi = W0。 计算从 Ri中提取的结果的数量 Ni： （1）MiiiiiwwRcN11其中，|Ri|表示集合 Ri的基数。c1是常数，可以取 0.1,0.01 等等，视对返回

11、结果的数量的要求而定。我们规定搜索引擎的权重以百分数表示，即令。所以（1）可表示为：1M1iiw （2）iiiwRcN1 将每个 Ri中前 Ni个结果取出，并合并形成 2 级结果集，对 2 级结果集用位置排序法进行排序，取出前 n 个结果形成 3 级结果集。其中： （3）MiiNcn12c2为常数，它的作用和 c1一样，用来控制 3 级结果集中结果的数量。n 不宜太多或太少，可以定义 n的上下限。如果通过 c2的调节不能使 n 落在这个范围内，那就应该强迫 n 属于这个范围。 每个独立搜索引擎，我们可以根据占有率来调整的权重，但是在算法分析部分Miiinn1iS我们会看到这样做有不妥之处。于是

12、本文提出了贡贡献比率这个概念：定义 1： Si对 3 级结果集的贡献比率 pi表示为 Si对 3 级结果集贡献的结果数 ni除以 Si 在 2 级结果集中的个数。公式表示为：pi = ni / Ni （4）再定义规范化的贡献比率调节系数iP （5）MiiiippP1 重新调整每个 Si的权重 Wi： （6）iiiPcwcw43其中 c3和 c4为常数， 且 c3+c4 =1 。c3和 c4的大小决定了 Pi对 Wi的影响力。对每个 Wi重新计算完毕后，将每个 Wi重新化成百分比形式（化为百分比形式还可以保证每次 Pi对 Wi的影响力是一样的）： （7）niiiiwww1 对每次查询，都重复步骤

13、到步骤。 对搜索结果总数量的适应性为了简单，我们假设只有两个独立搜索引擎S1，S2。对于查询串 q1, S1返回 100000 个结果，S2返回 150000 个结果，总结果数为 250000；对于查询串 q2，S1返回 1000 个结果，S2返回 1500 个结果，总结果数为 2500。显然最终我们需要的 2 级结果集的结果数应该与上述总结果数近似成正比，FBWM方法通过以百分比的形式提取结果确保了这一点，而系统预定法和普通的权重分配法就不具有这种灵活性。所以说 FBWM 方法避免了人为的设定取回数量带来的不合理之处，很好的适应了 Si对不同的查询串返回结果的不可预测性以及返回结果的数量差别

14、太大。 对独立搜索引擎性能变化的适应每次查询都会对各个独立搜索引擎的权重作调整，当此元搜索引擎的使用频率较高时，完全可以及时地适应独立搜索引擎性能的变化。实际的元搜索引擎大都是设计了一个统计模型，来监视各个独立搜索引擎的性能变化，而不是仅仅参照相对滞后的独立搜索引擎公布的技术信息。 对独立搜索引擎的搜索精度的差别的适应为什么用贡献比率而不用占有率？举例来说，假设对某个查询串 q，S1返回了 200 个搜索结果，S2返回了 800 个搜索结果，S1和 S2初始的权重分别为 W1=0.5 和 W2=0.5。则提取到 2 级结果集的数量分别为 N1=200*0.5=100，N2=800*0.5=40

15、0。假设最终 S1的 100 个搜索结果有 50 个入选了 3 级结果集，而 S2的 400 个搜索结果也只有 50 个入选。显然，S1的搜索质量比 S2高，应该从 S1的结果集中多取，但是 S1和 S2的结果在 3 级结果集中的占有率都是 50/（50+50）=0.5。根据公式（6），没有起到调整权重的作用。而 S1的贡献比率 p1=50/100=0.5，S2的贡献比率 p2=50/400=0.125；S1的贡献比率调节系数 P1=0.5/(0.5+0.125)=0.8，S2的P2=0.125/（0.5+0.125）=0.2。可以看到 S1的权重必定会有所提高，S2的必定会下降。这才能适应不

16、同的独立搜索引擎在搜索精度上的差别。 与训练集方法的不同之处虽然都是根据各个独立搜索引擎的结果集在高质量的结果集中占有情况来调整权重，但是FBWM 算法根据的是贡献比率，训练集方法根据的是占有率；训练集方法中的权重决定的是各个独立搜索引擎的搜索结果在总结果集中占有的比例，而 FBWM 方法中的权重决定的是从各个独立搜索引擎的结果中选取结果的比例；因为没有维护查询结果集，所以 FBWM 方法的效率和资源占用方面比训练集策略有明显优势，但是也失去了对独立搜索引擎针对不同查询串的搜索性能差异的处理能力。3.3 搜索结果的排序这一部分要把搜索结果按规则评分，把得分最高的结果放在最前。在本文讲述的模型里

17、，搜索结果的排序过程先是把第 2 结果集里的结果用位置排序法排序，选出其中前 N 个结果形成第 3 结果集，选出前 K 个结果形成第 4 结果集（一般的，KN）。对第 4 结果集的结果应用改进的位置/全文排序法（IPFTS 算法）进行排序。最后，把排好序的第 4 结果集和第 3 结果集的结果提交给用户接口。这一部分提出了一个“改进的位置/全文排序法”，简称 IPFTS（Improved Place & Full-Text Sorting）方法。在这个方法中，提出了一个概念：词条匹配等级。应用词条匹配等级可以使排序结果更加准确。这里需要注意的是，全文排序法，词条匹配等级这些概念在拥有数据库的机器

18、人搜索引擎中是很自然的被应用的，但是对元搜索引擎来说，它的操作对象是文本而不是数据库，所以在应用这些概念时就要费一些周折了。IPFTS 算法在排序时综合考虑了位置信息和全文信息与查询串的相关度两个因素。由于位置信息已经在 3 级结果集的形成过程中应用了，所以IPFTS 算法要处理的第 4 结果集里的结果的顺序已经是按照位置信息排序后的顺序，所以这里 IPFTS算法的重点是全文排序，只不过最后在全文排序的结果中加入位置信息的影响。IPFTS 算法是在对摘要排序法的改进的基础上提出的。摘要排序法的优点是实现简单，速度快。缺点是返回的摘要过于简单，而且各个独立搜索引擎的用户接口不同，导致同一个结果在

19、不同的独立搜索引擎返回的摘要不同。摘要排序法往往导致返回摘要信息多的搜索引擎的搜索结果排名靠前，而不是与词条相关度高的搜索结果排名靠前。因此IPFTS 算法决定提取搜索结果的全部文本内容（文档）作为判别相关性的依据。这样做的最大问题是效率。但在后文的算法分析部分，我们将会看到此模型的 4 级结果集结构缓解了这一问题。在计算查询串与文档的相关度时，我们引入了词条匹配等级这个概念。它的提出出于这样一种思想：假设一个查询串 q 有 m 个词条 l1，l2，lm，如果在文档 D1中，l1出现了 m 次, l2到 lm一次也没出现，而在与文档 D1长度相同的文档 D2中，l1,lm各出现一次。则按照先前

20、的算法，D1与 q的相关度和 D2与 q 的相关度都是 m 。但是，显然，D2是比 D1更好的结果。 （例如：查询串 q=“信息 获取 技术”，则词条“信息”出现很多次而“获取”和“技术”没有出现的文档，与“信息”， “获取”， “技术”都出现的文档相比，自然是后者具有更高的相关度）于是，我们考虑给词条匹配全面的文档奖励：更高的词条匹配等级。定义 2： 设查询串 q 有 X 个词条，文档 D 中包含有这 X 个词条的 N 个（N=X）,则文档 D 与查询串q 的词条匹配等级为 N。ri表示第 4 结果集中第 i 个结果;Di表示 ri对应的全部文本信息，即文档;q 表示用户输入的查询串;lj表

21、示 q 中第 j 个词条。X 为查询串 q 中的词条数。对每个 ri： 仿照摘要排序法，计算 Di与 q 的普通相关度（是指没有词条匹配等级影响的相关度）。先计算q中每个词条lj与文档Di的相关度Rl(lj, Di)：),(ijDlRl（8）),(1) ),()(ln(ijDlOccurencekijiDklLocationDLength其中 Length(Di)为 Di的长度；Occurrence(lj, Di)为 lj在 Di中出现的次数；Location(lj, k, Di)为词条 lj在 Di中第 k 次出现的位置。再计算 Di与 q 的相关度 Rq(q, Di)： （9）XjijiD

22、lRlDqRq),(),(其中，X 为查询串 q 中的词条数。 计算文档 Di与查询串 q 的词条匹配等级。定义词条 lj与文档 Di的词条匹配等级系数mg(lj, Di)： （10）计算查询串 q 与文档 Di的词条匹配等级MG(q, Di)：= （11）),(iDqMGXjijDlmg1),(其中 X 为 q 中词条的个数。 计算查询串 q 与文档 Di的相关度 R(q, Di)： （12）),(),(),(iiiDqRqDqMGDqR 计算位置信息的得分 P(ri)：P(ri) = 1/i （13）公式(13)表示第 4 结果集中第 i 个结果的位置信息得分是它所在的位置的倒数。 综合位

23、置信息和相关度信息先将相关度和位置信息得分分别标准化，再乘以各自的权重，相加，得到最终排序分数 Rank(ri)： )(irRank（14）KiiiKiiirPrPcDqRDqRc1615)()(),(),(其中 c5，c6是常数，它们的大小决定了位置信息和相关度信息对最终排序的影响力。K 为第 4 结果集中结果的个数（第 4 结果集的基数）。最后，将第 4 结果集中的 ri按照 Rank(ri)的值从大到小排列。IPFTS 算法就是一种加入了词条匹配等级的全文相关度计算方法与位置排序法的融合。除了位置排序法本身的特点外，还有以下特点： 对独立搜索引擎用户接口的差异的适应IPFTS 算法是根据

24、搜索结果的网页全文来计算相关度，不管各个独立搜索引擎的用户接口以什么形式返回结果，都不影响 IPFTS 算法的最后结果。 对返回结果的有效性的保证对第 4 结果集的结果来说，因为要获取它的全文，所以要链接它的 URL，并将它的全文下载到本地。这无形当中检测了 URL 的有效性。这是目前很多搜索引擎没有做的。例如，经常会在 Google 和Baidu 等搜索引擎的搜索结果中发现无效链接（死链接）。这多半是出于时间效率上的考虑。在稍后的分析中会看到，由于本模型的第 4 结果集较小，所以时间上的代价可以接受。 时间代价问题本模型假设第 4 结果集的结果数为几百。普通的元搜索引擎提取摘要时，处理的结果

25、往往是几千、几万甚至更多，所以要下载的网页数也达到几百到几千。以 Google 为例，它每页显示 10 个搜索结果，也就是说每获取 10 个搜索结果的摘要信息，就要下载一个网页。而 IPFTS 算法略掉了从较为庞大的结果集中提取摘要的步骤，所以在获取网页方面，本模型的 IPFTS 算法并没有花费更多的时间。当然，这是以参加精确排序的结果数减少为代价的。3.4 模型的特色 4 级结果集结构使最有用的搜索结果接受最多最精确的处理，使那些不太有用的结果浪费很少时间。在一定程度上解决了元搜索引擎响应速度慢的缺点。另外它使一些时间代价大的算法得以实施。 根据反馈信息自动调整权重的算法能根据每次查询的反馈

26、信息自动调整独立搜索引擎的权重。做到了在没有人工干预的情况下，自动的监视独立搜索引擎的性能变化，并根据变化作相应的调整。而且，FBWM 算法对不同的查询串返回结果的数量的巨大差别，对各个搜索引擎精度的差别作了相应的处理。 词条匹配等级词条匹配等级的引入，使得含有查询串中多数词条的文档从只含有较少词条但词条出现次数较多的文档中脱颖而出。 改进的位置/全文排序法较位置/摘要排序法，能更精确的判别结果与查询串的相关度；对独立搜索引擎用户接口的差异有很好的适应性，还能保证第 4 结果集中结果的有效性。4. 结束语用户接口、分发器、结果提取模块和结果排序模块构成了元搜索引擎。本文对元搜索引擎中的结果提取

27、模块和结果排序模块提出了一种新的查询结果处理模型，该模型利用 4 级结果集的结构、根据反馈信息自动调整权重的算法、词条匹配等级的概念和改进的位置/全文排序法等技术，有利于克服元搜索引擎查询速度慢，独立性差的缺点。将来如果能结合用户接口模块和分发器模块的新技术共同应用，将会使元搜索引擎更具威力。参考文献：1 Eric J. Glover，Using Extra-Topical User Preferences To Improve Web-Based Metasearch., PhD thesis. University of Michigan 2001.2 Yuwono B, Lee D. S

28、erver ranking for distributed text database systems on Internet. Proceedings of 5th International Conference on Database Systems for Advanced Applications.，Melbourne ,Australia: World Scientific Pub Co Inc，April, 1997. pp. 391-400.3 徐宝文，张卫峰.搜索引擎与信息获取技术.北京：清华大学出版社，2003. pp.146-147，153.4 Sergey Brin,

29、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 Query 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 model for the q