（计算机应用技术专业论文）个性化元搜索引擎的关键技术的研究与设计.pdf

中北大学学位论文 个性化元搜索引擎的关键技术的研究与设计 摘要 在这个信息爆炸的年代里，快速地、有效地在i n t e r n e = t 上查询信息是一项艰巨的任 务。搜索引擎增强了人们定位和收集信息的能力，但现有的搜索引擎在搜索效率、信息 维护、信息重复、网络及站点负载等方面还存在着很多不足，研究开发功能强大、覆盖 面广、接口友好、返回信息准确的网络搜索引擎已成为亟待解决的课题。 元搜索引擎正是满足这种需求的产物，元搜索引擎技术是一种集成搜索引擎技术， 它主要通过成员搜索引擎选择、文本选择、结果融合三个主要步骤来完成信息检索任务， 如果系统策略设计得当，成员搜索引擎选择方法合适，那么相对于独立的传统搜索引擎 来说，元搜索引擎一般可以达到更高的搜索覆盖率和更好的查询效果。但是元搜索引擎 也会面临与传统搜索引擎一样的问题，就是不能对用户进行个性化分析和提供相应的有 针对性的服务，而且如果系统的集成策略设计地过于简单和机械化，则元搜索引擎多数 情况下并不会取得更好的信息检索效果。 本文针对现有元搜索引擎的局限性和当前用户的个性化需求，以用户兴趣模型为基 础，提出了实现用户个性化搜索的相关算法。本文主要的研究工作如下： ( 1 ) 分析了个性化搜索的特点，研究了用户模型及基于用户模型的学习方法。 ( 2 ) 提取用户兴趣主题特征，分析出用户搜索的兴趣类，这些兴趣类为成员引擎 个性化调度和结果合成处理提供了依据。 ( 3 ) 提出了基于用户兴趣的成员引擎个性化调度算法。 ( 4 ) 提出了基于个人兴趣的搜索结果过滤算法。 最后，本文结合实际实现了一个个性化元搜索引擎实验系统，并对文中提出的算法 进行了实验和分析。同时，面向用户对搜索引擎的需求发展趋势，指出了今后的主要研 究方向。 关键词：元搜索引擎，个性化，用户兴趣，调度策略，结果合成 中北大学学位论文 t h er e s e a r c ha n dd e s i g no nk e y t e c h n o l o g i e s f o rp e r s o n a l i z e dm e t a - s e a r c he n g i n e s w a n gh o n g x i ay i ns i q i n g a b s t r a c t i nt h ee r ao fi n f o r m a t i o ne x p l o s i o n , t h ef a s ta n dd 猗c i e n ti n f o r m a t i o ns e a r c h i n gi n i n t e r n e ti sa na r d u o u st a s k s e a r c he n g i r i c e r se n h a n c eu st h ea b i l i t yo fl o c a t i n ga n dg a t h e r i n g i n f o r m a t i o n b u tt h ee x i s t i n gs e a r c he n g i n e ss t i l lh a v el o r so fd e f i c i e n c yo ns e a r c h i n g e m c i e n c y , i n f o r m a t i o nm a i n t e n a n c e i n f o r m a t i o nr e p e t i t i o n , l o a do fn e t w o r ka n dw e b s i t e s s o i t sa ne a g e r l yd e m a n dt or e s e a r c ha n dd e v e l o pas e a r c he n g i n e 、】l ，i n le n g i n ew i t hp o w e r f u l f u n c t i o n ，w i d ec o v e r i n g ，f r i e n d l yi n t e r f a c ea n da c c u r a t ef e e d b a c k n 圮m e t a - s e a r c he n g i n ei st h ee x a c t l yr e q u i r e d ，w h i c hi sa ni n t e g r a t e ds e a r c ht o o l ，aw e b s e a r c he n g i n eb a s e da nm e t a - s e a r c ht e c h n o l o g ya i m sa th o wt ot a k eu s eo fa n de x t e n dt h e c a p a b i l i t i e so f i t ss u b - e n g i n e st os a t i s f yt h en e e a ：l so fe n g i n eu s e s o r d i n a r i l y , t h ep r o c e d u r eo f am e t a - s e a r c he n g i n ei n c l u d e st h r e es t e p s ：d a t a b a s es e l e c t ( s u b - e n g i n e ss e l e c t ) d o c u m e n t s e l e c ta n dr e s u l tm e r g e c o m p a r i n gw i t ho r d i n a r yi n d e p e n d e n tw e be n g i n e m e t a - e n g i n eh a s i l i g hp o s s i b i l i v yt oa c h i e v eh i ，g hc o v e r a g e ，p r e c i s i o na n dr e c a l l o nt h eo t h e rh a n d ，t h e e 伍c i e n c ya n dp e r f o r m a n c eo fam e t a - s e a r c he n g i n ed e p e n d sm u c ho ni t si i m e ra d m i n i s t r a t i o n a n dm a n a g e m e n tp o l i c i e s ，i fi t a d o p t ss i m p l er e s u l t - m e r g i n ga n ds u b - e n g i n e s e l e c t i n g m o d u l e s ，n e g l e c t st h ei n d i v i d u a ld e m a n d sa n dt h en e c e s s i t yo fp r o v i d i n gi n t e l l i g e n ts e r v i c e ， t h eu s e r sw i l la l s of a c em u c hd i m c u l t i e st of i n do u tt h ed e s i r e dw e br e s u l t s c o n s i d e r i n gt h el i m i t a t i o no ft h ee x i s t i n gm e t a s e a r c he n g i n e sa n du s e r s p e r s o n a l i z i n g q u e s t s ，t h e nb a s e do nu s e rp r o f i l e s ，t h i sp a p e rp r o p o s es e v e r a la l g o r i t h m sf o rp e r s o n a l i z e d s e a r c h i t sm a i nr e s e a r c hw o r ki n c l u d e s ： ( 1 ) t h ea r t i c l ea n a l y z e st h em a i na r i t h m e t i co f t h em e t a - s e a r c he n g i n et e c h n o l o g y r 2 ) e x t r a c t e dt h et o p i c so f u s e r si n t e r e s t sa n da n a l y z e dc a t e g o r i e so f u s e ri n t e r e s t s t h e s e c a t e g o r i e sr e p r e s e n tt h eu s e r ss e a r c hi n t e n t i o na n dp r o v i d et h ef o u n d a t i o nf o rs e a r c he n g i n e s s c h e d u l i n ga n d r e s u l t sf i l t r a t i n g ( 3 ) ap e r s o n a l i z e ds c h e d u l i n gs t r a t e g yb a s e do nu s c rp r o f i l e si sd e s i g n e dt os e l e c tm o s t l a t e n t l yu s e f u ls e a r c he n g i n e sf o ru s e rq u e r y ( 4 ) a na l g o r i t h mo f r e s u l t sm e r g i n gb a s e d o nl l s e rp r o f i l e si sp r o p o s e d i nt h ee n d , w ed e s i g na n di m p l e m e n ta l le x p e r i m e n ts y s t e mo fp e r s o n a l i z e dr e c t a - s e a r c h e n g i n e a n do ni tav a r i e t yo fe x p e r i m e n t sh a v eb e e nc a r r i e do u ta n da n a l y z e d a tt h es a m e t i m e s ，w ep r e s e n tf u t u r es e a r c hw o r kf a c i n gu s c i s r e q u i r e m e n t sf o rs e a r c he n g i n e k e yw o r d s ：m e t a - s e a r c he n g i n e ，p e r s o n a l i z i n g , u s e rm o d e l ，s t r a t e g yo fd i s p a t c h i n g ， r e s u l t sm e r g i n g 2 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 五丝鑫一一 bj ： 迎2 ：垒型 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论文的规定，其中包 括：学校有权保管、并向有关部门送交学位论文的原件与复印件； 学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复 制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容 ( 保密学位论文在解密后遵守此规定) 。 签名； 五缝霉 日期： 导师签名：日期： 2 啤牟￥ 叠1 2 垒：兰f 中北大学学位论文 1 1 课题背景 第一章引言 近年来，随着i n t e r n e t 以及相关技术的发展与成熟，人们已经进入了信息量极大丰 富的时代。i n t e m e t 己成为当今世界人们获取所需资源和信息交流的主要场所。网络中 海量信息给人们带来了获取信息的方便，然而浩如烟海的信息内容庞杂，组织松散，又 给人们带来了寻找所需信息的麻烦。人们往往需要耗费大量的宝贵时间，才能找到所需 的有用信息。因此，对于上网查找信息的用户来说，功能更先进、效率更高的信息检索 工具显得极为重要。 然而，任何一个搜索引擎都不可能1 0 0 覆盖网上信息资源，即使一些著名品牌的 搜索引擎的信息覆盖率也很少有超过4 5 ；同时，不同搜索引擎的检索结果的重复率仅 仅在3 0 左右。因而一个搜索引擎通常不能找到用户需要的所有信息，用户在进行检索 时需要在多个搜索引擎之间进行切换，在多个检索结果列表之中挑选对自己有用的内容 0 1 1 2 1 。基于这个原因，一个能集成不同搜索引擎检索结果的检索工具元搜索引擎出 现t 【3 j e 4 j 。 。 元搜索引擎是一种基于搜索引擎的搜索引擎，用于提供与查询需求相关的信息线索 或者全文。元搜索引擎通过自己定制的检索界面，能够同时对多个搜索引擎进行检索， 为用户提供一个统一的查询界面，用户只需提交一次检索请求，由元搜索引擎负责转换 处理后提交给各个独立的搜索引擎，由这些成员搜索引擎完成实际的信息检索，最后将 所有查询结果经过处理后集中起来以统一的格式返回给用户。如i n f o r m a k e t , m e t a c r a w l e r , s a w y s e a r c h , p r o f u s i o n 等。 然而传统i n t e m e t 对于同一用户查询，没有考虑用户的差异，使得不同用户获得的 是同样的搜索结果，显然这种搜索信息的模式已经越来越难以适应迅速增长的i n t e r n e t 信息资源，用户迫切需要一种能够根据用户的特点自动组织和调整信息的搜索模式，这 也是个性化搜索服务应运而生的原因。 个性化信息服务是未来信息服务的主流模式，它实现的是“信息找人，按需服务”。 个性化服务的形式是多种多样的，既可以是向用户推荐页面或新闻的个性化推荐服务， 中北大学学位论文 也可以是在用户检索信息的过程中提供个性化检索结果的个性化检索服务，还可以是减 少用户浏览负担、调整网站显示的个性化网站等。但所有这些不同形式的个性化服务都 首先需要建立对用户的描述，然后才能针对不同的用户提供不同的个性化服务。为用户 建立模型的目的就在于通过对用户信息需求、兴趣爱好和访问历史的收集、统计、分析， 建立一个反映用户基本兴趣和信息需求的信息模型，并将模型用于帮助用户更好地获取 新的信息。 作为个性化服务的基础和核心，用户模型的质量直接关系到个性化服务的质量。只 有在高质量的用户建模的基础上，才能实现个性化服务系统所追求的各种目标。所以， 有必要将建模技术从具体的个性化服务形式中脱离出来作为一项基础技术研究，它能促 进个性化服务的发展，提高个性化服务系统的易用性。 1 2 本课题研究的目的及意义 通过比较当前各类搜索引擎的优势和不足，我们发现，在目前己经存在的搜索引擎 类型中，元搜索引擎的天然优势显然是最突出的。它可以对独立搜索引擎在检索范围上 的局限性作出一定程度的弥补和改善【5 1 1 6 1 。它不仅为那些不得不改变的独立搜索引擎指 了一个发展方向，而且可以在适当数据模型的基础上商效集成它们的功能，提高查全率 ( r e c a l l ) 和查准率( p r e c i s i o n ) 。对用户而言，元搜索引擎可以使用户提交的检索请求一次 性递交给多个独立的搜索引擎进行查找，获得多个独立搜索引擎的检索结果，节省对闻， 提高效率。目前，国外非常重视元搜索引擎的研究和开发，因此，我们也应对这一领域 有充分的重视。我国对于元搜索引擎已有了初步的研究，并且出现了一些元搜索引擎。 但是与国外的元搜索引擎相比，在很多指标上还存在很大的差距，对元搜索引擎进行进 一步的研究，对于优化信息检索结果，具有深远意义【日。 因此，我们立足于提高元搜索引擎的性能，引入个性化概念，选择元搜索引擎为研 究对象，设计出了一个结构更合理，功能更优越，同时能够融合很多相关领域技术，体 现个性化查询的元搜索引擎结构模型，希望能为查询效率更高的检索工具的早日实现作 出贡献。 2 中北大学学位论文 1 3 论文的研究内容 ( 1 ) 分析元搜索引擎实现的主要技术，并选取几个典型的元搜索引擎进行比较，在此 基础上讨论元搜索引擎所面临的问题，提出发展个性化元搜索引擎的必要性。 ( 2 ) 围绕如何建立用户兴趣模型，研究了建立用户兴趣模型的关键技术及方法，包括 特征词提取的方法，用户兴趣表示法，用户兴趣学习法等。然后研究了用户个性化兴趣 模型的体系结构，分析设计各部分的实现算法，包括评定页面的用户兴趣度、页面的分 词、将文本转化为向量空间、进行特征提取、通过用户反馈及观察用户行为，建立和更 新用户模型的算法。 ( 3 ) 研究元搜索引擎的调度策略。对现有的相关研究进行分析比较，提出了基于兴趣 分类采样的成员引擎特征表示法，以此设计出一种基于用户兴趣的个性化调度算法。调 度策略以较小的资源耗费为用户选择适合用户查询的相关成员引擎，体现用户的个性化 搜索。 ( 4 ) 研究元搜索引擎的结果合成。在分析现有合成算法的基础上，提出了基于用户兴 趣的搜索结果过滤算法，此算法通过计算查询结果与用户查询的相似度，结合成员引擎 的表现，为用户提供个性化搜索结果。 ( 5 ) 设计个性化元搜索引擎原型系统并进行实验分析。通过实验和实验数据分析，对 算法进行验证或评价。 本文所研究的内容创新点在于，针对用户所浏览的w e b 页面，分析这些页面与用户 兴趣的相关度，提出了“用户兴趣度”的概念，通过暗地观察用户行为( 如收藏、保存、 打印、浏览时间、拖动滚动条次数等) 分析页面的用户兴趣度。按照用户兴趣度从大到 小降序排列，抽取用户最近感兴趣的页面的关键词，结合用户输入的查询关键词，改变 关键词的权重，逐渐丢弃不能反映用户兴趣的陈旧的词条，达到建立和更新用户兴趣模 型的目的。结合用户兴趣模型改进了成员搜索引擎调度策略及查询结果合成，实现了基 于用户兴趣的个性化调度策略和基于用户兴趣的搜索结果过滤算法。 1 4 论文的结构 第l 章简述了本文的研究背景，通过分析现有传统搜索引擎的发展现状及不足之处， 3 中北大学学位论文 分析了发展个性化元搜索引擎的必要性。 第2 章为整个论文的研究基础，简单介绍了信息检索和搜索引擎的涵义及现状，详 细介绍了元搜索引擎的涵义、特征及其体系结构、实现原理，分析元搜索引擎实现的主 要技术，并选取几个典型的元搜索引擎进行比较，在此基础上讨论元搜索引擎所面临的 问题，提出发展个性化元搜索引擎的必要性，并分析了个性化搜索的现状，说明了建立 用户兴趣模型的必要性。 第3 章是本文研究重点之一，介绍了用户兴趣模型的涵义，研究了建立用户兴趣模 型的关键技术及方法，并通过用户反馈及观察用户行为，建立和更新了用户兴趣模型。 第4 章为改进成员搜索引擎选择策略，分析了成员搜索引擎选择策略的复杂性，从 选择策略的两个部分：成员引擎的特征表示和调度算法，进行了相关研究的分析和比较， 提出了基于用户兴趣的个性化调度算法。 第5 章在分析了结果合成算法的相关研究之后，以前面章节提出的算法为基础，提 出了一种基于用户兴趣的搜索结果过滤算法，它是实现用户个性化搜索的关键之一。 第6 章介绍了整个系统的设计及实现，并通过实验分析验证和评价了本文提出的算 法。 第7 章是对本文工作的总结以及指出了将来进一步的研究方向。 4 中北大学学位论文 2 1 信息检索 2 1 1 信息检索概述 第二章元搜索引擎相关技术综述 信息检索( i n f o r m a t i o nr e t r i e v a l ) 是从结构化的文档集中找出与用户需求相关的信息， 与数据库系统不同，信息检索研究的主要不是结构数据的查询和事务处理的问题，而是 研究大量文本文档的信息组织和检索。它处理的对象是非结构化数据，主要有文本数据 ( 新闻、科技论文等) 、网页、多媒体数据( 图像、视频、图形、音频) 。典型的信息检 索问题是基于用户的输入定位相关的文档，典型的信息检索系统有联机图书馆目录系统 和联机文档管理系统。 信息检索通常是指从以任何方式组成的信息集合中，查找特定用户在特定时间和条 件下所需信息的方法与过程，完整的信息检索含义还包括信息的存储。信息检索的全过 程应包括两个主要的方面： ( 1 ) 信息标引和存储过程对大量无序的信息资源进行标引处理，使之有序化，并 按科学的方法存储，组成检索工具或检索文档，即组织检索系统的过程。 ( 2 ) 信息的需求分析和检索过程分析用户的信息需求，利用己组织好的的检索系 统，按照系统提供的方法与途径检索有关信息，即检索系统的应用过程。 因此，信息检索的实质是将描述特定用户所需信息的提问特征与信息存储的检索标识进 行异同的比较，从中找出与提问特征一致或基本一致的信息。提问特征是对信息的需求 进行分析，从中选择出能代表信息需求的主题词、分类号或其它符号。 2 1 2 信息检索系统分类 i n t e r n c t 上的信息检索系统通常分为两类：基于关键词检索的信息检索系统和基于 目录结构的信息检索系统。 ( 1 ) 基于目录结构的信息检索系统 目录结构的信息检索系统，其典型代表y a h o o ( h t t p ：w w w y a h o o c o m ) ，它通过有专 5 中北大学学位论文 业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，每个目录下都有一 些以该目录为主题的网页。用户进行查找时，可以根据自己要查找的内容主题，按照目 录结构逐步缩小范围。这类通过手工维护得很好的系统的优点是提供的网页准确率高， 可以有效的覆盖所有热门的主题。但它们的缺点是网页分类过于主观，而且需要高昂的 代价来建立和维护，更新改进的慢，同时不能很好的覆盖所有深奥的主题。 ( 2 ) 基于关键词检索的信息检索系统 w e b 上的文档通过超链接互相联系起来，这种链接结构可以看作是一个有向图，每 个文档就是这个图中的一个结点，而一个超链接则是一条有向边。基于这种有向图结构， 人们开发出一种软件来遍历w e b ，循着超链接去访问每个w e b 文档。这种软件就是所 谓的网络爬虫( s p i d e r , c r a w l e r 等) 。这类信息检索系统通过关键词匹配实现查找的自动更 新，涵盖的网页数量巨大，但通常返回太多的低质量相关性不大的结果。 2 1 3w e b 信息检索系统的研究与发展 信息检索技术伴随着w w w 的发展是引人注目的，w e b 信息检索系统大约经历了 三代的更新发展：第一代搜索引擎以人工分类的目录检索为主，如：y a h o o ；第二代搜 索引擎以g o o s e 为代表，以关键字查询为主，在基本解决“查全”的基础上考虑如何 “查准”，采用基于关键词数量评价、基于大众评价和网页重要性等技术来优化搜索结 果。第三代搜索引擎在第二代搜索引擎的基础上，通过先进的文本分析及集合技术来进 一步优化搜索结果，实现了人工智能和搜索引擎技术的结合。把和用户需求有关的内容 提炼并聚类，大大提高了检索速度，同时体现个性化和智能化。目前信息检索技术的发 展有如下趋势： ( 1 ) 自然语言检索 自然语言查询是信息检索系统一种理想的查询说明方式，与人的自然的需求提问方 式一致。采取自然语言查询的思想，就是把用户提交的一段自然语言，去掉非用词，留 下主干词，然后利用这些词进行词组查询或词组近似查询。 ( 2 ) 智能检索或知识检索 传统的全文检索技术基于关键词匹配进行检索，往往存在查不全、查不准、检索质 量不高的现象，特别是在网络信息时代，利用关键词匹配很难满足人们检索的要求。智 6 中北大学学位论文 能检索利用分词词典、同义词典，同音词典改善检索效果。另外，智能检索还包括歧 义信息和检索处理，如“苹果”，究竟是指水果还是电脑品牌，“华人”与“中华人民共 和国”的区分，将通过歧义知识描述库、全文索引、用户检索上下文分析以及用户相关 性反馈等技术结合处理，高效、准确地反馈给用户最需要的信息。知识检索的主要理论 依据是本体论。 ( 3 ) 智能化、个性化方向发展 由于检索返回的结果数据量加大，如何更有效的使用户获得最想要的信息成为人们 研究的热点。人们逐渐把人工智能、数据挖掘等技术引入到信息检索领域，使w e b 搜 索引擎朝着智能化、个性化方向发展。 2 2 搜索引擎技术综述 2 2 1 搜索引擎概述 搜索引擎3 1 是指能够自动地对w w w 资源进行分析处理，并通过查询为用户返回匹 配资源的系统。它一般是h i t c r n c t 上的一个网站，它的主要任务是将互连网资源存储于 可供查询的大型数据库中。当用户输入关键字查询时，搜索引擎依据此关键字在索引数 据库中查找相关信息，若索引数据库中有这方面的信息，则将信息反馈给用户；若没有 则调用搜索方法进行搜索，并在一定时问界限内向用户反馈信息。 2 2 2 搜索引擎的工作机制 从搜索引擎的定义来看，一般搜索引擎主要由网络蜘蛛、索引与检索三大模块构成。 ( 1 ) 网络蜘蛛是一个可以浏览网页的程序，它会定期地自动地在网上漫游，首先 打开一个网页，然后再通过网页上的链接去浏览其他不同的网页，如此往复。对于一些 新出现的网站或在自动搜索中有所遗漏的站点，用户也可以自行向搜索引擎提交网站地 址，使得站点内容能被及时得以搜索。在决定访问链接顺序的过程中，最常见算法有： 深度优先、广度优先、有限深度广度策略。 ( 2 ) 索引网络蜘蛛将遍历得到的页面和地址存放在网页数据库中。为了提高检索 的效率，需要建立索引。索引模块总的来说是通过分析获取的网页，首先排除h t m l 7 中北大学学位论文 等语言的标志符号，将出现的字或词全部抽取出来，然后记录每个字词的出现网址及相 应的位置，最后将结果存入索引数据库。索引数据库实际上就是一个很大的查询表，上 面记录着某个特定字词在互联网上出现的一级位置信息。 对于英文搜索引擎，由于是以单词为语言的基本单位，因此一般建立索引采用的都 是词表法，即首先建立一个词表，然后将对应单词的出现位置记录下来，而检索的时候， 就是以这些词语作为检索入口，并通过位置匹配可以实现多个词语的组合检索。但对于 中文搜索引擎来说，由于语言的基本单位是汉字，在最底层往往采用的是字表法。和词 表法相似，先建立一个汉字字表，然后对于网页中出现的汉字均记录在相应的字表项内， 当检索的时候，采取字索引之间的位置匹配完成词语的检索，为了提高检索速度，一般 还会在字索引的基础上建立一些词索引，有的是根据用户的提问动态生成已检索词的词 索引，有的则是建立一个常用词表，然后生成这些词的索引。另外，无论是中文系统还 是英文系统都还会建立一个停用词表，以提高检索效率。 ( 3 ) 检索该软件用来筛选索引中无数的网页信息，挑出符合查询要求的网页并将 它们分级排序，与查询关键字关联越大的排得越前，然后将分级排序后的结果显示给查 询用户。具体来说，当用户进行检索的时候，一般使用的是纯自然语言词汇或者是自然 语言词汇组成的布尔逻辑式。对于前者，可以直接利用检索算法查询索引数据库中的词 索引，或者是利用单字索引进行位置匹配，以获得检索结果。而对于后者，则首先要分 析检索式的逻辑关系，分别对检索式中的各个检索词进行检索，最后再通过逻辑运算获 得最终结果。由于网络上信息数量非常庞大，可能会产生一个相当大的结果集，那么如 何精简结果以及如何将最重要的结果首先返回用户就显得十分重要。最常用的方法是将 结果按相关度进行排序，把引擎认为最相关的结果放在最前面。相关度计算有很多的算 法，其中一个很重要的算法就是词频法，即通过计算网页中的检索词的出现频率来决定 该网页的相关程度，检索词出现次数越多则说明该网页越重要，虽然这种算法有很多缺 陷，往往不能达到最好的效果，但由于计算网页中一个词的词频十分简单，使得该算法 很容易实现。 2 2 3 搜索引擎的分类 虽然目前对搜索引擎的分类还没有一个共识，但是传统的观点是按照其索引方式可 8 中北大学学位论文 以将搜索引擎分为以下两种大类： 1 目录式搜索引擎 基于目录的搜索引擎主要通过人工发现信息，依靠编目员的知识进行甄别和分类， 对w e b 信息资源建立层次结构的清单表，将收集到的w e b 信息资源分类到某一类中， 每一个分类目录针对一个专题和领域，用户通过一层层的目录逐步缩小查询的范围，直 到发现目标。例如y a h o o ，o p e nd i r e c t o r y ，s n a p 等，都采用这种方式。 基于目录的搜索引擎的特点是具有非常好的信息质量，但由于采用手工进行w e b 页面信息的获取和维护，所以存在以下问题： ( 1 ) 信息覆盖率低，如果查找的信息没有对应的分类项，则无法进行搜索； ( 2 ) 分类是按分类者或分类软件分析而定，不一定与用户的意见一致； ( 3 ) 信息实时更新不及时； ( 4 ) 目录维护耗费大量的人力资源； ( 5 ) 采用漫游查询方式的工作效率不高，并且由于目录查询树结构的不断增大， 查询某一特定主题的代价和时间越来越大； 为了解决基于目录的搜索引擎存在的问题，人们引入了人工智能技术，这样就出现 了基于机器人的搜索引擎。 2 基于机器人的搜索引擎 1 9 9 4 年出现了所谓的r o b o t 或称s p i d e r ，它们的功能是自动在w e b 上按某种策略 进行远程资料的搜索与获取，并生成本地索引。由于不需要人的介入，可以自动地在网 络中穿梭，速度、覆盖面和及时性大大提高。r o b o t 是一种计算机的程序，该程序最重 要的功能是使用索引策略，用题目、u r l 、关键词进行索引，也可以是这几项的某种组 合检索。 基于机器人的搜索引擎由于采用机器人自动漫游w e b 页面，使用全文索引方式， 与基于目录的搜索引擎相比、信息覆盖率高、查询结果丰富，信息更新快，并节约了大 量的人力资源。例如a l t a v i s t a ，h o t b o t ，e x c i t e ，天网等，都采用这种方式，又由于 机器人智能技术的不足，所以存在以下问题： ( 1 ) 信息准确度相对于基于目录的搜索引擎较低； ( 2 ) 网络负载大； 9 中北大学学位论文 除了以上两大类的搜索引擎之外，其它文献中还存在以下几种搜索引擎类型：基于客 户的搜索引擎，分布式搜索引擎，元搜索引擎。 2 2 4 搜索引擎的现状和发展方向 由于不同的搜索引擎的索引数据库不相同，而且采用了不同的索引结构与检索、排 序技术，因此检索效果是不一样的，在一个搜索引擎上找不到的网页可能在另一个搜索 引擎上找到的。通常单个搜索引擎能找到相关信息不超过所有相关信息的一半，用户一 般通过多个搜索引擎进行检索才能比较全面地检索所需的内容，因而对用户来说很不方 便。 搜索引擎存在的不足之处主要是以下几个方面。 ( 1 ) 数据冗余度：搜索引擎主要能过r o b o t 将网页的全部或部分内容下载到自建索引 库中，由于下载到自建索引库中，下载的页面许多是无用或暂时信息，既影响检索速度， 也增加了用户检索负担。 ( 2 ) 检索方式：用户很简单地用关键词或关键词之间的组配来准确地表达真正需要的 信息内容，表达困难导致检索困难。 ( 3 ) 数据覆盖率：每个引擎的覆盖面相当有限。 ( 4 ) 准确率：搜索结果不精确。 以上是目前的传统的搜索引擎面临的主要问题，其它问题还包括索引机器人爬行造 成的网络拥塞、巨大的维护开销、缺乏满足用户个性化查询需求的手段等。 为用户提供更完美的搜索结果不仅仅需要新兴的技术支持，更涉及搜索技术的发展 方向问题。现今搜索引擎的研究方向主要有集中在： ( 1 ) 人机交互接口技术 人机界面技术的不同往往使得搜索引擎表现出不同的特色。当前搜索引擎涉及的人 机界面技术主要有四类：搜索请求提交技术、搜索结构表现技术、搜索向导技术和搜索 行为分析技术。搜索请求提交技术中包括多语言查询技术、编码转换技术、模糊语义查 询、精确语义查询以及采用自然语言的搜索请求提交接口。其中采用自然语言的搜索请 求提交技术的难点包括如何理解自然语言及所代表的实际含义，如何根据问题找出用户 实际想要的内容；如何建立大规模的知识库等。搜索结果表现技术为搜索结果的准确度 1 0 中北大学学位论文 及相关度、搜索结果的母语评价等。搜索向导技术是一种接口技术，通过具有亲和力、 易用型的接1 ：3 ，时刻的帮助来方便用户的搜索。搜索行为分析技术核心是如何跟踪分析 用户的搜索行为，充分利用这些信息来提高用户的搜索效率，其提高搜索效率的主要有： 群体行为分析和个性化搜索。 ( 2 ) 更加智能化的r o b o t 和新的数据库索引技术 传统的r o b o t 都是机械化地按照一定的模式顺序对站点的内容乃至链接进行查找， 未来这项工作一定会朝着更加智能化方向发展，并且可能具有以下一些智能：站点基本信 息的收集的智能化。搜索引擎不必每次更新时都要一个个页面地比较，而是智能地知道 自上次访问后哪些页面己更新，直接收集新的页面：站点数据库建立的智能化。r o b o t 查 找链接和页面时，能够根据用户的访问频度智能化地从用户访问频度高的站点开始查 找，对上升速度和下降速度特别快的还要特别处理。使搜索引擎的数据库内容是用户经 常访问并乐意访问的，使搜索引擎越来越贴近用户。现行的索引技术随着资料量的增大， 其耗费的资源指数速度增长，极大地影响到搜索数据库的容量，可以通过用提高智能化、 分类分库的方式、并行化方式加以解决和改进。 ( 3 ) 集成化搜索引擎的发展方向 目前的大多数搜索引擎都有自身特定的查询范围和对象。有使用频率最高的网页搜 索引擎如g o o g l e ，y a h o o 等，也有面向文件查询的搜索引擎，如天网。还有面向图片多 媒体信息的搜索引擎。当提出多样化的查询请求时，用户不得不在多个搜索引擎之间来 回切换，非常不便。所谓集成化搜索，就是用户在搜索时只需输入一次查询目标，即可 在同一接口得到各种有关联的查询结果。这种搜索可以节省搜索时间，提高搜索效率， 搜索的结果全面、准确。因而集成搜索是搜索引擎发展的一个重要方向，其中多媒体信 息的搜索问题具有很强的挑战性。 以上我们了解了一些新兴技术在搜索引擎中的应用以及搜索引擎的发展趋势和未 来的研究方向。随着搜索技术的不断完善和发展，我们相信未来的搜索引擎一定会朝更 方便易用的人机界面，更准确的搜索结果方向发展。为了弥补或一定程度上解决传统搜 索引擎的不足，元搜索引擎于上世纪9 0 年代末产生了。 中北大学学位论文 2 3 元搜索引擎 2 3 1 元搜索引擎的产生 元搜索引擎( m e t as e a r c he n g i n e ，m s e ) 是指在搜索引擎之后或之上的搜索引擎，是 在搜索引擎的基础上建立起来的可以同时或分时查询多个搜索引擎( 包含普通搜索引擎 如g o o g l e ，i n f o s e e k , e x c i t e ，a l t a v i s t a , y a h o o ! ，h o t b o t ，或其他元搜索引擎，在本文中统 称为成员搜索引擎，c o m p o n e n ts e a r c he n g i n e ，简称为成员引擎) 的网络信息检索系统。 2 3 2 元搜索引擎的基本构成 元搜索引擎主要由三部分组成( 如图2 1 所示) ，即：请求提交代理、检索接口代理、 结果显示代理。“请求提交代理”负责实现用户的“个性化”的设置要求，包括调用哪 些搜索引擎，检索时间限制，结果数量限制等。“检索接口代理”负责将用户的请求“翻 译”成满足不同搜索引擎的“本地化”要求的格式。“结果显示代理”负责所有的元搜 索引擎检索结果的去重、合并、输出处理等。 、卜+ i 请求提交代理i 检索 1 卤 接口 独 代理 立 用 搜 索 结果 引 户 显示 擎 一结果显示定制i 代理 图2 1 元搜索引擎原理图 ( 1 ) 请求提交代理负责将用户的请求发给独立的搜索引擎。 一般的元搜索引擎设定了它所调用的独立搜索引擎，比如w i d e w a y s e a r e h 。有些元 1 2 中北大学学位论文 搜索引擎让用户自己选择所用的搜索引擎。还有一种通过分析用户的兴趣和网络的实际 情况来选择搜索引擎，这有利于提高用户查询的准确度和对用户的响应速度。如何智能 的选择成员搜索引擎是元搜索引擎的一个关键技术。 ( 2 ) 检索接口代理由于不同的搜索引擎所支持的查询方式的不同，比如有些 搜索引擎支持s t c 粕m i n g 方式，即使是同一种方式也有不同的表达方法，所以必须将元 搜索引擎中的查询请求映射到对应的搜索引擎中，而且使得语义信息不丢失。 ( 3 ) 结果显示代理元搜索引擎的结果一般有网页标题，内容摘要，所指向网 页的u r l ，相关度，信息返回时间，所采用的引擎标志等。这些搜索结果是多个独立搜 索引擎的并集。元搜索引擎的结果应该具有多种排序的方式以满足不同的用户的要求。 元搜索引擎常用的排序方式有：相关度排序、时间排序、域名分类排序、搜索引擎排序 等。 2 3 3 元搜索引擎的分类 元搜索引擎根据不同的标准可以划分为不同的类型。根据检索机制可以划分为集中 罗列式元搜索引擎和统一入口式元搜索引擎例，以下对这两种类型的元搜索引擎作详细 介绍。 集中罗列式元搜索引擎集中罗列式元搜索引擎按照一定的形式将所有的独立搜 索引擎集中呈现在页面上，并提供了一个公共的检索入口，但实际上用户一次只进入一 个独立搜索引擎。这种类型的元搜索引擎的结果反馈页面多直接引用原始搜索引擎的结 果页面。从表面上看，这类元搜索引擎与独立搜索引擎具有更多的相似点，它们的特点 是： ( 1 ) 一次检索一个搜索引擎； ( 2 ) 检索结果直接调用原始独立搜索引擎的结果页面； ( 3 ) 只支持原始独立搜索引擎支持的检索语法； 统一入口式元搜索引擎统一入口式元搜索引擎为收录的独立搜索引擎建立了一 个公共查询入口，用户发出检索请求后，提问表达式被分别提交给多个独立搜索引擎， 最终反馈的结果是多个独立搜索引擎查询结果的融合。根据结果显示的不同，这类元搜 索引擎又可以分为直接调用原始页面型、混合综合型和分散综合型。 1 3 中北大学学位论文 ( 1 ) 直接调用原始页面型元搜索引擎，检索结果直接来自原始搜索引擎站点的结果页 面。 ( 2 ) 混合综合型元搜索引擎，将各个独立搜索引擎中查找的结果进行融合，结果显示 以记录为单位，记录描述包括该记录被检出的来源。 ( 3 ) 分散综合型元搜索引擎，这种类型与混合综合型元搜索引擎在结果显示上有所不 同，它以独立搜索引擎为单位进行结果显示，在同一个独立搜索引擎得到的结果被集中 列在该搜索引擎之下。 2 3 4 元搜索引擎的评价指标 由于元搜索引擎之间的个体差异性很大，很难进行精确的对比i 埘。但是作为一种搜 索引擎，元搜索引擎也有搜索引擎的一些基本指标，如查全率、查准率、召回率、响应 速度、响应时间、用户负担等 1 l 】。元搜索引擎性能评价指标体系主要包含五个部分： ( 1 ) 是否提供足够的检索选项。包括是否提供高级检索服务，是否可以限定最长 检索时间，是否可以设置每个搜索引擎返回的结果数量，是否可以设置每页显示的结果 数目，是否可以设置标题大小和摘要大小等。检索选项越多，用户使用的时候就越灵活。 这也是衡量一个元搜索引擎性能的一个标准。但是由于元搜索引擎的检索特性向它所调 用的独立搜索引擎检索特性的转换所具有的复杂性，许多元搜索引擎不提供复杂的检索 特性。 ( 2 ) 对网络资源的覆盖类型。是否可提供主题范畴的目录服务索引擎，除了独立 搜索引擎数据库外，还可以选择搜索u s c n e t ，m p 3 文件、图像文件、声音文件等类型的 其他网上资源，并提供基于主题范畴的目录检索服务。有些元搜索引擎的主页还提供了 频道服务、专用搜索引擎导航服务等。 ( 3 ) 成员搜索引擎的选择策略。有些元搜索引擎固定地调用几个独立搜索引擎， 用户不能修改。有些元搜索引擎的高级特性中让用户选择调用哪些搜索引擎。这两种策 略都有不足之处，前一种将跟不上搜索引擎的发展潮流。后一种，对于不熟悉搜索引擎 的用户来说可能选择不到适合自己需要的搜索引擎。文献1 2 中提出了通过遗传算法实现 独立搜索引擎的自动调度方法。这种算法如能融入到元搜索引擎系统中，必会大大提高 系统的查准率。 1 4 中北大学学位论文 ( 4 ) 对搜索结果的处理能力。对独立搜索引擎返回的搜索结果的处理能力，这也是评 价元搜索引擎性能的又一重要指标【1 3 】。它包括结果的处理和结果的显示。不同的元搜索 引擎提供不同的结果显示方式。如按照时间、按照搜索引擎、按照相关度等来排序。相 比之下按照相关度来显示搜索结果更合理一些。 ( 5 ) 相关度评价。每个搜索引擎开发商为了将最满意的结果放到越前面，不遗余力地 创建出各种相关度指标体系，虽然没有一种方法是完美的，但都有创新和独到之处。面 对这些众多的相关度评价指标，按照怎样的方式对成员搜索引擎返回的结果进行一致性 的排序是元搜索引擎结果处理部分面临的主要问题。 2 3 5 元搜索引擎的发展现状 元搜索引擎集成多个独立搜索引擎，大大提高了检索覆盖面，对于专业性不太强， 甚至比较含混的查询往往能够返回非常全面的结果，其本身因为扩大了检索面，所以从 一定程度讲，检索的准确性也会得到提高。 国外的元搜索引擎的发展速度很快，目前网络中已经有上百个元搜索引擎，其中不 乏有很多优秀的元搜索引擎，如m a m m a , m e t a c r a w l e r , s a v v y s e a r c h , d o g p i l e ，p r o