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

19 一种元搜索引擎的查询结果处理模型一种元搜索引擎的查询结果处理模型 摘 要 为改进元搜索引擎查询速度慢 独立性差的缺点 本文设计了一个元搜索引擎的结果处理 模型 该模型结合元搜索引擎的特点设计了一种 4 级结果集的结构 提高了元搜索引擎结果处理的效率 在结果提取部分提出了根据反馈信息自动调整权重的算法 FBWM 在没有人工干预的情况下自动监视 各独立搜索引擎的性能变化并随之动态调整其权重 在结果排序部分 提出了改进的位置 全文排序法 IPFTS 在算法中引入了词条匹配等级的概念 不但能提高搜索结果和查询串相关度的精度 还能保 证排名在前的搜索结果的 URL 的有效性 关键词 元搜索引擎 结果处理 FBWM 算法 IPFTS 算法 词条匹配等级 1 引言 搜索引擎按其工作原理可分为目录式搜索引 擎 机器人搜索引擎和元搜索引擎三大类 其中 元搜索引擎具有无需人工干预 无需维护庞大的 数据库以及搜索的查全率高等优点 但也具有查 询处理速度慢 搜索性能过于依赖所调用的独立 搜索引擎等缺点 为了克服这些缺点 本文对元 搜索引擎的结果处理部分提出了一种新的处理模 型及相关算法 论文第2节简要介绍元搜索引擎的 体系结构 第3节介绍本模型的结构和一些算法的 思想和实现步骤 第4节是全文总结 2 元搜索引擎的体系结构 一个元搜索引擎就是一个 高层 的搜索引擎 它是调用其他搜索引擎的搜索引擎 元搜索引擎 接收用户的查询串并把它提交给多个下层搜索引 擎 再把下层搜索引擎返回的结果合并成一个统 一的结果返回给用户 一个元搜索引擎一般包括 用户接口 分发器 结果提取和结果排序 4 个模 块 如图 1 所示 图 1 元搜索引擎德体系结构 用户接口接收用户的输入并向用户输出搜索 的结果 分发器以用户接口传送的查询串为依据 根据所调用的独立搜索引擎的特点产生不同的查 询语句 以适应各个不同的独立搜索引擎的特定 要求 例如在 Google 中把 OK HERE 作为一个词 来看待 而在其他一些搜索引擎中会被看成是 OK 和 HERE 两个词 结果提取模块负责从多个 独立搜索引擎返回的结果中提取部分或全部结果 再把这些结果交给结果排序模块 它要解决的是 怎样从独立搜索引擎中提取结果和提取多少等问 题 目前的处理方法主要有 系统预定法 权重分 配法 1 和 信息获取的训练集策略 等 2 结果排序 模块负责把结果提取模块提交的结果按照一定的 策略排序 再交给用户接口 元搜索引擎的结果 排序模块工作的原则是在保证效率的基础上尽可 能利用一切可用信息提高结果排序的质量 目前 的处理方法有 将响应最快的搜索引擎的搜索结果 先返回 星星体系 位置排序法 摘要排序法 位置 摘要排序法 等 2 3 一种元搜索引擎的结果处理模型 结果处理模型涉及图 1 中的结果提取模块和 结果排序模块 它的工作过程是对各个独立搜索 引擎搜索到的结果进行提取 并将这些结果进行 排序后再提交给用户接口 3 1 模型的 4 级结果集结构 各个独立搜索引擎把各自的搜索结果提交给 结果提取模块 结果提取模块以此为 1 级结果集 利用 FBWM Feedback Based Weight Modifying 方法 根据各个独立搜索引擎的权重从 1 级结果 集中提取一部分结果形成 2 级结果集 对 2 级结 果集的结果用位置排序法排序 取其排位在前的 用户接口分发器 结果排序模块结果提取模块 SE1 SE2 SEn www 一种元搜索引擎的查询结果处理模型 20 一部分 得到 3 级结果集 根据各个独立搜索引 擎对 3 级结果集的贡献比率 定义 1 重新调整各 个独立搜索引擎的权重 提取 3 级结果集中排在 前边的一些结果形成 4 级结果集 再对 4 级结果 集中的结果应用改进的位置 全文排序法 IPFTS 排序 完毕后 将 4 级结果集的结果和剩余的 3 级结果集的结果提交给用户接口 图 2 4 级结果集示意图 这样的结果集结构设计是出于这样一种思想 每个独立搜索引擎都会返回上百万结果 但是据 调查 最终用户可能浏览到的网页少于 100 个 所以一般情况下 返回 1 000 000 个结果和返回 100 个结果 对用户来说几乎是一样的 为了提高 性能 我们在庞大的较低级结果集中用低级快速 的算法挑选出一部分网页构成较高级的结果集 在新结果集中应用更高级的 精度更高但时间复 杂度也更高的算法 从新结果集中再提取新的子 集 应用更加复杂的排序算法 最终目的是 达到搜索精度和效率的平衡 3 2 搜索结果的提取 这里的提取是指从各个独立搜索引擎各自的 搜索结果集中提取部分搜索结果 作为元搜索引 擎进一步处理的结果集 搜索结果的提取方法有 系统预定法 权重分配法和训练集方法等 系统预定法过于死板 它限制从各个独立搜 索引擎的结果集中提取结果的数量 也限制了最 终结果集的上限 权重分配法可以更改所取结果 的总数量 并利用权重使从各个搜索引擎的结果 集取得结果各占一定比例 然而独立搜索引擎发 展的速度很快 其性能随时变化 如果等这些搜 索引擎公布这些变化或明显地感到其性能发生变 化时再调整它们的权重 就不能及时 合理 有 效地利用独立搜索引擎的最新成果 训练集方法 则要维护一个庞大的训练集 削弱了元搜索引擎 无须维护大量数据这一优点 3 2 1 FBWM 算法的思想 由此本文提出一种可以根据反馈信息自动调 整权重的算法 简称 FBWM 方法 它实际上也是 基于学习的方法 但是与训练集方法相比它有自 己的特点 FBWM 算法不固定每次查询所返回结果的数 量的总数 2 级结果集的基数 因为对于不同的 查询串 搜索引擎返回的结果的数量相差悬殊 我们对每个独立搜索引擎规定一个比率 从每个 独立搜索引擎的结果集中 按照这个比率提取排 名在前的一部分结果 这个比率与各个独立搜索 引擎的权重相关 从各个独立搜索引擎的结果集 提取出来的结果合到一起 就形成了 2 级结果集 然后对 2 级结果集中的结果用位置排序法进行排 序 形成 3 级结果集 根据各个独立搜索引擎的 搜索结果对 3 级结果集的贡献比率 并不仅仅是 在 3 级结果集中占有率 来调整它们的权重 对 3 级结果集的贡献比率越大 说明这个独立搜索引 擎返回结果的质量越高 所以应该从它的结果集 中多取一些结果 3 2 2 符号的约定 Si表示元搜索引擎调用的第 i 个独立搜索引擎 假设共调用 M 个独立搜索引擎 Ri表示第 i 个独立搜索引擎返回结果的结果集 Wi为 Si的权重 Ni表示从 Ri中根据 Wi提取结果的数量 ni表示在3 级结果集中 属于Ri中结果的数量 3 2 3 FBWM 算法的描述 FBWM 算法的步骤如下 首先对每个独立搜索引擎 Si赋以权重 W0 即 Wi W0 计算从 Ri中提取的结果的数量 Ni 1 M i iiii wwRcN 1 1 其中 Ri 表示集合 Ri的基数 c1是常数 可 以取 0 1 0 01 等等 视对返回结果的数量的要求而 1 级结果集 全部结果 2 级结果集 实施排序的初始结果集 3 级结果集 最终显示的结果集 4 级结果集 实施高精度排序算法 的结果集 一种元搜索引擎的查询结果处理模型 21 定 我们规定搜索引擎的权重以百分数表示 即 令 所以 1 可表示为 1 M 1 i i w 2 iii wRcN 1 将每个 Ri中前 Ni个结果取出 并合并形 成 2 级结果集 对 2 级结果集用位置排序法进行 排序 取出前 n 个结果形成 3 级结果集 其中 3 M i i Ncn 1 2 c2为常数 它的作用和 c1一样 用来控制 3 级结 果集中结果的数量 n 不宜太多或太少 可以定义 n 的上下限 如果通过 c2的调节不能使 n 落在这 个范围内 那就应该强迫 n 属于这个范围 每个独立搜索引擎 我们可以根据占有率 来调整的权重 但是在算法分析部分 M i ii nn 1 i S 我们会看到这样做有不妥之处 于是本文提出了 贡贡献比率这个概念 定义 1 Si对 3 级结果集的贡献比率 pi表示为 Si 对 3 级结果集贡献的结果数 ni除以 Si 在 2 级结果 集中的个数 公式表示为 pi ni Ni 4 再定义规范化的贡献比率调节系数 i P 5 M i iii ppP 1 重新调整每个 Si的权重 Wi 6 iii Pcwcw 43 其中 c3和 c4为常数 且 c3 c4 1 c3和 c4 的大小决定了 Pi对 Wi的影响力 对每个 Wi重新 计算完毕后 将每个 Wi重新化成百分比形式 化 为百分比形式还可以保证每次 Pi对 Wi的影响力是 一样的 7 n i iii www 1 对每次查询 都重复步骤 到步骤 3 2 4 FBWM 算法的分析 对搜索结果总数量的适应性 为了简单 我们假设只有两个独立搜索引擎 S1 S2 对于查询串 q1 S1返回 100000 个结果 S2 返回 150000 个结果 总结果数为 250000 对于查 询串 q2 S1返回 1000 个结果 S2返回 1500 个结 果 总结果数为 2500 显然最终我们需要的 2 级 结果集的结果数应该与上述总结果数近似成正比 FBWM 方法通过以百分比的形式提取结果确保了 这一点 而系统预定法和普通的权重分配法就不 具有这种灵活性 所以说 FBWM 方法避免了人为 的设定取回数量带来的不合理之处 很好的适应 了 Si对不同的查询串返回结果的不可预测性以及 返回结果的数量差别太大 对独立搜索引擎性能变化的适应 每次查询都会对各个独立搜索引擎的权重作 调整 当此元搜索引擎的使用频率较高时 完全 可以及时地适应独立搜索引擎性能的变化 实际 的元搜索引擎大都是设计了一个统计模型 来监 视各个独立搜索引擎的性能变化 而不是仅仅参 照相对滞后的独立搜索引擎公布的技术信息 对独立搜索引擎的搜索精度的差别的适应 为什么用贡献比率而不用占有率 举例来说 假设对某个查询串 q S1返回了 200 个搜索结果 S2返回了 800 个搜索结果 S1和 S2初始的权重分 别为 W1 0 5 和 W2 0 5 则提取到 2 级结果集的数 量分别为 N1 200 0 5 100 N2 800 0 5 400 假 设最终 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的必定会下降 这才能适应 不同的独立搜索引擎在搜索精度上的差别 与训练集方法的不同之处 虽然都是根据各个独立搜索引擎的结果集在 高质量的结果集中占有情况来调整权重 但是 FBWM 算法根据的是贡献比率 训练集方法根据 的是占有率 训练集方法中的权重决定的是各个 独立搜索引擎的搜索结果在总结果集中占有的比 例 而 FBWM 方法中的权重决定的是从各个独立 搜索引擎的结果中选取结果的比例 因为没有维 护查询结果集 所以 FBWM 方法的效率和资源占 一种元搜索引擎的查询结果处理模型 22 用方面比训练集策略有明显优势 但是也失去了 对独立搜索引擎针对不同查询串的搜索性能差异 的处理能力 3 3 搜索结果的排序 这一部分要把搜索结果按规则评分 把得分 最高的结果放在最前 在本文讲述的模型里 搜 索结果的排序过程先是把第 2 结果集里的结果用 位置排序法排序 选出其中前 N 个结果形成第 3 结果集 选出前 K 个结果形成第 4 结果集 一般 的 K N 对第 4 结果集的结果应用改进的位置 全文排序法 IPFTS 算法 进行排序 最后 把排 好序的第 4 结果集和第 3 结果集的结果提交给用 户接口 这一部分提出了一个 改进的位置 全文排序法 简称 IPFTS Improved Place Di表示 ri对应的全部文本信息 即文档 q 表示用户输入的查询串 lj表示 q 中第 j 个词条 X 为查询串 q 中的词条数 3 3 3 IPFTS 算法的描述 对每个 ri 仿照摘要排序法 计算 Di与 q 的普通相 关度 是指没有词条匹配等级影响的相关度 先计算q中每个词条lj与文档Di的相关度Rl lj Di ij DlRl 8 1 ln ijD lOccurence k iji DklLocationDLength 其中 Length Di 为 Di的长度 Occurrence lj Di 为 lj在 Di中出现的次数 Location lj k Di 为词条 lj 在 Di中第 k 次出现的位置 再计算 Di与 q 的相关 度 Rq q Di X j iji DlRlDqRq 9 其中 X 为查询串 q 中的词条数 一种元搜索引擎的查询结果处理模型 23 计算文档 Di与查询串 q 的词条匹配等级 定义词条 lj与文档 Di的词条匹配等级系数 mg lj Di 10 计算查询串 q 与文档 Di的词条匹配等级 MG q Di 11 i DqMG X j ij Dlmg 1 其中 X 为 q 中词条的个数 计算查询串 q 与文档 Di的相关度 R q Di 12 iii DqRqDqMGDqR 计算位置信息的得分 P ri P ri 1 i 13 公式 13 表示第 4 结果集中第 i 个结果的位置 信息得分是它所在的位置的倒数 综合位置信息和相关度信息 先将相关度和位置信息得分分别标准化 再 乘以各自的权重 相加 得到最终排序分数 Rank ri i rRank 14 K i ii K i ii rPrPcDqRDqRc 1 6 1 5 其中 c5 c6是常数 它们的大小决定了位置 信息和相关度信息对最终排序的影响力 K 为第 4 结果集中结果的个数 第 4 结果集的基数 最后 将第 4 结果集中的 ri按照 Rank ri 的值 从大到小排列 3 3 4 IPFTS 算法的分析 IPFTS 算法就是一种加入了词条匹配等级的全 文相关度计算方法与位置排序法的融合 除了位 置排序法本身的特点外 还有以下特点 对独立搜索引擎用户接口的差异的适应 IPFTS 算法是根据搜索结果的网页全文来计算 相关度 不管各个独立搜索引擎的用户接口以什 么形式返回结果 都不影响 IPFTS 算法的最后结 果 对返回结果的有效性的保证 对第 4 结果集的结果来说 因为要获取它的 全文 所以要链接它的 URL 并将它的全文下载 到本地 这无形当中检测了 URL 的有效性 这是 目前很多搜索引擎没有做的 例如 经常会在 Google 和 Baidu 等搜索引擎的搜索结果中发现无 效链接 死链接 这多半是出于时间效率上的考 虑 在稍后的分析中会看到 由于本模型的第 4 结果集较小 所以时间上的代价可以接受 时间代价问题 本模型假设第 4 结果集的结果数为几百 普通 的元搜索引擎提取摘要时 处理的结果往往是几千 几万甚至更多 所以要下载的网页数也达到几百到 几千 以 Google 为例 它每页显示 10 个搜索结果 也就是说每获取 10 个搜索结果的摘要信息 就要 下载一个网页 而 IPFTS 算法略掉了从较为庞大 的结果集中提取摘要的步骤 所以在获取网页方面 本模型的 IPFTS 算法并没有花费更多的时间 当 然 这是以参加精确排序的结果数减少为代价的 3 4 模型的特色 4 级结果集结构 使最有用的搜索结果接受最多最精确的处理 使那些不太有用的结果浪费很少时间 在一定程 度上解决了元搜索引擎响应速度慢的缺点 另外 它使一些时间代价大的算法得以实施 根据反馈信息自动调整权重的算法 能根据每次查询的反馈信息自动调整独立搜 索引擎的权重 做到了在没有人工干预的情况下 自动的监视独立搜索引擎的性能变化 并根据变 化作相应的调整 而且 FBWM 算法对不同的查 询串返回结果的数量的巨大差别 对各个搜索引 擎精度的差别作了相应的处理 词条匹配等级 词条匹配等级的引入 使得含有查询串中多 数词条的文档从只含有较少词条但词条出现次数 较多的文档中脱颖而出 改进的位置 全文排序法 较位置 摘要排序法 能更精确的判别结果与查 询串的相关度 对独立搜索引擎用户接口的差异有 很好的适应性 还能保证第4 结果集中结果的有效 性 4 结束语 一种元搜索引擎的查询结果处理模型 24 用户接口 分发器 结果提取模块和结果排 序模块构成了元搜索引擎 本文对元搜索引擎中 的结果提取模块和结果排序模块提出了一种新的 查询结果处理模型 该模型利用 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 Server 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 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 Engines ZHANG 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 query results of meta search engines which aims at improving the