（计算机应用技术专业论文）网页抓取策略研究.pdf

j c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho nw e bcr a w l i n gs t r a t e g i e s c a n d i d a t e ：w e n gy a n q i n g s u p e r v i s o r ：p r o f z h a n gg u o y i n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：j a n u a r y ，2 010 d a t eo f o r a le x a m i n a t i o n ：m a r c h ，2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：锅莞强 日期： 2o f o 年易月1 7 日 哈尔滨工程大学 学位论文授权使用声明 、 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数 据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编 本学位论文，可以公布论文的全部内容。同时本人保证毕业后结 合学位论文研究课题再撰写的论文一律注明作者第一署名单位 为哈尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 晚授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) 镐坼 日期：枷o 年易月fp 日 导师( 签字) ：孑彰锵 沩幻年j 月纱日 哈尔滨t 稗大学硕士学伸论文 摘要 随着w e b 上信息的爆炸性增长，人们无法直接而准确地定位感兴趣的资 源，越来越多地依赖搜索引擎。然而，由于w e b 的规模巨大，任何一个网络 爬虫均无法获取w e b 上的所有网页。既然不能抓取到全部网页，那么就需要 网络爬虫在有限的时间内尽可能多地抓取较为重要的网页。网页抓取策略就 是研究以怎样的顺序来访问w e b 上的网页以使得网络爬虫能够优先获取w e b 上的重要页面。 本文首先对构建高效率网络爬虫所需的关键技术进行深入研究，其中 u r l 调度器决定了网络爬虫抓取网页的顺序，是实现网页抓取策略的主要功 能组件。接着在分析多种网页重要度评定标准的基础上，选取基于p a g e r a n k 的链接分析评定标准作为衡量网页重要度的依据。p a g e r a n k 技术充分利用了 网页间的超链接信息，综合考虑了一个网页的反向链接数目和质量，客观定 义了其在整个w e b 上的相对重要性。最后，通过对不同网页抓取策略的研究， 发现一个好的网页抓取策略在能够优先获取重要页面的同时，还需满足抓取 速度，对抓取站点的礼貌性和均衡性的要求。然而，现有的网页抓取策略均 不能很好的同时满足这些要求。因此，本文提出了一种综合权重网页抓取策 略，采用两级优先级调度策略。站点级的调度可以满足礼貌性和均衡性的要 求，网页级的调度通过引入历史信息机制，可以获得质量更高的网页。 本文设计和开发了w e b c r a w l e r 网络爬虫以获取实验所需的数据集，并在 其基础上，采用虚拟抓取的方式来对比不同的网页抓取策略。由于w e b 动态 变化的特点，这也使得只有虚拟抓取才能保证不同的网页抓取策略可以在等 同的条件下进行对比。实验表明，综合权重网页抓取策略在保证抓取速度， 礼貌性和均衡性的前提下，获得了更好的网页质量。 关键词：网络爬虫；网页重要度；网页抓取策略；网页排名 哈尔滨t 程大学硕十学位论文 a b s t r a c t w i t ht h ee x p l o s i v eg r o w t ho fi n f o r m a t i o no nt h ew e b ，p e o p l ec a l ln o td i r e c t l y a n da c c u r a t e l yl o c a t er e s o u r c e sw h a tt h e yi n t e r e s ti n ，s ot h a tt h e ya r em o r ea n d m o r ed e p e n d e n to ns e a r c he n g i n e s h o w e v e r , o w i n gt ot h el a r g es c a l eo fw e b ，i t 产 m a k e sa n yw e bc r a w l e rw e r eu n a b l et oo b t a i na l lt h ew e bp a g e s s i n c ew e b c r a w l e r sc a l ln o tc r a w lt oa l lp a g e s ，i ti sn e e dt oc r a w la sm u c hi m p o r t a n tw e b p a g e sa sp o s s i b l ei nal i m i t e dp e r i o do ft i m e w e bc r a w l i n gs t r a t e g yi st os t u d yi n w h a to r d e rt oa c c e s st h ew e bp a g e s ，m a k i n gw e bc r a w l e r sh a v ep r i o r i t ya c c e s st o f i r s t l y ，t h i st h e s i si n t e n s i v e l ya n a l y z e st h ek e yt e c h n o l o g i e so fb u i l d i n g e f f i c i e n tw e bc r a w l e r s ，i n c l u d i n gu r ls c h e d u l e rt h a td e t e r m i n e st h eo r d e ro fw e b c r a w l i n g u r ls c h e d u l e r i st h em a i nf u n c t i o n a l c o m p o n e n t st or e a l i z ew e b c r a w l i n gs t r a t e g i e s t h e n ，o n t h e b a s i so fa n a l y z i n gav a r i e t yo fw e bp a g e s i m p o r t a n c ea s s e s s m e n tc r i t e r i a ，t h ep a p e rs e l e c t sp a g e r a n kb a s e dl i n ka n a l y s i s a s s e s s m e n tc r i t e r i aa sab a s i so fe v a l u a t i n gw e bp a g ei m p o r t a n c e p a g e r a n k t e c h n o l o g ym a k e sf u l lu s eo fh y p e r l i n k si n f o r m a t i o nb e t w e e nw e bp a g e ，w h i c h c o m p r e h e n s i v e l yc o n s i d e r st h er e v e r s el i n kn u m b e ra n dq u a l i t yt oaw e bp a g e p a g e r a n kt e c h n o l o g ya l s oo b j e c t i v e l yd e f i n e st h e i rr e l a t i v ei m p o r t a n c eo nt h e e n t i r ew e b f i n a l l y ，ag o o dw e bc r a w l i n gs t r a t e g yi sd i s c o v e r e d ，w h i c hh a s ，- p r i o r i t y a c c e s st oi m p o r t a n tp a g e sa n ds i m u l t a n e o u s l ym e e tt h er e q u i r e m e n t so f c r a w l i n gs p e e d ，c o u r t e s ya n db a l a n c eo ft h ec r a w l e ds i t e h o w e v e r , t h ee x i s t i n g w e bc r a w l e r sc a l ln o tv e r yw e l lm e e tt h e s er e q u i r e m e n t sa tt h es a m et i m e t h e r e f o r e ，t h i st h e s i sh a sd e s i g n e dac o m p r e h e n s i v ew e i g h tw e bc r a w l i n gs t r a t e g y , u s i n gt w op r i o r i t ys c h e d u l i n gp o l i c y s i t e - l e v e ls c h e d u l i n gc a l lm e e tt h ec o u r t e s y a n db a l a n c er e q u i r e m e n t s ，w h i l ew e b l e v e ls c h e d u l i n gc a na c c e s st oh i g h e rq u a l i t y 哈尔滨t 程大学硕十学伸论文 p a g e st h r o u g ht h ei n t r o d u c t i o no f h i s t o r i c a li n f o r m a t i o nm e c h a n i s m t h i st h e s i sh a sd e s i g n e da n dd e v e l o p e daw e b c r a w l e rt oo b m i nt h er e q u i r e d e x p e r i m e n t a ld a t as e t s ，a n do ni t sb a s i s ，u s i n gav i r t u a lc r a w lw a yt oc o m p a r e d i f f e r e n tw e bc r a w l i n gs t r a t e g i e s b e c a u s ew e bd y n a m i c a l l yc h a n g e s ，i tm a k e s v i r t u a lc r a w lb e c o m et h eo n l yw a yt oe n s u r ed i f f e r e n tw e bc r a w l i n gs t r a t e g i e sc a n b ec o m p a r e du n d e rt h es a m ec o n d i t i o n s e x p e r i m e n t ss h o wt h a tt h ec o m p r e h e n s i v e w e i g h tw e bc r a w l i n gs t r a t e g yc a no b t a i nb e n e rq u a l i t yi nt h ec o n t e x to fm e e t i n g the r e q u i r e m e n t so fc r a w l i n gs p e e d ，c o u r t e s ya n db a l a n c e k e yw o r d s ：w e bc r a w l e r ；w e bp a g ei m p o r t a n c e ；w e bc r a w l i n gs t r a t e g i e s ； p a g e r a n k 哈尔滨t 程大学硕十学位论文 目录 第1 章绪论1 1 1论文的研究背景和意义1 1 1 1 搜索引擎技术“1 严 1 2 2 网络爬虫”3 1 2国内外研究现状“4 1 3 论文的主要工作5 1 4 论文的组织结构6 第2 章网络爬虫关键技术研究8 2 1网络爬虫体系结构8 2 2u r l 调度一1o 2 2 1u r l 调度策略o 1 0 2 2 2 礼貌性要求1 1 2 3 d n s 解析12 2 3 1域名和口对应问题”1 2 2 3 2 定制d n s 13 2 4网页抓取l5 2 4 1 多线程并行抓取l5 2 4 2 单线程异步抓取l6 2 4 3爬虫禁止协议”16 i 2 5 网页分析1 7 2 6u r l 判重18 2 6 1减少u r l 存储空间l8 2 6 2 减少u r l 查找时间“1 8 2 7 本章小结1 9 哈尔滨丁稃大学硕十学位论文 第3 章网页重要度评定标准2 0 3 1 基于u r l 规则的评定标准2 l 3 2 基于链接分析的评定标准”2 2 3 2 - l链接分析技术概述2 3 3 2 2 基于反向链接数的评定标准2 5 3 2 3 基于p a g e r a n k 的评定标准2 6 3 3基于主题内容的评定标准”2 9 3 3 1主题爬虫2 9 3 3 2 主题相关性判定标准2 9 3 4 综合评定标准“3 0 3 5 本章小结3 l 第4 章网页抓取策略研究3 2 4 1宽度优先抓取策略“3 2 4 2 深度优先抓取策略一3 3 4 3 基于链接分析的抓取策略3 4 4 3 1周期性网页重要度计算”3 4 4 3 2 批量网页重要度计算3 5 4 4 大站点优先抓取策略3 5 4 5 基于历史信息反馈的抓取策略”3 6 4 6 综合权重抓取策略3 6 4 7 本章小结4 1 第5 章实验设计和结果分析4 3 5 1实验概述一4 3 5 2 实验平台设计”4 4 5 2 1 w e b c r a w l c r 介绍4 4 5 2 2w e b c r a w l e r 主要类及功能4 5 5 2 3 w e b c r a w l e r 抓取算法4 6 哈尔滨丁稃大学硕十学何论文 5 3实验数据集的获取4 7 5 4 评定指标4 8 5 5 实验和结果分析4 9 5 6 本章小结”5 2 结 仑5 3 参考文献5 5 攻读硕士学位期间发表的论文和取得的科研成果5 9 致 射一6 0 一 哈尔滨t 程大学硕+ 学付论文 第1 章绪论 1 1论文的研究背景和意义 近年来，伴随着互联网信息的爆炸性增长，万维网( w b r l dw i d ew e b ， 简记为w 曲) 技术得到广泛应用，它的开放性和其上信息传输的迅速性极大 地方便了人们获取信息。由于w e b 具有海量信息的特点，人们无法快速准确 直接地定位感兴趣的资源，因此越来越多地依赖于搜索引擎。然而，传统的 通用搜索引擎如g o o g l e 、百度等正面临着巨大的挑战。在这些挑战中，一方 面是由于w e b 信息资源的快速增长，使得搜索引擎无法索引到全部网页；另 一方面是由于w e b 信息资源的动态变化，使得搜索引擎无法保证对其索引信 息的及时更新。既然搜索引擎不能够获取w e b 中的全部网页，那么优先获取 w e b 中一些重要网页就显得十分有必要。 搜索引擎依靠网络爬虫来获取被其索引的网页。网络爬虫通过一定的策 略在w e b 上搜集网页，源源不断地提供给搜索引擎，进而为用户提供检索服 务。然而网络爬虫不可能抓取到w e b 中的所有页面，主要原因是w e b 巨大 的规模使得任何一个搜索引擎均无法存储所有的网页。另外，网络爬虫在抓 取网页的过程中，需要在某一时刻重新抓取已经访问过的网页集合来检验网 页内容的变化情况，这就可能存在有些网页从来不曾被网络爬虫抓取过的可 能。基于以上两点原因，让网络爬虫以适合的网页抓取策略优先去访问w e b 中重要的网页集合非常有意义。 1 1 1 搜索引擎技术 搜索引擎指的是一种在w e b 上应用的软件系统，它以一定的策略在w e b 上搜集和发现信息，在对信息进行处理和组织后，为用户提供w e b 信息查询 服务【l 】。从使用者的角度看，这种软件系统提供一个网页界面，用户通过浏 览器提交一个查询词，然后搜索引擎很快返回一个可能和用户输入内容相关 图1 1 搜索引擎体系结构 网页搜集子系统主要负责在互联网上搜集网页信息，通过给其提供少量 的起始页面，网页搜集子系统即能够按照一定的规则沿着网页上的超链接进 行网页抓取，直至抓取完互联网上的全部网页或者满足某种规定的搜集结束 条件。 索引子系统分析网页搜集子系统抓取到的网页信息，建立索引库，供检 索子系统查询。索引子系统主要使用的技术为分词，索引词选取，停用词过 滤，索引归并、压缩及更新，以及倒排文件缓存。 检索子系统是用户与搜索引擎的接口，它通常是一个w e b 应用程序，负 责接收和解释用户请求，查询网页索引库以及返回排序后的检索结果。 2 哈尔滨t 稃大学硕十学何论文 !h-i 1 2 2 网络爬虫 网络爬虫是在w e b 上获取网页的程序，通常作为搜索引擎的网页搜集子 系统。大体上来说，网络爬虫拥有一个抓取任务队列，里面保存着所有待抓 取的网页u r l 。抓取开始时，队列中存放预先设定的种子u r l 集合，然后 网络爬虫从任务队列中获取一个u r l ，连接此u r l 对应的w e b 服务器，下 载该页面，抽取页面中包含的所有链接u r l ，并把这些u r l 加入到抓取任 务队列中，爬虫以某种策略从任务队列中获取下一个待抓取的u r l 并下载， 重复此过程直到抓取任务队列为空或者满足预先设定的抓取结束条件，网络 爬虫的工作流程如图1 2 所示。 图1 2 网络爬虫工作流程 哈尔滨丁稃大学硕十学位论文 一个好的网络爬虫在设计上面临很多挑战【2 1 。外部方面，网络爬虫必须 要避免对w e b 服务器或网络链路的过度负载。内部方面，网络爬虫又要面对 海量数据的处理。除非拥有无限的计算资源和抓取时间，否则网络爬虫就必 须要决定应该以怎样的顺序去抓取哪些网页。除此之外，网络爬虫还需要决 定对已抓取网页的重新访问时间，以保证保存网页信息的数据库中内容的时 效性。 1 2 国内外研究现状 关于网页抓取策略的研究，国外开始于2 0 世纪9 0 年代末。c h o 等人在 文献 2 】中第一次引入了网页抓取策略的概念。他从s t a n f o r d e d u 域上抓取了 1 8 0 ，0 0 0 个网页，在此数据集上使用爬虫模拟器对比了宽度优先网页抓取策 略，基于反向链接数的网页抓取策略以及基于p a g e r a n k 的网页抓取策略。实 验证明，基于p a g e r a n k 的网页抓取策略效果最好，其次是宽度优先网页抓取 策略，基于反向链接数的网页抓取策略最差。然而他的实验数据仅仅来自一 个域，并没有在完整的w e b 上进行实验。 n a j o k 和w i e n e r 在文献 3 中使用宽度优先抓取策略获取了3 2 8 ，0 0 0 ，0 0 0 个网页，他发现宽度优先抓取策略可以在抓取过程的早期获得很多高质量的 网页，但是他的工作仅针对宽度优先抓取策略，并没有和其他网页抓取策略 进行对比。 a b i t e b o u l 等人在文献 5 中提出了一种基于o p i c 的网页抓取策略。在此 策略中，每个网页有一些初始的“现金 ，这些“现金”可以平均分发给它所 指向的网页。这种“现金”流动方式类似于p a g e r a n k 的计算，但它更快而且 只需一个计算步骤。基于o p i c 网页抓取策略的网络爬虫会优先抓取“现金 数量多的网页，实验证明了此策略优先获取了高质量的网页，然而，同n a j o k 和w i e n e r 的研究一样，也没有将基于o p i c 网页抓取策略同其它网页抓取策 略进行对比。 c a s t i l l o 等人在文献【3 8 】中提出了大站点优先网页抓取策略，此策略通过 4 哈尔滨工程大学硕十学何论文 站点中待抓取网页数作为调度依据，在抓取的过程中让更多的站点存在待抓 取网页，使得网络爬虫对待抓取站点保持了良好的均衡性。然而，大站点优 先网页抓取策略仅把站点上的待抓取网页数量作为站点调度的依据，忽略了 站点中的网页重要度。而在实际情况下，站点的重要度是由站点内所有网页 的重要度共同决定的。 国内对网页抓取策略的研究起步较晚。近些年对这一领域的研究主要是 针对国外前些年的研究成果。李学勇等人在文献 4 中对比了基于链接评价的 多种网页抓取策略，总结出提高链接价值预测的准确性，降低计算的时空复 杂度，以及增加网络爬虫的自适应性，是提高网页抓取策略对网络爬虫抓取 效率影响的关键因素。刘悦在文献 2 3 】中就链接分析技术在网页抓取策略中 的重要性进行了研究，提出一种优化的链接分析算法来更好的衡量抓取到得 网页质量。然而，国内的大部分研究并没有在大规模的数据集中进行实验， 相关研究与国外相比还存在一定的差距。 网络爬虫是搜索引擎的重要组成部分，网页抓取策略又是网络爬虫中最 关键的技术之一。然而，搜索引擎中最核心的网页抓取策略与搜索结果排序 算法均作为商业秘密被工业界保护起来。这些技术的保密，一方面是由于竞 争的原因，另一方面也是为了防止搜索引擎欺骗技术所导致的垃圾检索结果。 对于这些核心技术，工业界仅仅向外公布过一些技术概要，但由于细节的缺 失无法重复使用。这就使得学术界对这些方面的研究一直落后于工业界，近 几年研究进展缓慢。但是，由于搜索引擎在当今的互联网时代所扮演的角色 越来越重要，迫切需要学术界针对这些搜索引擎核心技术做更多的研究，追 赶工业界的步伐。 1 3 论文的主要工作 本文首先介绍了课题的研究背景和意义，说明网页抓取策略在搜索引擎 的网页搜集子系统中的重要性。然后深入研究构建一个高效率的网络爬虫所 需要的关键技术，这些关键技术用于解决w e b 规模巨大所带来的挑战。 ， 哈尔滨丁程大学硕士学何论文 针对如何确定网页重要度这一问题，分析了多种网页重要度评定标准， 包括基于u r l 规则的网页重要度评定标准，基于链接分析的网页重要度评定 标准以及基于主题内容的网页重要度评定标准。通过对这些网页重要度评定 标准的对比分析，选取基于p a g e r a n k 的链接分析网页重要度评定标准作为本 文衡量不同网页抓取策略在获取网页质量上的依据。 在选定的网页重要度评定标准下，分析了不同的网页抓取策略各自的优 缺点。通过研究它们在获取页面质量，抓取速度，礼貌性和均衡性上的差异， 提出了一种新的网页抓取策略一综合权重网页抓取策略来改进它们的不足。 最后，本文设计和开发了一个小型通用网络爬虫w e b c r a w l e r 用于获取实 验所需的数据集。在实验数据集上使用网络爬虫应用不同的网页抓取策略进 行虚拟抓取，分析每种网页抓取策略所获取的网页质量，得出实验结果。 1 4 论文的组织结构 本文共分五个章节，具体内容如下： 第1 章主要介绍课题背景和意义，国内外研究现状以及本文的工作和章 节安排。 第2 章主要研究了网络爬虫的体系结构和关键技术，用于满足w e b 巨大 规模对网络爬虫带来的挑战。 第3 章研究了多种网页重要度评定标准，分析每种网页重要度评定标准 的优缺点。本文选取基于p a g e r a n k 的链接分析网页重要度评定标准作为衡量 不同网页抓取策略在获取页面质量上的依据。 第4 章研究不同的网页抓取策略，包括宽度优先抓取策略，深度优先抓 取策略，基于链接分析的抓取策略以及大站点优先抓策略。通过对这些网页 抓取策略的对比分析，针对它们的不足提出了一种新的网页抓取策略一综合 权重网页抓取策略来满足优先获取重要网页集合的要求。 第5 章设计并开发了一个小型通用网络爬虫w e b c r a w l e r ，作为获取实验 数据并对比多种网页抓取策略的实验平台。通过实验证明综合权重网页抓取 6 一 哈尔滨丁稃大学硕十学位论文 策略在选定的网页重要度评定标准下优于已有的网页抓取策略。 论文最后总结了本文的工作，分析不足之处，并指出了本文还需进一步 改进的方向。 7 哈尔滨t 程大学硕+ 学位论文 第2 章网络爬虫关键技术研究 第1 章中已经对网络爬虫的基本概念，工作流程做了简要介绍，本章将 进一步研究设计一个高效率的网络爬虫所需要的关键技术。在此之前，先来 看一下高效率网络爬虫的体系结构。 2 1网络爬虫体系结构 任何一个网络爬虫的基本工作流程都是相似的，设定初始种子u r l 集合 s 作为网络爬虫的输入信息，重复执行如下步骤：首先从集合s 中以某种策 略获取一个待抓取的u r l ，解析出此u r l 中主机名所对应的地址，使用 h t t p 协议连接此口地址所对应的w e b 服务器并下载此u r l 对应的网页， 下载网页后提取页面中所有链接u r l 。对于提取到的每个链接u r l ，如果是 相对u r l 则转换成绝对u r l ，然后判断此链接u r l 是否已下载或是否存在 于集合s 中，对于没有被下载且不存在于集合s 中的链接u r l ，把它加入到 集合s t 6 ) 。 斯坦福大学开发的搜索引擎g o o g l e 的网络爬虫由五个功能组件构成，每 个功能组件运行在单独的进程中【7 1 。这五个不同的进程分别为u r l 服务器进 程，抓取进程，存储服务器进程，索引进程以及u r l 解析进程。u r l 服务 器进程首先从保存待抓取u r l 文件中读取种子u r l 并把这些u r l 分配给多 个抓取进程去下载。每一个抓取进程分别运行在不同的主机上，采用单线程 异步i o 方式抓取网页。抓取进程把下载的网页传送给唯一的存储服务器， r 存储服务器把这些网页压缩后存储在网页数据库中。索引服务器从网页数据 库中读取网页，抽取其中的链接并把这些链接保存到链接文件中。u r l 解析 服务器读取这个链接文件，把其中的相对u r l 转化成绝对u r l 并保存到待 抓取u r l 文件中供u r l 服务器读取。一般情况下，g o o g l e 的网络爬虫大体 上需要三到四个抓取进程，所以总共四到八台主机即可完成整体的抓取任务。 i n t e m e ta r c h i v e 网络爬虫【8 】也使用多台主机同时抓取网页，每个抓取进程 一 哈尔滨t 稃大学硕十学何论文 对6 4 个不同站点上的网页进行抓取，相同站点下的网页不会赋给不同的抓取 进程。每个抓取进程从待抓取u r l 文件中读取自己负责站点下的u r l ，并 把这些u r l 放入其每个站点一个的任务队列中，网页下载过程同样也是采用 单线程异步i 0 的方式进行。一旦网页被下载，马上提取其中的链接u r l ， 如果这个链接u r l 所对应的站点属于本抓取进程自己所负责的，则放入到这 个站点对应的任务队列中，否则把此链接u r l 放入一个日志文件中。周期地， 一个后台进程读取这个日志文件，把每个u r l 根据其站点部分传送到所对应 的抓取进程每个站点的任务队列中，同时过滤掉其中重复的u r l 。 从上述网络爬虫的基本工作流程中可以看出，构建一个网络爬虫大体上 需要如下五个功能部州9 】：一个存储待抓取u i u 集合的u r l 调度器，此u r l 调度器能以某种策略从u r l 集合中选取一个u r l 并提供给网络爬虫作为抓 取目标；一个d n s 解析器，用于根据u r l 中主机名解析出所对应的i p 地址； 一个网页抓取模块，使用h t t p 协议下载一个u r l 所对应的网页；一个网页 分析器，负责从一个网页中提取出所有的链接u r l 或某些感兴趣的信息；一 个u r l 判重器，根据u r l 访问历史判断一个给定u r l 是否以前出现过。 根据网络爬虫的各功能部件可以得到其体系结构，如图2 1 所示： 图2 1 网络爬虫的体系结构 9 哈尔滨下程大学硕十学佗论文 从网络爬虫的体系结构可以看出各功能部件是如何相互协作完成w e b 信 息搜集任务的。设计一个高效率的网络爬虫必须要使得各个功能部件之间紧 密合作，并且能够处理w e b 上的海量数据。下面将根据网络爬虫的各功能部 件来研究设计一个高效率的网络爬虫所需要的关键技术。 2 2u 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 调度器决定了网络爬虫抓取网页的顺序。 实现u r l 调度器的最简单方法是利用一个先进先出队列来保存所有待 抓取u r l 集合，u r l 出队的顺序与它们入队的顺序是一致的。然而由于一 个网页包含的大部分链接都是位于同一主机的相对u r l ，所以经过网页分析 后提取出的这些相对u r l 将按顺序进入u r l 调度器，之后出队时也集中在 一起，这就会使抓取线程连续去抓取位于同一主机的多个u r l ，这些抓取线 程同时向同一w e b 服务器的频繁访问将导致类似于拒绝服务( d e n i a lo f s e r v i c e ，d o s ) 攻击，这样的行为被认为是不礼貌的，因此u r l 调度器的设 计要求必须满足礼貌性要求【l o l 。 2 2 1 u r l 调度策略 u r l 从调度器中弹出的顺序即是u r l 调度策略，它也决定了网络爬虫 抓取网页的顺序。由此可见，u r l 调度器的关键在于以某种合理的策略决定 u r l 弹出的次序，这也是本论文研究的重点，即研究以何种策略抓取网页可 以优先获取w e b 中重要的页面集合。 u r l 调度器实现调度策略的方式通常使用优先级队列来保存所有待抓 取的u r l 集合，优先级的定义即是对网页重要度的评定【】。不同的优先级 l o 哈尔滨t 程大学硕十学何论文 定义规则将使得u r l 被调度的顺序不同，因此网络爬虫抓取网页的顺序不 同，最终获取的网页集合也不同。评价一个u r l 调度策略的优劣，即是评价 网络爬虫的网页抓取策略的优劣，主要标准是以此u r l 调度策略所能获取的 网页集合重要度权重和，获得重要度权重和最大的u r l 调度策略被认为是最 优的调度策略。 2 2 2 礼貌性要求 一般来讲，网站的管理人员很愿意让自己的网页被搜索引擎的网络爬虫 抓取到，从而可能得到更多的访问流量。但另一方面，网站绝不希望由于网 络爬虫的密集抓取活动阻碍了普通用户通过浏览器的正常访问，这会使用户 得到这个网站访问起来很困难的印象，从而不再光顾。管理良好的网站通常 会有一个监视器在后台运行，检测是否有来源于单个口地址过分密集的访 问。一旦出现这种情况，可能会通告该地址的拥有者注意行为，或者干脆 屏蔽来自它的访问，更有甚者，还会在互联网上公布该口地址作为黑名单【l 】。 因此，适当地规划网页的抓取，限制单位时间内对同一网站的网页抓取数量 是网络爬虫必须要认真对待的问题，这就是所谓的网络爬虫礼貌性要求。 总结起来，网络爬虫访问w e b 服务器的礼貌性要求要符合两点：一是要 保证同一时刻不能有两个抓取线程访问同一w e b 服务器，另一个是要保证对 同一w 曲服务器的连续访问要拥有一定的时间间隔，不能过于频繁【1 2 】。 为了保证同一时刻不能有两个抓取线程访问同一w e b 服务器，可以使每 个抓取线程负责一个主机下的所有网页的抓取任务，各抓取线程负责的主机 互不相同。可以使用先进先出队列保存此抓取线程对应的u r l 任务队列。每 当抓取线程从u r l 调度器中获取一个u r l 时，可以根据此u r l 主机部分将 其放入到对应的抓取线程任务队列中。由于每个抓取线程所连接的w e b 服务 器不同，所以多个网页抓取线程就可以同时进行网页抓取而不违反礼貌性的 要求。 对于礼貌性要求的第二点保证，可以通过控制抓取线程任务队列中u r l 哈尔滨t 稃大学硕十学何论文 出队时间间隔达到。时间间隔的设定要考虑到w e b 服务器能容忍的程度，时 间间隔过短容易造成对w e b 服务器的频繁访问而被认为不礼貌，时间间隔过 长又会影响抓取线程的工作效率。 2 3d n s 解析 d n s 是域名系统( d o m a i nn a m es y s t e m ) 的缩写，该系统用于命名组织 到域层次结构中的计算机和网络服务。在i n t e r n e t 上主机是由3 2 位的i p 地址 标识的。然而i p 地址不容易记忆，域名即是为了便于人们对m 地址的记忆 而出现的。它们之间的转换工作称为域名解析，域名解析需要由专门的域名 解析服务器来完成，d n s 就是进行域名解析的服务器。 d n s 是全球分布式服务，当需要进行一次域名解析时，如果当前名字服 务器不能解析此域名将会转发解析请求给上级名字服务器，此过程递归进行 直到所请求的域名被正确解析。因此，一次d n s 请求可能会花费数秒或数十 秒时间才能完成。在通过浏览器访问网页时，d n s 解析不会造成太大的影响， 然而对于搜索引擎的网络爬虫而言，由于需要频繁地访问w e b 服务器，d n s 解析的时间过长将成为网络爬虫的主要瓶颈，对于高效率的网络爬虫必须要 解决d n s 瓶颈问题。 首先，分析一下域名和m 的对应关系。 2 3 1 域名和i p 对应问题 在互联网中，域名和i p 地址的对应存在复杂的关系，多个不同的u r l 可能会指向相同的物理网丽【13 1 。这种情况下，如果网络爬虫以u r l 作为抓 取目标时，就会导致相同网页的重复抓取，造成资源的浪费。为了解决这个 问题，需要分析清楚域名和口地址的对应关系。 域名和p 地址的对应关系存在四种情况：一对一，一对多，多对一和多 对多。一对一不会造成重复抓取，而后三种情况都有可能会造成重复抓取。 一个域名对应多个i p 的情况可能是由于d n s 轮转产生的，这种情况在 哈尔滨t 稃大学硕十学位论文 商业站点中较常见，因为商业站点的单位时间访问量大，需要复制服务器内 容，通过d n s 轮转达到负载均衡，满足大量用户同时访问的需要。 多个域名对应一个口的情况可能是由于虚拟主机技术产生的。虚拟主机 技术是互联网服务器采用的节省服务器硬体成本的技术，虚拟主机技术主要 应用于h t t p 服务，将一台服务器的某项或者全部服务内容逻辑划分为多个 服务单位，对外表现为多个服务器，从而充分利用服务器硬体资源。存在于 同一p 地址标识的物理服务器下的多个虚拟主机内容互不重复，每一个虚拟 主机拥有各自独立的域名，但对应同一p 地址。 多个域名对应多个m 的情况则是由于一个站点有多个域名相对应，同时 每个域名又分别对应对个m 地址，这种情况相当于上述两种域名和p 地址 对应关系的结合。 网络爬虫必须要解决由于后三种域名和m 地址对应关系所造成的重复 抓取，这样可以减少抓取时间，节约保存网页的存储空间。要解决重复抓取 网页，就要找出那些指向同一物理位置u r l 的多个域名和d 地址，这是一 个逐渐累积的过程。首先要累积到一定数量的域名和m 地址，然后把这些域 名和口对应的首页和首页链接出的最开始几个页面抓取回来。如果比较结果 一样，则应该归为一组。以后抓取的时候可以只选择其中的一个进行抓取即 可。选择的时候应该优先选择有域名的，因为有的网站对于直接用i p 访问的 被禁止的，例如，w w w 1 6 3 t o m 对应的i p 地址为：2 0 2 1 0 8 4 2 7 3 ， 2 0 2 1 0 8 4 2 9 1 ，2 0 2 1 0 8 4 2 6 4 ，2 0 2 1 0 8 4 2 6 3 ，2 0 2 1 0 8 4 2 7 1 ，2 0 2 1 0 8 4 2 7 2 但是直接用h t t p ：e 2 0 2 10 8 4 2 7 3 访问是被拒绝的。 2 3 2 定制d n s 通常操作系统都会提供一个d n s 解析的接口，例如u n i x 类操作系统通 过g e t h o s t b y n a m e 函数来达到此功能。然而操作系统提供的这个接口通常都是 同步的，当抓取线程利用此接口进行d n s 解析时，抓取线程被阻塞直到d n s 解析完成。这就导致d n s 解析的时间开销占到了单次抓取工作的7 0 而成 为网络爬虫的主要瓶颈，因此为了提供网页抓取效率，必须要定制一个d n s 哈尔滨t 稃大学硕十学何论文 解析器来代替操作系统提供的d n s 解析接口。 定制的d n s 解析器可以通过三种方法来提升d n s 解析的效率。 第一种方法是定制一个d n s 客户端，利用多线程的方式进行多个d n s 解析请求的并行处理，并且这种方式可以协助在多个名字服务器间做负载均 衡，避免频繁地向同一个名字服务器发送请求而导致类似于拒绝服务( d e n i a l o f s e r v i c e ，d o s ) 攻击。 第二种方法是采用缓存服务器来保存d n s 解析结果，这种方式可以大大 减少d n s 解析次数，只在第一次遇到一个新的域名时才进行真正的d n s 请 求，之后都从缓存服务器中获取d n s 解析结果。在实际使用中，要设计适当 的缓存服务器的刷新策略，同时要尽量将缓存d n s 结果放在内存中，这样可 以考虑使用一台专门的机器作为