（计算机应用技术专业论文）搜索引擎中主题爬虫的研究与实现.pdf

硕十论文 搜索引擎中主题恺虫的研究与实现 摘要 随着i n t e m e t 的迅速发展，网络信息增长的速度和人们获取所需信息能力之间的矛 盾越来越突出。本文围绕主题搜索引擎这一社会研究的新热点技术，对主题搜索引擎 中占有重要地位的主题爬虫给予研究和讨论。主题搜索引擎中的信息采集，即主题爬 虫系统的搜索策略的研究，对于主题搜索引擎的应用与发展具有非常重要的作用。论 文首先对主题搜索引擎的基本功能进行了简单介绍，引出主题搜索引擎的重要组成部 分主题爬虫，并分析了主题爬虫的基本结构及工作原理。然后对网络爬虫的搜索 策略进行了讨论，重点介绍了基于w e b 超链接结构和基于网页文本内容的启发式搜索 策略，并对它们进行了比较。在计算文本内容相似度算法的讨论中引入了经典的基于 向量空间模型的分类方法。设计并初步实现了一个主题爬e p s o f t s p i d e r ，介绍了该爬 虫的结构以及相关设计细节。该爬虫的搜索算法是对a u t h o r i t i e sa n dh u b s 算法的改进， 采用了w e b 超链接分析和网页文本内容相结合的启发式搜索策略。最后对该爬虫的性 能进行了测试，同时给出了实验结果及分析。 关键词：搜索引擎，主题爬虫，a u t h o r i t i e sa n dh u b s 算法，w e b 超链分析。向量空 间模型 彤i 论史搜索b ：擎中主题爬虫的酽究实现 a b s t r a c t w i n lt h er a p i dg r o w t ho ft h ei n t e m e l t h ec o n f l i c tb e t w e e nt h eg r o w t ho ft h ew e b i n f o r m a t i o na n dt h ea b i l i t yo fp e o p l ea c h i e v i n gi ti sb e c o m i n gh u g e ra n dh u g e r s u r r o u n d i n gt h er e s e a r c ho nt h i sh o t s p o t , t h ei m p o r t a n tp a r to ft h et o p i c s p e c i f i cs e a r c h e n g i n et h a ti sc a l l e df o c u s e dc r a w l e ri sd i s c u s s e di nt h i sp a p e r n l er e s e a r c ho nt h e s e a r c h i n ga l g o r i t h m i sv e r y i m p o r t a n t t ot h e a p p l i c a t i o n a n dd e v e l o p m e n to f t o p i c s p e c i f i cs e a r c he n g i n e f i r s t l y , t h eb a s i ct h e o r yo ft o p i c - s p e c i f i cs e a r c he n g i n ei s s i m p l yi n t r o d u c e di nt h i sp a p e r n l es t a t u so ff o c u s e dc r a w l e ri nt o p i c s p e c i f i cs e a r c h e n g i n ei sb r o u g h tf o r w a r d t h ew o r kt h e o r yo ft h ef o c u s e dc r a w l e ri sa n a l y z e d t h e n s e v e r a lk i n d so fs e a r c ha l g o r i t h m so ff o c u s e dc r a w l e ra r ed i s c u s s e d ，t h es e a r c ha l g o r i t h m b a s e do nw e b h y p e r l i n ka n dt h eo n eb a s e do np a g ec o n t e n ta r ed e t a i l e d i nt h ec o u r s eo f t h er e l a t i v i t yj u d g i n gb e t w e e nt h ep a g ec o n t e n ta n dt h et o p i c ，t h em e t h o db a s e do nv e c t o r s p a c em o d e l w h i c hi sw i d e l ya p p l i e di nt h ef i l e do f t h et e x tc l a s s i f i c a t i o ni su s e d l a s l l y 8 - f o c u s e dc r a f t i e rc a l l e ds o f t s p i d e ri sb r o u g h tf o r w a r da n dd e s i g n e d 1 1 1 i sc r a w l e ru s e st h e s e a r c ha l g o r i t h mb o t hb a s e do nw e bh y p e r l i n ks t r u c t u r ea n dp a g ec o n t e n t ，a n di m p r o v e s o na u t h o r i t i e sa n dh u b sa l g o r i t h m t h ed e t a i l so fs t r u c t u r ea n dd e s i g na r ei n t r o d u c e d t h e p e r f o r m a n c eo f t h i sc r a w l e ri st e s t e da n dt h er e s u l ti sp r e s e n t e d k e yw o r d s ：s e a r c he n g i n e ，f o c u s e dc r a w l e r ，a u t h o r i t i e sa n dh u b s w e bh y p e r l i n k a n a l y s i s ，v s m 声鹱 本学位论文怒我在譬师的指导下取褥的醭究成果，尽我熙知，在本 学位论文中，除了加以栎注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的间事对本学位论文做豳的贡献均已在论文 孛佟7 鹱确麓说磷。 研究生签名：- 二警陋 秭筇5 月i 舀 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按徐密的有关麓定帮程序楚理。 研究生签名： 瑚虫斑 埘年月i 旦 硕士论文搜索引擎中主题犯虫的研究与实现 1 绪论 1 1 课题背景 该课题属于计算机应用领域，课题源于某公司研究项目：主题搜索引擎的设计 与开发。 随着i n t e r n e t t n t r a n e t 的迅速发展，网络对我们的影响已经越来越大。丽在网上 发展最为迅猛的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 的迅速发展使搜 寻引擎迅速地更新。现今，搜索引擎所解决的问题不论在质量还是数量上都达到了 令人惊叹的地步。 搜索引擎是为了解决如何在知识海洋中邀游而出现的技术。搜索引擎以一定的 策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户 提供检索服务，从而起到信息导航的目的。搜索引擎提供的导航服务已经成为互联 网上非常重要的网络服务，搜索引擎已经成为人们在网络中的“导游”。搜索引擎 技术因而成为计算机工业界和学术界争相研究、开发的对象。 作为搜索引擎的基础和组成部分，w e b 信息采集正发挥着举足轻重的作用，并 且随着应用的深化和技术的发展，它也越束越多的应用于站点结构分析、页面有效 性分析、w e b 图进化、内容安全检测、用户兴趣挖掘以及个性化信息获取等多种服 务和研究中。 传统的搜索引擎信息采集的目标就是尽可能多地采集信息页面，甚至是整个 w e b 上的资源。随着w w w 信息的爆炸性增长，信息采集的速度越柬越不能满足实 际应用的需要。最近的试验表明即使大型的搜索引擎，它对w e b 的覆盖率也只有 3 0 - 4 0 i ”。解决这一问题的直接办法是升级信息采集器的硬件，采用处理能力更强 的计算机系统，然而这种方法的扩展性有限，性价比也不高。一个更好的解决方法 是采用分布式方法来提高并行能力，但是并行不但增加了系统的歼销和设计的复杂 硕t 论文 搜索引擎中主题怛虫的研究与实现 性，并且并行换来的效益也随着并行采集器数目的增加而显著地减小。目前，一般 的大型搜索引擎都采用了并行机制，但并行带来的改善效果仍远不能满足人们的需 要，人们需要从其它角度改善目前的困境。 针对上述情况，另一种形式的搜索引擎悄然出现，它可以在较小的范围内取得 比通用搜索引擎更令人满意的结果，以满足某些特定用户的需要，这就是主题式搜 索引擎。 1 2 相关研究内容 1 1 1 搜索引擎 所谓搜索引擎，就是一种指能够自动对w w w 资源建立索引或进行主题分类，并 通过查询为用户返回相关资源的系统。目前，网络上使用的搜索引擎很多，像 a 1 t a v i s t a 、i n f o s e e k 、y a h o o 等都是网络上非常著名的搜索引擎。它们所采用的技术和 实现的方法各有其特点。按照信息搜索方法和查询方式的不同，搜索引擎的发展可以 分为以下四代： 1 基于目录的搜索引擎。这类搜索引擎主要是利用人工分类方法将网络信息按 主题分类，建立可浏览等级式搜索引擎，向用户提供服务。具体的实现是各大网站管 理者根据搜索引擎的规范提供站点的描述，搜索引擎能根据这些描述由编辑员来建立 数据库。如y a h o o 就是这类搜索引擎，它的优点是网页准确度很高；缺点是索引库的 更新需要人工干预，所以速度慢，覆盖面小，费用高。 2 基于r o b o t 的搜索引擎。它的特点是网页信息的采集不需要人工干预，主要是 利用一种称为r o b o t 的软件程序，自动在网络中爬行，进行信息采集、处理，提供查 询的服务，并能够自动更新索引库。这类搜索引擎的典型代表是o o o g l e ，它是利用网 络中普遍存在的超链接结构，自动抓取网页。它的优点是费用较低，缺点是分类不精 确，误检、漏检率高。 3 以人工智能为特点的搜索引擎。第三代搜索引擎的特征是加入了人工智能的 成果，增加搜索引擎与用户的交互，减少两者之间信息的不对称。采用w e b 数据挖掘 技术，自动分类技术等，出现了主题和地域搜索服务，搜索平台逐步向桌面、移动等 方向拓展，往智能化、个性化的方向发展。 4 主题搜索引擎。也称为“专业搜索引擎”、“专题搜索引擎”，本论文中称 为主题搜索引擎。它主要是为用户提供某个主题或是某个域的w e b 网页资源的检索 服务，它所提供的资源都是与某个主题相关的，服务上更具有专业特色，有一定程 度的个性化。因此它比前三代搜索引擎更加有效和准确，具有主题覆盖率高、智能 2 硕士论文搜索引擎中主题吧虫的研究与实现 化程度高、检索对象多样化、服务个性化和专业化等特点。其实，主题搜索引擎中 涵盖了r o b o t 搜索和人工智能等方面的技术，而且在使用上更具有实际意义。基于 主题的网络爬虫在主题搜索中的作用是按照启发式搜索策略从网络中获取主题相关 资源，从而在很大程度上缓解了用户使用搜索引擎取得大量无关页面的问题。因此 就当今用户对搜索引擎的实际要求来说，对主题爬虫进行研究是十分有用的。本论 文主要就是针对主题式搜索引擎中的主题爬虫展开讨论的。 随着互联网服务的多样化，用户获取信息方式的变化以及服务商对此进行的技 术创新，推动了搜索形态的变化，也是不同搜索服务商竞争的核心。用户对搜索引 擎的认知度和使用量继续迅速提高，而对搜索引擎的要求也在不断提高，这就必然 增加搜索服务提供者之间的竞争，然而有竞争才会有进步，搜索引擎必定会朝着更 加人性化和实用性的方向发展。 为了跟上网络发展的速度，建立一个能够与w e b 相适应的主题式搜索引擎将会 面临许多挑战。搜集网络文档所需的快速爬行技术，存储索引和网络文档所需的大 存储空间，必须有效处理数据的索引系统，快速查询的检索系统等等，随着网络的 扩展，都成为搜索技术的难点。然而，随着时代的发展，计算机技术的更新，硬件 方面的效率也在飞速增长，这在一定程度上缓和了软件上的困难。在这样的基础上， 我们希望主题式搜索引擎中的爬行技术在保证下载页面存储和建立索引的代价尽可 能得小，处理查询的速度尽可能得快，搜索引擎使用起来尽可能得人性化。 1 2 2 搜索引擎发展的国内外概况 国外的搜索引擎技术发展的较早，已经有十几年的历史，y a h o o ! 是最早提供分 类目录向导的搜索引擎。根据用户输入的检索式，y a h o o ! 将返回相关的y a h o o ! 分类 目录、w e b 网站、w e b 网页和新闻。目前a l t a v i s t a 是i n t e m e t 上最大的搜索引擎之 一，它提供常规搜索、高级搜索和主题搜索，包括图像、视频和音频等。a l t a v i s t a 所拥有的庞大的数据库使得用户找到所需信息的可能性大大增加。g o o g l e 有四十亿 个可搜索网页，每天处理的搜索请求己达2 亿次，在操作界面中提供多达3 0 多种语 言选择，包括英语、主要欧洲国家语言、日语、中文简繁体、朝语等。 国内开始研究搜索引擎是在上世纪末本世纪初，虽然国内起步较晚，但是已经 涌现了出一些很优秀的产品。目前国内技术水平最高的搜索引擎是百度，它的功能 齐全，包括新闻搜索、网站搜索、m p 3 搜索、图片搜索等，在中文搜索支持方面甚 至有些地方超过了g o o g l e ，更新速度也较快些。在搜索结果中百度还设置了相关搜 索功能能够提供用户与查询关键词有联系的信息，从而进一步提高了查询的准确 度。随着搜索市场价值的不断增加，越来越多的公司开发出了自己的搜索引擎，中 硕士论文搜索引擎中主题爬虫的研究与实现 国搜索、搜狐的搜狗、阿里巴巴的商机搜索等也陆续面世，自然，搜索引擎技术也 成为技术人员关注的热点。 近年来，随着w w w 技术的广泛应用，上面介绍的一些传统的通用搜索引擎， 正面临着巨大的挑战口叫。首先是w e b 信息资源呈指数级增长，传统的搜索引擎无 法覆盖网络中的所有页面；然后是w e b 信息资源的动态变化，搜索引擎无法保证对 所有信息的及时更新；最后是传统的搜索引擎提供的信息检索服务，不能满足人们 日益增长的对个性化服务的需要。面对这些挑战，为了适应不同人群需要的各种“主 题搜索引擎”( t o p i c s p e c i f i cs e a r c he n g i n e ) 应运而生，并引起研究者的高度重视， 成为当今社会的研究热点【5 7 l 。 1 3 本文研究内容及结构 本论文安排如下； 第一章主要介绍课题的研究背景和相关研究内容以及发展现状。 第二章主要剖析网络爬虫在搜索引擎中的地位，并介绍主题爬虫与通用爬虫的 区别及其基本原理和结构，讨论了主题页面的分布特征。 第三章主要研究和讨论本系统中所要用到的关键算法，其中包括基于内容的搜 索算法、w e b 超链接分析的各类算法及比较以及主题相关性算法。 第四章主要说明系统的设计过程，对设计中所用到的一些技术以及u r l 的提 取、页面的分析、搜集策略的选择等主要方面作了详细的论述，并给出设计方案和 算法。 第五章给出系统的实际运行过程和部分实验数据，并对实验结果进行了分析， 说明本系统是切实有效的。 第六章对本论文的主要工作做了总结，同时也提出了今后需要进一步做的研究 和工作。 4 硕 论文搜索引擎中主题爬虫的研究与实现 2 网络爬虫简介 2 1 网络爬虫在搜索引擎中的地位 搜索引擎的工作原理基本都是一样的，利用一个称为网络爬虫c r a w l e r ( 也叫做 网络蜘蛛s p i d e r 或网络机器人r o b o t ) 的程序，本论文统一称为网络爬虫，采用多线 程并发搜索技术，在互联网中访问各节点，定期搜索信息，抓取网页，并根据网络 链接提取其他网页，对网页进行分析，提取关键词、u r l 等信息，然后索引器对爬 虫所提取的信息进行排序并存入索引数据库，用户可以通过用户接口输入所需信息 的关键词进行查询，检索器则根据用户提交的关键词在索引数据库中查找相关信息， 并按照相关度进行排序输出。 因为搜索引擎与网络用户的关系非常密切，因此它一直专注于在三个方面提升 用户的体验度，即为准、全、快。用专业术语讲就是：查准率、查全率和搜索速度 ( 即搜索耗时) 。其中比较容易提高的是搜索速度，因为对于搜索耗时在1 秒以下的 系统来说，用户已经很难辨别其快慢了，再加上网络速度的影响，就更难分辨搜索 引擎本身的搜索速度。因此，对搜索引擎的评价就集中在了另外两方面：准和全。 搜索引擎的查全需要保证一些比较重要的结果不被遗漏，而且能够找到最新的网页， 这需要搜索引擎有一个强大的网页收集器，即网络爬虫；搜索引擎的查准，则需要 保证搜索的前几十条结果都和搜索的关键词的相关度很高，即使用户很满意，这是 由排序技术来决定的。 搜索引擎是一个技术含量很高的网络应用系统。它包括网络技术、数据库技术、 检索技术、语言处理技术及智能技术等等。 各种搜索引擎虽然在设计细节上有所不同，但是基本构造通常都可分为四部分： 网络爬虫、索引模块、信息检索和用户接口，功能如下所述： ( 1 ) 网络爬虫：网络爬虫c r a w l e r 日夜不停地在互联网的各节点中自动爬行， 从一个或一组u r l 开始访问，并尽可能多、尽可能快地从中发现和抓取 信息。因为互联网上的信息更新很快，所以还要定期更新己经搜集过的 旧信息，以避免死链接和无效链接。 ( 2 ) 索引模块：索引分析器i n d e x e r 对网络爬虫所下载的页面进行分析，过滤 掉无用的信息，把文件表示成一种便于建立索引的方式，抽取最优索引 信息以表示文档，并利用所抽取信息建立索引数据库，从而使用户能够 很容易的查找到所需要的信息。 5 硕十论文搜索引擎中主题爬虫的研究与实现 ( 3 ) 信息检索：检索器s e a r c h e r 根据用户查询的关键词从索引数据库中快速 查找相应的文档，并进行相关度的计算，然后将输出结果按照相关度排 序回馈给用户，其中检索算法、信息查询和组织的方式都会在很大程度 上影响检索模块的系统性能。 ( 4 ) 用户接口：提供用户与搜索引擎的交互窗口，用于关键字的输入，查询 结果的输出，用户接口应尽量设计的人性化。 搜索引擎的体系结构大致可分为两种，集中式和分布式，这两种方法都有适合 自己的应用条件。集中式体系结构容易处理数据的统一性问题，采集页面的时候可 以从全局的角度来找出最优页面，并有效利用了通信带宽。但当系统规模比较大搜 索的页面非常多时，如果采用某种分布式方法，将会明显提高系统的性能，可以实 现更快的采集速度和更高的采集性能。搜索引擎的各个组成部分，除了用户接口之 外，都可以进行分布式处理：搜索器可以在多台机器上相互合作、相互分工进行信 息的发现和获取，以提高信息发现和更新的速度；索引器可以将索引分布在不同的 机器上，以减小索引与机器性能之间的矛盾；检索器可以在不同的机器上进行文档 的并行捡索，以提高检索的速度和性能。 搜索引擎虽然外在表现呈现出多样化，所提供的功能也有所不同，但是就其实 现来说，构造基本都是一样的。本论文所讨论的搜索引擎其结构分为四部分，即上 文所提到的网络爬虫、索引模块、信息检索以及用户接口。网络爬虫在搜索引擎中 占有重要地位，对搜索引擎的查全、查准都有一定程度的影响，它决定了搜索引擎 数据容量的大小，而且网络爬虫设计得好与坏直接影响搜索结果页面中的优等页面 和死链接( 即链接所指向的网页已经不存在) 的个数。目前如何发现更多的网页、 如何正确提取网页内容，如何提高信息抓取的速度以及如何识别网站中内容相同的 网页等都是网络爬虫需要进一步改进的问题。 根据上文的讨论，可以得到搜索引擎的基本框架结构以及网络爬虫在搜索引擎 中的位置如图2 1 1 所示。 本论文的主要研究工作就是针对图中网络爬虫部分的分析，在文章的接下来部分 将对其进行讨论，详细介绍网络爬虫的工作原理以及功能等。 6 硕士论文搜索引擎中主题爬虫的研究与实现 冬磊：声恼 压困 压圈 图2 1 1 搜索引擎体系结构 2 2 网络爬虫的结构及基本原理 对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前已经 公布的数据来看，容量最大的搜索引擎也只不过是抓取了整个互联网网页总量的酉 分之四十左右。这其中的原因一方面是抓取技术的瓶颈，网络爬虫无法访问w e b 中 的所有网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和 处理技术的问题，网络中的页面数量以及索引页面的大小，就目前的抓取技术及存 储技术来看，都不可能全部被处理，而且，因为数据总量太大，在提供搜索时也一 定会引起效率方面的问题。所以很多搜索引擎在设计的时候，只是选择抓取相对来 7 硕士论文 搜索引擎中主题爬虫的研究与实现 说比较重要的网页及链接，这就在一定程度上缓和了那些技术瓶颈所带来的问题， 同时也不会影响用户的使用。 当前基于w e b 的搜索引擎采纳了信息发现的模式和等级算法，这些是从传统的 文本信息发现系统中产生的，并且以单一文档索引为基础。w e b 文档的超文本结构， 能被利用并开发成能提供更多来自w e b 文档和链接页面内容的信息，从而提高检索 的有效性。搜索引擎应该能够把属于各种w e b 站点的不同页面的所有信息都放在 起，通过使用可记忆功能去实现正确定位信息的方法。对此在本论文第三章中会有 详细讨论。 搜索引擎中的关键技术网络爬虫【羽，它的主要功能就是搜集i n t e m e t 中的各种信 息。它是利用网页中的超文本链接( h y p e r l i n k ) 来访问网页的，从一个事先制订好 的u r l 列表开始，这个列表中的u r l 一般是从过去的访问记录里提取出来的，通 常是一些比较流行的站点和新闻网页，利用h 1 v r p 等标准协议，通过u r l 从一个页 面爬行到另一个页面，直到没有满足条件的新的u r l 为止。 c r a w l e r 访问了一个网页后会对它进行分析，抽取出新的u r l ，将之加到访问 列表中，同时，c r a w l e r 提取的网页将彼放入到数据库中。网络爬虫搜集的信息有很 多种，例如h t m l 文件的u r l 、标题、长度、文件建立的时l - 日j 、链接数目以及一 些多媒体信息等。这些信息都需要c r a w l e r 自动获取，其中标题、文件中的超链接 数目需要c r a w l e r 分析h t m l 文件得到，因为h t m l 文件格式较为固定，所以这些 相关信息通过分析文件内容就能获得。c r a w l e r 所抓取的信息将被搜索引擎用于建立 索引数据库，而它所包含的超链接将被c r a w l e r 用于访问新文档的起始u r l ，这个 过程反复进行，从而使w e b 中的信息得到收集。 网络爬虫的基本结构如图2 2 1 所示。 图2 2 1 通用网络爬虫模块图 网络爬虫在爬行的时候需要用到一些网络协议，协议处理模块就是实现这个功 硕士论文 搜索引擎中主题爬虫的研究与实现 能的。u r l 处理模块的作用是给将要采集的u r l 进行排序，按照一定的算法向协 议处理模块分配u r l 。内容检测模块是用来处理网络中普遍存在的将近3 0 左右的 重复页面，在一定程度上提高系统的效率。 搜索引擎的c r a w l e r 一般要定期访问大多数以前搜集的网页，从而更新索引数 据库，以反映出网页的变化情况，去除一些死链接，网页的部分内容和变化情况将 会反映到用户查询的结果页面中去 爬虫在网络中爬行的时候，将w e b 上的网页集合看成是一个有向图，从给定的 起始u r l 开始，沿着网页中的链接，按照一定的策略进行。通常用到以下几种遍历 算法 1 深度优先算法。该算法是指网络爬虫会从选定的一个超链接开始，按照一条 线路，一个一个链接访问下去，直到达到这条线路的叶子节点，即不包含任何超链 接的h t m l 文件，处理完这条线路之后再转入下一个起始页，继续访问新的起始页 面所包含的链接中的一条直到到达叶子结点。这个方法有个优点是网络爬虫在设计 的时候比较容易。 2 广度优先算法。广度优先算法是指网络爬虫会先抓取起始网页中包含链接的 所有网页，然后再选择其中的一个链接网页，继续抓取在这个网页中链接的所有网 页。这种搜索方法是实现通用网络爬虫的最佳方法，因为它的特点是易于实现，并 且能够避免陷进一个无穷尽的深层分支中去，可以让网络爬虫并行处理，从而提高 其抓取速度。 3 启发式搜索算法。源于人工智能，即先通过在线获得的领域知识评价待访问 链接的价值，借以推断信息资源的分布情况，然后按一定的原则选择价值最大的链 接进行下一步的搜索，找到到达目标节点的最佳路径，删除不好节点，保留那些好 的节点。主要用于主题爬虫的搜索策略 4 基于自动分类的搜索算法，原理是把c r a w l e r 看成a g e n t ，使其具有一定的自 主性，可以学习w e b 上的知识，具备经验信息，计算网页是否属于所需要的主题类 型，从而得到下载的正确方向。 2 3 网络爬虫的分类及比较 基于w e b 的信息采集、发布和相关的信息处理成为人们日益关注的焦点，也成 为人们竞相讨论和研究的热点问题。搜索引擎可以分为通用搜索引擎和主题搜索引 擎。传统的搜索引擎的目标是尽可能多地采集信息页面，即注重查全率，而比较少 地考虑采集页面的准确性，因此，它不可避免的存在着很多缺陷。随着w w w 的爆 炸性增长，搜索引擎的速度越来越不能满足实际的需要。主题搜索引擎则可以通过 9 硕士论文 搜索引擎中主题爬虫的研究与实现 对整个w e b 按主题分块采集，只搜索与主题相关的信息，从而克服了通用搜索引擎 采集海量数据的弊端，从主题角度可以说提高了整个w e b 的采集覆盖率。对于传统 搜索引擎的信息采集来说，信息更新一遍需要几周甚至一个月的时l 日j 1 1 l ，这就使用 户得到的信息失去了它原有的价值。一个好的缓解办法就是采用主题采集，通过减 小采集页面的数量来提高效率，进而增加已采集页面的有效性。传统的搜索引擎要 消耗很多系统和网络资源，而它们中大部分利用率很低，基于主题的搜索引擎有效 地提高了采集到的页面的利用率。 主题搜索引擎是在通用搜索引擎的网络爬虫模块中加入了对所查询主题与网页 内容的相关性的判定，应用各种算法实现对主题相关页面的访问。基于此，用于搜 索引擎页面采集的网络爬虫也分为通用网络爬虫和主题网络爬虫两种，它们的区别 如下所述： 1 通用爬虫不分主题，只是根据爬虫的控制策略随机分配爬行任务，而主题爬 虫却是面向主题的，爬虫以特定主题为目标访问页面。 2 通用爬虫之间不存在主题方面的通讯与合作，而主题爬虫以主题为中心进行 合作，爬虫之间存在爬行任务的推荐。 3 通用爬虫的目标是尽可能多的搜集质量好的页面，但对于页面内容没有要求， 包含所有方面，主题爬虫的目标是尽可能多的爬行与主题相关的资源，尽可能少的 爬行与主题无关的页面，过滤掉无关网页，使某个主题的资源覆盖率变大，同时要 求相关资源质量好。 图2 2 1 所描述的是通用爬虫的基本模块，主题爬虫是在通用爬虫的基础上加入 了对主题的判断，但在搜索策略上却有本质的不同。主题爬虫是本论文研究的重点， 在后续章节中将对主题爬虫的相关技术作进一步的介绍，并将详细介绍自行设计的 主题爬虫的模块及原理。 2 4 主题页面在w e b 上的分布特征 从表面上看，w e b 上页面的分布杂乱无章，但是经过研究发现4 1 ，其实主题 页面的分布是有规律可循的，大致总结为四个特征：h u b 特性、主题关联特性、站 点主题特性、t u n n e l 特性。通过对这些特性的研究，在爬虫进行基于主题的爬行过 程中以找到一些对链接预测和页面过滤有用的规律。 1 h u b 特性 美国c o r n e l l 大学的j k l e i n b e r g 发现w e b 上存在大量的h u b 页面，这种页面不 但含有许多出链，并且这些链接趋向于同一个主题。也就是说，h u b 页面是指向相 关主题页面的一个中心。另外，他还定义了权威页面( a u t h o r i t y ) 的概念，指其它许 0 硕十论文 搜索引擎中主题爬虫的研究与实现 多页面都认为相关于某一主题的有价值的页面。好的h u b 页面一般指向多个 a u t h o r i t y 的页面，而好的a u t h o r i t y 页面会被多个h u b 页面所指向。根据这个思想， 他还提出了a u t h o r i t i e sa n d h u b s 算法，这个算法将在3 2 2 节中介绍。 2 主题关联特性 在h u b 特性的基础上，又有人提出了主题关联特性的概念。主题关联特性是指 页面所包含的链接趋向于指向和该页面同主题的页面；对于链接到某主题页面的页 面，它所包含的其它链接指向的页面也趋向于该主题。这实际上源于h u b 特性，主 要是从页面设计者的角度考虑的。页面设计者一般会把本页面指向于与本页面相关 的其他页面。 3 站点主题特性 研究人员发现，一个站点趋向于说明一个或几个主题，并且那些关于同一主题 的页面较紧密地在此站点内部链接成团，而各个主题团之间却链接较少。这应该与 网站设计者的设计思路有关。每个网站在设计时都有目标，而这种目标般就集中 在一个或几个主题中。而网站的浏览者往往也有目标，他们一般也趋向于浏览同一 主题的页面。网站设计者为了满足浏览者的实际需要而将相关内容紧密链接。 4 t u n n e l 特性 w e b 中主题页面团之间往往要经过很多无关链接才能相互到达。这些无关链接 就像一个长长的隧道，因此称为“隧道现象 ( t u n n e l ) 。主题爬虫在爬行时，t u n n e l 的存在将会对爬行的页面质量、覆盖率和准确度都造成极大地影响。在设计爬虫的 搜索算法时，为了提高爬行页面的准确率，需要提高相关性判定阈值，这样将过滤 掉大量的t u n n e l ，但同时也会丢掉t u n n e l 另一端的主题团，从而影响覆盖率。反过 来，如果为了提高覆盖率而降低相关性判定阈值，就会混入大量的无关页面，从而 影响准确率。为了解决这个问题，在设计链接预测算法时通过给被判定为不相关的 链接一个再次被选择的机会，这个机会发生的概率一般要大于t u n n e l 出现的估计概 率值。该算法将在4 4 节作详细的介绍。 2 5 主题爬虫的设计目标 类似于通用爬虫与通用搜索引擎之间的关系，主题爬虫与主题搜索引擎之间的关 系也像图2 1 1 中所描述那样。主题爬虫在网络中漫游，从中搜集优等的与主题相关的 网络资源，通过索引器的索引再由检索器排序输出给用户，以此完成主题搜索引擎整 个过程。因此，对于主题搜索引擎来说，主题爬虫的性能优劣直接影响到整个搜索引 擎的性能。 主题爬虫的基本工作流程是按照事先给出的主题，分析w e b 中的超链接和己经下 顾士论文搜索引擎中主题爬虫的研究与实现 载的网页内容，来预测下一个要爬行的u r l ，保证尽可能多地下载与主题相关的网页、 尽可能少地下载无关网页以此来提高主题爬虫的效率与准确率。主题爬行器的设计 主要从以下几个方面来考虑： 1 下载高质量的网页。前面已经说过，随着w e b 网页数量的急剧增长，爬虫不可 能下载所有的网页，要最大程度的满足用户的需求，就必须提高所下载网页的质量， 以保证下载的网页可用价值尽量高。如何评价一个待爬行网页的质量是设计主题爬虫 时首先需要解决的一个问题。 2 判断已经下载的网页与主题的相关性。对于已经下载的网页，我们可以通过提 取网页中的文字信息，包括围绕在链接周围的文字和网页内容，从而充分利用信息， 按照一定方法来计算网页与文本的相关性。 3 决定待爬行u r l 的访问次序。通用搜索引擎以搜集海量数据为目标，爬虫在爬 行的时候只需按照深度优先遍历或者广度优先遍历的方法下载页面，尽量提高爬虫的 爬行范围，而主题爬虫因其自身的特点，在爬行的过程中就要考虑优先访问与主题相 关页面，即要考虑如何管理待爬行的u r l 队列，从而使每次爬行都从相关度最高的页 面开始。 4 尽量降低被爬行网站的负担。因为爬虫在爬行的过程中，需要访问别人的服务 器，这样就要占用对方的计算机资源，如c p u 、磁盘空间等，同时也占用了网络带宽， 增加了网络的负担。爬虫的设计应该将这些消耗降到最小，否则网站w e b 管理员会屏 蔽爬虫。 2 6 本章小结 本章从搜索引擎的角度出发，首先对搜索引擎的基本结构、原理和功能进行了 分析，指出搜索引擎的四个组成部分，并对各个部分进行了简单介绍，从而引出在 搜索引擎中占有最重要地位的网络爬虫，接着对爬虫的结构和功能进行了详细介绍， 然后提出网络爬虫的分类，同时指出了通用爬虫的不足之处和主题爬虫研究的现实 意义，分析了主题页面在w e b 中的分布特征，最后给出了主题爬虫的设计目标为 本论文以下内容的研究提供了理论基础。 硕士论文搜索引擎中主题爬虫的研究与实现 3 网络爬虫的关键算法 搜索引擎中最关键的部分是网络爬虫，它的性能好坏直接影响着搜索引擎的整 体性能和处理速度。网络爬虫的搜索策略与搜索引擎的性质和任务密切相关。传统 的通用搜索引擎的主要目的是获得较高的w e b 覆盖率，尽可能多的下载网页，它的 网络爬虫通常采用图的遍历算法( 如广度或深度优先策略) 来搜索w 曲；主题搜索 引擎的特点是搜索的内容只限于特定的主题或专门的领域，因而在搜索过程中没有 必要对整个w e b 进行遍历，只需要选择与主题页面相关的页面进行访问即可。即主 题搜索引擎更注重下载网页的准确性，因此可以说主题信息搜索策略是主题搜索引 擎技术的核心。对主题搜索引擎而言，决定网络爬虫搜索策略的关键是如何将不相 关的网页快速地过滤并删除掉，因为网页过滤的速度和准确性将会直接影响网络爬 虫的性能。以何种策略访问w e b ，成为近年来主题搜索弓i 擎网络爬虫研究的焦点之 _ 1 1 5 1 6 1 为了优先爬行高质量的相关网页，研究者们设计了许多启发策略和相关算 法，这些策略大致分为两大类：基于文字内容的搜索策略和基于w 曲图的超链接结 构的搜索策略。 这一章将重点介绍本论文所设计的主题爬虫在设计和实现的过程中将会用到的 各种关键算法及其思想。 3 1 主题爬虫的搜索策略 3 1 1 基于内容评价的搜索策略 基于内容评价的搜索策略的主要特点是利用页面中的文本信息作为领域知识指 导搜索，并根据页面或链接文本与主题( 如关键词、主题相关文档等) 之间相似度的高 低来评价链接价值的高低。这类搜索策略的代表有f i s h - s e a r c h 算法、s h a r k - s e a r c h 算 法，下面分别介绍： 1 f i s h s e a r c h f i s h s e a r c h 算法于1 9 9 3 年由荷兰t u e 大学的d e b r a 教授提出，并整合到了当时流行 的m o s a i c 测览器上，是实时搜索中比较有名的算法【r 丌 该算法的关键是根据用户的种子站点和查询的关键词或短语，将包含查询串的页 面看作与主题相关，计算该页面与主题的相关度，动态地维护待爬行u r l 的优先级队 列u r l _ q u e u e 。这个队列分为前端，中部和尾部三部分，另外还需要几个参数：d e p t h ， 一、 1 3 碗士论文搜索引擎中主题耙虫的研究与实现 w i d t h 和p o t e n t i a ls c o r e ，分别用于记载被搜索网页的层深、每页最多分析的链接数目 ( 在此，我们称其为孩子数) 和u r l 的相关度。这个算法的基本思想是：它以一个 u r l 为起始搜索网页，在搜索这个u r l 的基础上动态的建立一个列表，这个列表中包 含有待搜索的u r l 。这个列表中的u r l ( 即孩子链接) 具有优先级的区分，优先级高 的u r l 将排在列表中的前端，将会比排在列表后面的u r l 提前被搜索。在每一步开始 时，取出列表中的第一个u l u 进行分析。如果该网页可以访问，则经过分析对它的 p o t e n t i a ls c o r e 赋值，并改变其相应的d e p t h 和w i d t h 值，然后再重新进行下一个u r l 的 检索。 f i s hs e a r c h 算法的具体描述如下： 从最初的u r l 列表中选择u r l ，并取得与之对应的网页文件，将这个文件与用 户的查询内容对比，检查二者的相关性。 给每个u r l 赋相应的d e p t h 值。如果这个文件是相关的，那么这个文件中所出 现的u r l 的p o t e n t i a l _ s c o r e 将被赋值为l ，并获得一个最初设定的d e p t h 值。如果这个文 件不相关，那么将这个文件中出现的u r l 的p o t e n t i a l _ s c o r e 酸值为o 5 或0 两种值，获得 的d e p t h 值将减少，具体赋值情况如中维护方法所述。 将此文件中的u r l 按下面的方法加入到u r l 列表中1 1 9 】： 如果这个文件相关，则把这个文件前口w i d t h 个孩子( 口是预定义的大于1 的 常量) 加入至i u r lq u e u e 的前端。 如果这个文件不相关，则把这个文件前w i d t h 个孩子的u r l 加入到u r l q u “e 队列中紧挨着相关网页的孩子节点后面。 剩下的孩子u r l 加入到u r l - - q u e u e 的尾部( 也就是说只有在时间允许的情况 下才有可能被爬行) 。 在获取文件的时候，对w e b l 艮务器的传输速度进行监测，如果速率很低，则将 文件中的u r l 的d e p t h 设为0 。 在经过一段特定的时1 日j 之后，或u r lq u e u e 己为空时停止运行。 算法伪代码如下【l8 】： f i s h s e a r c h ( s t a r t i n g _ u r l s ，t o p i c ，、 r i d t h , d ) e n q u e u e ( u r l _ q u e u e ，s t a r t i n g _ u r l s ，d ) ；将种子u r l 入栈，深度为d i n tn u m v i s i t e d = o ： w h i l e ( n u m v i s i t e d o ) s t e p i ：i f ( 当前页面不相关) ( 对u r l _ l i s t 的前w i d t h 个孩子节点( c h i l d _ n o d e ) p e t e n t i a l s c o r e = o 5 ； 对剩余孩子节点，p o t e n t i a l _ s c o r e = o ： ) e l s e 对u r ll i s t 的前( 口w i d t h ) 个节点( a a 4 于预先设置的常量，一般为 1 5 ) p o t e n t i a l s c o r e = 1 ； 对所有剩余的孩子节点，p o t e n t i a l s c o r el - o ； s t e p 2 ：f o r ( e a c hui nu r l _ l i s t ) i f ( ui nu r l _ q u e u e ) 比较u r l _ q u e u e 中的s c o r e 和u 的s c o r e ，用最大值取代 u i 啦q u e u e 中的s c o r e ； 如果有需要，按照s c o r e 对u r l _ l i s t 排序； e l s e 如果有需要，按照p o t e n t i a l _ s c o r e 的大小在u r l l i s t 寻找合适位置 插入； s t e p 3 ：f o r ( e a c h u i n u r l _ l i s t ) 计算深度d e p t h ，d e p t h ( u ) i f ( 当前页面相关)、 d e p t h ( u ) = d ； e l s e d e p t h ( u ) = d e p t h ( p a g e ) 一1 ； i f ( ui nu r l _ q u e u e ) 比较u r lq u e u e 中的深度和d e p t h ( u ) ，用