（计算机应用技术专业论文）搜索引擎中网络爬虫的研究.pdf

摘要 搜索引擎作为信息检索技术在互联网时代的应用，使人们能够更有效的从互 联网获取各种资源。但随着互联网的发展，传统的搜索引擎，即通用搜索引擎 渐渐不能满足人们对信息检索服务日益增长的需求。近年来，面向主题的搜索 引擎应运而生。本文围绕主题搜索引擎，对主题搜索引擎中占有重要地位的主 题爬虫相关技术进行了研究和讨论。 网络爬虫用来从互联网上抓取页面。通用爬虫会从一些种子链接开始，目标 是获取互联网上所有的页面。而主题爬虫的目标是获取与特定主题内容相关的 页面，因此除了具有通用爬虫的基本功能外，还需要对页面的内容和链接进行 分析从而能够对爬虫爬行的路径进行指导和预测。主题网络爬虫选择什么样的 爬行策略对互联网进行访问，直接影响着其爬行的效率。本文着重研究并改进 了基于c o n t e x tg r a p h 的主题爬行算法，研究工作主要有以下几个方面： ( 1 ) 研究了搜索引擎中通用网络爬虫和主题网络爬虫的技术原理、工作流程， 着重分析了主题网络爬虫的主题爬行策略，对主题网络爬虫常用的基于链接分 析的爬行策略和基于内容分析的爬行策略进行分析比较。 ( 2 ) 针对传统的主题爬行算法不能很好解决“隧道现象 的问题，本文详细介 绍了一种基于c o n t e x tg r a p h 的主题爬行算法，它通过预测新抓取页面在c o n t e x t g r a p h 中所处的层次，能够指导网络爬虫沿着最有可能找到目标页面的路径爬 行，进而较好地解决“隧道现象的问题。 ( 3 ) 使用一种基于词频差异的特征选择方法和改进的t f - i d f 公式对基于 c o n t e x tg r a p h 的主题爬行算法进行了改进，加入词的类别权重作为对t f i d f 公 式的调整，以提高特征选择和评价的质量。 ( 4 ) 实现了一个主题爬虫原型，通过实验对各算法进行了分析和比较，验证了 本文改进的算法能够得到更加准确的文档集特征及权重，进而提高主题爬虫的 性能。 关键词：搜索引擎，主题爬虫，c o n t e x tg r a p h ，特征选择 a b s t r a c t t h es e a r c he n g i n ea st h ei n f o r m a t i o nr e t r i e v a lt e c h n o l o g yi nt h ei n t e r n e tt i m e s a p p l i c a t i o nm a k e st h ep e o p l em o r ee f f e c t i v et og a i nn e t w o r kr e s o u r c e s b u tw i t ht h e d e v e l o p m e n to fi n t e m e t ，t h et r a d i t i o n a ls e a r c he n 酉n e ，n a m e l yt h eg e n e r a ls e a r c h e n g i n ec a n n o ts a t i s f yt h ep e o p l e si n c r e a s i n g l yd e m a n dt ot h ei n f o r m a t i o nr e t r i e v a l s e r v i c e t h i st h e s i sr e s e a r c ha n dd i s c u s sc o r r e l a t i o nt e c h n i q u e st ot h ef o c u s e dc r a w l e r w h i c hh e l dt h ei m p o r t a n tp o s i t i o ni nf o c u s e ds e a r c he n g i n e w e bc r a w l e ri su s e dt od o w n l o a dw e bp a g e sf r o mi n t e r n e t s t a r t i n gf r o ms o m e s e e d i n gl i n k s ，g e n e r a lw e b c r a w l e rs e a r c h e sa l lt h ew e bp a g e st h r o u g h o u tt h ei n t e r n e t t h ef o c u s e dc r a w l e ra i mt og e tm o r cp a g e sr e l a t e dt ot o p i c ，a p a r tf r o mt h e f u n d a m e n t a lf u n c t i o no fg e n e r a lw e bc r a w l e r ，t h ef o c u s e dc r a w l e rs h o u l da b l et o a n a l y z el i n k sa n dc o n t e n ti nw e bp a g e s t og u i d ea n df o r e c a s tc r a w l e r sc r a w l i n gp a t h w h a tc r a w l i n gs t r a t e g yd o e st h ec r a w l e ru s e dt ov i s i tt h ei n t e r n e th a v eas i g n i f i c a n c e i m p a c to nt h ef o c u s e dc r a w l e r se f f i c i e n c y t h i st h e s i ss t u d i e da n di m p r o v e dt h e f o c u s e dc r a w l i n ga l g o r i t h mb a s e do nt h ec o n t e x tg r a p h t h em a i nr e s e a r c hw o r k sa s f o l l o w s ： ( 1 ) r e s e a r c ho ng e n e r a lc r a w l e ra n df o c u s e dc r a w l e r s t e c h n i c a l p r i n c i p l ea n d w o r k f l o w ；m a k eac a r e f u la n a l y s i so ff o c u s e dc r a w l e r sc r a w l i n gs t r a t e g y t h i st h e s i s i n t r o d u c ea n da n a l y s i sg o o da n db a dp o i n t so ft h ec r a w l i n gs t r a t e g i e sb a s e do nl i n k a n a l y s i sa n db a s e d o nc o n t e n ta n a l y s i sw h i c ha r eu s u a l l yu s e db yf o c u s e dc r a w l e r ( 2 ) t or e s o l v et h ep r o b l e mt h a tt r a d i t i o n a lf o c u s e dc r a w l i n ga l g o r i t h mc a n n o td e a l w i t h “t h et u n n e l ，t h i st h e s i si n t r o d u c e di nd e t a i lac r a w l i n ga l g o r i t h mb a s e do nt h e c o n t e x tg r a p h ，b yp r e d i c t i n gt h el e v e lo fw e bp a g e si nt h ec o n t e x tg r a p h ，t h e c r a w l i n ga l g o r i t h ma d v a n c e sa l o n gt h em o s tp r o m i s i n gp a t ht h a tl e a d st ot a r g e t d o c u m e n t sa tl o wc o s to fc r a w l i n gi r r e l e v a n tp a g e st of i n dt a r g e td o c u m e n t sq u i c k e r a n dr e s o l v e “t h et u n n e l ” ( 3 ) t oi m p r o v et h ef e a t u r es e l e c t i o na n da p p r a i s a lq u a l i t yu s e di n t h ec r a w l i n g a l g o r i t h mb a s e do nc o n t e x tg r a p h ，t h i st h e s i su s e da f e a t u r es e l e c t i o nm e t h o db a s e d o nt h ew o r df r e q u e n c yd i f f e r e n c ea n dam o d i f i e dt f - i d ff o r m u l aj o i n e dt h ew o r d s c a t e g o r yw e i g h t ( 4 ) ad e m os y s t e m - - f o c u s e dc r a w l e rw a sp r o p o s e di nt h i sp a p e r t h ee x p e r i m e n t r e s u l t ss h o wt h a tt h ef e a t u r es e l e c t i o nq u a l i t ya n dt h ef o c u s e dc r a w l e r sp e r f o r m a n c e c a n i m p r o v eb yt h ei m p r o v e da l g o r i t h mp r o p o s e di nt h i sp a p e r 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 , c o n t e x tg r a p h ，f e a t u r es e l e c t i o n h i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：夔煎日期： 竺：兰：堡 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：壅塞 导师( 签名) ：童l 垂k 日期：竺丝! ：丝 武汉理工大学硕士学位论文 1 1 选题背景 第1 章引言 人类社会的发展离不开知识的获取与发现，进入互联网时代以后，信息出现 了飞速地增长，对于网络上不断涌现的各种信息，人们的接受能力却是十分有 限的，这时人们就急切的需要一种技术手段，能够使信息的获取更加方便、准 确【1 1 。在这种需求的带动下，搜索引擎出现了，经过了几十年的发展，搜索引擎 现在已经成为了我们日常上网必备的工具之一，使用搜索引擎我们可以比较方 便地查找到所需要的信息，搜索也渐渐成为了人们开启互联网世界大门的一把 钥匙。 从技术的本质来讲，搜索引擎其实是信息检索技术在互联网时代的一种应用 表现形式。信息检索技术起源于对文献的参考查询和摘录索引工作，早在十九 世纪下半叶就已经开始对其进行相关的研究。信息检索包括对信息的存储、组 织、表现、查询、存取等几个方面1 2 。其中对信息的索引和检索是关键，通过对 信息合理的组织可以使用户能够更加方便的对其进行访问；如何将用户的要求 准确合理的表达出来也是一个问题，往往需要使用系统规定的查询语言将用户 的要求通过规范化的形式表达出来；根据用户提出的查找要求，系统接下来所 做的工作就是准确、快速的返回符合要求的内容。信息检索技术发展到今天已 经积累了许多成熟的理论，这些理论为搜索引擎的发展提供了强大的理论支撑。 1 2 关于搜索引擎与爬虫 搜索引擎的工作过程，主要包括三个步骤【3 】：从网上获取页面、建立索引、 从索引中查找结果并排序。 ( 1 ) 从网上获取页面：搜索引擎的网络爬虫程序每隔一段时间就会对网上的页 面进行遍历，从一些页面开始，通过页面上的链接爬行到其它的页面，反复地 进行这个过程，在爬行的过程中会对相应的页面进行存储，为下一步的工作提 供原始的页面数据【4 l 。 ( 2 ) 建立索引：搜索引擎的索引模块会对爬虫获取的页面进行分析，根据页面 武汉理工大学硕士学位论文 中的内容分析提取页面的相关信息，然后依据这些信息采用倒排的方式对它们 建立索引。倒排索引是一种基于分词来对文档集合进行索引的方式，倒排索引 通常由两个部分所组成：分词表和位置信息，分词表是由文档集合中所有分词 所组成的集合，系统在对页面进行分析的同时，还会记录下页面中各个分词在 文档中所处的位置，使用倒排索引的方式可以大大地提高查找的速度。 ( 3 ) 从索引中查找结果并排序：前两步都是在为这一步的工作做准备，这一步 也是搜索引擎中唯一直接与用户打交道的部分。搜索引擎会根据用户的要求， 找出符合用户要求的所有页面。根据在上一个阶段计算的每一个分词与拥有该 词的页面的相关程度，对返回的所有页面进行排序，相关程度高的在返回的结 果中会处于比较靠前的位置，被用户选择的可能性也就相应的增大。最后，系 统会将查找及排序的结果( 包括页面的地址和概述等信息) 综合起来返回给用 户。这个过程可以简要用图1 - 1 表示： 图1 - 1 搜索引擎的基本结构 对于搜索引擎来说，要进行检索，就必须要有检索的对象数据，爬虫的 产生主要就是为了解决数据的来源问题，爬虫在互联网中爬行，不断地获取新 的页面，然后将它们交给系统的其它模块做进一步地处理。1 9 9 4 年4 月，华盛 顿大学的b r i a np i n k e r t i o n 创建了w e b c r a w l e r ，w e b c r a w l e r 是第一个抓取整个网 页全文的爬虫程序，后来a o l 收购了w e b c r a w l e r ，让它运行在自己的网络上【列； 1 9 9 7 年，e x c i t e 购买了w e b c r a w l e r ，并且a o l 开始使用e x c i t e 来加强自己的 n e t f i n d ，w e b c r a w l e r 为之后许多的应用打开了大门。 2 早 由 武汉理工大学硕士学位论文 现在看来，网络爬虫程序几乎不可能获取网上全部的页面，因为在软硬件性 能不断提高的同时，互联网的规模也在以更快的速度增大，所以一个好的网络 爬虫程序需要能够在较短时间内获取尽可能多的页面。除此之外，随着网络中 信息快速的增长，通用的搜索引擎在多个方面都面临着挑战，为了解决这些问 题，出现了用于对指定的主题进行搜索的主题网络爬虫1 5 j 。主题网络爬虫能够根 据一定的页面及链接分析算法，尽可能地过滤掉与主题没有关系的页面与链接， 保留那些与主题关系比较密切的链接并将它们放入等待爬取的队列中；然后按 照一定的方法从等待爬取的队列中选择下一步将要处理的链接，不断地重复这 个过程，直到达到某个停止条件的时候结束。相比较来说，通用网络爬虫的目 标是尽可能多地收集网上的页面，在这个过程中它并不在乎页面处理的前后顺 序以及所收集页面的主题情况。但是主题网络爬虫则需要尽可能多的获取与事 先指定的主题关系比较密切的页面，这样做能够有效的提高网络爬虫在爬行时 的效率。 1 3 论文主要内容及组织结构 本文对主题网络爬虫通常使用的基于链接分析的爬行算法和基于内容分析 的爬行算法进行了介绍和分析，针对它们不能很好解决“隧道现象一的问题， 本文详细介绍了一种基于c o n t e x tg r a p h 的主题爬行算法能够比较好的解决这个 问题，它通过构造示例页面的c o n t e x tg r a p h 来预测新获取的页面与目标页面之 间的距离，距离较近的将优先得到处理。 基于c o n t e x tg r a p h 的主题爬行算法使用t f i d f 公式对文档中词的权值进行 计算，并据此对文档集合进行特征词集合的提取。然而通过t f i d f 公式计算得 到的词的权重不够准确，这会影响到特征选择的效果和主题爬虫的性能。针对 这个问题，本文使用一种基于词频差异的特征选择方法和改进的t f i d f 公式 对基于c o n t e x tg r a p h 的主题爬行算法进行了改进，加入了词所在类别的权重作 为对t f i d f 公式的调整，以提高特征选择的质量，实验表明这些改进能够得到 更加准确的文档集合的特征词集以及词的权重，进而提高主题爬虫的性能。 本文共分为五章，文章的结构以及各章主要内容如下： 第一章简要介绍了网络爬虫的相关背景，包括搜索引擎的基本原理，爬虫的 简史以及发展的情况等，最后给出了本文整体的组织结构。 第二章首先介绍了通用网络爬虫的相关情况，包括通用网络爬虫的原理、结 3 武汉理工大学硕士学位论文 构以及工作流程。然后介绍了主题网络爬虫的相关情况以及在主题网络爬虫中 使用的一些关键技术，详细研究了主题网络爬虫在爬行时使用的基于链接分析 的爬行算法和基于内容分析的爬行算法，并从理论上分析了它们的优点和缺点。 第三章研究了基于c o n t e x tg r a p h 的主题爬行算法，该算法能够避免基于内 容分析的主题爬行算法和基于链接分析的主题爬行算法普遍存在的局部最优的 问题，不仅能够在距离目标页面较近的地方表现出良好的性能，而且在距离目 标页面比较远的时候也能够有比较好的表现，相比较传统的主题爬行算法来说 具有比较明显的优势。在详细介绍该算法的基础上，本文引入了基于词频差异 的特征选择算法与改进的t f i d f 公式对基于c o n t e x tg r a p h 的主题爬行算法进 行了改进。 第四章设计了一个主题爬虫系统，对本文提出的算法进行验证分析比较。试 验表明改进的算法能够有效地提高爬虫系统的性能。 第五章对本文的主要工作进行了总结，分析了存在的不足，同时也提出了今 后需要进一步研究的工作。 4 武汉理工大学硕士学位论文 第2 章网络爬虫研究 网络爬虫程序其实是一个基于h i t p 协议的网络程序，这个名字的得来是因 为它像爬虫一样在互联网这张以页面为节点、以链接为边的大网上“爬行 。爬 虫从一些起始页面开始，在对这些起始页面进行分析以后，沿着从这些页面中 找到的链接再对其它的页面进行访问。网络爬虫程序主要应用于搜索引擎，除 此之外网络爬虫程序还可以用于对网站进行扫描：爬虫程序从网站的主页开始， 对整个站点进行扫描，进而得到这个站点所有页面文件的列表以及相互之间的 链接关系，这种扫描能够得到反映站点内容和结构等方面的信息，例如网站中 无效的链接，进而帮助管理员对网站进行管理。c , o o g l e 就提供了这样的工具： 网站管理员中心( h t t p ：w w w g o o g l e c o m w e b m a s t e r s ) 。 作为搜索引擎中非常核心的一部分。作为爬虫来讲，需要其尽可能多、尽可 能快的为搜索引擎提供页面数据。如果一个搜索引擎的其它部分设计的非常优 秀，却没有足够的数据来支持，仍然不是一个优秀的搜索引擎。如果把搜索引 擎中的索引模块与爬虫模块比做是搜索引擎这个大机器的两个齿轮，那么一个 好的搜索引擎设计，就是要求将这两个齿轮的转速相匹配，这样才能够紧密配 合在一起，相互协同工作。 2 1 通用爬虫研究 2 1 1 通用爬虫的工作流程 通用网络爬虫工作的流程一般为：爬虫程序从一些起始链接开始，建立 h t f p 通信连接，发送h 1 曙请求，获得帅响应后保存对应的页面文件，为 下一步的工作提供原始的数据。通用网络爬虫在爬行的过程中通常需要维护一 个还没有访问链接的集合、一个已经访问过链接的集合和一个不可访问链接的 集合：将被网络爬虫处理过的页面对应的链接放到已经访问链接的集合中；如 果在爬行的过程中发现无法访问的页面，则将其链接放到不可访问的链接集合 中；在获取页面的h t m l 文件以后，通过分析，对其中的链接地址进行提取， 过滤掉那些已经访问过或者不能访问或者已经在等待访问的队列中的链接，然 5 武汉理工大学硕士学位论文 后将余下的链接作为新的等待处理的链接加入到等待访问的链接集合中，爬虫 程序不断地重复这个过程直到满足一定的停止条件，结束本次的爬取工作。通 用网络爬虫的一般结构如图2 - 1 所示： 一 提取链接 存储h t m l 文件 指导爬取 图2 1 通用爬虫的结构 ( 1 ) 页面抓取模块：这个模块的主要作用是使用h t y p 协议对h t m l 页面文件 进行下载，然后将获取到的页面文件交由下一个模块做进一步的处理。 ( 2 ) 链接分析模块：这个模块作为网络爬虫的核心部分，主要功能是对页面抓 取模块获取的页面进行处理，提取并分析其中的链接，然后将这些链接按照所 属类别放入到各个链接集合中。此外，从页面中提取的链接一般情况下格式并 不一样：有可能是包含了协议的名称、主机的名称以及资源文件名称的规范形 式，也可能是省略了一些内容的不规范形式，为了便于下一步对这些链接的处 理，需要事先将它们转换成规范统一的链接格式。 ( 3 ) 链接队列：存放经链接分析模块处理后得到的各个链接队列。在爬虫爬行 的过程中，爬虫会根据这些队列选择下一个处理的目标。在实际应用中一般还 需要对这些队列的大小进行控制，这样做可以减小爬虫执行爬行任务时服务器 的压力，提高爬行的速度和效率，防止因为等待爬取队列中的链接数量过多而 加重服务器的负担。但是，如果将等待下载的链接队列规定地太小，又可能造 成队列很快为空，爬虫因为没有新的等待处理的链接而停止。 就爬行的方式来说，通用网络爬虫主要是基于图论来工作的：以事先选取的 一些种子链接作为起点，使用宽度或者深度优先的方式对网络进行遍历，其目 标是能够尽可能的覆盖整个网络。 6 武汉理工大学硕士学位论文 广度优先遍历( 又称宽度优先遍历) 是图论中经常用的遍历算法之一，这个 算法是很多重要图论算法的基础，比如d i j k s t r a 最短路径算法和p r i m 最小生成树 算法都使用了这种遍历方法的思想【3 5 l 。这种遍历方式使用了一个先入先出的队 列，它先对一个页面上所有的链接进行处理，然后才继续处理这个页面所指的 下一层页面，直到形成回路或者遍历完成时终止，如图2 2 所示。这种遍历方式 的优点和缺点都比较明显：对于网站的层次比较少的情况，这种遍历方式的收 敛速度比较快；但是对于那些规模比较大，网站层次比较多的站点则存在难以 深入的问题，对于那些所处位置比较深的页面可能难以进行有效的获取。 图2 2 基于广度优先遍历的爬行 与广度优先遍历对应的深度优先遍历则是尽可能深地对图进行遍历。这种方 式使用了一个先入后出的队列，深度优先遍历首先从一个页面开始，查看这个 页面中是否还有尚未处理的链接，如果有的话取出其中一个还没有处理的链接， 将其作为一条爬行的路径，沿着这条路径一直地进行下去，直到到达这条路径 的终点，即到达一个不含有任何链接的页面或者已经形成回路，然后沿着这条 来访的路径回溯，再访问这条路径上其它还没有处理的节点，这个过程一直持 续到起始页面上所有的链接都被处理完毕时为止。这种遍历方式的优点在于对 于那些规模比较大的站点，能够获取到更深的页面，缺点在于有可能会造成爬 虫的陷入问题，使服务器的压力变大，因此通用网络爬虫一般情况下并不使用 这种遍历的方式。 7 武汉理工大学硕士学位论文 2 1 2 爬虫程序的实现方式 构造网络爬虫程序有两种方式：第一种是把网络爬虫程序设计成递归的形 式，第二种是采用非递归的形式来实现【1 1 1 。 递归是指程序在运行的过程中直接或者间接调用自身而产生的重入现象，采 用递归方式实现的程序具有结构比较清晰、可读性比较好、容易理解等优点【3 5 1 ， 通用爬虫使用递归实现的伪代码如下： v o i dr e c u r s i v e s p i d e r ( s t r i n gl i n k ) d o w n l o a dl i n k p a r s el i n k f o re a c hl i n kf o u n d c a l l r e c u r s i v e s p i d e r ( w i t hf o u n dl i n k ) e n d f o r p r o c e s st h ep a g ej u s td o w n l o a d e d 虽然在某些情况下使用递归的方式来实现网络爬虫程序是合理的，但这只有 在爬虫所访问的页面数量比较少的时候才是合适的。考虑到在实际的应用中网 络爬虫程序需要具有能够访问大量页面的能力，而递归程序在运行的时候需要 把每次递归的过程都压入堆栈进行保存，如果递归程序要运行很多次的话，这 个堆栈就会变的非常的大，这样就有可能会耗尽系统内存导致程序终止运行。 所以对于大型的网络爬虫而言，一般情况下是不会使用递归作为其程序实现方 式的。 构造网络爬虫程序的第二种思路是使用非递归的方式来实现网络爬虫程序， 这种方式需要另外使用一个队列。当使用非递归方式的时候，给定网络爬虫程 序一个要访问的页面，它会把这个页面加入到等待访问的队列中。当网络爬虫 程序发现新的链接时，也会把它们加入到这个队列中。当网络爬虫程序处理完 当前的页面后，它就会从队列中取出下一个需要处理的对象。爬虫程序采用非 递归实现的伪码如下： 8 武汉理工大学硕士学位论文 b r e a d t h f i r s t ( s t a r t i n g _ u d s ) f o re a c hl i n k ( s t a r t i n g _ u r l s ) e n q u e u e ( f r o n t i e r ，l i n k ) ； ) w h i l e ( v i s i t e d m a x b u f f e r ) d e q u e u e _ l a s t _ l i n k s ( f r o n t i e r ) ； ) ) ) 虽然以上伪码中只出现了一个队列，但是在实际的程序中网络爬虫程序需要 同时使用四个队列i l l l ：等待处理的队列中保存的是等待被网络爬虫程序处理的 链接，就像在计算机进程调度中进程所处的就绪状态；下一个被爬虫处理的链 接会被先被放进正在处理的队列，就好像进程调度中进程从就绪态转为运行态； 在爬虫访问过程中无法达到的页面的链接将被放入无效链接队列中，放进这个 队列中的链接以后将不再被处理；已经完成爬取的队列保存的是已经过爬虫处 理并且能够访问存储的页面所对应的链接。 2 2 文本信息模型 对文本的分析和处理是整个信息检索工作的基础，为了便于计算机对文本的 分析和处理，我们首先要清楚在计算机中，文本是如何表示和定义的，这就需 要建立一种在计算机中对文本进行描述的数学模型，也就是文本模型。文本模 型是能够被计算机识别的一种信息格式，这种格式应当具有可识别、冗余度低 等特点1 1 3 j 。以下是三种比较常用的文本信息模型： ( 1 ) 布尔模型1 1 4 】：使用一组特征词来对一个文本进行表示。 ( 2 ) 向量空间模型：文本由一个特征词的列表组成。这些特征词会根据它们在 文档中出现的次数，所处的位置等得到相应的权值1 1 5 , 1 6 。 ( 3 ) 概率模型：通过词的概率值来表示这些词在相关的文档以及不相关的文档 9 武汉理工大学硕士学位论文 中出现的可能性，然后计算文档之间关系的远近。 目前主题网络爬虫对页面的描述和主题相关性的判断主要还是使用向量空 间模型。向量空间模型基于这样一个假设：即组成文档的词与它们出现的前后 顺序是没有关系的，同时这些词对于表征文档的主题所起到的作用也是相互独 立的。所以可以把文档看作是一些词组成的集合，即把文档d ；看作是由一组词 ( 互，疋，l ) 构成的，对于每一个词正，会根据它对表征文档主题的重要 程度赋予一定的权值嵋i r 刀。如果将互，瓦，瓦看成一个n 维坐标系，m ， ，m 为对应的坐标值，那么一个文档就可以看作是在向量空间中的一个点， 如图2 3 所示。 图2 3 向量空间模型示意图 文档在向量空间中使用一个列向量来表示： 巧。五 ( 2 - 1 ) 其中刀表示向量空间中全部诃l 的数量；i 表示特征词；表示特征词的权 值。文档集合在向量空间中的表示是一个矩阵的形式： 五 瓦 己 乙呢。岷：形， ( 2 2 ) 在向量空间模型中，文档之间相似的程度可以通过计算文档向量之间的夹角 c o s 值来得到【冽： 1 0 匕 屹 k 武汉理工大学硕士学位论文 唧，。褊。 - 1 ( 2 3 ) 对于主题相关性的判断，假如某个主题表示为虿一( w l 灯，w ：，w i 田) ，则计算 文档d ，与主题厅之间相关联程度的公式如下： 咖囝。编。 f 善 ( 2 - 4 ) 如果计算得到的结果大于一个事先设定的值口，则可以认为这个页面与主题 的关系比较密切，将其存储起来，否则就丢掉这个页面。这个公式中的彤；表示 为：w , j t f f i f ；, jx l o g n 乃；正，表示为：正，一i 聂f 了r e q 而, , s，加吼，表示第f 个词在 第，个文档中出现的频率。 形，就是t f i d f 公式，公式中的是文档集合中文档总的数量，刀；是包含 了词七；的文档的数量。如果一个词只在很少的文档中出现，我们希望它能够作 为文档的特征，那么这个词的权重就应该比较大；反之，如果一个词在大量的 文档中出现，它就不能有效的对文档进行表征，因此它的权值应该比较小。 i t i d f 公式简单且容易实现，但比较粗糙，在后面的章节中本文将基于词所属 类别的权重对其进行改进。 2 3 主题爬虫原理 通用网络爬虫要能够尽可能多地收集页面，在这个过程中并不考虑处理页面 的前后顺序以及所获取的页面是否与主题相关。主题网络爬虫在传统爬虫基础 上，加入了w e b 数据挖掘等相关技术使爬虫在爬行的过程中能够尽可能地沿着 能够找到目标页面的路径进行爬行。从而提高现有搜索引擎查找的精度与更新 的周期。 主题网络爬虫的基本思想是根据事先指定的主题，对于已经下载的页面内容 和页面中的链接进行分析，据此计算当前页面与主题相关的程度并预测下一个 需要处理的链接，以保证在爬行的过程中尽可能多地获取与主题关系比较密切 的页面，尽可能少地对不能找到目标页面的路径进行爬取。在这个过程中，主 武汉理【大学硕士学位论文 题网络爬虫需要使用一定的算法尽可能地过滤掉页面中与主题没有太大关系的 链接，保留那些可能与主题关系比较密切的链接并将其放入相应队列中；然后 使用一定的方法从队列中选出下一步要处理的页面的链接。图2 4 是传统网络爬 虫与主题网络爬虫在工作流程上的对比。 传统爬虫 图2 4 传统爬虫与主题爬虫工作流程对比 在结构上，与通用搜索引擎所使用的网络爬虫不太一样，主题网络爬虫除了 应该具有能够提取页面中的链接和抓取页面的模块以外，还需要具有能够计算 页面主题相关程度和预测链接的主题相关程度的模块。具体来讲主题网络爬虫 除了具有一般爬虫的功能之外，还需要解决以下一些问题【5 】： ( 1 ) 怎样规范化的定义主题，即使用什么样的形式化定义或者模型来准确、灵 活的描述用户所指定的抓取目标。 ( 2 ) 怎样计算与判断页面与主题之间相关的程度。 ( 3 ) 怎样确定等待抓取链接的优先级别。 ( 4 ) 怎样提高主题爬虫对网络的覆盖面。由于隧道现象的存在【2 4 j ，爬虫如何通 旦一 里一 由 武汉理 。走学硕士学位论文 过一些链接穿过与主题不太相关的页面到达目标页面也是主题网络爬虫面临的 一个问题，而这与( 3 ) 中提到的尽量不爬取与主题关系没有太大关系的页面是 比较矛盾的，如何处理这对矛盾对主题网络爬虫而言又是一个挑战。 总的来说，对于主题网络爬虫而言，抓取目标的描述也就是主题的定义是页 面分析算法与主题爬行算法的基础，而页面分析算法和主题爬行算法是决定爬 虫的特点和主题搜索引擎所能提供服务的关键所在。对主题网络爬虫的研究也 就主要围绕这几点来展开。 2 4 主题爬行策略 由于页面中存在着各种各样的链接，即使是目标页面也会包含一些指向与主 题不相关页面的链接。因此，爬虫在爬行阶段所需要解决的一个重要问题就是： 从等待处理的链接队列的大量链接中，优先选择出与那些能够到达或者通过其 能够找到目标页面的链接进行爬取。图2 - 5 形象的说明了这点，在图2 5 中标为 黑色的为与主题相关的页面，即目标页面，要找l o 这些页面，通用爬虫是通过 遍历整个圈的方式去查找，而主题爬虫则是使用更加智能的方法优先沿着那些 最有可能找到目标页面的路径进行爬行( 围中加粗的箭头表示爬虫的爬行路径， 其中主题爬虫部分标注的路径的是最理想的情况，即只针对能够找到目标页面 的路径进行爬行，实际的情况往往达不到这种理想的效果，可能会漏掉一些能 够找到目标页面的爬取路径，也可能对一些找不到目标页面的路径进行爬行) 。 通用爬虫 主恿爬虫 图2 - 5 普通爬虫和主题爬虫爬行策略对比 武汉理工大学硕士学位论文 主题爬行算法是主题搜索引擎区别于通用搜索引擎的核心所在，在主题爬行 的过程中，链接所得到的分数越高，它获得处理的优先级就越高。反之，如果 经过预测，发现某个链接与主题没有太大的关系，则会放弃这个链接。通过这 种方式，爬虫就减少了对不能找到目标页面的路径的爬取，从而保证了爬行的 效率和质量。但是，这个过程也可能将潜在的能够到达目标页面的路径去掉。 因此，爬行算法的好坏将直接影响着网络爬虫爬行的效率以及获取页面的质量。 好的主题爬行算法可以大大的提高所获取的页面与主题相关的可能性，同时有 效的减少主题网络爬虫因为对不能找到目标页面的路径进行处理而产生的额外 开销，由此可见主题爬行算法的研究对于主题爬虫而言具有重大的意义。目前 常用的主题爬行算法主要包括两大类：基于内容分析的算法和基于链接分析的 算法。 2 4 1 基于内容分析的爬行算法 基于内容分析的主题爬行算法主要是利用页面的内容特征对页面与主题的 相关程度进行评价，进而对爬虫爬行的过程进行指导。比较有代表性的有：b e s t f i r s ts e a r c h ，f i s hs e a r c h ，s h a r ks e a r c h 等三种算法l 叭。 b e s tf i r s ts e a r c h 算法的基本思想是利用如果某个页面与主题相关，那么与之 邻近的页面通常也与主题相关这一页面分布的主题团特征，通过分析当前已经 获取的页面，使用一定的算法来预测与其邻近页面的主题相关情况，然后使用 最好优先的原则每次优先选择经预测最有可能找到目标页面的链接作为下一个 处理的对象。与主题关系比较密切的页面，它所包含链接的优先级就高，这样 就确定了等待处理的链接队列中链接的前后顺序。如果等待处理的队列已经满 了的话，则会将优先级最低的链接从这个队列中删除。b e s tf i r s ts e a r c h 算法的处 理过程可以简要用图2 6 来表示： 1 4 武汉理工大学硕士学位论文 图2 - 6b e s tf i r s ts e a r c h 算法 这个算法比较容易实现并且效率较高，因此得到广泛的使用，在主题爬虫研 究领域，通常将其作为对算法性能进行比较的基础，这也是在本文后面的实验 中选择该算法作为对比对象的原因。但该算法也有缺点：使用这种算法的网络 爬虫在距离目标页面较近的地方爬行的时候性能较好，但是在距离目标页面较 远的地方进行爬行时，性能下降的比较厉害。因此b e s tf i r s ts e a r c h 算法只能算是 一种局部最优的算法。b e s tf i r s ts e a r c h 算法的伪码如下所示： b f s ( t o p i c ，s t a r t i n g _ u r l s ) f o re a c hl i n k ( s t a r t i n g _ u r l s ) e n q u e u e ( f r o n t e r ，l i n k ) ； w h i l e ( v i s i t e d m a x _ b u f f e r ) d e q u e u e _ b o t t o m _ l i n k s ( f r o n t i e r ) ； ) ) f i s hs e a r c h 算法是1 9 9 3 年由荷兰t u e 大学的d eb r a 教授提出的一种主题爬 武汉理工大学硕士学位论文 行算法。他将网络爬虫在网络中爬行的过程比喻为一群鱼在大海中寻找食物的 过程。算法中的每一条鱼代表一个链接，当鱼找到食物( 即通过该链接发现目 标页面) 时，它的生存能力就会增强( 沿着这个链接方向的搜索深度增加) ，并 且它后代的生存能力与它一样( 即后代链接的搜索深度保持不变) 。在这个过程 中，页面与主题之间的相关程度使用一种二值分类器来进行衡量，使用这种分 类器得到的预测结果只有是与否两种情况。如果没有发现食物( 即通过该链接 没有发现目标页面) 时，它本身的生存能力保持不变( 这个链接本身的搜索深 度不变) ，但是它后代的生存能力会降低( 后代链接的搜索深度减一) ；如果沿 着某个方向一直找不到新的食物( 如果沿着某个方向经过一些链接后仍然没有 找到目标页面) ，那么它的生存能力会逐渐降低直至死去( 不再沿这个方向继续 爬行) 1 2 1 】。f i s h s e a r c h 算法具有动态的特点，同时相对来说比较容易实现，但 是它对页面与主题之间相关性的判断仅仅是一种简单的相关或者不相关的二值 判断，显得比较粗糙。 m h e r s o v i c i 等将f i s hs e a r c h 算法进一步拓展为s h a r ks e a r c h 算法。与 f i s hs e a r c h 算法所不同的是，这种算法考虑到f i s hs e a r c h 算法仅仅通过简单的 是与否进行页面相关性的判断显得过于粗糙，因而使用了向量空间模型，对主 题相关性的计算进行改进。页面与主题之间的相关程度使用向量空间模型计算 得到一个介于0 到1 之间的连续值。与f i s hs e a r c h 算法相比，s h a r ks e a r c h 算法 的准确度有所高，能够更好地对爬虫爬行的方向进行指导，从而进一步提高爬 虫爬行的效率。s h a r ks e a r c h 算法的伪码如下所示： s h a r k ( t o p i c ，s t a r t i n g _ u r l s ) f o re a c hl i n k ( s t a r t i n g _ _ u r l s ) s e t _ d e p t h ( 1 i n k , d e p t h ) ； e n q u e u e ( 丘o n t e r ，l i n k ) ； ) w h i l e ( v i s i t e d o ) f o r e a c ho u t l i n k ( e x t r a c t _ l i n k s ( p a g e ) ) s c o r e = o - r ) n e i g h b o r h o o d _ s c o r e ( o u t l i n k ) + r i n h e r i t e d _ s c o r e ( o u t l i n k ) ； 1 6 武汉理工大学硕士学位论文 i f ( p a g e s c o r e 0 ) s e t _ d e p t h ( o u t l i n k ，d e p t h ) ； e l s e s e t _ d e p t h ( o u t l i n k ，d e p t h ( 1 i n k ) 1 ) ； e n q u e u e ( f r o n t e r ，o u t l i n k ，s c o r e ) ； 坂f x o n t e r m a x _ b u f f e r ) d e q u e u e _ b o t t o m _ l i n k ( f r o n t e r ) ) ) 以上讨论的三种算法是在主题爬虫中基于内容分析的爬行算法。它们强调了 文本内容对指导主题爬行的重要性，但是忽略了链接之间的结构在爬行的过程 中所起的作