（通信与信息系统专业论文）bbs热点分析系统研究.pdf

中文摘要 摘要； b b s ，即电子公告栏，是目前大众尤其是大学生钟爱的交流方式和言论重地。 由于可以发表平时不敢说的言论，b b s 成为了社会热点问题和学校焦点问题的发 散地。但它的缺点是人们可以利用它匿名的特点发表不负责任的言论确相安无事， 而且很多时候社会上的主流观点却成为了人们批判和抨击的对象。因此对b b s 上 的言论进行正确的舆论导向是一样很重要的工作。 网络爬虫是伴随着搜索引擎的诞生而出现的，是一个自动提取网页的程序， 它为搜索引擎在w e b 上下载网页，是搜索引擎的关键组成部分。由于w e b 信息的 爆炸式增长，人们获取网络信息的方式也越来越依靠搜索引擎，因此对网络爬虫 的要求也越来越高。现在比较常用的几种爬虫有：聚焦爬虫、个性爬虫、分布式 爬虫、主题爬虫等。 利用爬虫可以自动从网上不间断获取数据的特性，我们对某高校b b s 进行大 量的数据获取，对主题行为进行了详细研究，通过m a n a b 仿真和c 玳码实现，根 据现有信息预测未来主题的回帖情况，对每个帖子的未来走势进行科学预测和热 点分析，从而起到协助学校b b s 舆论导向的作用。 本文主要介绍网络爬虫产生和发展，各种网络爬虫的特点，重点介绍了主题 爬虫的工作原理，并介绍了在此基础之上开发的热点分析系统的设计和实现。 关键词：搜索引擎；网络爬虫；b b s ：热点分析 分类号：t p 3 1 9 a b s t r a c t a b s t r a c t b b s ，n a m e l yb u l l e t i nb o a r ds y s t e m , a tp r e s e n ti sp e o p l e s ，e s p e , c i a u yc o l l e g e s t u d e n t s f a v o r i t es t y l eo fc o m m u n i c a t i o na n dt h em o s ti m p o r t a n tp l a c eo fd e l i v e r s p e e c h e s b u tp e o p l e sa r ea l l o w e de x p r e s st h ei r r e s p o n s i b l es p e e c h e sw i m o u tb e i n g p u n i s h e d b e c a u s e t h e y a r ea l w a y sa n o n y m o u s 1 1 l e w s i t u a t i o n i s t h a t i n m a n y t i m e s t h em a i n s t r e a mo p i n i o n smc r i t i c i z e da n da t t a c k e di n s t e a do fs u p p o a i n gb yp e o p l e t h e r e f o r e ，i ti so n eo f t h em o s ti m p o r t a a tt h i n g st os u p e r v i s ea n dg u i d et h es p e e c h e si n _ b b sb yr i g h tm l s i t l l e $ 1 kw e b c r a w l e ra p p e a r e dd u et ot h eb i r t ho f 帕s e a r c he n g i n e w e b c r a w l c ri sa s o f t w a r eo fc a t c h i n gt h ew e bi n f o r m a t i o na u t o m a t i c , a l l y 锄di st h ek e yc o m p o s i n go t s e a r c he n g i n e w i 山t h eb u r s to ft h ew e bi n f o r m a t i o n , p e o p l ea i r eg e t t i n gi n o r ca n d d l o l _ eu s e dt oo b t a i ni n f o r m a t i o nd e p e n d i n go l ls e a r c he n g i n e , s ot h ec a p a b i l i t yo f w e b c r a w l e rn e e dt ob ei m p r o v e de i t h e r t h e r ea 增。咖ef a m i l i a rw e b c r a w l e ri nt h e m a r k e ts u c ha sf o c u s i n gw e b c r a w l 盯i n t e l l i g e n tw e b c m w l e r , d i s t r i b u t i n g w e b c r a w l e r , t o p i cw e b c r a w l e r , e r e ， r e c u r r i n gt ot h ec h a r a c t e r i s t i co fw e b c r a w l e r st h a tt h e yc g e ti n f o r m a t i o nf i o m i n t e r n e ti n e e s r l t l ya n da n t o m a t i e a l l y , w eh a v eo b t a i n e dal o td a t a 矗d mo n ec o l l e g e b b sa n dh a v ea n a l y z e dt h o s ed a t ad e t a i l e d l y t h r o u g ht h em a t l a bs i m u l a t i o na n dc # o r o g r a m m i n g , w eh a v e d o n eal l o t t w a l - et h a tc a nf o r e c a s tt h ef u t u r ef e e d b a c ks i t u a t i o n t o e v e r yn o l oi nt h eb b $ d e p e n d i n go nt h ee x i s t i n gd a t aa n dt h e nh a v eh c l p e dc o l l e g e f l l l p e l v i s ot h eb b s 1 1 l i bp a p e rh a sm a i n l yi n t r o d u c et h ee m e r g o n c ea n dd e v e l o p m e n to fw e b c r a w l c r , t h ec h a r a c t e r i s t i c s o f e v e r y k i n d o f w e b c r a w l e r s ，i n t h ee n d f o c u s e d o l l i n t r o d l l c j a g t h e d e s i g n i n ga n d r e a l i z i n g o f t h c b b s h o t s p o t a n a l y s i s s y s t e m k e y w o r i ) $ z $ e a r e l ae n g i n e ；w e b c r a w l e r ；, b b s ：h o t s p o t a n a l y s i s c l a s $ 1 、1 0 t p 3 1 9 致谢 本论文是在我的导师刘云教授的悉心指导下完成的，在此，我首先要对刘云 老师两年半来对我无微不至的关心、教育和培养说声：谢谢您i 在攻读硕士学位 期间，刘老师果敢的工作作风、一丝不苟的治学态度、深厚的学术功底、对实验 室和学校的高度责任感以及她正直无私的品格无时无刻不在激励我朝着更高的目 标迈进。她在学术上对我严格要求，在生活中的关心却是无微不至，可以说我在 研究生阶段所取得每一点进步都凝结着刘老师的大量心血! 在读研的两年半中，张振江老师也对我科研和学术水平的提高给予了很大的 帮助和指导工作，对本论文的完成也提出了很多宝贵意见。在此对他在科研上的 指导和生活上的关心表示感谢! 实验室的孟嗣仪老师、穆海冰老师也对我的论文提出了很多建设性意见和耐 心指导，在此对他们的付出表示感谢j 感谢在科研进步的道路上给过我帮助的实验室的师兄师姐和同学们! 由衷地感谢父母对我的养育之思，他们这么多年在生活、学习和其他任何方 面对我默默地支持和帮助是我前迸的最大动力，对他们说声：谢谢您们! 最后，感谢在百忙之中为我评阅论文的专家、老师们l 辛苦了l 序 本论文是围绕目前高校b b s 的舆论引导工作的重要性展开的。设计并开发了 一套b b s 热点分析软件，用于发现b b s 上潜在的可能造成不良影响的热点帖子， 及时发现并配合其它手段阻止不良情况的蔓延。 论文首先介绍系统的产生背景，现实意义以及重要性，并对系统作了整体设 计。网络爬虫模块和热点分析模块是整个热点分析软件的关键都件，也是本论文 经常提到的关键词，因此论文花了大量章节对这两块进行了详细介绍。 论文第二章和第三章是系统实现的理论依据和铺垫。第二章详细介绍了网络 爬虫的产生和发展，简要介绍了几种热点的网络爬虫，包括：聚焦网络爬虫、个 性化网络爬虫、分布式网络爬虫的原理，最后介绍了网络爬虫的关键算法。第三 章重点介绍了主题网络爬的工作原理和功能结构，这是本系统中网络爬虫模块实 现的理论基础 第四章详细介绍了高校b b s 网络爬虫及热点分析系统的开发平台和关键技 术，为系统实现做软件和硬件上的准备 第五章是论文的重点，详细介绍了高校b b s 网络爬虫和热点分析软件的具体 实现过程，包括数据库设计、代码实现原理和实际的运行效果。 最后总结论文所做的工作进行总结并对下一步工作做合理展望。 1 引言 1 1 系统的产生背景及现实意义 1 1 1 高校b b s 的特点 b b s 是b u l l e t i nb o a r ds y s t e m 的缩写，即电子公告栏，是一个可以自由发表 言论的网络论坛。由于b b s 具有相当程度的言论自由度，它很快成为了大众，尤 其是大学生钟爱的交流方式和言论重地。很多学生借助b b s 发表平时不敢说、不 愿意说的言论，使这里成为社会热点问题和学校焦点问题的发散地。由于b b s 具 有匿名性的特点，很多人发表很多不负责任的言论却相安无事，这个现象也使得 b b s 上的意见和观点体现出了多元化和情绪化的特点。而更有意思的情况是，社 会上的主流观点却成为了人们批判和抨击的对射”b b s 上的评论虽然短小也不是 很正式，但却很能反映当代大学生的人生观和价值观，因此对他们进行正确的舆 论导向是一样很重要的工作。 1 1 2 舆论导向的重要性 b b s 的舆论形成速度非常快，再加上很多人情绪化的言论添油加醋，形成星 火燎原之势，使得一个很小的问题在很短时间内被扩大成很难解决的矛盾，因此 必须通过争取的方法杜绝这种情况的发生 在大学校园里，b b s 是最能反映学生思想的前沿阵地，学生们可以在这里对 学校的方方面面的不足，如住宿问题、洗浴问题、食堂伙食问题等发表意见并提 出一些建设性意见，但也有一些学生借此发表一些煽动性和挑衅的言论，而且确 实是能瞬时唤起广大学生的“共鸣”，这种b b s 迅速升成热点话题的现象反映的一 下几种情况： 1 ) 话题本身确实反映了社会、学校在某一方面存在的问题，这就需要学校在 最短时间内给出这一问题的正面回答，并尽快做出相应的解决方法并实施，防止 问题的严重化和扩大化 2 ) 某些人情绪化的发泄。每个人都会有不理智的时候，特别是在高校的学生， 思想活跃，但有时候也很容易冲动，意气用事，当遇到生活上、学习上遇到不愉 快的事情，就会把b b s 当成发泄的渠道而且这种发泄往往能在很短时间唤起广 大学生的共鸣，如果尽早发现并加以控制，就可以控制情绪化的进步扩大，否 则等形成大面积的支持性回帖，就为时已晚，甚至会发生被群体回击的情况。 3 ) 某些人的蓄意辟谣。由于b b s 不用于一般的交流方式和信息发布渠道，具 有匿名性和很大的言论自由度，因此很多人借此机会在上面发布一些偏激言论和 编造的虚假信息。处理这种问题的方法是不仅要尽快地发布与事实相一致的正确 信息，而且要讲出道理，争取网上舆论的正面支持 可见b b s 舆论导向的作用是相当重要的。 1 1 3 系统重要性 通过上面的分析，我们可以看出，舆论导向的工作重点在于一个“早”字， 即越早越快发现潜在的热点话题，并给予正确弓l 导，越能制止不良情况的发生。 但是，二十四小时不问断的监控着某个b b s 系统，包括不同的板块，实时发现热 点话题，需要投入大量的人力和时间，而且人工的监督难免会出现疏漏，是很不 科学的监督方式。b b s 网络爬虫就在这方面体现出了它强大的优势 可以通过网络爬虫实时的获取b b s 上的根贴和回帖数据，通过分析大量的数 据，建立b b s 回帖的数学模型，根据现有数据预测未来可能出现的潜在热点话题， 并对可能造成不良影响的话题加以引导 这种系统的最大特点是通过最少的人力，花费最少的精力来监控b b s 系统， 改变了传统的通过人工手动的监督模式，提高了监控的效率和力度。 1 2 论文的工作和整体结构 1 2 1 系统的整体设计 图1 1 系统整体设计 如图1 1 所示，系统主要包括两大部分，其中b b s 网络爬虫模块主要负责从 高校b b s 上抓取各种信息，包括主题信息、发帖信息、回复情况等，将这些数据 存储到后台数据库中热点分析模块通过分析数据库中的大量数据，建立b b s 话 题的统计模型，建立起一套科学的数学仿真模型，预测可能出现的热点帖子，最 后进行舆论引导。 2 韭夏交道太堂亟堂焦i 幺塞呈l直 本论文重点介绍了上述两个关键模块( b b s 网路爬虫模块和热点分析模块) 的 实现流程，包括前期的市场分析、中期的整体规划和设计，后期的具体开发实现 和最后的系统展望。 1 2 2 论文整体结构 第一章：引言介绍系统的产生背景和现实意义，论文的工作和整体框架 第二章：网络爬虫综述介绍网络爬虫的产生和发展，简要介绍了几种热点 的网络爬虫，包括：聚焦网络爬虫、个性化网络爬虫、分布式网络爬虫的原理， 最后介绍了网络爬虫的主要算法 第三章：主题网络爬虫一重点介绍了主题网络爬虫的工作原理和功能结构， 是b b s 网络爬虫实现的基础。 第四章：开发平台简介一详细介绍了高校b b s 网络爬虫及热点分析系统的开 发平台及关键技术 第五章：高校b b s 网络爬虫及热点分析系统的设计和实现一详细介绍了高校 b b s 弼络爬虫和热点分析软件的具体实现过程，包括数据库设计、代码实现原理 和实际的运行效果 第六章；结论和展望一总结论文所做的工作进行总结并对下一步工作做合理 展望。 2 网络爬虫综述 2 1 网络爬虫的产生和发展 图2 1 网络爬虫在搜索引擎当中的位置结构图 随着互联网的兴起及发展。人们获取信息的途径由传统方式逐渐被网络替代。 起初，人们主要通过浏览网页来获取所需信息，但随着w e b 不断庞大，用这种方 式来寻找自己所需的信息变得越来越困难。现在，大多数的人很大程度上依赖于 搜索引擎来帮助自己获取有用信息，因此搜索引擎技术作为最典型的w e b 信息获 取技术，其发展直接影响人们获取信息的质量，网络爬虫也就应运而生网络爬 虫类程序是搜索弓l 擎中的一个重要部分，它的效率和质量直接影响到搜索引擎的 效率和质量【4 j 。 网络爬虫出自s p i d e r 的意译，具有相同词义的词语还有c r a w l e r ，r o b o t s w a n d e r e r 等等。网络爬虫定义有广义和狭义之分，狭义上的定义为利用标准的 h t t p 协议根据超链接和w e b 文档检索的方法遍历万维网信息空间的软件程序；而 4 广义则是所有能利用h t t p 协议检索w e b 文档的软件都称之为网络爬虫。网络爬虫 是一个功能很强的自动提取网页的程序，它为搜索引擎从万维网上下载网页，是 搜索引擎的重要组成。它通过请求站点上的h t m l 文档访问某一站点。它遍历 w 曲空间，不断从一个站点移动到另一个站点，自动建立索引，并加入到网页数 据库中。网络爬虫进入某个超级文本时，它利用h t m l 语言的标记结构来搜索信 息及获取指向其他超级文本的u r l 地址，可以完全不依赖主题干预实现网络上的 数据获取和搜索。 自从1 9 9 4 年4 月世界上第一个w e b 检索工具w e b c r a w l e r 问世以来，目前较 流行的搜索引擎o o o g l e ，y a h o o ，a l t a v i s t a ，i n f o s e e k i n f o ，m a r k e t 等出于商业机 密的考虑，目前各个搜索引擎使用的c r a w l e r 系统的技术内幕一般都不公开，现有 的文献也仅限于概要性介绍。随着w e b 信息资源呈指数级增长及w e b 信息资源动 态变化，传统的搜索引擎提供的信息检索服务已不能满足人们日益增长的对个性 化服务的需要，它们正面i 临着巨大的挑战以何种策略访问w e b ，提高搜索效率， 成为近年来专业搜索引擎网络爬虫研究的主要问题之一 2 2 网络爬虫的热点技术 2 2 1 聚焦患虫的工作原理和关键技术 网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页， 是搜索引擎的重要组成传统爬虫从一个或若干初始网页的u r l 开始，获得初始 网页上的u r l 。在抓取网页的过程中，不断从当前页面上抽取新的u r l 放入队列， 直到满足系统的一定停止条件1 2 】，如图2 2 ( a ) 流程图所示。 图2 2 ( a y f 专统网路爬虫工作流程图2 二抽) 聚焦网路爬虫工作 聚焦爬虫的工作流程较为复杂，需要根据一定的网页分析算法过滤与主题无 关的链接，保留有用的链接并将其放入等待抓取的u r l 队列然后，它将根据一定 的搜索策略从队列中选择下一步要抓取的网页u r l ，并重复上述过程，直到达到系 统的某一条件时停止，如图2 2 ( b ) 所示。另外，所有被爬虫抓取的网页将会被系 统存贮，进行一定的分析、过滤，并建立索引，以便之后的查询和检索；对于聚 焦爬虫来说，这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指 导。稻对于通用普通网络爬虫，聚焦爬虫还需要解决三个主要闯题： ( 1 ) 对抓取目标的描述或定义； ( 2 ) 对网页或数据的分析与过滤； ( 3 ) 对u r l 的搜索策略。 抓取目标的描述和定义是决定网页分析算法与u r l 搜索策略如何制订的基 础。而网页分析算法和候选i 瓜i 搏序算法是决定搜索引擎所提供的服务形式和爬 虫网页抓取行为的关键所在这两个部分的算法又是紧密相关的 抓取目标描述 现有聚焦爬虫对抓取目标的描述可分为基于目标网页特征、基于目标数据模 式和基于领域概念3 种。 6 其中，网页特征可以是网页的内容特征，也可以是网页的链接结构特征，等 等基于目标数据模式的爬虫针对的是网页上的数据，所抓取的数据一般要符合 一定的模式，或者可以转化或映射为目标数据模式。另一种描述方式是建立目标 领域的本体或词典，用于从语义角度分柝不同特征在某一主题中的重要程度。 基于目标网页特征的爬虫所抓取、存储并索引的对象一般为网站或网页。根 据种子样本获取方式可分为： ( 1 ) 预先给定的初始抓取种子样本( 如种子u r l ，目标网页样本等) ； ( 2 ) 预先给定的网页分类目录和与分类目录对应的种予样本，如y a h o o ! 分类结 构和通过学习训练得到的分类器等： ( 3 ) 通过主题行为确定的抓取目标样例，分为： a ) 主题浏览过程中显示标注的抓取样本； ”通过主题日志挖掘得到访问模式及相关样本。 聚焦爬虫系统体系结构 下面分析两种具有带表性的体系结构。 基于分类器的聚焦爬虫 目前大多数的聚焦抓取都采用了类似的工作流程，其系统结构如图2 3 所示。 根据一个主题目录和主题指定的初始点( 如书签) 来描述抓取目标，并在主题测览过 程中，将主题标注的感兴趣网页放入相应的主题目录，修改主题样本系统的两个 主要部分是网页分类器和网页选择器( d i s t i n c t ) 网页分类器负责学习抓取目标的特 点，计算网页的关联度，并过滤网页。选择器负责计算网页的重要程度，发现中心 型网页，并由此动态决定网页的访问顺序。 图2 3 基于分类器的聚焦爬虫流程图 - 基于主题学习的聚焦爬虫 7 协作聚焦爬虫的体系结构关键在于对主题的浏览模式的学习模块。爬虫体系 结构如图2 4 所示系统通过记录主题在浏览到感兴趣的网页时，点击“有用”按 钮的行为。记录相相关网页，为主题建立浏览模型。之后，系统对经过标注的网 页进行l s i 聚类，根据聚类结果构建概念图，表示不同类别之间的联系。这样，系 统就可以利用不同网页问的链接关系，学习主题的浏览行为。主题浏览模式学习 还可以通过对日志的挖掘来获得，系统同样要通过建模和学习两个部分来完成对 爬虫的指导。 网 l r n j ；_ 即_ 妒j z ：霹呵j ：了譬i 飘 ! 匝鲴_ 堰塑翳叫塑强圆 一一：。一三。一丘_ i 竺型 图2 4 基于主题学习的聚焦爬虫工作图 2 2 2 个性化智能爬虫 随着网络资源的不断扩增，面对搜索引擎巨大数量的返回结果。主题要找到 所需的资料越来越困难，因此急需一种面向主题的个性化搜索引擎搜索引擎的 个性化可以通过两种技术来实现，“群体行为分析”和“个性化搜索”“群体 行为分析”通过对一段时间内主题的大量检索词的分析，从而得出与某一个检索 词相关信息而后者是搜索行为分析技术最有前途的方向，通过积累主题的搜索 个性化数据，使主题的搜索更加精确。 已经有人实现了一种名为p i s e ( p e r s o n a li n t e l l i g e n ts e a r c he n g i n e ) 的个性化职 能爬虫”。，它就是基于。个性化搜索”的技术，采用逐步求精的策略来实现个性 化，同时实现了实时性它的个性化体现在搜索引擎返回的信息是符合主题的个 人想法的，而不是只与主题输入的关键字相匹配；实时性体现在它不是从本地服 务器上存储的索引数据库中查找主题需要的信息，而是实时地到网上寻找最新信 息，返回给主题。适应于这些特点，p i s e 的爬行虫在网址的初始化和爬行策略上 具有一定的特色 一、p i s e 的体系结构 p i s e 是一个客户服务器模式的软件，分为三部分；客户端、服务器端和爬行 虫，如图2 5 所示： s 韭塞銮重态堂亟圭堂焦盈塞匿釜塞皇绽釜 圈2 5 p i s e 原理图 客户端功能：在服务器上注册本主题的客户i d 号；输入关键字；显示 相关网址以及简要介绍。 服务器端功能：向客户端返回爬虫得到的相关网址及此网址的简要介 绍；根据主题的点击与浏览时间，计算主题对某个网页的对应某个关键字的兴 趣度，存入个性化信息库；根据兴趣度对个性化信息库的内容进行更新；启动 网络爬虫搜索i n t e r a c t 。 主题信息库功能：存储客户个性化信息， i d 号、关键字、相关网址、 兴趣度等；客户注册信息、i d 号、密码等。 爬行虫功能：与远程网页服务器建立连接，依据一定的爬行策略获取 网页内容；对网页进行解析，返回与主题关键字相关的网页网址 主题第一次使用p i s e 时通过客户端软件向服务器发出注册申请，注册内容包 括主题的爱好，经常浏览的网页等；服务器端接到申请后，根据申请的内容建立 主题基本信息库( 表2 1 ) ，同时建立个性化信息库( 表2 2 ) 其中感兴趣的网址由 两部分组成：一部分是主题输入的经常浏览的网址，对应的关键字为空；另一部分 是服务器根据主题的兴趣爱好初始化的网址，并把兴趣爱好作为关键字爬行虫 在接收到主题查询关键字后，以一定的方式初始化，并以一定的爬行策略获褥网 页服务器中相关网页的网址，通过服务器程序返回给客户端供主题查询。 表2 1 用户基本数据库 用户名用户m爱好 经常浏览的网页 l李飞0 0 0 1羽毛球、游泳 h t t p ：，、吼h u t o mi 9 表2 2 用户个性化数据库 用户名用户i d 爱好兴趣程度 李飞0 0 0 1 刘海 0 0 0 2 张克 0 0 0 3游泳o 7 孙翔 0 0 0 4 二、p i s e 爬行虫的核心技术 关键字确定 p i s e 爬行虫的初始u r l 主题使用p i s e 进行搜索时，首先输入要搜索的关键字， 爬行虫接收到关键字后，到主题库中查询，看是否有关键字字段与主题的关键字 相匹配，如果有则用相应的记录中感兴趣的网址字段的值作为初始的u r l ，否则用 关键字字段为空的相应记录的感兴趣的网址字段的值( 即主题经常浏览的网址) 以及其他主题的对应统一关键字的感兴趣网址作为初始的u r l 。每一次搜索都会向 主题返回一些相关网址，服务器程序根据主题点击的次序及浏览的时间计算出兴 趣度，把主题兴趣度到达一定数值的网址存入主题库，同时存入查询的关键字， 为下一次查询提供初始u r l 。并且更改库中网址的兴趣度，当兴趣度降低到一定值 时就删除此记录。这样，虽然第一次查询可能返回结果不多也不太精确，但因为 每一次新的查询都是在以前查询基础上进行的，初始u r l 都更接近主题的意图，我 们根据一般情况下同类两站才会互相链接可以知道，查询的结果会越来越精确。 爬行策略 爬行策略对搜索引擎来说是很关键的，它涉及到查全率、查准率、搜索速度 等搜索指标分析p i s e 的特点，我们注重的是速度和相关性，因此尽快地找到相 关性较高的网页是我们的目标我们知道每一个网站的建立都有它的目的性，即 使像援狐这样的综合性两站，也把不同类别的内容分别放到了不同的主机服务器 上，因此我们可以把网站按内容分为不同的类别与我们关键字相匹配的只能是 某一个类别，所以我们要查找的目的就变为要查找某一类别的网站，然后再从此 网站中找出相应的网页。根据以上分析可以制定出p i s e 的爬行策略，如果某一个 网页中没有与关键词匹配的文本，则可以判断出此网页的网站不属于我们要查找 妁类剔，因此放弃内部链接，只把外部链接放入查询队列。另外，把稳关锚点对 应的链接网址放入优先队列，让这些网址对应的网页得到优先处理，以尽快给主 题返回结果具体实现如图2 6 所示。 1 0 j s 塞奎塑盍堂亟堂僮监塞旦缝艘蜜堡签 外部链内部链 最优趴列次优队列 等待队列 完成酿列 国2 6 u r l 队列国 按照链接与关键词的可能匹配程度我们将爬行队列分为四级：最优队列、次优 队列、等待队列和完成队列。如果某一网页中没有与关键词匹配的文本。则将此 网页的外部链接放入次优队列；如果有与关键词匹配的文本，将匹配锚点的内部 链接以及外部链接放入最优队列，不匹百己锚点的外部链接放入次优队列，内部链 接放入等待队列；已经处理完的链接放入完成队列。 网页相关度的计算 为了提示主题相关性大小，返回相关度是很必要的。根据对相关性贡献的大 小。我们分几个层次为网页的相关性赋值： 1 ) 如果网页的r i f l e 与关键字匹配，给此网页相关度增加一个固定的数量值，如 1 0 。 2 ) 如果网页文本中的小标题与关键字匹配，给此网页相关度加5 ：其他文本与 关键字匹配，给此网页相关度加3 。网页文本相关度加权的方法：如果关键字在小 标题中出现次，在普通文本中出现次，则总的相关度加权为： ( 5 x 啊+ 3 x n 2 ) m i - i n 2 ) ( 2 1 ) 2 2 3 分布式网络爬虫 实际上，除了查询相关性评价算法的质量和查询响应速度外，索引弼页数量 的大小和新鲜度是评价一个搜索引擎好坏的重要指标因此，一个高效的 w e b c 趔w 1 妇系统是搜索引擎的重要基础通常，要使已爬行的网页库保持一定 的新鲜度，c h w l e f 的爬行周期应不超过1 5 天。按照目前的w e b 规模，即使是爬 行全部网页的3 0 9 6 ( 约l o 亿个) ，这个时间限制对c m w l 盯也是巨大的挑战，必须 采用合理的优化方法，并充分考虑到w e b 两络环境的各种性能限制，从而能在高 j e 塞至逼太堂亟堂僮i 金塞圈缝鲤鱼绽述 速爬行网页的同时不影响w e b 服务器和网络的正常运行。 己有的一些c r a w l e r 是在单机上运行的，如康柏系统研究中心的m e r c a t o r ，卡 内基梅隆大学的w e b s p h i n x 等，信息搜集速度比较有限，由于w e b 资源的海量性， 已无法在一个有效的时间范围内完成一次爬行互联网的任务。分布式c r a w l e r 系 统采用多机并行工作，提高系统的工作效率，并具有良好的可扩展性，是必然的 发展趋势。， 采用分布式的系统结构，它由多个c r a w l e r 组成，每个c r a w l e r 分布在不同的 计算机上，各自承担一部分网页爬行任务。并且并行协同工作。 1 ) c r a w l e r 结构 图2 7 单个爬虫工作图 单个c r a w l e r 的系统结构如上图所示每个c r a w l e r 从一组种子u r l 开始， 首先通过d n s 解析器获得该u r u 对应主机的口地址，然后按照机器人拒绝协议检 测被访闯主机是否允许访问该u r l ，通过检测后由h t r p h t r p s 下载模块下载该 网页。u r l 抽取器从下载的网页中抽取出新的u r l ，然后由u r l 过滤器逐个检测 u 甩是否符合过滤器限制。最后，通过一定的算法计算各个u r l 的相关度值，如果 该值达到了预先设定的阀值，则将该u r l 加入到本地u r l 数据库中；否则把该u r l 插入到u r l 发送队列中，由u r l 分发器定时转发给对应的c r a w l e r 爬行策略控 制器按照系统的爬行策略将待爬行的u r l 排序，使重要的u r l 资源得以优先下载， 实际当中大多采用基于p a g e r a n k 评价标准的方法，能过较好的得到预期效果。爬 行模块由若干个下载线程组成，每个线程都有一个线程u r l 队列，包含了一组待 爬行u r l 在实际的开发过程中我们深有感触的是，下载模块的设计与实现需要反 复推敲和不断改进，因为在遍历信息量无限大的w e b 的过程中，c r a w l e r 会遇到一 些不规范的w e b 服务器和网页内容，所以必须将所有的情况都尽可能的考虑到， 以免一个小小的失误导致整个线程和系统的中断。而且，线程的开发还和计算机 硬件的条件有很大的关系，需要合理设置线程的数量。 2 ) 分布式u r l 分配算法 分布式w e bc r a w l e r 的关键问题之一就是如何将巨大的t l r l 爬行任务均衡快 速地分配给各个c r a w l e r ，使每个c r a w l e r 根据分配策略负责爬行一定范围的u r l ， 这也是优化系统性能的重要措施。目前，许多w e bc r a w l e r 系统( 包括i g l 0 0 1 1 版) 都采用集中式的任务分割策略，即系统有一台主机作为协调器，每个c r a w l e r 启动 时在协调器上注册自己的i d 号。协调器采用哈希分配算法为各个c r a w l e r 分配u r l 爬行范围。在运行期间，c r a w l e r 对每个发现的u r l 都要用哈希函数进行判断，把 不属于本c r a w l e r 爬行范围的u r l 上传到协调器，由协调器根据u r l 的哈希值转 发给对应的c r a w l e r 。这种集中式策略的最大缺点是：所有u r l 都由协调器进行转 发，使协调器成为系统的性能瓶颈。为了解决这个问题，在i g l 0 0 1 2 版中人们设计 了u r l 二级哈希映射算法，使系统可以进行分布式的t l r l 分配，每个c r a w l e r 只 需在本地计算u r l 的哈希值，最多只需两次哈希运算就可确定每个u p & 的分配对 象，即它要分配给的c r a w l e r ，使i g l o o 可以进行高效均衡的分布式u p & 分配，并 且使系统具有动态可扩展性。 其工作原理如下：首先，i g l o o 系统中有一个系统监控器，它监视着各个c r a w l e r 的运行状，每个c r a w l e r 启动时要在监控器上注册自己的m 号，同时每个c r a w l e r 也维持有关其他c r a w l e r 的i d 号、m 地址、u r l 传输端口等信息。对每个新发现 的u r l ，c r a w l e r 用二级哈希映射算法判断是否属于自己的爬行范围，以决定是否 路由给其他c r a w l e r 在一次爬行周期内系统的最大规模一般是可以确定的，则假 设最大c r a w l e r 数目是m ，而系统当前运行的c r a w l e r 数目是n ，显然n 一定小于 m 。相应的每个c r a w l e r 有两张表：一张是逻辑节点表，存储m 个逻辑节点的信息， 每个表元素如果物理上对应的c r a w l e r 存在，则它的值为该c r a w l e r 的d 号，否 则为零；另一张是物理节点表，每个表元素存储系统当前各个c r a w l e r 的信息经 过标准化的u r l 的第一次哈希运算映射到相应的逻辑表元素上，如果该元素不为 零，则取出该d 号，判断是否需要将该u r l 路由给其他c r a w l e r ；如果该元素为 零，说明该逻辑节点目前还没有对应的物理c r a w l e r ，则要把映射到该元素上的所 有u r l 均分到系统当前的各个c r a w l e r 上，这是通过第二次哈希映射来完成的。经 第二次哈希映射，获得对应c r a w l e r 的m 号，最后判断是否路由该u r l 可以验 证，系统运行过程中n 可以动态变化，而不影响u r l 的均衡分配，而且能快速地 进行u r l 分配。 1 3 韭塞銮适太堂亟坐焦途塞垦垡跫皇绫述 2 2 4 网络爬虫算法 网页分析算法可以归纳为基于网络拓扑、基于网页内容和基于主题访问行为 三种类型。 一基于网络拓扑的分析算法 基于网络拓扑的分析算法，基于网页之间的链接，通过已知的网页或数据， 来对与其有直接或间接链接关系的对象( 可以是网页或网站等) 做出评价的算法。 又分为网页块粒度、网页粒度和网站粒度这三种“。 1 i 网页块粒度的分析算法 在一个页面中，往往含有多个指向其他页面的链接，这些链接中只有一部分 是指向主题相关网页的，或根据网页的链接锚文本表明其具有较高重要性。但是， 在p a g e r a n k 和h i t s 算法中，没有对这些链接作区分，因此常常给网页分析带来广 告等噪声链接的干扰在网页块级别进行链接分析的算法的基本思想是通过v i p s 网页分割算法将网页分为不同的网页块( p a g e b l o c k ) ，然后对这些网页块建立p a g e t ob l o c k 和b l o c kt op a g e 的链接矩阵，分别记为z 和x 。于是，在p a g et op a g e 图上 的网页块级别的p a g e r a n k 为既= x x z ；在b l o c kt ob l o c k 图上的b l o c k t ob l o c k 为= z x x 已经有人实现了块级别的p a g e r a n k 和h i t s 算法，并通过实验证明， 效率和准确率都比传统的对应算法要好 1 2 网页( w e b p a g e ) 粒度的分析算法 p a g e r a n k 和h i t s 算法是最常见的链接分析算法，两者都是通过对网页问链接 度的递归和规范化计算，得到每个网页的重要度评价p a g e r a n k 算法虽然考虑了 主题访问行为的随机性和s i n k 网页的存在，但忽略了绝大多数主题访问时带有目 的性，即网页和链接与查询主题的相关性针对这个问题，h i t s 算法提出了两个 关键的概念：权威型网页c a i i i l l 嘶t y ) 和中心型网页( h u b ) 。基于链接的抓取的问题 是相关页面之间的隧道现象，即很多在抓取路径上偏离主题的网页也指向目标网 页，局部评价策略中断了在当前路径上的抓取行为目前有人提出了一种基于反 向链接( b a c k l i n l 0 的分层式上下文模型( c o n t e x t m o d e l ) ，用于描述指向目标网页 一定物理跳数半径内的网页拓扑图的中心层为目标网页，将网页依据指向目标网 页的物理跳数进行层次划分，从外层网页指向内层网页的链接称为反向链接也 就是说离中心网页越近的网页作为目标网页的可能性越大，越靠外的网页偏离主 题越远。但是实际情况是，很多偏离中心网页的外层网页中同样包含目标网页的 链接，所以，需要建立从外层到内层的“隧道”链接，以便发现外层网页中的目 标链接。 1 3 两站粒度的分析算法 1 4 j e 鏖窑煎太堂亟堂僮监塞圜缝理虫绫述 网站粒度的资源发现和管理策略也比网页粒度的更简单有效。网站粒度的爬 虫抓取的关键之处在于站点的划分和站点等级( s i t c r a n k ) 的计算。s i t e r a n k 的计算 方法与p a g e r a n k 类似，但是需要对网站之间的链接作定程度抽象，并在一定的 模型下计算链接的权重。网站划分情况分为按域名划分和按i p 地址划分两种。 在分布式情况下，可以通过对同一个域名下不同主机、服务器的i p 地址进行 站点划分，构造站点图，利用类似p a g e r a n k 的方法评价s i t e r a n k 利用分布式的 s i t e r a n k 计算，不仅大大降低了单机站点的算法代价，而且克服了单独站点对整 个网络覆盖率有限的缺点。 二基于网页内容的网页分析算法 基于网页内容的分析算法指的是利用网页内容( 文本、数据等资源) 特征进行 的网页评价。网页的内容从原来的以超文本为主，发展到后来动态页面( 或称 h i d d e n w e b ) 数据为主，后者的数据量约为直接可见页面数据( p i w ，p u b l i c l y i n d e x a b l ew e b ) 的4 0 0 5 0 0 倍。与此同时，多媒体数据、w e bs e r v i c e 等各种网络资 源形式也日益丰富。因此，基于网页内容的分析算法也从原来的较为单纯的文本 检索方法，发展为涵盖网页数据抽取、机器学习、数据挖掘、语义理解等多种方 法的综合应用根据网页数据形式的不同，可将基于网页内容的分析算法，归纳 以下三类： 第一种是针对以文和超链接为主的无结构或结构很简单的网页； 第二种是针对从结构化的数据源( 如r o b m s ) 动态生成的页面，其数据不能 直接批量访问： 第三种针对的数据是介于第一和第二类数据之间，具有较好的结构，显示 遵循一定模式或风格，且可以蛊接访问。 2 1 基于文本的网页分析算法 可分为纯文本的聚类算法和超文本的聚类算法，其中，纯文本分类与聚类算 法，很大程度上借用了文本检索的技术。文本分析算法可以快速有效的对网页进 行分类和聚类。但是由于忽略了网页问和网页内部的结构信息，很少单独使用。 超文本分类和聚类算法是利用网页文本中存在的大量的 ，( h e a d 等有用的 标记信息。这些结构中表示不同的内容的重要程度。可以有效地提高分类精度， 降低复杂度。 2 2h i d d e n w e b 的网页分析方法 大约8 0 的数据是动态生成的这些内容大多“隐藏”存储在后台的可查询数 据库中，因此称为“h i d d e n w c b ”目前大多数的通用搜索引擎仅仅覆盖了部分的 p i w ，却忽略了数据量约为p i w 4 0 0 5 0 0 倍的h i d d e n w e b ( 或称为d e e pw e b ) 。针对 h i d d e nw e b 的爬虫与普通的聚焦爬虫相比，需要更多地对网页中表单进行发现、 1 5 堑塞銮垣鑫堂亟堂焦验塞嗵釜狸虫绽述 探测查询( p r o b i n g q u e r y ) 和分析。对于网页上表单的处理很多时候需要采用主题辅 助的半自动方法，如典型的i - i i w e 系统。该方法将表单表示为一组( e l e m e n t ，d o m a i n ) 二元组，并尝试通过标注、页面布局等信息确定表单的输入数据模式。另一种无 需人工辅助的方法则需要更多对网页后台数据库的反复查询，分析结果的数量和 属性。 2 3 数据密集型网页的分析方法 数据密集型网页的数据形式介于h i d d e n w e b 和文本密集型网页之间。它们具有 良好的结构性，又可以直接从页面读取；而且数据的语义在网页上显示标注，因 此不需要对这些网页之后的数据库进行探测查询。例如新闻网站的产品热点新闻 页面，具有统一的风格，其中的数据表示具有固定格式，并按照定目录层次结 构来组织，因此也称为分类导向型( t a x o n o m y d i r e c t e d ) 网页的获取工作主要集中 在对网页数据的抽取，如页面块或目录发现，结构化数据的记录边界确定等等。 爬虫将这些数据抽取出来，以一定格式在本地存储、分析，从而指导下一步的抓 取工作。基本思路是，将h t m l 页面转化为t o k e n 序列或标记树( m g 仃) ，如d o m 树 等数据结