（计算机应用技术专业论文）基于查询扩展的主题爬虫研究.pdf

摘要 摘要 随着信息多元化的增长，通用搜索引擎已经不能满足人们对个性化信息检 索服务日益增长的需要，用户对信息的需求更多的是针对受限领域和面向特定 主题的。应对这种需求，需要分类精确、数据全面、更新及时的面向主题的搜 索，主题爬虫就是主题搜索引擎的基础与核心。其基本思想是在爬行过程中按 预先定义好的主题有选择的收集相关网页，即先确定搜索范围，再找到最相关 的链接，避免下载不相关的网页。因而如何为领域、主题相关性的判定制定准 确的规则；如何利用丰富的上下文，理解用户的输入语义，并能返回准确的信 息，成为主题爬虫系统的研究重点。 本文的研究内容主要包括： 首先，在分析现有主题爬虫搜索策略的优缺点的基础上，改进了主题爬虫 系统的框架，并给出工作原理。 然后，建立基于词语共现的查询扩展算法，设计具有语义理解能力的主题 爬虫。 接下来，改进现有的p a g e r a n k 算法，将主题相关度的分析与排序算法结合 起来，提出了主题敏感的f d c p a g e r a n k 算法计算网页优先级，实现从语义上 分析的综合排序方法，提高主题爬虫爬行的精度。 最后，设计实现了实验原型系统f t s c r a w l e r ，通过在互联网上进行实验， 检验了f t s c r a w l e r 的运行效果，并由此验证了本文所提出的基于词语共现的主 题算法和主题敏感的f d c p a g e r a n k 算法的有效性。 关键词主题爬虫；共现词；查询扩展； f d c _ t o p i cs e n s i t i v ep a g e r a n k 算法 a b s 仃a c t i_ a b s t r a c t w i t ht h ei n c r e m e n to fi n f o r m a t i o no nt h ew e b ，g e n e r a ls e a r c he n g i n ec a n n o t s a t i s f yt h ed e s i r eo fp e r s o n a li n f o r m a t i o nr e t r i e v a l r e c e n t l y , t h el i m i t e da r e aa n d s p e c i a lt o p i ca r em o r ec o n c e m e db yu s e r s t h ea p p l i c a t i o no ft h ef o c u s e ds e a r c h e n g i n et e c h n o l o g yc a l ls o l v et h i sp r o b l e mc o m m e n d a b l y f o c u s e ds e a r c he n g i n ei s s p e c i a l i z e ds e a r c he n g i n e i to n l yf a c e so n ef i e l d o ro n et o p i c c o m p a r i n gw i t h c o m m o ns e a r c he n g i n e ，f o c u s e ds e a r c he n g i n eh a st h em e r i to fc o l l e c t i o nd o m a i n i n f o r m a t i o ne x a c t l y , c o v e t i n gt h ef i e l da r e ab e t t e r t h ec o r eo ft h ef o c u s e ds e a r c h e n g i n ei st h ec r a w l e r t h em a i n i d e ai sc o l l e c tw e bp a g e so nap r e d e f i n e dt o p i c s e l e c t i v e l ya n da v o i dt od o w n l o a d i n gi r r e l a t i v ew e bp a g e si no r d e rt of i n dm o r e a c c u r a t ea n du s e f u li n f o r m a t i o nf o rt h eu s e r t h e ya r et h ek e y s t o n e so ft h et o p i c c r a w l e rs y s t e mt om a k et h er i g h tr u l ew h i c hj u d g e st h er e l a t i o n ，t o u s et h e e n v i r o n m e n t ，a n dt ou n d e r s t a n dt h eu s e rs e m a n t i cm e a n i n g t h em a i n w o r ko f t h ed i s s e r t a t i o ni sj u s tl i k ef o l l o w s ： f i r s t l y , s t u d yt h ec r a w l e rs e a r c ha l g o r i t h m ，i m p r o v et h ef r a m eo ft o p i cc r a w l e r s y s t e ma n ds u m m a r i z e dt h et h e o r yo f i t sw o r k s e c o n d l y , d e s i g naq u e r ye x p a n s i o nm o d e lw h i c hu t i l i z e d t h ec o o c c u r r e n c e i n f o r m a t i o na n dt o p i cc r a w l e rw h i c hh a v es e m a n t i cu p s t a n d i n ga b i l i t y t h i r d l y , t o p i cs e n s i t i v ef d c p a g e r a n kt op r e d i c tt h ep r i o r i t y o fw e bp a g ei s d e s i g n e da n di m p l e m e n t e d l a s t ，t h ed e s i g na n di m p l e m e n tf t s c r a w l e r , t h ee x p e r i m e n t s s h o wo u rs y s t e m p e r f o r mw e l l k e y w o r d st o p i cc r a w l e r ；c o o c c u r r e n c ew o r d s ；f d c _ t o p i cs e n c i t i v ep a g e r a n k ； q u e r ye x p a n s i o n i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：丽毒签名：朔伶 日期：丝! ：挈 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此 日期：趟t ! ! ：二z 第1 章绪论 第1 章绪论 1 1 研究背景和意义 随着i n t e m e t 的高速发展，互联网上的信息呈指数级增长。目前，世界上绝 大多数国家和地区已经开通了i n t e r n e t ，它已成为在全球范围内传播和交流科技 信息、教育信息、商业和社会信息的最主要的渠道，成为人们工作、学习和生 活中不可缺少的信息获取工具。 w e b ( 全称万维网，w w w - w o r l dw i d ew e b ) 服务是目前应用最为广泛的 i n t e m e t 服务，它能够在i n t e m e t 上方便快捷的浏览和传递分布于网络各处的文 字、图像、声音和超文本信息。这些信息主要以h t m l 语言编写的文本，分布 在世界各地的w e b 服务器上，通过超链接将它们联系起来。 w e b 在中国的发展速度十分惊人。根据c n n i c ( 中国互联网络信息中心) 中国互联网络发展状况统计报告显示，中国网民规模继续呈现持续快速发展的 趋势。截至2 0 0 8 年6 月底，中国网民数量达到2 5 3 亿，网民规模跃居世界第 一位。比去年同期增长了9 1 0 0 万人，同比增长5 6 2 。在2 0 0 8 年上半年，中 国网民数量净增量为4 3 0 0 万人，网站总数达到了1 9 1 9 万个。而搜索引擎是网 民在互联网中获取所需信息的重要工具，是互联网中的应用基础。目前搜索引 擎的使用率为6 9 2 ，2 0 0 8 年上半年搜索引擎用户增长了2 3 0 4 万人，半年增长 率达到1 5 。5 ，搜索引擎用户量持续增长。 传统的通用搜索引擎如a l t a v i s t a 、g o o g l e 、y a h o o 等，作为一个辅助人们检 索信息的工具【1 成为用户访问万维网的入口和指南。但是，随着使用的深入， 这些通用性搜索引擎越发显示其不足： ( 1 ) 不同领域、不同背景的用户往往具有不同的检索目的和需求，通用搜 索引擎所返回的结果包含大量用户不关心的网页。 ( 2 ) 通用搜索引擎的目标是尽可能大的网络覆盖率，有限的搜索引擎服务 器资源与无限的网络数据资源之间的矛盾将进一步加深。 ( 3 ) 万维网数据形式的丰富和网络技术的不断发展，图片、数据库、音频 视频多媒体等不同数据大量出现，通用搜索引擎往往对这些信息含量密集且具 有一定结构的数据无能为力，不能很好的发现和获取。 ( 4 ) 通用搜索引擎大多提供基于关键字的检索，而用户很难简单的用关键 字来表达所需搜索的内容，表达的困难导致检索结果的不理想。 为了解决这些问题，w e b 领域中的研究者提出了主题搜索引擎的技术。主 题搜索引擎是一种只提供关于某一主题或者领域的网页信息的搜索引擎。主题 北京工业大学工学硕士学位论文 爬虫是主题搜索引擎的最重要的组成部分。由于主题爬虫根据既定的抓取目 标，有选择的访问万维网上的网页和相关链接，因而对目标主题来说它就可以 搜集到更丰富、相关性更高的页面，提高信息检索的查全率和查准率。同时由 于只搜索主题相关页面，一定程度上缓解了有限的搜索引擎服务器资源与无限 的网络数据资源之间的矛盾。另外，主题爬虫的目标主题可以更灵活的表示： 用户除了可以用关键字来表示目标主题外，还可以用过样本网页主题层次目录 等来表示其搜索要求【2 ，3 j 。这样，主题爬虫通过学习可以更准确的获取用户的检 索要求，同时用户使用起来也更加方便灵活，提高信息检索的效率。 同样，它也面临着诸多挑战：如何提高主题爬虫获取主题信息的质量，以 及如何在给定用户查询的情况下，返回与用户查询更相关的结果，是一个极有 意义的研究课题，我们有必要对主题爬虫进行深入的研究。 1 2 国内外研究现状 搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明的 a r c h i e 。虽然当时w o r l dw i d ew e b 还未出现，但网络中文件传输还是相当频繁 的，而且由于大量的文件散布在各个分散的f t p 主机中，查询起来非常不便， 因此a l a ne m t a g e 想到了开发一个可以以文件名查找文件的系统，于是便有了 a r c h i e 。a r c h i e 工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动 搜索网上的文件，然后对有关信息进行检索，供使用者以一定的表达式查询。 由于a r c h i e 深受用户欢迎，受其启发，美国内华达s y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除 了索引文件外，已能检索网页。 当时，“机器人 一词在编程者中十分流行。电脑“机器人”是指某个能以 人类无法达到的速度不间断的执行某项任务的软件程序。由于专门用于检索信 息的“机器人”程序像蜘蛛一样在网络爬来爬去，因此，搜索引擎的“机器 人”程序就被称为“蜘蛛”程序。世界上第一个用于监测互联网发展规模的 “机器人”程序是m a t t e wg r a y 开发的w o r l dw i d ew e bw a n d e r e r 。刚开始它只 用来统计互联网上的服务器数量，后来则发展为能够检索网站域名。与 w a n d e r e r 相对应，m a r t i nk o s t e r 于1 9 9 3 年1 0 月创建了a l i w e b ，它是a r c h i e 的h t t p 版本。a l i w e b 不使用“机器人”程序，而是靠网站主动提交信息来 建立自己的链接索引，类似于现在我们熟知的y a h o o 。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因 此，在m a t t h e wg r a y 的w a n d e r e r 基础上，对传统的“蜘蛛”程序工作原理作 了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那么从跟 踪一个网站的链接开始，就有可能检索整个互联网。到1 9 9 3 年底，一些基于此 第1 章绪论 曼! 曼! ! 苎曼曼! ! ! ! 曼! 曼! ! ! ! 曼! 皇! 曼! 皇! 曼! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 曼! ! ! ! ! ! 曼! ! 曼舅i _ ：i 寰! 曼! 曼! 鼍曼! 曼! 曼! 曼曼 原理的搜索引擎开始纷纷涌现，其中以j u m p s t a t i o n 、t h ew o r l dw i d ew 曲w o r m ， 和r e p o s i t o r y b a s e ds o f t w a r ee n g i n e e r i n g ( r b s e ) s p i d e r 最负盛名。然而 j u m p s t a t i o n 和w w ww o r m 只是以搜索工具在数据库中找到匹配信息的先后次 序排列搜索结果，因此毫无信息关联度可言。而r b s e 是第一个在搜索结果排 列中引入关键字串匹配程度概念的引擎。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时m i c h a e lm a u l d i n 将 j o h nl e a v i t t 的蜘蛛程序接入到索引程序中，创建了大家现在熟知的l y c o s 。同 年4 月，斯坦福大学的两名博士生，d a v i df i l o 和美籍华人杨致远共同创办了超 级目录索引y a h o o ，并成功的使搜索引擎的概念深入人心。这类搜索引擎一般 设计为综合性的门户网站，提供的服务种类多，内容广泛，设计的领域广，通 过分级目录浏览和关键词检索查找信息。因其提供的是免费的大众化的综合性 信息服务，所涉及的范围广泛而不深入，故被称为水平型门户网站。当时的搜 引擎数据库容量小，查询算法简单，效率不高。但是，它改变了传统的检索方 式，给用户带来了新鲜感，同时对网络的发展起到了极大的促进作用。 大约在1 9 9 6 年出现的第二代搜索引擎系统大多采用分布式方案( 多个微型 计算机协同工作) 来提高数据规模、响应速度和用户数量，它们一般都保持一 个大约5 0 ，0 0 0 ，0 0 0 网页的数据库，每天能够响应1 0 ，0 0 0 ，0 0 0 次用户检索 请求。1 9 9 7 年1 1 月，当时最先进的几个搜索引擎号称能建立从2 0 ，0 0 0 ，0 0 0 到1 0 0 ，0 0 0 ，0 0 0 的网页索引。a l t a v i s t a 搜索引擎声称他们每天要承受2 0 ， 0 0 0 ，0 0 0 次查询。中文搜索引擎虽然发展较晚，但是经常使用的搜索引擎的网 页数量也都在十万以上。然后匹配算法简单，用户满意度低。 自1 9 9 8 年起到现在，出现了一个搜索引擎空前繁荣的时期，一般称这一时 期的搜索引擎为第三代搜索引擎。以g o o g l e 和百度为代表的第三代搜索引擎具 有如下几个特点【训。 1 索引数据库的规模持续增大，一般的商业搜索引擎都保持在几亿甚至上 百亿张网页。 2 除一般意义上的搜索外，开始出现主题搜索、元搜索和地域搜索，很多 小型的垂直门户网站即特定领域的门户网站开始使用该技术。 3 在检索内容方面，不仅能够检索静态网页，而且能够检索动态网页以及 d o c 、x l s 、p p t 、p d f , 等多种格式文档：并开始使用自动文类技术来组织网页。 4 检索结果相关度评价成为研究的焦点。其中最著名的超链接分析技术， 在这方面s t a n f o r d 大学的g o o g b 系统【5 j 和i b m 的c l e v e r 系统在此方面作出了 很大的贡献。 5 朝着智能化、个性化方向发展。随着海量信息检索技术的发展，基于搜 索的应用越来越广泛。各大商业搜索引擎纷纷推出音乐搜索，图片搜索，电影 3 北京工业大学工学硕士学位论文 搜索，新闻搜索以及硬盘搜索等。人们逐渐把人工智能、数据挖掘等技术引入 到信息检索领域，使i n t e m e t 上的搜索引擎朝着智能化、个性化的方向发展。 1 3 本论文的研究工作 本文在完成研究课题和撰写论文的过程中所做的主要工作是： 首先，在分析现有主题爬虫搜索策略的优缺点的基础上，改进了主题爬虫 系统的框架，并给出工作原理。 其次，建立基于词语共现的主题算法，设计了具有语义理解能力的主题爬 虫。实验证明可以很好的理解用户的输入，提高返回信息的准确性。 再次，改进现有的p a g e r a n k 算法，将主题相关度的分析与排序算法结合起 来，提出主题敏感的f d c p a g e r a n k 算法计算网页优先级，实现从语义上分析 的综合排序方法，提高主题爬虫爬行的精度。 最后，设计实现了实验原型系统f d c c r a w l e r ，通过在互联网上进行实验， 检验了f d c c r a w l e r 的运行效果，并由此验证了本文所提出的基于词语共现的 主题算法和主题敏感的f d c p a g e r a n k 算法的有效性。 1 4 本论文的组织 本文论文安排如下： 第一章为引言，介绍了论文研究的背景和意义，概述了当前搜索引擎技术 发展情况，国内外研究现状，并介绍了本论文的研究内容。 第二章相关理论与技术部分主要介绍了搜索引擎的概念、分类、体系结 构，重点讨论了信息检索模块。 第三章讨论了通用网络爬虫系统的工作原理及体系结构。在此基础上进一 步阐述了主题爬虫系统的主要工作原理并且分析了各种主题爬行策略的优缺 点。 第四章是本论文的重点。主要介绍了设计基于查询主题爬虫系统的关键技 术，包括w e b 页面的采集、页面预处理，基于共现词的语义查询扩展算法、 f d c t o p i cs e n s i t i v ep a g e r a n k 算法。 第五章基于查询扩张的主题爬虫系统的实现部分描述主要的c + + 类和数据 结构，并给出了页面预处理算法的实现。 第六章总结与展望部分对论文所做工作进行了总结，并对主题爬虫系统需 要改进或进一步研究的问题作了阐述和展望。 第2 章搜索引擎基础 第2 章搜索引擎基础 2 1 搜索引擎的概念 搜索引擎一般指的是一种在w e b 上应用的软件系统，它以一定的策略在 w e b 上搜集和发现信息，在对信息进行处理和组织后，为用户提供w e b 信息查 询服务 6 】。从使用者的角度看，这种软件提供一个网页界面，让它通过浏览器 提交一个词语或短语，然后很快返回一个可能和用户输入内容相关的信息列 表。这个列表中的每一个条目代表一篇网页，至少包括3 个元素： 标题：以某种方式得到的网页内容的标准。最简单的方式就是从网页的 标签中提取的内容。 u r l ：该网页对应的“访问地址”。有经验的w e b 用户常常可以通过这个元 素对网页内容的权威性进行判断，例如：h t t p ：w w w x i n h u a n e t c o m 上面的内容 通常就比其他一些网站上的信息更权威一些。 摘要：以某种方式得到的网页内容的摘要。最简单的一种方式就是将网页 内容的头若干字节( 例如5 1 2 字节) 截取下来作为摘要。当然还有其它的一些 更复杂更适中的方式。 搜索引擎提供信息查询服务的时候，它面对的只是查询词，而有不同背景 的人可能提交相同的查询，关心的是和这个查询词相关的不同方面的信息，但 搜索引擎通常不知道用户背景的，因此搜索引擎既要争取不漏掉任何相关的信 息，还要争取将那些“最可能被关心”的信息排在列表的前面。这也是对搜索 引擎的根本要求。 2 2 搜索引擎分类 目前，网络上使用的搜索引擎很多，像a l t a v i s t a 、i n f o s e e k 、y a h o o 等都是 网络上非常著名的搜索引擎，它们所采用的技术和实现方法各有其特点。为了 明确研究方向，研究者们往往根据所采用的技术手段和研究范围的不同，对搜 索引擎进行分类。目前使用最多的是两种分类方式。 按照信息搜索方法和查询方式的不同，通常将搜索引擎分为三大类：基于 网络爬虫的搜索引擎、目录式搜索引擎和元搜索引擎，分别介绍如下： 1 基于网络爬虫的搜索引擎 基于网络爬虫的搜索引擎也叫全文搜索引擎或网页搜索引擎，采用关键词 检索的方式。它将w e b 看作一个大规模的全文数据库。在其中，一张网页对应 多个关键词。然后采用关键词匹配进行信息检索。它通常由网络蜘蛛s p i d e r 北京 业大学工学硕士学位论文 ( 也叫r o b o t ，c r a w l e r ) 提取网页信息，加以处理后入库。用户搜索使用时， 只需输入关键词即可，搜索引擎检索网页数据库后返回查询结果。结果中包含 w e b 页面标题和u r l 信息，同时根据相关性进行降序排列，以便用户选择。 由于基于网络爬虫的搜索引擎的优点是信息量大、更新及时、不需人工干 预。从理论上讲，如果某网页中出现了用户的查询关键字，那么就将这一网页 列入搜索引擎结果，并将其返回给用户。其服务方式是面向网页的全文检索服 务。虽然全文检索技术在w e b 搜索引擎中取得了辉煌的成绩，但此类系统返回 给用户的信息过多，而且可能有许多无关信息。 此外，与查询关键词相关的两个问题【7 1 。一是“忠实表达 问题：在很多 情况下，用户的需求很难简单的用关键词串来表达，表达的困难导致了检索的 困难。二是“表达差异”问题：同一概念可能使用不同的检索词来表示。因此 对同一概念的检索，不同的用户可能使用不同的关键词来查询，例如：“计算 机”和“电脑”表达的是同一个意思。此外，这类搜索引擎还存在着词汇的歧 义问题，即同一词汇往往包含多个意思，被使用于不同的场合。以上所述，即 是全文检索技术的一些缺陷。 2 目录式搜索引擎 目录式搜索引擎【8 】，也叫分类式搜索引擎。这类搜索引擎提供了一份按类 别编排号的互联网网址目录，在各类目录下排列着属于该类网站站名和u r l 信 息。它并不收录网页的全部内容，其数据库是依靠专职编辑或志愿人员建立起 来的。这些编辑人员在访问了某个w e b 网站后撰写一段对该网站的描述，并根 据网站的内容和性质将其归为一个预先分好的类别，把网站的u r l 和对网站的 描述放在这个类别中，从而形成分类目录。每个目录下面还有更具体的子目 录。信息的类别也由大n d , 、由粗到细，整个搜索引擎形成一个层次型的类别 目录。用户可以按分类目录逐层检索，一级一级地向下访问，直至找到自己感 兴趣的网站。如y a h o o ，搜狐，网易等。 以中文雅虎( y a h o o ) 为例【9 j 。它有1 4 个一级目录，最深有6 级子目录， 用户得到的是以手工方式录入得到的w e b 页面摘要信息，而非全文内容信息。 y a h o o 给用户提供了两种查询方式【lo j ：浏览目录查询和关键词自动搜索。需要 注意的是，分类目录的关键词查询智能在目录名、网站的名称、网址、简介等 内容中进行，它的查询结果也只是被收录网站首页的u r l 地址，而不是具体的 网页。不过，由于只在网站的描述中进行搜索，因此网站本身的动态变化不会 反映到搜索结果中来，这也是目录型搜索引擎与基于网络爬虫的搜索引擎之间 的一大区别。 由于采用人工的方式对w e b 页面信息进行获取和维护，目录式搜素引擎的 突出特点是具有比较好的信息质量，但同时它也存在以下几点不足： 第2 章搜索引擎基础 曼曼曼皇i i i i；o 曼! ! 曼皇! 曼曼 ( 1 ) 随着w e b 信息量急剧增加，需要更多的人力来收集、组织信息，人工 维护代价大。 ( 2 ) 对主题进行分类具有很大的模糊性和主观性，对使用者来说，有时并不 知道所需信息属于哪一些类别。 ( 3 ) 分类很难将一些偏僻领域覆盖进去，包括的内容不全，难以全面反映 w e b 上的信息。 要解决第一个问题，一般采用网页的自动分类技术、网页摘要自动生产技 术等来辅助人工搜集信息。第二个缺点则可以采用个性化等方法来弥补。第三 个问题的解决方法可以借鉴爬虫技术，主动发现新的网页，使得信息的及时性 得到加强。 3 元搜索引擎 也称多元搜索引擎。它通过一个统一的用户界面，帮助用户在多个独立搜 索引擎中挑选并利用其中若干个合适的搜索引擎来实现检索操作，是对分布于 网络的多种检索工具的全局控制机制。元搜索引擎不需要网络蜘蛛遍历i n t e m e t 提取信息，也不需要维护页面索引数据库。主要特点为：当用户查询一个关键 词时，它把用户的查询请求转换成其它独立搜索引擎能够接受的命令格式，并 行地访问数个独立搜索引擎来查询这个关键词，并把这些独立搜索引擎返回的 结果经过处理后再返回给用户。总之，元搜索引擎是对多个独立搜索引擎的整 合、调用、控制和优化利用。典型的代表是m e t a c r a w l e r ，s a v y s e a r c h 等。 由于元搜索引擎灵活的选择性，能较好的将多个独立搜索引擎为己所用， 因此它既能充分发挥各个独立搜索引擎在某个搜索领域的特长和优势，同时又 能弥补各个独立搜索引擎信息覆盖面的不足，从而在一定程度上保证了搜索结 果的权威性和可靠性。当然，元搜索引擎也有其局限性：1 ) 大多数的元搜索引 擎都只能调用少数几个主要的独立搜索引擎如g o o g l e ，a l t a v i s t a ，i n f o s e e k 等，即使可以由用户灵活选择，但选项有限；2 ) 由于所调用的各个独立搜索引 擎在索引方法和相似度等各方面的差异，对所有独立搜索引擎返回的结果还不 能很好的进行排序；3 ) 为了保证系统运行的效率，大多数元搜索引擎只取每个 独立搜索引擎返回的前若干个搜索结果，这就必然影响到搜索结果的全面性。 按照检索内容及服务对象的不同，可以将搜素引擎分为：综合搜索引擎、 主题搜索引擎、专门用途的搜索引擎。 1 综合搜索引擎 综合搜索引擎向全体i n t e m e t 用户提供服务，以不同主题和类型( 网页、新 闻组、f t p 、g o p h e r ) 的资源为搜索对象，将各种主题与类型的信息按一定的 方式进行组织，因此其信息覆盖范围广，人们可利用它们检索几乎任何方面的 资源。目前大部分商业搜索引擎都是综合搜索引擎，它们的数据库容量非常 北京t 业大学工学硕士学位论文 大，搜集了各行业、各学科数以万计的网页。 2 主题搜索引擎 主题搜索引擎专门收集某一学科、某一个主题、某一行业范围内的信息资 源，并用更为详细和专业的方法对信息资源进行标引和描述，且往往在信息组 织时设计利用与该专业密切相关的方法和技术。其典型代表有h e a l t h c a t e 、 m e d i c a lw o r l ds e a r c h 等。 3 专门用途的搜索引擎 这种类型的搜索引擎专门收集某一类型的信息和资源供用户检索。例如查 询地图的b a i d u 地图；专门收录新闻信息i 拘d e j a n e w s ；专门收录各种域名的 c h e c kd o m a i n ，利用它可以搜索世界大多数国家的域名注册情况。 除了上述的搜索引擎，还有f t p 搜索引擎、p 2 p 搜索引擎、桌面搜索引擎等。 2 3 搜索引擎的基本工作原理 当今搜索引擎的主流是基于网络爬虫( c r a w l e r ) 的网页搜索系统，搜索引 擎的基本工作原理，可以看作三步：从互联网上抓取网页j 建立索引数据库专 在索引数据库中搜索排序，如图2 1 。 其基本工作原理如下所示： ( 1 ) 从互联网上抓取网页。利用能够自动收集网页的网络爬虫，自动访问 w e b ，并沿着网页中的所有u r l 获取其他网页，重复该过程直到达到事先设定 的条件为止。 在i n t e m e t 中，信息是使用h t m l 语言描述的，不同的h t m l 页面通过 其中所包含的超级链接相互联接，这些超级联接是以u r l ( u n i f o r mr e s o u r c e l o c a t o r ) 的方式被表示出来的。c r a w l e r ( 也称s p i d e r 或r o b o t ) 1 1 】采用一定的 策略( 如广度优先，或深度优先等) 对w e b 进行遍历并下载文档，系统中维护 一个超链接队列( 或者堆栈) ，其中包括一些起始u r l 。这些起始的u r l 通常 选取一些质量较高、含有较多超链接的门户网站，如：新浪、搜索、雅虎等。 c r a w l e r 从这些u r l 出发，下载相应的页面，并从中抽取出新的超链接加入到 队列( 或者堆栈) 中。上述过程不断重复直到队列( 或者堆栈) 为空【1 2 。为了 提高效率，搜索引擎中可设置多个c r a w l e r s 进程同时遍历不同的w e b 子空间。 c r a w l e r 在进行网页搜集的时候遵循一定的协议。对于那些不允许被访问的网 页，c r a w l e r 将不涉及。 第2 章搜索弓【擎基础 皇曼! ! 曼曼苎! 曼! 曼! i 一 _i i i_ 一ii ：i i i ! 曼曼曼! ! ! 鼍 图2 - 1 搜索引擎系统结构 f i g2 - 1t h ef r a m eo f s e a r c he n g i n es y s t c m ( 2 ) 建立索引数据库。由索引系统程序对收集回来的网页进行分析，提取 相关网页信息( 包括网页所在u r l 、t i t l e 域、编码类型、网页内容包含的关键 词、关键词位置、生成时间、大小、与其它网页的链接关心等) ，然后用这些相 关信息建立网页索引数据库。 分析程序通过一些特殊算法，从c r a w l e r 抓取的网页源文件中抽取主题 词，并对其赋予不同权值，以表明这些主题词同网页内容的相关程度，以判断 网页内容【1 3 1 。如一个文章的题目往往能够概括文章的核心内容，它必然会被赋 予一个较高的值。同时，分析程序还将此网页中的超链接提取出来，返回给搜 集程序，以便c r a w l e r 进一步深入搜集信息。 ( 3 ) 在索引数据库中搜索并将返回结果排序显示。 在用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合 该关键词的所有相关网页。根据一定的相关度算法计算返回的结果网页与查询 的相关度、索引词的词频等。相关度越高，排名越靠前。最后，由网页生成系 统将搜索结果的链接地址和网页内容摘要等内容组织起来返回给用户。 北京工业大学工学硕士学位论文 2 4 信息检索模型 信息检索的核心就是判断待检索内容与用户所要求的查询式相关与否的问 题，通常通过一个相关性评价的算法来实现。这个算法一般都会把文章按照一 定的顺序排列起来。信息检索分为狭义和广义两类。狭义的信息检索仅仅指从 数据库中提取出与查询内容相关的信息。广义的信息检索包括了对信息进行标 引存储以及对信息进行查找两个过程。 信息检索技术发展的过程中，出现了多种检索策略【1 4 】，如布尔检索( b o o l e a n r e t r i e v a l ) ”】、向量空间模型( v e c t o rs p a c em o d e l ，简称v s m ) t 1 6 1 、潜在语义检索 ( l a t e n ts e m a n t i ci n d e x i n g ) 17 1 、概念检索( p r o b a b i l i s t i cr e t r i e v a l ) t 18 1 、推理网络 ( i n f e r e n c en e t w o r k s ) t 1 9 】、神经网络( n e u r a ln e t w o r k s ) e 2 0 1 、遗传算法( g e n e t i c a l g o r i t h m s ) 2 1 1 、模糊集检索( f u z z ys e tr e t r i e v a l ) 【捌以及基于概念的检索等。不 同的检索模型提供了不同的数据表示形式，解决检索问题的能力也各不相同。 信息检索模型的好坏直接影响到系统的输出结果。 比较常用的检索模型有四种：布尔检索模型、向量空间模型、概率模型和 概念检索模型。 1 布尔模型 布尔模型是在信息检索系统中用得最普遍的模型，它是基于集合论和布尔 代数的一种简单检索模型。在布尔模型中，一篇文档通过一个关键词条的集合 来表示，这些词条都来自一个词典，对应于文档中的特征项。在查询与文档匹 配的过程中，主要看该文档中的词条是否满足查询的条件。若满足则认为该篇 文档与查询是相关的，若不满足则认为是不相关的。 布尔模型的一个查询是由一些逻辑操作符号( 如：a n d 、o r 和n o t ) 连 接起来的关键词所组成。检索时，根据用户提交的检索条件在文档表示中的逻 辑关系是否满足，将检索文档分为两个集合：匹配集和非匹配集。因匹配结果 的二值性，故无法在匹配结果集中进行查询结果的相关性排序。布尔模型的文 档表示能力差，无法区别特征项对文档内容贡献的重要程度，并且逻辑表达式 过于严格，往往会因为一个条件未满足而忽略了其它全部特征，造成大量的漏 检。但布尔模型实现简单，计算的代价相对较少，检索速度快，比其它模型的 查询语言更容易表达；该模型适合于那些明确直到自己想要查找什么信息的用 产。 在倒排文件中，布尔查询操作可以通过如下方式来实现。一般是先对查询 串( 由a n d 、o r 和n o t 等布尔操作符与关键词组合而成) 中每个词条分别进 行查询得到对应的列表，然后根据查询串的布尔操作符来对这些列表进行归 第2 苹搜索引犟基础 i i_ 并。 为克服简单布尔模型匹配函数过于严格而导致漏检率高的重大缺陷，研究 者们在布尔模型的基础上对其进行了扩展，提出了p 范数模型。在p 范数模型 中，一般将文档d 表示为d = 瓴，d 2 ，k ，以) ，其中d ，表示第i 个特征词对文档 内容的贡献程度。n 表示特征项的个数。用户查询可表示为q = ( g 。，q ：，k ，吼) ， 其中q 。表示第i 个特征词条对查询内容的贡献程度。反和g ，均在 0 ，1 】区间上取 值。 为判断文档和查询之间的相似程度，人们还定义了文档与用户查询间的相 似度。其计算方法如公式2 1 所示。 神咖一in 掣型 l ? p ( 2 - 1 ) 该式中的矾、g ，和上一段中的含义相同，尸【1 ，佃】。根据具体应用改变 矾、g 。和p 的取值即可以达到不同的检索效果。当p = 4 - o o 且z 的取值为0 或 1 ，q ，= q 2 - - k = q 。= 1 时，p 范数模型退化成简单布尔模型。 2 向量空间模型 向量空间模型v s m 是现代信息检索、特别是搜索引擎中普遍使用且效果较 好的一种检索模型。它是由s a l t o n 等人在2 0 世纪6 0 年代提出的。向量空间模 型主要包含有文档的向量化表示和文档之间的相似度的计算两个问题。 ( 1 ) 文档的表示 在v s m 中，将文档看成是由相互独立的特征词条( 正，瓦，k ，乙) 所构成，n 表示特征词条( 简称特征词或特征项) 的个数，它也是向量空间的维数。对于 每一特征词正，根据其在文档中的重要程度赋予一定的权值彬，并将 五，疋，k ，z 看成一个1 1 维坐标系中的坐标轴，彬，k ，形为对应的坐标值。这 样文档就被映射成空间中的一个点。对于所有文档和用户都可以映像到此文档 向量空间，从而将文档与查询的匹配处理过程转化为向量空间中的矢量匹配问 题，即向量之间的相似度计算问题。当全部文档向量与某个提问向量的相似度 都计算完毕之后系统就把相似度超过某一阈值的文档按照相似度大小降序排列 输出。 设d 是一个文档集合，文档d 是文档集合d 中的一个文档，则在v s m 中 每个文档都被表示成： d l = ( w 1 1 ，w j 2 ，k ) 而查询请求q i 表示成： 北京_ - 7 业大学工学硕士学位论文 曼曼曼! 曼曼! ! ! ! 曼曼! 曼曼! ! ! ! ! 曼! ! 曼曼曼! ! ! ! 曼! ! ! ! ! ! 曼! 曼! ! 皇! ! ! 皇! 曼! ! i 曼! 皇曼曼曼! 曼曼曼曼曼曼! ! 皇! ! ! ! 曼! 曼曼曼鼍 g = ( q j l , q j 2kq 雎) 这里，对于k = 1 , 2 ，k 刀，和g 肚分别表示特征词条瓦在文档口和查询请求中 的权值，其值的大小反映了特征词条瓦在文档口中或在查询请求o j 中的重要 程度。 对于每个特征词条的权值计算，其目标就是要能够最大限度地区分出不同 的文档。最为典型的且使用最广泛的文档特征权重计算方法是i f * i d f 表示法， 它是s a l t o n 和m c g i l l 在1 9 8 3 年针对向量空间信息检索范例提出来的。在该方 法中，t f ( t e r mf r e q u e n c y ) 表示特征项在文档中出现的次数，通常称为词条 频度；i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 反映了该特征词条出现在不同文档的 频繁程度的数值，通常称为反向文档频度。 特征词条的权值计算公式如下。 彬= 砑( z ，d ) 木i d f ( t ，)( 2 2 ) 公式2 2 中，t f ( t 。，d ) 表示特征词z 在文档d 中出现的次数，而反向文档 频度i d f ( t ，) 的计算公式如2 3 所示。 i d f ( t j ) = l g ( 1 d l d f ( t _ f ) + o 5 ) ( 2 3 ) 公式2 3 中例表示文档集合d 中的文档总数，d f ( t t ) 表示文档集合d 中包 含特征词z 的文档总数。在应用中，为避免因文档长度引起的权值变化，一般 要对词条的权值进行归一化处理，其中i 形i 是向量的模。 彬= t f ( t 。，d ) 木i d f ( t ，)( 2 4 ) 一彬 j 形j ( 2 5 ) 从公式2 4 可以看出，特征词的权值与t f 成正比例，与d f 成反比例。一 方面，特征词在文档中出现的频率越高，说明它在表示文档内容方面的能力就 越强( 与t f 成正比例) ；另一方面，出现该特征项的文档数越多，说明该特征 项区分文档主题及内容的能力就越差( 与d f 成反比例) 。所以t f * i d f 表示方 法增强了特征项对于文档的表达能力和区分能力。实际上，向量空间模型的量 化基础是词条频率和出现文档频率。t f * i d f 的提出是基于这样的假设：对区别 文档最有意义的词语应该是那些在文档中出现频率足够高的，但在整个文档集 合的其它文档出现的频率足够少的词语。由于v s m 的适应性号、可扩展性 强、具有较强的可计算性和可操作性，现有的l y c o s 、a l t a v i s t a 、s m a r t 等系 统使用的都是向量空间模型。 ( 2 ) 相似度计算 相似度计算是一个重要的概念。据调查，由于搜索引擎返回的检索结果往 往过于庞大，用户一般只会浏览选取检索结果前面的一部分。因此，要提供更 好的检索服务，就要将符合查询请求的文档选出排在最前面，这就需要计算文 第2 章搜索引擎基础 档与查询的相关度。 在向量空间模型中，向量的每一维的值就是该特征项在文档中的权值，所 有的文档和查询则分别映像成为r l 维向量空间的一个点。相关度的计算也就演 变成了两个向量之间的距离或者向量夹角的计算，大大降低了问题的复杂性。 通常的计算向量x = ( x 1 ，k ，x n ) 和y = 。，k 儿) 的相似度的有公式2 - 6 和公式 2 7 。 几一 1 ( 墨一咒) 2 s i m ( x ，d = 岩f 一 ( 2 6 ) nf 月 擂# 母撂开 。毛 2 5 x i y i s i m ( x ，d = c o s ( x ，d = t 量f ( 2 - 7 ) i ”fn 蕃# 枣善订 公式2 - 6 用向量之间的距离来度量相似度，距离越近说明相似度越高；公 式2 7 用向量之间的加压余弦来度量相似度，夹角越小说明相似度越高。 向量空间模型的有点： ( 1 )向量模型使得对查询向量中关键词权重的赋值成为可能，词条权 重模式改善了检索性能。 ( 2 )利用计算得到的相