（计算机应用技术专业论文）基于网站目录及链接关系的spider爬行策略的研究与实现.pdf

摘要 基于网站目录及链接关系的s p id e r 爬行策略的研究与实现 摘要 随着互联网( i n t e m e t ) 近几年来的飞速发展，互联网上提供的信 息也呈现爆炸式的增长态势，面对w e b 信息以几何级数不断增长的 情况，如何能够快速获取对用户更有价值的、更有质量的信息便成为 了研究的热点之一。网络机器人s p i d e r 是整个搜索引擎系统的重要组 成部分，它是搜索引擎的数据来源，s p i d e r 的效率决定着整个搜索引 擎系统的内容质量的高低、信息能否及时的更新。 本文首先从搜索引擎的发展和种类出发，研究了搜索引擎的基本 组成工作原理和网络机器人的组成体系结构，重点分析了基于网页质 量研究的网络机器人的爬行策略。通过对w e b 结构上的挖掘分析， 结合对链接种类的分析，设计了一种新的针对高质量网页及潜在的高 质量网页为爬行目标的网络机器人爬行策略。本文的主要研究内容主 要包括以下几个方面： 1 通过对一般网络机器人的体系结构的分析，以及对j e f f h e a t o n s p i d e r 开源爬虫的研究，提出了本文所设计的网络爬虫的体系结构。 2 对基于网页质量优先爬行的几种网络机器人爬行策略进行了 分析和比较。 3 对w e b 的结构形式进行了分析，结合对网页间链接的分类研 究，提出针对高质量网页和潜在高质量网页为目标的网络机器人爬行 策略。 4 通过对实验数据进行分析，并与b a c k l i n k 算法网络机器人进行 比较，证明了本文所设计的爬行方案的可行性和必要性。 5 对运行结果和下一步本课题的实现内容做了分析和简单的展 北京化工人学硕t - 学位论文 望。 关键词：链接分析，网站目录，爬虫，高质量网页； a b s t r a c t r e s e a r c ha n di m p l e m e n t a t i o no fw e b d i r e c t o r ya n d l i n k r e l a t i o n s h i pb a s e ds p i d e rc r a w l i n gs t r a t e g y a b s t r a ct w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，i n f o r m a t i o np r o v i d e db yt h e i n t e r n e th a v es h o w ne x p l o s i v eg r o w t h i nt h ef a c eo fm a s s i v ea n d c o n s t a n t l yu p d a t e di n f o r m a t i o no nt h ei n t e r n e t ，s e a r c he n g i n e sp r o v i d ea q u i c ka n de a s yf o rp e o p l et of i n di n f o r m a t i o nt h ew a y t h r o u g ht h eu s eo f s e a r c he n g i n e s ，u s e r sc a nb r o w s et h es e a r c hr e s u l t sp a g eo nt h ef a c eo f w e bi n f o r m a t i o ng r o w i n gg e o m e t r i c a l l y ，h o wt h eu s e rc a nf a s ta c c e s st o m o r ev a l u a b l ea n dm o r ei n f o r m a t i o nh a sb e c o m eo n eo ft h eh o t s p o t s n e t w o r kr o b o ts p i d e ri sa ni m p o r t a n tc o m p o n e n to ft h es e a r c h e n g i n ei t ，i td e t e r m i n e s t h eq u a l i t yo fc o n t e n to ft h ee n t i r es e a r c h e n g i n es y s t e m ，d e t e r m i n e si ft h ep a g e sc a nb eu p d a t e di nt i m e t h i sp a p e rs t a r tf r o mt h ed e v e l o p m e n ta n dt h es o r t so fs e a r c he n g i n e ， s t u d i e dt h es t r u c t u r eo fs e a r c h e n g i n e a n dt h e c o m p o s i t i o n o ft h e s p i d e r ，f o c u s e do na n a l y z i n gt h es p i d e rc r a w l i n gs t r a t e g yw h i c hb a s e do n h i g l lq u a l i t yw e bp a g e s t h r o u g hs t u d y i n gt h es t r u c t u r eo fw e ba n d a n a l y z i n gt h es o r t so fl i n k s ，d e s i g n e dan e ws p i d e rc r a w l i n gs t r a t e g y w h i c hf o c u s e do nb o t ht h eh i g hq u a l i t yw e b p a g e sa n dt h ep o t e n t i a lh i g h q u a l i t yw e bp a g e s t h em a i n r e s e a r c hc o n t e n t sm a i n l yi n c l u d et h e f o l l o w i n g ： 1 t h r o u g ht h ea n a l y s i so nt h es t r u c t u r eo fn o r m a ls p i d e ra n dt h e s t u d yi nj e f fh e a t o ns p i d e r , d e s i g nt h es t r u c t u r eo fs p i d e ru s i n gt h e s t r a t e g yd e s i g n e di nt h i sp a p e r 2 a n a l y za n ds t u d ys o m ek i n d so fs p i d e rc r a w l i n gs t r a t e g y i i i 北京化t 火学硕。l ：学位论文 w h i c hb a s e do nt h eq u a l i t yo ft h ew e b p a g e s 3 a n a l y zt h es t r u c t u r eo ft h ew e b ，a n dt h es o r t so fl i n k s ，d e s i g n an e ws p i d e rc r a w l i n gs t r a t e g yw h i c hf o c u s e do nt h eb o t ht h eh i g h q u a l i t ya n dt h ep o t e n t i a lh i g hq u a l i t yw e bp a g e s 4 t h r o u g ht h ea n a l y s i so ft h ee x p e r i m e n t ，a n dt h ec o m p a r i s i o n w i t ht h eb a c k l i n ks t r a t e g y , p r o v et h ef e a s i b i l i t ya n dn e c e s s i t yo ft h e s p i d e rc r a w l i n gs t r a t e g yd e s i g n e di nt h i sp a p e r 5 s u mu pa n dg i v et h ea n a l y s i sa n das i m p l eo u t l o o ko ft h en e x t s t 印o ft h es u b j e c t k e yw o r d s ：h y p e r l i n k a n a l y s i s ；w e bd i r e c t o r y ；s p i d e r ； h i g h q u a l i t yw e bp a g e s ； 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：日期： 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名： 导师签名： 日期：塑皇：兰：皇 日期：2 竺z ：兰：主 第一章引言 1 1 课题研究目的和意义 第一章引言 近年来，随着w w w 的飞速发展，根据最近调查报告显示，截至2 0 0 8 年6 月，中国网站数量已经达到1 9 1 万个，半年内增加了4 1 5 万个，比2 0 0 7 年同期 增加了6 0 7 万个，年增长率达到4 3 6 。其中增长最快的是c n 域名下的网站， 目前c n 下网站数已达1 3 7 万，年增长率达到1 3 7 5 【l 】。除了不断有新的网页出 现外，旧的网页也可能会因为各种原因删除，有研究【2 】指出：5 0 网页的平均生 命周期大约为5 0 天。在网页数量激增，大量网页不稳定的情况下，网页之间也 存在链接关系，这种链接关系是：网站内部是有序的、层次清晰的；网站外部之 问的链接关系则是复杂的、随意的、层次不清晰的。如果把w e b 页面看作节点， 页面间的超链接看作边，那么整个万维网可以看作一个巨大的有向图，也称之为 网络图。整个w e b 图中大约有9 2 的节点是相互连通的【3 】，在这种情况下如何 才能高效快捷地为用户找到自己所需要的内容，就成为当今搜索引擎要解决的一 个重要问题。通过对w e b 的结构挖掘能够获得比较好的爬行效果。w e b 结构挖 掘的主要内容在于超链接分析，即通过分析页面的链接关系来研究网页的引用关 系， 从而发现有用模式，提高搜索质量【4 5 】。 面对数量庞大的网页，如何快速高效的获取用户所需要的信息就是当前搜索 引擎要解决的一个重要课题。 1 2 搜索引擎的发展历程及现状 1 2 1 搜索引擎发展历程 9 0 年初当时万维网( w o r l d w i d e w e b ) 还未出现，为了查询散布在各个分散的 主机中的文件，曾有过a r c h i e ，g o p h e r 等搜索工具，随着互联网的迅速发展， 基于h t t p 访问的w e b 技术的迅速普及，他们就不再能适应用户的需要【6 】。在 1 9 9 4 年1 月，第一个既可搜索又可浏览的分类目录e i n e tg a l a x y ( t r a d e w a v e g a l a x y ) 上线，它还支持g o p h e r 和t e l n e t 搜索。同年4 月，y a h o o 目录诞生， 随着访问量和收录链接数的增长，开始支持简单的数据库查询。这就是我们说的 早期的，目录导航系统，他们的缺点网站收录更新都是要考人工维护，所以在 信息量剧增的条件下，就不是非常受用了。 1 9 9 4 年7 月，l y c o s 推出了基于r o b o t 的数据发现技术，并支持搜索结果相 北京化t 人学硕 ：学位论文 关性排序，并且他第一个开始在搜索结果中使用了网页自动摘要。i n f o s e e k 也是 同时期的一个重要代表，他们是搜索引擎史上一个重要的进步。 1 9 9 5 年，一种新的搜索引擎工具出现了元搜索引擎，第一个元搜索引 擎是华盛顿大学的学生开发的m e t a c r a w l e r 。用户只需提交一次搜索请求，由元 搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎，并将从各独立搜 索引擎返回的所有查询结果，集中起来处理后再返回给用户。 1 9 9 5 年1 2 月a l t a v i s t a 推出了大量的创新功能使它迅速到达当时搜索引擎的 顶峰，它第一个支持自然语言搜索的搜索引擎，具备了基于网页内容分析，智能 处理的能力，第一个实现高级搜索语法的搜索引擎( 如a n d ，o r ，n o t 等) ，同 时a l t a v i s t a 还支持搜索新闻群组( n e w s g r o u p s ) ，搜索图片等具有划时代意义的 功能。同时期还有i n k t o m i ，h o t b o t 等搜索引擎。 1 9 9 7 年8 月n o r t h e m l i g h t 公司正式推出搜索引擎，它第一个支持对搜索结 果进行简单的自动分类，也是当时拥有最大数据库的搜索引擎之一。 1 9 9 8 年l o 月，g o o g l e 诞生。它是目前最流行的搜索引擎之一，具备很多独 特而且优秀的功能，并且在界面等实现了革命性创新。 1 9 9 9 年5 月，f a s t ( a l l t h e w e b ) 公司发布了自己的搜索引擎a l l t h e w e b ，它 的网页搜索可利用o d p ( o p e nd i r e c t o r ya d d r e s s ) 自动分类，支持f l a s h 和p d f 搜索，支持多语言搜索，还提供新闻搜索、图像搜索、视频、m p 3 、和f t p 搜 索，拥有极其强大的高级搜索功能。它曾经是最流行的搜索引擎之一，后在2 0 0 3 年2 月被o v e r t u r e 收购。 在中文搜索引擎领域，1 9 9 6 年8 月成立的搜狐公司是最早参与作网络信息 分类导航的网站，曾一度有“出门找地图，上网找搜狐的”美誉。由于其人工分类 提交的局限性，随着网络信息的暴增，逐渐被基于r o b o t 自动抓取智能分类的新 一代信息技术取代。 台湾中正大学吴升教授所领导的g a i s 实验室1 9 9 8 年1 月创立了o p e n f i n d 中文搜索引擎，是最早开发的中文智能搜索引擎，采用g a i s 实验室推出多元排 序( p o l y r a n k t m ) 核心技术，截止2 0 0 2 年6 月，宣布累计抓取网页3 5 亿，开始进 入英文搜索领域。 北大天网是教育网最流行的搜索引擎，它由北大计算机系网络与分布式系统 研究室开发，于1 9 9 7 年1 0 月2 9 日正式在c e r n e t 上提供服务，2 0 0 0 年初成 立天网搜索引擎新课题组，由国家9 7 3 重点基础研究发展规划项目基金资助开 发，收录网页约6 0 0 0 万，利用教育网优势，有强大的邱搜索功能。 百度中文搜索由超链分析专利发明人、前i n f o s e e k 资深工程师李彦宏和好友 徐勇2 0 0 0 年1 月创建，目前支持网页信息检索、图片、f l a s h 、音乐等多媒体信 2 第章引言 息的检索。并且百度在中文领域第一个开始使用p p c ( p a y - p e r - c l i c k ， 付费，即用户点击广告后广告主才为此付费) 经营模式。 2 0 0 2 年开始进入搜索引擎市场的中搜是由慧聪国际主持开发的， 域的后起之秀。目前处于起步阶段，技术没有特别见长的优势。 1 2 2 搜索引擎分类 即按点击 是搜索领 随着信息的爆炸式增长，各种各样的搜索引擎也如雨后春笋般大量出现，在 美国2 0 0 7 年的一项针对搜索引擎的调查中发现，g o o g l e ，y a h o o ，m s n ，a o l 和a s k 占据了美国9 8 3 左右的搜索引擎市场。但除此之外，在美国还有其他 1 5 9 1 个搜索引擎在服务着，还有成百上千的针对特殊语言和国家的搜索引擎， 如果计算上某些网站提供的自己网站站内的搜索引擎，那搜索引擎的数量会是以 万来计算网。如此大量的搜索引擎究其工作原理特点，可以分为以下几个种类【8 】： ( 1 ) 基于网络机器人的搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、a l t a v i s t a 等，国内著名的有百度( b a i d u ) 。它们都是通过从互联网上提取的各个网站的信 息( 以网页文字为主) 而建立的数据库中，检索与用户查询条件匹配的相关记录， 然后按一定的排列顺序将结果返回给用户，因此它们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己的 检索程序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人”( r o b o t ) 程序，并 自建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的几家引擎 阴；另一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如l y c o s 引擎。 ( 2 ) 基于目录分类索引的搜索引擎 目录分类索引虽然有搜索功能，但严格意义上并不算是真正的搜索引擎，仅 仅是根据目录分类把网站进行分类列表而已。这类搜索引擎并不使用网络机器人 下载w e b 文档，而是人工收集或者w e b 站点作者主动提交网站的分类信息。目 录一般也不对文档内容进行自动分析和简历索引而是人工对w e b 站点文档等进 行分类，将w e b 信息按照主题分类并树状形式加以组织。用户可以完全不用进 行关键词( k e y w o r d s ) 查询，仅靠搜索引擎提供的目录分类也可以找到需要的信 息。目录分类索引中最具代表性的莫过于y a h o o ! 雅虎。其他著名的还有 l o o k s m a r t 等。国内的搜狐、新浪、网易也都有此类搜索引擎。 ( 3 ) 元搜索引擎 一般搜索引擎对w e b 覆盖度都是很低的，不超过2 0 。而元搜索引擎同时 在其他多个搜索引擎上进行搜索，它首先将对用户查询请求进行预处理，变成若 3 北京化t 人学硕+ l ：学位论文 干个底层搜索引擎能处理的格式，然后向各个搜索引擎发送查询请求，对返回的 结果进行处理，组合结果消除重复的结果，并将最终的结果返回给用户。著名的 元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等。中文元搜索引擎中具有代表性 的有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜索结果， 如d o g p i l e ，有的则按自定的规则将结果重新排序，如v i v i s i m o 。 1 3 搜索引擎的基本框架及工作原理 搜索引擎并不是实时地使用用户提交的查询搜索互联网，而是对预先下载 整理好的网页索引数据库进行搜索【1 0 1 。 搜索引擎的基本组成框架【1 1 】如下图所示： e 口 闩e 图1 - 1 搜索引擎框架图 f i g 1 - 1s t u r c t u r eo fs e a r c he n g i n e 网络机器人( s p i d e r ) 模块，根据某种爬行策略对w e b 进行遍历并下载保存 遍历过的文档的程序。 分析器：对网络机器人下载的文档进行分析以用于索引。 索引器：将文档表示为一种便于检索的方式并保存在索引数据库内。 检索器：从索引中找出与用户查询请求相关的文档。 搜索引擎的原理如下：网络机器人从互联网中抓取网页，并沿着爬行过的网 页中的u r l 爬到其他网页，重复这个过程，并将爬行过的所有网页保存下来。 由分析器对收集回来的网页进行分析，提取相关网页信息，根据一定的相关度算 法进行大量复杂的计算，然后索引器用这些相关信息建立网页索引数据库，当用 户输入关键词搜索后，由检索器从网页索引数据库中找到符合该关键词的所有相 关网页返回给用户。 作为整个搜索引擎的资源采集部分，网络机器人的性能、所爬行网页的数量、 质量将直接影响到整个搜索引擎的性能。因此对网络机器人的研究与改进有着深 4 第一章引言 远的意义。 5 第二章基于链接分析的网络爬虫算法 第二章基于链接分析的网络爬虫算法 2 1 网络爬虫介绍 2 1 1 网络爬虫概述 网络爬虫，也被称作s p i d e r ，是一个遍历网络图的个程序，它将遍历过程 中途经的网页保存起来，是搜索引擎的重要组成部分【l2 1 。爬虫通常以若干种子网 页作为爬行的起点，通过分析种子网页得到网页中的u r l 链接，将得到的u r l 链接放入待爬u r l 队列中，整个爬行过程就是不断从队列中取出u r l 下载该网 页，分析该网页得到u 也，直到达到某个条件的时候停止。 s p i d e r 在w e b 爬行获取网页的过程中，要面对如下问题：网络在不断快速的 发展，网络中的信息量也十分的巨大，一个搜索引擎不可能覆盖整个w 曲，当前 著名的搜索引擎g o o g l e 也只覆盖了整个w 曲的1 0 ；另一方面s p i d e r 在爬行 过程中，要把爬行过的网页保存起来的，在不断的爬行过程中，必定会受到硬件 资源的限制，它所能存储的网页是有限的。由于上述两方面问题，就要求s p i d e r 在爬行时尽量找到w e b 中的高质量网页来爬行保存。因此一个优良的爬行策略 对一个优秀的搜索引擎是很必要的。 2 1 2 网络爬虫的基本组成及工作原理 网络爬虫要完成以下功能：获取待爬行链接、下载网页并分析该网页将分析 网页得到的链接进行处理，保存爬行过的网页。下面就是网络爬虫的基本组成结 构1 1 4 】： 图2 - 1 网络爬虫基本框架图 f i g2 - 1s t r u c t u r eo fs p i d e r 7 北京化丁火学硕i ：学位论文 链接分析模块：分析获取超链接的使用协议( 如h t t p ) ，主机名或者i p 地 址和所在服务器上的路径，供页面采集模块建立通信连接，抓取网络资源使用。 页面采集模块：是网络爬虫与互联网的接口，主要作用是通过各种w e b 协 议编写协议请求消息，利用s o c k e t 网络通信先从服务器请求获取网页头信息，分 析网页头信息确定以某种方式接收主体信息，再获取网页主体部分，然后将采集 到的页面交由后续模块进一步处理。此模块一般采取多线程技术。 页面分析模块：该模块主要功能是分析采集页面，提取页面文档需要的超 链接，页面链接的u r l 一般是多种格式的，可能是完整的包括协议( 如h t t p ：) 主机名( w w w s o h u c o m ) 路径( 如d o w n l o a d m p 3 ) 也可能是相对路径 ( d o w n l o a d m p 3 ) 必须对它们进行处理得到同意的标准格式的u r l 。 链接过滤模块：过滤不符合要求的超链接，并维护已访问的u r l 、未访问 的u r l 和不能访问的u r l 。 原始页面数据库：存放爬下来的原始页面文档。 爬虫程序从原始u r l 种子开始，通过对链接分析获取该网页，并从该网页 中发现u r l ，这些u r l 通过分析加入到u r l 队列中待爬行，网页则直接保存 到原始页面数据库中，然后不断重复从u r l 队列取出u r l 来爬行。 2 2 网络爬虫搜索策略的发展及现状 在搜索引擎发展的早期，互联网的规模也较小，可以做到尽量全的覆盖整个 互联网，出现两种较为经典的爬行策略，分别是深度优先策略和广度优先策略。 下面详细讲解两种爬行策略的工作原理。 图2 2 网络结构图 f i g2 - 2s t r u c t u r eo fi n t e r a c t 一一一一一一一一一一 二二j 二 第二章基于链接分析的网络爬虫算法 如图2 2 所示为网页及网页间的超链接，图中方块代表网页，箭头表示存在 一条从箭头尾部网页指向箭头指向网页的超链接。 深度优先策略：深度优先的爬行策略中，一个节点的子孙节点的优先级要大 于该节点的兄弟节点，根据这个条件不断的迭代来完成爬行。如图2 2 中所示网 络结构，从网页l 开始爬行时会通过链接发现网页2 、3 、4 、5 ，待爬行队列为2 、 3 、4 、5 ，在网页l 爬行结束后从待爬行队列中取出第一个网页爬行，即对网页 2 进行爬行，网页2 爬行完成后，根据深度优先的规则将发现的网页加入到待爬 行队列的首部，此时待爬行队列为6 、7 、8 、9 、1 0 、3 、4 、5 。爬行的过程就是 不断的从待爬行队列中取出网页爬行，并将新发现的网页加入队列的过程。由于 重要的网页往往离种子节点的距离较近，例如当我们打开某些新闻网站时候，位 于首页的往往是最重要的新闻。随着不断的冲浪( 可以理解为深度不断加深) ，所 看到的网页的重要性越来越低，甚至偶尔会出现无法访问的情况。有研究表明， 中文万维网直径的长度只有1 7 ，所以在使用深度优先策略的时候会对深入的层 次有一个限定，当爬虫爬到规定层次后它将不再搜索新的网页，而是返回待爬行 队列继续爬行。 宽度优先策略：也成为广度优先或者层次优先，跟字面上的意思类似，爬行 策略的核心就是长幼有序的规则，祖先节点的优先级总是大于孩子节点的优先 级。如图2 。2 所示的网络结构中，使用宽度优先爬行，爬行顺序就会是l ，然后 l 发现的网页2 、3 、4 、5 为第二层，当网页1 爬行结束之后就开始对第二层网 页进行爬行，通过对第二层网页的爬行来发现新的下一层网页6 、7 、8 、9 、1 0 如此一层层的进行爬行，直到达到某个终结条件为止。 在爬行网页策略的选择上宽度优先相对于深度优先有如下几个优点： 1 重要的网页一般离种子站点的层次差较一般网页离种子站点的层次 差要小。 2 万维网的深度没有我们想象的那么神，到达某一个网页的路径通常 很多，总会存在一条很短的路径到达。 3 宽度优先规则有利于多个爬虫合作抓取。 随着互联网的爆炸式发展，网站数量和网页的数量都呈几何级数增长，覆盖 整个网络的搜索引擎已经是无法做到的了，网络爬虫对网页的爬行不再是遍历而 是有所取舍，根据对网页的判断方式不同，可以分为针对网页质量的爬行策略和 针对网页内容的爬行策略。 9 北京化t 大学硕。1 ：学位论文 针对网页内容的爬行策略是作为主题型搜索引擎的核心出现的。 随着互联网上多元化信息的增长，传统的搜索引擎即通用的搜索引擎已经不 能满足人们对个性化信息检索服务日益增长的需要。近年来，面向主题的搜索引 擎应运而生，以提供分类更细致精确、数据更全面深入、更新更及时的互联网搜 索服务。 所谓主题型搜索引擎，也被称作聚焦搜索引擎或垂直搜索引擎，就是以构筑 某一领域或学科领域的互联网信息资源库为目标，智能地在互联网上搜集符合设 定专题或满足学科需要的信息资源。 主题型搜索引擎的爬虫与通用搜索引擎的爬虫相比，增加了一个网页主题相 关性判断的模块，通过对网页中的文本内容的判断来确定该网页是否符合所要爬 行的主题。主题爬虫通过主题相关性判断模块来指导爬行，只有网页相关性达到 一定程度网页才会被爬行保存。 近期关于针对网页内容的爬行策略的研究集中于如何更有效率的判断链接 所连接的网页是否是符合爬行主题要求等方面。 本文所设计的爬行策略是针对网页的质量，下面就详细介绍分析下近年来针 对网页质量的爬行策略的研究现状。 2 3 注重网页质量的网络爬虫搜索策略 网页的质量即网页的重要性，网页的重要性体现在其他网页对该网页的引 用，也就是该网页被其他网页中的超链接所指向。在关注于网页质量的s p i d e r 爬行策略中经典的有以下几个： 2 3 1p a g e r a n k p a g e r a n k 算法是f l j b r i n 和p a g e 最先提出的【1 5 1 ，它对网页的质量进行评价，对 每个网页赋予一个衡量其重要性的权威值，最早被用于检索结果的排序，后来也 应用于网页采集、检索结果聚类、查找相关网页等许多方面。p a g e r a n k 基本思想 是假设一个w 曲漫游者每次按统一的概率在当前网页中挑选下一步要访问的链 接，而当遇到一个没有出链的网页时，漫游者以一个很小的概率删b 到任意的一 个页面，设厅是页面，的链出页面集，助是页面，的链入页面集，则在任意时 问点，漫游者位于页面，的概率p ( i ) 见式( 2 1 ) ： 1 0 第二章基于链接分析的网络爬虫算法 删邓椰一，踹，珈1 ) 其中，0 胚1 ，通常取值为0 1 5 。根据式( 2 1 ) ，如果一个网页是重要的， 那么或者是因为有较多的页面链接指向它，或者是因为指向它的页面都比较重 要，由式( 2 1 ) 计算出的p a g e r a n k 值很好地反映网页之间的相互引用关系，被重要 页面引用较多的网页重要性也较大，所以能较好地反映页面权威性【1 6 】。 2 3 2h i t s h i t s ( h y p e r t e x ti n d u c e dt o p i cs e a r c h ) 算法是k l e i n b e r g 于19 9 9 年提出的关于 超链接的检索算法【1 7 】。该算法通过对网络中超链接的分析，利用页面的被引用次 数及其链接数目来决定不同网页的权威性【l8 1 。h i t s 涉及两个重要的概念： a u t h o r i t y ：表示一个权威网页被其它网页所引用的数量，即该权威网页的入度值。 若某网页被引用的数量越大，则该网页的入度值越大，a u t h o r i t y 越大；h u b ：表 示一个w e b 页面指向其它网页的数量，即该w e b 页的出度值，它提供了指向权威 页面的链接集合。若某网页的出度值越大，则该网页的h u b 值越大。h u b 起到了 隐含说明某话题权威页面的作用。h u b 页面本身可能并不突出，但它却提供了指 向就某个公共话题而言最为突出的站点链接，如一门课程主页上推荐的参考文献 站点。一般情况下，好的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 y 和h u b 的相互作用可用于权威网页的挖掘和高质量w e b 结构和资源的自动发现，这就是 h i t s 算法的基本思想。h u b 和a u t h o r i t y 的关系可以用图2 2 来表示。 i l u b 指向秘戚，i 的超链接集合o q w c b 0 a u t h o r i t y 页被许多l l u b ? j 指向的权戚的、曲页 m 2 4h u b 页与a u t h o r i t y 页关系图 f i g 2 - 3r e l a t i o n s h i po fh u ba n da u t h o r i t yp a g e s 北京化1 = 人学硕一l ：学位论文 2 3 3b a c k l i n k 和o p i c b a c k l i n k 和o p i c 算法是在针对网页质量的爬行的策略中的常见算法【1 9 2 0 1 ， 两种算法有相近的部分，下面就来具体介绍： b a c k l i n k 对待爬队列中的所有u r l 做统计，当一个网页u r l 被其他网页所 链接，则认为它是重要的，b a c k l i n k 将队列中被其他网页链接所指向最多的u r l 地址取出爬行，并将该网页u r l 中的超链接加入待爬队列，重新计算队列中u r l 的被链接数，确保被链接指向数量多的u r l 总是被优先的被爬行。 o p i c 与b a c k l i n k 类似，它被称为w e i g h e db a c k l i n k c o u n t 算法，在该算法中， 并不是仅仅的统计一个网页u r l 的被链接数量，而是为每个网页分配固定数量 的“c a s h ，当这个网页有链接的时候，它的“c a s h 就会平均地分配到每个链接所 指向的网页中，在爬行的时候，就会从待爬行链接队列中取出“c a s h 最多的网页 来爬行，完成爬行后将该网页的“c a s h 向它的链接平均分配下去，重新计算排列 待爬u r l 队列中各个网页u r l 的“c a s h ，确保“c a s h 大的u r l 是被优先爬行的。 这两种爬行策略在计算上较为方便快速，适合指导网络机器人实时的对网页 的爬行。 2 3 4 几种搜索策略的分析比较 ( 1 ) p a g e r a n k ：在网页数量比较少的情况下，p a g e r a n k 方程组可以解出， 而面对互联网上成亿的网页，再解方程是不太现实的【2 1 1 。在实际应用中，使用中 近似迭代的方法计算网页的p a g e r a n k 值。由于整个网络的页面数量巨大，采用普 通的迭代计算方式将会非常的耗费时间，而s p i d e r 在爬行网络的过程中不可能给 出大量的时间用于迭代计算，那样的话s p i d e r 效率会相当低，搜索引擎也很难能 满足用户对信息的需求型2 2 1 。第二，p a g e r a n k 在计算的过程中需要记录网络中 任意两个有链接关系的网页间的链接信息，当面向的对象扩展到整个网络的情况 下，就会出现主存容量无法满足计算数据的要求。所以p a g e r a n k 并不适合用户指 导s p i d e r 爬行，p a g e r a n k 算法经常被用在对返回给用户查询结果进行排序方面， 近几年来的针对爬行算法策略的研究也有很大一部分是针对改进p a g e r a n k 算法 计算效率来进行的。第三，p a g e r a n k 算法和主题是相互独立的【2 3 1 ，没有考虑到 网页和主题之间的相关性，一个网页只有惟- - i 拘p a g e r a n k 值，而一个网页( 尤其 是一些门户站点的网页1 却可以同时涉及多个分散的主题【2 4 1 。例如在主题“军事” 上有较高权威性的网页不一定在“娱乐”上也有较高的权威性。其次，链接在很多 时候只是起到导航甚至是广告的作用，相互链接的网页之间有时并没有主题相关 的联系。因此对页面上的所有出链都传递同样的p a g e r a n k 值并不是十分准确的 1 2 第二章基于链接分析的网络爬虫算法 f 2 5 】。第四，p a g e r a n k 往往无法正确判断刚刚放到互联网的网页的重要性，因为 刚放入互联网内的网页有可能没有很多甚至没有任何的链接指向它，这时即使是 非常重要的网页的p a g e r a n k 值也会非常低。 ( 2 ) h i t s ：虽然h i t s 算法取得了很大的成功，但也存在着些问题，主要 有： 1 容易发生主题偏移【2 6 1 。由于h i t s 算法局限于w e b 页面之间的链接关系，忽 略了页面的内容，在应用过程中表现出不稳定性，有时会出现主题偏移问题。一 般地，一个好的h u b 应指向许多好的a u t h o r i t y 页面，但是，如果一个h u b 包含有 多个主题，就会有许多链接指向不相关的w e b 页面，这些不相关页面的a u t h o r i t y 权重虽然较低，但是h i t s 算法将它们的a u t h o f i t y 叉重之和作为该h u b 的权重，该 权重就可能很大，而实际上只有很少链接指向有价值的a u t h o r i t y 页面。 2 容易产生不合理结果。作为一种基于页面粒度的算法，hi t s 往往意味着 给不同的文档或w e b 站点作者规定不平等的影响权重，导致筛选出来的结果不尽 客观合理。 3 无关链接的影响。通常情况下，一个页面上的链接并不都与主题有关，它 包括站点内的导航链接，广告链接等，这些链接对权威没有贡献，若不从权重传 播分析中去除，将会极大影响h i t s 算法的效果。但有些链接的过滤比较复杂， 技术要求较高，不容易过滤。 4 无关页面的影响【2 7 】。无关页面的引入有两个途径：一是基于相似度的搜索 引擎返回的根集中就包含无关页面，所就对根集的质量有很高的要求：二是根据 链接关系生成基本集时引入的。由于h i t s 算法只是简单地根据链接关系确定权 重，缺乏对页面有效性的判断，容易造成无关页面获得较大的h u b 权重和a u t h o r i t y 权重，从而导致输出的h u b 页面和a u t h o r i t y 页面与查询主题无关。 5 对种子节点质量要求很高。由于h i t s 算法在计算f l j h u b 页面和a u t h o r i t y 页 面的时候是使用种子节点扩展后得到的所有网页来计算的，如果种子节点的质量 较低就会影响后续爬行过程中网页的质量，如果种子节点包含多个主题的网页， 也会很容易出现爬行主题漂移。 ( 3 ) b a c k l i n k 和o p i c 的缺点和p a g e r a n k 的缺点类似，容易发生主题漂移， 因为b a c k l i n k 和o p i c 算法都没有对网页内容上进行判断，虽然可以在选取种子 节点对爬行主题进行控制，但效果并不可靠。 b a c k l i n k 和o p i c 也存在对新出现的高质量网页无法识别的问题。 以上几种基于链接分析的爬虫算法都是以尽可能的爬行高质量网页作为目 标的，但除了存在以上分析说明的缺点外，以上几种注重网页质量的爬行策略都 无法解决的无法对潜在高质量网页进行爬行的问题，本文所设计的爬行策略将在 北京化- t 大学硕l ：学位论文 对高质量的网页进行爬行的同时对潜在的高质量网页也进行爬行。 1 4 第三章理论基础及相关技术 3 1 数据库的选择 第三章理论基础及相关技术 本文在实现算法的过程中，需要将数据稳定地进行存储，并能够快速安全地 进行读写。 作为微软下一代的数据管理与商业智能平台，s q ls e r v e r2 0 0 5 将是微软5 年来具有里程碑性质的企业级数据库产品【2 8 1 。 s q ls e r v e r2 0 0 5 中包含了非常丰富的新特性：通过提供一个更安全、可靠 和高效的数据管理平台，增强企业组织中用户的管理能力，大幅提升i t 管理效 率并降低运维风险和成本；通过提供先进的商业智能平台满足众多客户对业务的 实时统计分析、监控预测等多种复杂管理需求，推动企业管理信息化建设和业务 发展；同时，s q ls e r v e r2 0 0 5 将提供一个极具扩展性和灵活性的开发平台，不 断拓展应用空间，实现i n t e r n e t 数据业务互联。 大大减少了应用程序宕机时间，提高了系统的可伸缩性和性能，并加以更 严格的安全控制，s q - ls e r v e r2 0 0 5 在支持现实中最苛刻的企业级系统要求的道 路上，迈出了极大的一步。s q ls e r v e r 是微软服务器家族中重要的一部分，通过 微软服务器系列产品共有的e n g i n e e r i n gs t r a t e g y 所实现的增强的管理性和集成 性，客户可以有效降低总体拥有成本并从更快的开发部署时间中受益。 s q ls e r v e r2 0 0 5 将在安全性、高可靠性、性能、扩展性、可管理性方面有 极大的提高，不仅能够确保企业级数据业务的实时稳定运行、还能够大大提高管 理效率、降低操作复杂度和运维成本。 s q ls e r v e r2 0 0 5 将提供更加强大的开发工具和各类新的开发特性，在大大 提高开发效率的同时，将进一步拓展应用空间。例如，x m l 数据库与w e bs e r v i c e 的支持将使您的应用实现i n t e r n e t 数据互联，n e t 集成极大的扩展了开发空间， 异构数据集成、s e r v i c eb r o k e r 使您的数据和其它应用无缝集成，各种新数据类 型和t s q l 扩展带来了诸多灵活性。c 撑、v b n e t 、x q u e t y 、x m l a 、a d o n e t2 0 、 s m o 、a m o 等都将成为s q ls e r v e r 数据平台上开发数据相关应用的有力工具。 基于s q ls e r v e r2 0 0 5 有安全、可靠、读写效率高、易于操作等优点，因此 本文选用s q ls e r v e r2 0 0 5 数据库。 3 2j e f fh e a t o ns p i d e r 介绍 j e f f h e a t o n 在其编著的网络机器人j a v a 编程指南【2 9 】一书中提供了一个 1 5 北京化t 大学硕卜学位论文 开源的s p i d e r 程序，在此书中系统的讲述了该开源s p i d e r 的体系结构、基本工 作原理以及具体类的实现功能原理等，下面就是对j e f fh e a t o n 编