（计算机应用技术专业论文）基于领域的网络爬虫技术的研究与实现.pdf

摘要 随着w e b 信息爆炸式的增长，如何有效的在w e b 中获取有用的信息已变得 及其困难。搜索引擎在信息检索中扮演着重要的作用，已经为人们在日常生活 中进行信息检索不可缺少的工具。y a h o o 、g o o g l e 、m s n 、百度等商业搜索引擎 正是众多通用搜索引擎中最成功的典范，但随着网络变得越来越复杂，这些通 用的搜索引擎也有时会在信息领航中也会迷失方向。然而，最近几年对各种搜 索技术的研究方兴未艾，基于p 2 p 技术的流媒体搜索、元搜索技术、垂直搜索 技术等都成为了搜索领域研究的热点。本文的核心工作就是对主题相关的网络 爬虫进行研究。 首先深入分析一个大规模的搜索引擎，细述了其工作原理，常用的几种搜 索策略，并分析了其优劣点，随后从两个方面分析了w e b 爬虫的技术实现困境： 一是通用搜索引擎需要解决的技术问题，二是通用搜索引擎存在的局限性。接 着给出了主题相关的网络爬虫的实现框图。 考虑到如何克服高度并发、以及对网络带宽的占用问题，提出了设计一个 d n s 解析器，以便于有效的利用网络带宽，减少网络传输延时；为了高效的对 页面进行抓取，保证在进行并行抓取时，各进程间通信的问题，让各个组件之 间高效的工作，在设计中引入了非阻塞套接字技术。u r l 的调度技术在网络爬 虫系统的设计中起着关键的作用，提出了基于概率模型的启发示度量规则，让 我们的网络系统有着更加智能的路由功能，以便于始终可以向着用户设定的主 题进行页面获取。在给出了基于概率模型的启发示度量规则后，更进一步的提 出了基于最佳优先搜索的隧道技术，用于克服对某个主题在进行抓取多次后， 若偏离了原先的主题，可以让其迅速停止工作，从而在u r l 队列中选取下一个 u r l 作为下一次的页面抓取出发点。考虑到技术的完整性，简要的给出网络爬 虫的其他相关技术的实现。 文本分类是主题网络爬虫不可缺少的技术组件。本文提出了一种改进的贝 叶斯分类算法，通用的贝叶斯分类器认为所有的所有词项的重要性都是等概率 的，在这里认为应更加的倾向于各标题中的词项。 最后，设计了一个f o c u s e d c r a w l e r 的原型，给出实验数据。通过对比，分 析、测试、比较了各算法之间的优劣。 关键词：网络爬虫，文本分类，概率模型，搜索引擎 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 ft h ew e bi n f o r m a t i o n ，h o wt oe f f e c t i v e l yg e tu s e f u l i n f o r m a t i o ni nt h ew e bh a v eb e c o m ed i f f i c u l t i e s s e a r c he n g i n ep l a ya ni m p o r t a n t r o l ei ni n f o r m a t i o nr e t r i e v a lf o rp e o p l e i nt h e i r d a i l y l i v e sa n db e c o m ea n i n d i s p e n s a b l et o o lw h e ns e a r c hi ni n t e r n e t y a h o o ，g o o g l e ，m s n ，a n db a i d ua r et h e m o s ts u c c e s s f u l e x a m p l e s i nt h o s eo ft h e l a r g e n u m b e ro fc o m m e r c i a l g e n e r a l p u r p o s es e a r c he n g i n e s t h e s eg e n e r a l - p u r p o s es e a r c he n g i n e sa r es o m e t i m e s l o s ei t sd i r e c t i o na sn e t w o r k sb e c o m em o r ec o m p l e x h o w e v e r , i nr e c e n ty e a r s v a r i o u ss e a r c ht e c h n o l o g i e se m e r g i n g ，s u c ha ss t r e a m i n gm e d i as e a r c hb a s e do np 2 p t e c h n o l o g y ，m e t as e a r c ht e c h n o l o g y ，v e r t i c a ls e a r c ht e c h n o l o g yh a v eb e c o m eah o t r e s e a r c hi nt h ef i e l do fs e a r c h t h ec o r ew o r ki nt h i sp a p e ri ss t u d y i n gd o m a i n - b a s e d c r a w l e r f i r s t l y ，w ea n a l y z eal a r g e s c a l es e a r c he n g i n ed e e p l y ，s t a t ei t sw o r k i n gp r i n c i p l e i nd e t a i l s ，a n da n a l y z et h e i ra d v a n t a g e sa n dd i s a d v a n t a g e si ns e v e r a lc o m m o n l yu s e d s e a r c h s t r a t e g y ，a n dt h e na n a l y z e d t h ed i f f i c u l t i e so fw e bc r a w l e rt e c h n i c a l i m p l e m e n t a t i o nf r o mt w oa s p e c t s f i r s t ，s o m et e c h n i c a li s s u e sm u s tb er e s o l v e di n g e n e r a l - p u r p o s es e a r c he n g i n e s ，a n dt h eo t h e ri st h el i m i t a t i o no ft h es e l f - e x i s t e n c e t h e nw ep u tu pw i t ha ni m p l e m e n t a t i o nd i a g r a mo fd o m a i n - r e l a t e dn e t w o r kc r a w l e r t a k i n gi n t oa c c o u n th o wt oo v e r c o m ec o n c u r r e n c y ，a sw e l la st h ep r o b l e mo ft h e o c c u p y i n go ft h en e t w o r kb a n d w i d t h ，w ep r o p o s et or e - d e s i g no fad n s r e s o l v e ri n o r d e rt oe f f i c i e n t l yf a c i l i t a t en e t w o r kb a n d w i d t ha n dr e d u c en e t w o r kt r a n s m i s s i o n l a t e n c y ，f o re f f i c i e n tc r a w l i n gt h ep a g e sa n de n s u r et h a tp a r a l l e lc r a w l i n gi nw e b ，a s w e l la st h ec o m m u n i c a t i o no fa n yp r o c e s sa n de n a b l et h ev a r i o u sc o m p o n e n t sw o r k e f f i c i e n t l y ，an o n - b l o c k i n gs o c k e tt e c h n o l o g yi si n t r o d u c e di no u rd e s i g n i n g u r l t h es c h e d u l i n gt e c h n o l o g yo fu r li nt h en e t w o r ks y s t e md e s i g n i n gp l a yak e yr o l e ，a p r o b a b i l i s t i cm o d e lb a s e do nm e t r i c sa r ep r o p o s e dt h a ti n s p i r e df r o ma s e to fr u l e s ，s o t h a to u rc r a w l e rs y s t e mh a sam o r ei n t e l l i g e n tr o u t i n gf u n c t i o n i no r d e rt oa l w a y s a c c e s st os o m et o p i cp a g e st h a tt h eu s e rs e t a f t e rg i v e nap r o b a b i l i t y b a s e dm o d e l t h a tm e a s u r e ，w ef u r t h e rp r o p o s e dt u n n e lt e c h n o l o g yb a s e do nt h eb e s t - f i r s ts e a r c h i i s t r a t e g yu s e dt oo v e r c o m et h et o p i cd r i f t i n gd u r i n gac r a w l i n g o nm a n yo c c a s i o n s i f d e v i a t e df r o mt h eo r i g i n a lt o p i c ，t h ec r a w l e rc a ns t o pw o r k i n gi n s u c hu r ls o q u i c k l y s or e m o v eau r l i nt h eh e a do fq u e u ea sau r lt oc r a w la sn e x ts t a r t i n g p o i n t i nl i g h to ft h ei n t e g r i t y o ft e c h n o l o g y ，w eb r i e f l yg i v et h eo t h e rr e l a t e d t e c h n o l o g yi m p l e m e n t a t i o no ft h ec r a w l e r t e x tc l a s s i f i e ri sa ni n d i s p e n s a b l ec r a w l e rt e c h n o l o g yc o m p o n e n ti nt o p i c n e t w o r kc r a w l e r t h ep r i n c i p l eo fb a y e s i a n c l a s s i f i c a t i o ni ss i m p l ea n dt h e i m p l e m e n t a t i o ni sn o to v e r l yc o m p l i c a t e dc o m p a r e dw i t ho t h e rc l a s s i f i e r ，a n dh a sa h i g hp e r f o r m a n c e i nt h i sp a p e r a l li m p r o v e db a y e s i a nc l a s s i f i c a t i o na l g o r i t h m p r o p o s e d ，g e n e r a lb a y e s i a nc l a s s i f i e rb e l i e v et h es a m ei m p o r t a n to ft h ep r o b a b i l i t y a b o u ta l lt h ew o r d s ，h e r ew ea r em o r ei n c l i n e dt ot h ew o r d s i nt h et i t l eo ft h ei t e m f i n a l l y ，w ed e s i g n e dap r o t o t y p eo ff o c u s e d - c r a w l e r ，a n dg i v et h ee x p e r i m e n t a l d a t ab ya n a l y s i s ，t e s t i n g , a n dc o m p a r i n gt h e m e r i t sa n ds h o r t c o m i n g so ft h e a l g o r i t h m s k e y w o r d s ：c r a w l e r ；t e x tc l a s s i f i c a t i o n ；p r o b a b i l i t ym o d e l ；s e a r c he n g i n e i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：连盘连日期：兰1 2 ：兰：塑 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时 授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 武汉理_ _ l = 大学硕士学位论文 1 1 选题的背景 第1 章绪论 随着网络信息的爆炸式增长，通用搜索引擎面临着索引规模、文本库如何 如何快速更新和个性化需求等多方面的挑战【1 ，2 1 。为应对这些挑战，适应特定用 户需求的主题式和基于个性化搜索的主题网络爬虫( f o c u s e dc r a w l e r ) 应运而生 1 3 j ，又被称作垂直搜索引擎。基于领域的网络爬虫的搜索引擎( 即第四代搜索引 擎) 已经成为当前搜索引擎和w e b 信息挖掘中的一个研究热点和难点。 正如我们所知，通用搜索引擎在商业运用中取得了极大的成功，具有代表 性的有g o o g l e 、y a h o o 、b a i d u 等国内外知名的搜索。搜索引擎自诞生起就受到 到研究研究学者们的广泛关注。搜索引擎正是人们为了解决网上信息检索的难 题，逐渐成为人们获取知识和访问互联网的入口，但它同时也暴露出一些缺点。 其一，是由于其通用性，爬虫抓取网页时没有针对性，因而也无法对其抓取的 结果进行针对特定领域的进一步分析，导致查询结果不够深入和专业化【4 】；另一 个问题在于对用户提出的查询，通用搜索引擎通常会返回许多与用户所寻找的 主题无关的结果，造成信息过载1 3 ，4 j ( i n f o r m a t i o no v e r l o a d ) 。 与此同时，国内外的专家学者们对专业爬虫技术进行了广泛的研究。国内 具有代表性的有：刘金红、陆余良在他们所写的关于主题网络爬虫综述性的文 章罩给出了主题网络爬虫的研究目标，分析了近年来国内外主题爬虫的研究方 法和技术1 5 l 。刘文建在他的博士论文罩提出了将网络信息查询与收集有机结合起 来，建立面向用户兴趣的新型信息服务系统1 6 j ，该系统可以自动识别用户兴趣， 自动生成用户角色模型，帮助用户生成检索请求，向用户推送信息。张岭在他 里的博士论文里提出了将智能挖掘算法有机的结合到搜索引擎中，智能化w e b 信息评价，资源价值标定、分布式图结构索引等w e b 信息挖掘的模型7 1 。李盛 韬在他的硕士论文里基于主题的w e b 信息采集技术1 8 j ，具体涉及到u r l 选择、 s p i d e r 采集、页面分析、u r l 与主题的相关性判定等技术进行的细致分析。李 京京在他的硕士学位论文里对主题爬虫的关键技术进行了研列9 1 ，主要提出了结 合p a g e r a n k 算法，进而改进s h a r k s e a r c h 算法，是一种即基于网页权威又兼顾 网页之间的相关性的算法。 武汉理工人学硕士学位论文 国外的研究者在这个领域的研究也是相当的活跃。其中，c h r i s t o sm a k r i s ， y a n n i sp a n a g i s ，e v a n g e l o ss a k k o p o u l o s 等人提出一种利用w e b 页面分类来解决 产生个性化结果的算法1 1 0 j 。g a l m p a n i d i s ，c k o t r o p o u l o s ， i p i t a s 等人开发 了一个隐含语义索引分类器，用来检索基于特定域的w e b 文档1 1 1 1 。s o u m e n c h a k r a b a r t i ，m a r t i nv a nd e nb e r g ，b y r o nd o m 提出了聚焦爬虫的概念，用来有 选择性的搜出那些已定义好主题的页耐引。z h i q i a n gw a n g 和r u i f a nl i 提出了用 反向索引解决那些频繁更新聚集主题的搜索引擎【1 2 j 。c h e nd i n g 和j a g d i s hc 提 出了用自组织映射关系来于个性化的搜索引擎1 1 3 1 。a l e x a n d r o sb a t z i o s ，c h r i s t o s d i m o u ，a n d r e a sl 等人提出基于语义w e b 的智能代理的b i o c r a w l e r 爬虫，通过 学习语义内容来相应的调节爬虫行为i l 训。g a u t a mp a n t 提出了用支持向量机作为 主题爬虫的向导，利用链接结构附近的和所有父页面的词汇来优化爬虫行为【1 引。 j y h - j o n gt s a y ，c h e n y a n gs h i h ，b o l i a n gw u 提出了自动主题爬虫a u t o c r a w l e r ， a u t o c r a w l e r 是一个由用户兴趣模型构成的，用于协调用户和标识目标实例和关 键词的搜索引擎i l 酬。k eh u 和w i n gs h i n gw o n g 提出了一个概率模型的智能w e b 爬虫【1 7 】，用来预测宽度优先搜索的深度的分布。m y u v a r a n i ，n c h s n i y e n g a r ， a k a n n a n 提出了l s c r a w l e r 爬虫1 1 引，通过推测基于链接关系的关键词和链接上 下文之间的相关度来检索文档。r u ic h e n ，b i p i nc d e s a i ，c o n gz h o u 提出了 c i n d ir o b o t i l 9 】，是一个基于多层检测模式来发现相关w e b 页面的爬虫。a t h e n a s t a s s o p o u l o u 和m a r i o sd d i k a i a k o s 提出构造一个贝叶斯网络来自动分类可访的 会话日志【2 0 1 。q i o n gl i ，t a oj i n ，y u c h e nf u 等人设计和实现了一个主题驱动的 爬虫1 2 ，用于使用词频和编辑原理来计算相关度和提炼相关页面的初始集。 a n d r eb e r g h o l z 和b o r i sc h i d l o v s k i i 通过描述p i w 来发现隐含页面的入口，设计 了一个基于域的爬虫1 2 2 j ，这个爬虫用预定义好的文档和相关关键词来初始化。 a l e x a n d r o sn t o u l a s ，p e t r o sz e r f o s ，j u n g h o oc h o 构造一个可用于发现下载隐含页 面的爬虫l2 3 1 。x y u a n ，m h m a c g r e g o r ，j h a r m s 研究网络发现现有网络4 0 的流量是由于爬虫引起的，设计了一个可以消除网络拥塞的方法【2 4 l 。z h uq i a n g 设计了一个基于增强学习和模糊聚类理论的o f c 的聚焦w e b 的爬虫算法1 2 5 l 。 在主题搜索引擎中使用的爬虫程序并不像通用爬虫那样迸行全网抓取，这 类程序仅访问与给定主题相关的网页，搜索算法在访问页面之前进行预测分析， 从而识别出这些页面是否与主题相关，决定是否访问或者确定访问的优先顺序。 通常将这类爬虫称为聚焦爬虫( f o c u s e dc r a w l e r ，也被称为主题驱动爬虫 2 武汉理。i ：大学硕士学位论文 t o p i c d r i v e nc r a w l e r 或主题爬虫) ，聚焦爬虫可以有效地减少采集页面的数量， 同时也节约了网络带宽，提高信息搜索的效率。 1 2 搜索引擎的发展现状 为了高效地抓取与主题相关的页面，研究者提出了许多主题定制爬行策略 和相关算法，使得网络爬虫尽可能多地爬行主题相关的网页，尽可能少地爬行 无关网页，并且确保网页的质量。互联网上的搜索引擎可以分为两大类：目录 式搜索引擎以及基于关键词的搜索引擎【2 6 ，2 7 1 。 1 人工目录式搜索引擎 目录式搜索引擎的数据库是由人工编辑的，由专业人员对网络上的信息按照 主题进行组织，编制成为层次次的主题或主题目录。 目录式搜索引擎的典型代 表是y a h o o 、o p e nd i r e c t o r y 。y a h o o 的信息组织方式具有以下特点：完备分类 体系，归纳网上信息。它将传统的分类思想移植于网上信息的组织，在此思想 的指导下，结合网络信息源的特点，构筑类目体系。o p e nd i r e c t o r y 是一个开源 的项目，由全球所有的有共同爱好的一群人提供他们知识领域的相关文档目录。 由于网络信息高增迅速，使得采集信息的速度远远跟不上信息增长的速度， 更不用说编制主题索引的速度了；不同搜索引擎的体系结构不同，分类体系的 建立缺乏统一的标准，使得同一内容的信息在不同搜索引擎中经常会被归入不 同类目，造成用户的困扰；成本高，时效差。随着网络应用技术的不断深入发 展，用户不再满足于这种对网站分类和摘要的简单查找，更希望对内容进行查 找，于是就出现了基于关键词查询的搜索引擎。 2 按关键词进行搜索 目前互联网上的搜索引擎大多数都采用了基于关键词的查询技术，其典型 代表为g o o g l e 和百度，其内容可以覆盖互联网上的绝大多数网页内容。基于关 键词的搜索引擎由用户的提问词组成，这种情况会导致数以百万计的页面1 2 ， 用户一般只关心前几页的结果。 目前，搜索引擎与目录索引有相互融合渗透的趋势。原来一些纯粹的全文 搜索引擎现在也提供目录搜索，如g o o g l e 就借用o p e nd i r e c t o r y 目录提供分类 查询。而像y a h o o ! 这些老牌目录索引则通过与g o o g l e 等搜索引擎合作扩大搜 索范围。在默认搜索模式下，一些目录类搜索引擎首先返回的是自己目录中匹 武汉理工人学硕士学位论文 配的网站，如国内搜狐、新浪、网易等。 针对基于关键词搜索引擎所存在的不足，搜索引擎向着智能化、个性化方面 发展，搜索引擎已成为一个新的研究、开发热点领域。这些技术主要有以下几 占1 2 7 1 j 、 ( 1 ) 用户行为日志的特征分析 通过分析用户使用网络的行为特征，如经常浏览的内容、集中上网时间、 使用软件情况、使用习惯，包括用户使用点击鼠标记录等一切能获取用户信息 的行为以日志的形式获取。例如，网络用户一般只查看最前面的几页的搜索结 果，普通网络用户很少使用操作符构造提问式等。该研究还对搜索次数与用户 每分钟查看的文献或目录数进行了分析。从而演化出了基于日志的网络搜索引 擎技术，数据挖掘技术起到了关键性的作用。 ( 2 ) 多媒体搜索技术 一般而言，可用的网络检索的多媒体信息一般有图像、声音、视频等。如 国内的百度在m p 3 搜索技术应用方面也比较成熟。但目前的多媒体搜索引擎覆 盖面小，检索功能不够完善，效果也不太理想，因此，多媒体搜索技术尤其是 音频、视频数据的检索仍是搜索引擎的一个研究重点。 ( 3 ) 智能信息检索技术 智能检索主要包括自然语言处理、个性化搜索等技术，目前涉及这一领域 的研究较多。以下三点值得我们注意1 7 1 ：1 ) 智能搜索软件发展的一个方向是增 加语言分析功能。2 ) 要开发针对个人用户兴趣的信息搜索工具。3 ) 智能信息 搜索的研究可以把人工智能的理论和应用有机地结合起来。 ( 4 ) 基于p 2 p 的搜索技术 以p 2 p 为技术核心的b t 为用户带来了全新的体验，人们可以互相共享资料， 新松获取自己想要的信息。j 下如我们所知，目前的互联网是以服务器为中心的， 人们向服务器发送请求，然后浏览服务器回应的信息，而对等搜索技术p 2 p 是 以用户为中心，所有的用户都是平等的伙伴。相隔万里的用户可以通过p 2 p 共 享硬盘上的文件、目录甚至整个硬盘。把这一理念具体运用到搜索引擎技术上 来：p 2 p 将使用户能够深度搜索文档，而且这种搜索无须通过w e b 服务器，也 可以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎无可比 拟的深度。 ( 5 ) 对检索结果进行优化处理 4 武汉理工人学硕十学位论文 目前这方面的研究主要集中在结果排序的优化算法、结果的聚类及可视化 等领域。要想真正解决网络搜索问题，完全满足用户的各种信息查询需求，搜 索引擎还需要解决的很多难题。 1 3 文本分类技术概述 如何有效地将网页按照某种给定的模式进行机器学习自动分类是一个非常 重要的课题。传统的操作模式有人工方式或半自动方式，是由某个领域的专家 人员经过检查后，形成分类摘要，并将所得到的结果按照预定的要求放到某个 特定的类库中。由于这种分类方法加入了人的智能，所以信息分类一般比较准 确，分类质量较高。可以较好的满足用户的要求。利用这种方法所开发出来的 搜索引擎代表有y a h o o ，o p e n d i r e c t o r y 等。 文本分类在信息检索系统中是对被检索的文本集按照事先预定的要求进行 有序的组织，将内容相似或相关的文本组织在一起，以便于后续进行高效准确 地查询信息检索系统。主动式的信息发现就要是解决将用户目标和源文本进行 自动归类，将收集到的文本资源划分为与用户相关类或无关类。 传统的自动文本分类方法主要有【2 8 羽】：朴素贝叶斯分类、支持向量机、最 大熵算法、最大期望值、神经网络和规则学习算法等。传统的文本分类器适用 于完整的、无结构的文本，对于像w e b 网页这种常常是局部的、半结构的文档， 许多在传统文本集中性能良好的算法处理效果并不显著。w e b 文档的半结构性 对于自动文本分类器是个难题，也是目前的一个研究热点。 与基于主题信息采集相比较，w e b 网页分类可实现另一种实际意义上的按 特定点题信息进行分类。本文第4 章所研究的页面分类算法是基于改进的朴素 贝叶斯分类的。就是对已下载网页的处理，按照训练算法将网页分类，在检索 时仅在符合需求的类别中查找。建立自动的分类信息资源，为用户提供分类信 息目录。 1 4 本文的结构及研究的内容 本文在第1 章罩主要简述了搜索引擎的发展现状。并简要的介绍了主题网 络爬虫的关键技术之一文本分类技术。在第2 章里谈到了网络爬虫技术， 主要以通用网络爬虫作为引入点，介绍了其基本实现原理和相关技术；通用网 武汉理工大学硕士学位论文 络爬虫可能存在的问题及其技术困境，从而引出第3 章和第4 章，在第3 、4 章 里提出了自己解决方案。 第3 章和第4 章是本文的核心部分，较为详细的介绍了网络爬虫各个部件的 技术实现原理。如第3 章围绕领域相关的爬虫技术分述了各个组件的功能实现， 如域名解析器的设计、并行抓取策略、u r l 调度技术、页问存储更新技术、以 及与主题爬虫相关的其他技术。这些技术都是爬虫设计中最重要的技术，对爬 虫性能的影响也最为关键。我们作了重点阐述。 第4 章就文本分类技术作了介绍。文本分类是主题爬虫中不可少的技术之 一，也是最为核心的技术之一。现今有较为成熟的技术，如向量空间模型；有 一些研究热点，如朴素贝叶斯分类器、决策树分类器、支持向量机分类、神经 网络分类器等。本文中介绍了向量空间模型，引入了朴素贝叶斯分类技术并给 出了改进算法，作为自动主题分类之用。 第5 章就第3 、4 章的技术作了技术实现。简要介绍了实验步骤，作了数据 分析。本文的主要研究内容有： 1 领域相关的网络爬虫的体系结构的设计 2 高可用性的域名解析器( d n s ) 的设计 3 并行抓取策略( 非阻塞套接字技术的运用) 4 u r l 调度技术( 基于概率模型的度量规则和基于最佳优先搜索的隧道技 术) 5 页面存储更新技术 6 文本分类技术( 一种改进的基于朴素贝叶斯分类器的分类算法) 武汉理工人学硕十学位论文 2 1 网络爬虫概述 第2 章网络爬虫 网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页， 是搜索引擎的重要组成。它常常是一个计算机程序，日夜不停地运行。它要尽 可能多、尽可能快地搜集各种类型的新信息，同时因为互联网上信息更新很快， 所以还要定期访问已经搜集过的旧信息，以避免死链接和无效链接。由于互联 网中存在海量信息而且复杂多变，w e b 爬行器的实现常常采用分布式、并行计 算技术，以提高信息发现和更新速度。 图2 - 1 典型的大规模网络爬虫的解析图1 3 5 l 武汉理_ 【人学硕士学位论文 2 1 1 网络爬虫的工作原理 一个典型的大规模爬虫的解析图如图2 - 1 所示。传统爬虫从一个或若干初始 网页的u r l 开始，获得初始网页上的u r l ，在抓取网页的过程中，不断从当前 页面上抽取新的u r l 放入队列，直到满足系统的一定停止条件，另外，所有 被爬虫抓取的网页将会被系统存贮，进行一定的分析、过滤，并建立索引，以 便之后的查询和检索；对于聚焦爬虫来说，这一过程所得到的分析结果还可能 对以后抓取过程给出反馈和指导。 爬行器怎样抓取所有的w e b 页面呢? 在w e b 出现以前，传统的文本集合， 如目录数据库、期刊文摘存放在磁带或光盘里，用作索引系统。与此相对应， w e b 中所有可访问的u r l 都是未分类的，收集u r l 的唯一方式就是通过扫描 收集那些链向其他页面的超链接，这些页面还未被收集过。这就是爬虫的基本 实现原理1 3 5 ，3 6 1 。 他们从给定的u r l 集出发，逐步来抓取和扫描那些新的出链。这样周而复 始的抓取这些页面。这些新发现的u r l 将作为爬行器的未来的抓取的工作。随 着抓取的进行，这些未来工作集也会随着膨胀，由写入器将这些数据写入磁盘 来释放主存，以及避免爬行器崩溃数据丢失。没有保证所有的w e b 页面的访问 都是按照这种方式进行，爬行器从不会停下来，爬行器运行时页面也会随之不 断增加。除了出链1 外，页面中所包含的文本也将呈交给文本索引器，用于基于 关键词的信息索引。 通常来说写出一个基本的爬行器是比较简单的，但对于用于商业爬行器来说 时就会涉及到大量的工程问题，如抓取大量的可访问的w e b 页面。w e b 搜索公 司，如a l t a v i s t a ，n o r t h e r nl i g h t ， i n k t o m i ，以及诸如此类的公司都发表了爬行 技术的白皮书【3 7 l ，将这此技术细节拼接在一起也不是一件易事。在公众领域仅 仅存在一些文档所给出的细节，如一篇有关a l t a v i s t a sm e r c a t o r 爬行器的文章和 g o o g l e 公司第一代爬行器的描述基于这些信息，给出了一个大规模爬行器的精 确的结构图。 1 我们将贞面中的h r e f 标签定义为页面的 i j 链，在后文中我们给出了规范的定义，凶而文奉中名词“出 链”与“反向链接”被视为同义词 8 武汉理工人学硕+ 学位论文 2 1 2 网络爬虫的搜索策略 网络爬虫的抓取策略有m 地址搜索策略、广度优先、深度优先和最佳优先 等几种搜索策略【5 , 3 8 】。目前常见的搜索策略有【3 8 4 1 】： 1 基于i p 地址的搜索策略1 3 引。先赋予爬虫一个起始的i p 地址，然后根据 i p 地址递增的方式搜索本口地址段后的每一个w w w 地址中的文档，它完全不 考虑各文档中指向其它w e b 站点的超级链接地址。优点是搜索全面，能够发现 那些没被其它文档引用的新文档的信息源；缺点是不适合大规模搜索。 2 广度优先搜索策叫3 9 m j 。广度优先搜索策略是指在抓取过程中，在完成 当前层次的搜索后，才进行下一层次的搜索。这样逐层搜索，依此类摔推。该 算法的设计和实现相对简单。很多研究者通过将广度优先搜索策略应用于主题 爬虫中。他们认为与初始u r l 在一定链接距离内的网页具有主题相关性的概率 很大。 3 深度优先搜索策略【3 9 m j 。深度优先搜索在开发网络爬虫早期使用较多的 方法之一，目的是要达到叶结点，即那些不包含任何超链接的页面文件。在一 个h t m l 文件中，当一个超链被选择后，被链接的h t m l 文件将执行深度优先 搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优 先搜索沿着h t m l 文件上的超链走到不能再深入为止，然后返回到某一个 h t m l 文件，再继续选择该h t m l 文件中的其他超链。当不再有其他超链可选 择时，说明搜索已经结束。 4 最佳优先搜索策略【3 8 】。最佳优先搜索策略按照一定的网页分析算法，先 计算出u r l 描述文本的目标网页的相似度，或与主题的相关性，设定一个阀值， 并选取评价得分超过阀值的u r l 进行抓取。它只访问经过网页分析算法计算出 的相关度大于给定的阈值的网页。存在的一个问题是，在爬虫抓取路径上的很 多相关网页可能被忽略，因为最佳优先策略是一种局部最优搜索算法。因此需 要将最佳优先结合具体的应用进行改进，以跳出局部最优点。将在3 4 3 小节中 结合网页分析算法作具体的讨论。 9 武汉理。r 大学硕士学位论文 2 2 网络爬虫的实现 2 2 1 网络爬虫的技术实现 在2 1 1 小节中，基于c h a k r a b a r t i 博士的研究成果给出了一个典型的大规 模的爬虫的解析图。这个图反映出了在设计一个爬行器时应考虑到的一些技术 细节。包括缓存( c a c h i n g ) 、域名解析系统( d n s ) 、多线程、链接( u r l ) 提 取以及标准化文本。按照爬虫程序的排他性协议，为了减少可见的u r l 和页面 内容，以及在各服务器之间下载操作之间进行负载均衡( 一种较为优雅的实现 策略) 。我们忽略了更新速率、性能监测，以及如何操作隐藏页面这些问题。 一个典型的操行流程为【4 3 j ：首先u r l 队列有几个种子u r l 作为种子页面，每 个d n s 线程从u r l 队列中提取一个u r l ，并将该u r l 从队列中移除，准备尝试通 过地址解析得到该主机的i p 地址。由d n s 线程在d n s 数据库中查看是否有该主 机名是否已经被解析过了，如果已经解析过，则该线程直接从数据库中取得该 主机的i p 地址；否则d n s 线程向d n s 服务器请求获取该主机的i p 地址。当一 个用于读操作的线程收到已解析的i p 地址时，尝试打开一个h t t p 连接，请求 抓取指定的页面。 当页面下载完成后，由爬行器来检测该页面的内容来避免出现重复页面。接 着，爬行器将提取该页面中的u r l 且将该u r l 标准化，从而更进一步的来验证 爬行器是否能够爬行这些提取出来的u r l ，以及检查爬行器之前是否已经访问过 这些刚提取出来的u r l ，来避免爬行器陷入无限循环。可由m d 5 算法将这些u r l 作哈希处理，且在u r l 数据库中存取这些哈希值作为后需检查之用。 最后，假如这些u r l 是爬行器第一次遇到的u r l ，将由爬行器将这些u r l 插 入u r l 队列之中，对于一般用途的爬行器可以使用f i f o 数据结构来设计这样一 个u r l 队列。当然，考虑到成千上万的同步请求，爬行器首先要做的事就是将 把那些不能及时服务的请求打上时间戳并存取在一个服务之中。出于安全性考 虑，爬行器仅仅在这些时间戳足够旧时( 典型情况为1 0 秒) 【3 】访问那些u r l 。 其间，假如一个线程取得的u r l 为忙服务请求，则爬行器将该u r l 置入忙队列。 由所有的线程来在u r l 队列和忙队列之间间隔访问，来防止其中某一个队列出 现饥饿的情况。通用的网络爬虫的爬行算法如下：g e n e r a lc r a w l e r ( 7 ，d ，e ) ： 1 0 武汉理工大学硕士学位论文 1 ) i n i t i a l ( f r o n t i e r ) 2 ) w h il ef o n t i e r 硭oa n dv i s i t e d _ p a g e s m a x p a g e s 3 )甜d e q u e u e ( f r o n ti e r ) 4 ) d ( “) f e t c h ( ”) 5 )s t o r e ( d ，( 材，d ( “) ) ) 6 )u r l l i s t p a r s e ( d ( 甜) ) 7 ) f o r ，i nu r l 1 i s t 8 ) s t o r e ( e ，( 材，) ) 9 ) i f ，隹f r o n t i e ra n dv 隹d 1 0 ) e n q u e u e ( f r o n t i e r ， ，) 1 1 )e n di f 1 2 ) e n df o r 1 3 ) e n dw h i l e 图2 2 基本的网络爬虫实现算法 如图2 - 2 算法描述。语句1 使用种子u r l 初始化队列f r o n t i e r 。语句2 至 语句1 3 是由w h il e 语句控制的大循环，当存入u r l 的队列非空且所有可访页面 数未达到上限时，用爬行器周而复始的收集页面。语句3 至语句6 做负责取队 列头的u r l 存放在“中，抓取“页面存入在d ( u ) 中，以及将甜及所抓取的页面d ( u ) 存入集合d 中，以免主存溢出，同时解析页面d ( u ) 中的所有的u r l ，存放在链表 u r ll i s t 中。语句7 至语句1 2 首先将甜的所有的反向链接v 的所有的链接对存放 在集合e 中，若v 未被访问过，则将v 插入u r l 队列f r o n t i e r 之中。 2 2 2w e b 爬行的实现困境 通用网络爬虫通常需要解决以下几个技术问题1 1 ，2 ，7 ，1 0 1 ： 1 抓取一个页面可能有数秒的网络延迟，因此必须要尽可能的利用网络带 宽，同时抓取多个页面。 2 如何解决高度并发问题。就需要定制个性化的d n s 域名服务器，如 有多个d n s 服务器，才有可能实现多同步抓取。 武汉理r 大学硕士学位论文 3 如何保持爬行器较高的吞吐量。最好的方案是使用非阻塞的套接字技术。 4 如何防止u r l 重复。为了克服出现冗余抓取，必须合理的设计系统， 使其可以避免由粗心或是恶意用户构建一些站点，抓取那些可能是假冒 的u r l 集。 这些通用性搜索引擎也存在着一定的局限性【4 6 】，如： 1 通用搜索引擎大是基于关键字的检索技术，不支持基于语义的查询。 2 通用搜索引擎所返回的结果包含大量用户不关心的无用信息。这样用户 体验感会比较差。 3 通用搜索引擎的目标是尽可能全面的抓取整个w e b 上的资源，这样就存 在有限的搜索引擎服务器资源与无限的网络数据资源之间的矛盾问题。 4 通用搜索引擎往往对具有一定结构的高密集数据无能为力，不能很好地 发现和获取。 为了解决上述问题，主题爬虫应运而生，也就是本文提出的基于领域的网络 爬虫技术。与通用爬虫不同，主题