（计算机应用技术专业论文）一个增量更新的web信息采集系统的设计与实现.pdf

摘要 i n t e r n e t 的飞速发展，使网络成为人们发布、传输和获取信息的重要途径， 为人们生活、工作提供了丰富的信息和资源。w 曲信息采集作为获取网络信息的 重要方法，得到了迅速发展，被应用于多种服务和研究中。然而，由于w 曲信 息资源的动态性，造成了已采集信息的失效，传统的更新采集方式需要很大时空 开销。为了提高更新采集的效率，本文主要针对增量更新的w 曲信息采集进行 了研究。 w 曲网页变化有两个属性：内容属性和时间属性。根据这两方面，本文研究 了基于m d 5 算法和基于人工神经网络的增量更新策略。前者应用m d 5 算法对 网页内容进行信息摘要生成m d 5 值，通过比较m d 5 值来判断网页变化与否， 实现增量更新；后者通过人工神经网络对网页变化的时间间隔建立网络模型，采 用b p 算法来训练学习，得到一个预测模型，以此来预测出各网页的变化时间间 隔，通过与实际采集的时间间隔相比较判断网页是否发生变化，实现增量更新。 本文设计并实现了一个基于这两种增量更新策略相结合的w c b 信息采集系统： 先通过比较时间间隔，判断发生变化的网页，再对这些网页内容进行信息摘要生 成m d 5 值，与以前的相比较，验证网页是否确实发生了变化。对于变化的网页 进行下载更新，没有变化的网页不予处理。 实验表明，基于人工神经网络和m d 5 相结合的增量更新策略在判断网页是 否变化是有效的，网页变化时间间隔的人工神经网络预测模型能够在不下载网页 内容的情况下，根据以前采集的历史记录预测出网页变化时间间隔，而m d 5 能 够滤掉预测模型预测出的发生变化但实际没有发生变化的网页，从而减少系统对 未变化网页的更新所花费的系统资源和处理时间。本文实现的基于人工神经网络 和m d 5 相结合的增量更新的w e b 信息采集原型系统达到了预期的效果。 关键词w 曲信息采集；增量更新；m d 5 算法；人工神经网络；b p 算法 a b s 仃a c c a b s t r a e t 厅mt h cr a p i d l yd e v e l 叩i n go fi n t e m e l ，t h cn e t 、v o r ki sb e c o m i n gt h em a i n 印p m a c ht 0 p m m u i g a t i n g ，仃a n 锄i 缸f n ga 1 1 d 缸c h i n g 耐b 咖a t i o n np r o v i d e sp i e n t yo fi n f o 啪a t i 伽a n d 心s o u r c cf o rp e o p l c sl i v e s 锄dw 0 i k a st l l ei m p o r t a i l tw a yo f f e t c h i n gn e t w o r ki n f o m l a i i o n ，w e b c 阳w l i n gi sd e v e l o p i n gq u i c l ( 1 y ，a n di s 印p l y i n gi na 1 1k m d so f s e r v i c e sa i l dr e s e a r c h 铭h o w c v e l m ew 曲越妇m a i i o ni sd y n a m i c ，w h i c hm a k e sm ec 豫w l e di n f b n n a t i o ni n v a l i d 1 kt r a d i l i o n a l u p d a t e c r a w l i n gt e c l h l o l o 影r e q u i r ev e f yb i gs p a c e - t i i n cs p e n d i n g i no r d e rt 0 如p r o v ct h e e 币c i e n c y ，w eg e ti n t 0t h er e s e a r c ho ni 1 1 c r e m e n t a _ iu p d ec r a w i c r 1 1 1 e r e 础伽。砷咖u t e so f m ew c bp a g e sc h 锄g e ：c o n l c n t 砌b u t e 粕d et i m e 晰i b u t e a c c o r d i n gt o 廿l e s et w o 邵p e c 戗t 1 1 i sp 印盯d o e s m es n 】d i e so n m c r c m e m a lu p 出【t es t r 砷：g yb 髂e d o nm d 5a l g o r i t l l i n 锄dn e u r a in e t 、v o r kt e c l l l l o l o 盱t h ep r e c e d i n g0 n ea p p l i e s 圮m d 5 a l g o r i t l l m t 0g e m r a 士e m e s s a g ed i g e s t t l l ev a l u eo f m d 5 ，b yw h i c h w e j u d g cw h e i h e r t h ew c b p a g eh a sb c e nd m g e d t h el a 舱ro n em a k e sap r e d i dm o d c lt ow 曲c h a n g ei n t e r v a lb yn e u r a l n e t w o r kt e c h n o l o 科，a i l d 仃a i l l si tw i t l lt l l eb pa l g o r i 也m ，w ec o m p a r em er e a lc r a w l i n gi n t e r v a l w i t l lt l l ep r e d i c tc l l a i l g ei i i t e r v a lw h i c hi sp r e d i c t e db yt h em o d e l ，t oj u 起ew h e t l l e rt l l ew 曲p a g e h 嬲b e e nc h a n g e d t l l i sp a p 盯d e s i g n sa n dr e a l i z 髂ai n c r 唧e n 诅lu p 出【钯c r a w l e rw h i c hb 硒e d0 n m ec o m b i 删i 0 ft h em d 5a l g o r i t l l m 卸dm u r a ln 咖o r kt e c h n o l o g y c o m p a r ew 油m c i n t e r v a lt od i s c o v e rn ”w 曲p a g w l l i c hh a v eb e e nc h a n g e d 砒f i 斌，t 1 1 e n ，印p l i e sm d 5 a l g o r i t l l mt 0t h c mt og e n e r a t c 廿i ev a l u eo fm d 5 ，c o m p a r e 埘mt l l co l do n et 0c o m f i n l l 聃舸c h p a g e s h a v eb c e nc h 鲫g e di n 伍t h u p d a c et h ec h a 工l g e dp a g e sa n dd 0n o t | l i n gt oo t h e r s e x p e 曲1 e ms h o w st h a tt h ei n c r c i n e n t a lu p d a t es 仃a t 嚼，b e do n u m ln e t 、v o r kt c c 量l n 0 1 0 影 卸dm d 5a l g o r i t l l mi sv a l i dt o j u d g em ec h a i l g eo f w 曲p a g e s w i t l i o u td o w l l l o a d i i l gt h ec o m e n t o fw 曲p a g e ，t h cp r e d i c ti n o d e lt ow 曲c h 锄g ei i l t e r v a lc 矾p r c d i c tt 1 1 ei n c e r 、枷a c c o r d 吨t ot h c 化c o r d sc m w l e d b e f o r c a 1 1 d 恤em d 5a l g o r i l l 姐c 柚f i l 打a t em cp a g e sw h i c hh a v c n tb e e n 龇g e di l lf k t 丘d mm ec h a n g e dp a g e sd i s c o v e r c db yt l l ep r c d i c tm o d e l ，t h u s ，r e d u c et l l es y 咖m m s o u r c e 觚dp r o c e 嚣t i m et 0u p d a t et h ep a g e sw h i c hh a v e n tb e c nc h a n g e d t h ep r o t o t y p eo f i n c r e m e n t a lu p d a 把c r a w l e rb a s e do nn e u 豫ln e 似o r kt e c h n 0 1 0 留锄dm d 5a l g o r i t l l mw t l i c hi s r e a l i z c di i lt l 】i sp 印e fa c l l i e v e st l l ee x p e c t a i l tp u r p o s e k e y 帅r d sw 曲c r a w l i n g ：m c r c m e n t a l 叩d a 【e ：m d 5a l g o r i t l l i l l ：n e u m ln e t 、v o r k ：b p a 蟾o m l i i l - i i i 独创性声明 本人声明所呈交的论文足我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 躲盔距睨迎：乡 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：二蝉导师签名： 日期：蔓五么! 至 第1 章绪论 1 1 研究背景 第1 章绪论 随着i n t e r n e t 的飞速发展，人们的生活正发生着翻天覆地的变化，网络成为 人们发布、传输和获取信息的重要途径。根据2 0 0 7 年1 月中国互联网络信息中心 ( c n n i c ) 发布的全球互联网统计信息跟踪报告第2 4 期显示，截止到2 0 0 7 年1 月， 世界的总网民数量为l ，0 9 3 ，5 2 9 ，6 9 2 ，网民平均普及率为1 6 6 。如表1 1 所示。此 外，2 0 0 7 年1 月，n e t c r a r 网站的调查收到1 0 6 8 7 5 ，1 3 8 个站点的反馈，相比上 月增加了1 6 3 万个站点。站点增加量最多的是微软，在w i n d o w sl i v es p a c e 上的免 费博客服务增加超过了6 5 万个站点，g od a d d y 和g 0 0 9 l e 在2 0 0 7 年1 月增加站点数 均超过了l o 万，分别为1 6 5 万和l o 5 万“ 。 表1 1 世界各地区网民分布及增长 t a b l e1 11 h ed i s t r i b u t i o na i l dg r o 、砌1o f n l en e 眺p e o p l e 证r r 强ew o d d 总人口占世界网民占人 占世界网民2 0 0 0 年至 地区( 2 0 0 7 年估算值)总人口最新网民数口数量比数量比率2 0 0 7 年网民 的比例 塞 增长率 非洲9 3 3 ，4 4 8 。2 9 2“2 0 3 2 ，7 6 5 ，7 0 0 3 5 0 3 0 0 6 2 5 8 0 诬洲3 ，7 1 2 ，5 2 7 ，6 2 45 6 5 傩 3 8 9 ，3 9 2 ，z 8 8 l o 5 0 3 5 6 嘶2 如7 0 欧洲8 0 9 ，6 2 4 。6 8 61 2 3 嗍3 1 2 。7 2 2 ，8 9 23 8 6 0 2 8 ，6 0 9 1 9 7 6 0 中东1 9 3 ，4 5 2 ，7 2 7 2 9 0 1 9 3 8 2 4 0 01 0 o o 18 0 4 9 0 1 0 北美3 3 4 ，5 3 8 ，0 1 8 5 1 0 2 3 2 。0 5 7 0 6 76 9 4 0 2 1 2 0 1 1 4 7 0 拉美及 加勒比5 5 6 ，6 0 6 ，6 2 78 5 0 8 8 。7 7 8 ，9 8 61 6 0 0 9 6 81 0 3 9 1 3 0 地区 大洋洲3 4 ，4 6 8 ，4 4 30 5 0 1 8 4 3 0 3 5 95 3 5 0 1 7 0 1 4 1 9 0 9 6 总计6 ，5 7 4 ，6 6 6 ，4 1 71 0 0 0 0 1 ，0 9 3 ，5 2 9 ，6 9 2 1 6 6 0 9 61 0 0 瞄2 0 2 9 0 9 ； 另有研究报告表明，全球互联网“可见网页”超过1 1 5 亿页，而且还有很大 部分文件隐藏于数据库或受密码阻止，专家估计互联网络上的文件数量高达5 0 0 0 亿闭，而且还在以飞快的速度增长。 i n t e m e t 为人们的工作、娱乐和交流提供了丰富的资源和信息，但是同时， 也对人们有效、快速地使用这些资源和信息提出了一个挑战。w 曲信息丰富多彩， 包罗万象，涵盖了政治、经济、文化、娱乐，国内、国外等各个方面，而且i i l t c m e t 是一个开放性、动态性和异构性的全球分布式网络，数据的海量性、资源的分散 北京工业大学工学硕上学位论文 性、管理的不一致性、结构的多样性，使用户很难准确快捷地获得他们需要的信 息1 3 】。因此，人们在信息检索领域投入了大量的人力物力，各种、b 搜索引擎f 4 】 的研究成为热点和重点，作为这些搜索引擎的基础和组成部分，w 曲信息采集正 发挥着举足轻重的作用，并且随着应用的深化和技术的发展，它也越来越多地被 应用于站点结构分析、页面有效性分析、内容安全检测、w 曲数据挖掘等多种服 务和研究中p j 。 1 2 研究现状 随着w 曲信息采集的应用越来越广泛，传统的w 曲信息采集技术和其他技 术的结合也越来越紧密，各种各样的w 曲信息采集应运而生。根据国内外的研 究情况，可以把w 曲信息采集分为以下几类。 ( 1 ) 基于整个w 曲的信息采集基于整个w e b 的信息采集( s c a l a b l ew 曲 c r a w l e r ) ，是一种较传统的采集思想。基本思想：从一些种子u r l 扩展到整个 w e b 的信息采集。这种信息采集主要是作为门户搜索引擎和大型的w 曲服务提 供商的数据收集部分。优点：由于目标是采集整个w 曲，所以采集数据广，速度 快，对采集页面的顺序要求相对较低；缺点：1 ) 采集的范围和数量都非常巨大， 所以对采集速度和存储空问要求很高；2 ) 待刷新的页面太多，尽管并行很多的 采集器，但仍需数周乃至数月的时间来刷新一次，而且，随着并行采集器数量的 增加，整个系统能力的提高越来越小，稳定性却越来越低。这类w 曲信息采集 器构建的搜索引擎，适合搜索广泛的主题。事实上，这类信息采集仍有很强的应 用需求，目前在实际应用中占较为主流的地位。典型的代表有：g o o g i e 【6 7 】、 m e 嗽幻r f s l 和i n t e n l e ta r c l l i v e f 9 】。 ( 2 ) 基于主题的w e b 信息采集基于主题的w 曲信息采集( f o c u s e d c r a w l e r ) ，是指选择性地搜寻与预先定义好的主题集相关页面的采集器，对它的 研究现在比较热门。基本思想：搜索与特定主题相关的资料，通过分析已采集页 面的链接页面与主题的相似度来维护链接页面采集的优先级，优先级越高，页面 内容与主题的相似度越大，也就是与主题的相关性越大，优先采集这些链接页面。 优点：采集页面更加有针对性，采集效率高。缺点：采集速度较慢，相关性判断 带来较大的系统开销。典型代表有：n e c 研究院的c i t e s e c r 系统l l o ，“】、美国国家 科学数字图书馆的c b p 【1 1 l ，国内的北大天网【l l ，1 2 1 和中科院计算所的天罗信息采 集系统【5 1 。 ( 3 ) 基于用户个性化的w 曲信息采集基于用户个性化的w b b 信息采集 ( c u s t o l l l i z e dw 曲c r a w l e r ) ，是基于主题的w 曲信息采集技术研究一种轻量级 的采集系统。基本思想：不同的用户对一个搜索引擎提交同一个检索词，他们期 第1 章绪论 望的返回结果是不同的，然而搜索引擎却只能返回相同的检索结果，这显然不能 完全满足用户的需要。基于用户个性化的w 曲信息采集通过用户兴趣制导或与 用户交互等灵活手段来采集信息。个性化信息一般有两个来源：1 ) 用户手工在 系统提供的个性化设置页面里设置，这里主要考虑的问题是如何全面灵活简单的 提供这种设置，使得用户的各种喜好都能够表达；2 ) 系统自动获取，通过跟踪 用户的浏览习惯和兴趣等。优点：灵活、针对性强；缺点：实用性和有效性还有 待提高。典型代表有：s p h 小【1 3 】。 ( 4 ) 基于a g e n t 的w 曲信息采集基于a g e m 的信息采集( a g e n tb a s e d c r a w l e r ) ，是a g c m 与信息采集相结合的技术。基本思想：智能a g e m 系统是 指一种处于一定环境下包装的计算机系统，为了实现设计目的，它能够在该环境 下灵活地自主地活动。优点：除了具有自治性( a g e m 运行时不直接由人或其它东 西控制，它对自己的行为和内部状态有一定的控制权) 、社会能力( 多个a g e m 体 之间信息交换和协作) 、反应能力( 对环境的感知和影响) 和自发行为( a g e m 的行为 是自主的) ，还具有一般人类所有的知识、信念、意图和承诺等心智状态，这使得 智能a g e n t 系统具有人类的社会智能；缺点：系统设计会相对复杂，速度比较 慢。典型代表有：美国的爱荷华大学进行的燃h n i d 研究项目中通过模拟一 个生态系统的发展和演变设计的w 曲信息采集器h 面s p i d e r s 系统、美国麻省理 工学院的l e 血i a 系统【5 j 。 ( 5 ) 基于迁移的w 曲信息采集基于迁移的信息采集( r e l o c a t 曲l ew 曲 c r a w l e r ) i l ”，基本思想：在采集过程中，不是在本地向w 曲站点服务器发页 面请求，而是将自己上载到它所要采集的服务器中，在当地进行采集，并将采集 结果压缩后，回传到本地。优点：大量的节省了w 曲资源，大量的剪裁工作将 在被采集对象的服务器上完成。缺点：采集器可能并不被被采集对象所信任，因 为这样被采集站点会由于给访问者权限太大而易遭到病毒攻击。典型代表有：卡 内基梅隆大学( c m u ) 研制的s p h n x 【1 4 】。 ( 6 ) 基于元搜索的w 曲信息采集基于元搜索的信息采集 ( m e t a c m w l e r ) n ”，一直是搜索引擎研究的一个热点。基本思想；对用户提交的查 询请求通过多个领域或门户搜索引擎搜索，并将结果整合后以统一的界面提交给 用户。一般元搜索引擎并不保存w 曲页面的索引文件，但对于一些复杂的元搜 索引擎，它要保存为它服务的每个搜索引擎的信息特征，以便能够在用户查询到 来后做出好的搜索引擎选择。优点：使用户避免了在多个搜索引擎系统之间的切 换及查询请求的重复输入，不需要考虑网页索引数据库的建立和维护，可以集中 精力与财力用于查询请求的分发与查询结果的处理，可检索多个索引数据库，提 高检索的效率；缺点：检索时间有时过长，有些词组和布尔检索算符不能被正确 处理，检索结果较少，不支持许多独立搜索引擎所支持的高级检索功能。典型代 北京工业大学工学硕士学位论文 表：i n f o s p a c e l 、v i v i s i m o 、中文元搜索引擎具有代表性的有搜星搜索引擎。 ( 7 ) 增量式w e b 信息采集增量式w 曲信息采集( i i l c r e f n c n t a iw 曲 c r a w l e r ) 【1 7 ，l8 】一般用于更新采集的时候。基本思想：对待旧的页面采用增量式 更新，也就是说，采集器只需要采集新产生的或者已经发生变化的页面，而对于 没有变化的页面不进行采集。传统上的w e b 采集器根据自己的需要采集足量的 信息后停止采集，当一段时间后这些数据过时后，它会重新采集一遍来代替原有 的采集信息，这种采集器称作周期性w 曲采集器( p e r i o d i cw e bc r a w l e r ) 。而另 外种方法，理想状况中，已采集到的信息应该和w e b 中的信息是一致的，然 而实际上、b 的动态性、异构性和复杂性决定了采集到的信息在相当短的时间 内就可能过时，那种理想是不实现的，我们能够做的就是尽量逼近这种理想。优 点：极大地减小数据采集量进而极大地减小采集时空开销。缺点：增量式信息采 集在减小时空开销的同时，却增加了算法的复杂性和难度。典型代表有：i b m 设 计完成的信息采集器w 曲f o 眦t a i n 【1 9 】。它采用了一个优化模型来控制采集策略。 这个模型没有对w 曲页面变化的统计行为做任何假设，而是采用了一种适应性 的方法，根据先前采集周期里采集到的结果的实际变化率进行调整。 在i i l t e m e t 极其普遍的信息时代，很多人认为获取网页信息似乎比较简单， 只要有一个u r l ，它就对应着某个网页，w 曲信息采集系统只要根据u i u 获取 相应的网页内容，并进行网页解析，提取超链接，再根据获得的超链接获取网页 内容，如此循环执行就可以。但实际上，它却存在着许多困难和挑战。 第一，w 曲中的信息是完全异构、混乱和无序的，文件格式各式各样，包 括图像、图片、声音、文本以及s c r i p t 等，网络状况也随时间变化莫测。所有 的这些不确定性因素，为系统实现带来了极大的困难。这就要求采集系统有完善 的异常处理和故障恢复机制，充分考虑到实际网络环境中可能出现的各种情况 第二，w 曲信息容量的巨大性使得采集器不可能采集到所有的w 曲页面， 而且很多采集系统也没有足够大的空间来存放采集到的所有页面。如何提高采集 的效率，即在单位时间内采集到尽可能多的高质量页面，是采集系统面临的一个 难题。目前网页之间的相关度分析成为搜索引擎研究中的重点和难点，利用链接 分析技术分析网页相关度的算法日趋成熟，最著名的有g o o 酉e 研究的p a g e r a n k 算法【2 0 】和i b m 的c l w e v e r 系统采用的h i t s 算法1 2 ”，而且随着研究的深入， 各种改进算法也不断提出，很大程度上提高了搜索引擎的搜索效率。 第三，并行性问题，页面的采集速度一直是影响采集器性能的重要原因。一 方面，w 曲中的页面数量非常庞大，另一方面，网络中的连接速度又非常缓慢， 这客观上要求系统需要并行。然而，要并行又引入新的问题：1 ) 重复性( o v c d 印) ， 多个不同的采集器或采集线程在同时采集的时候增加了重复页面；2 ) 质量问题 ( q u a l i t y ) ，单个系统能够根据算法采集到全局最优的页面。而如果并行，每个采 第l 章绪论 集线程只能看到局部页面，它能够采集到的页面质量有所下降；3 ) 通信带宽代 价( c o i 啪u n j c a t i o nb a l l 捌d t l l ) ，为了并行，各个采集线程之间不可避免的要有 一些通信。多线程与并行机制使系统变得非常复杂。在这种复杂的环境下，系统 的许多瓶颈变得异常突出。目前主要通过研究u r l 调度策略、并行策略来优化 并行w 曲信息采集中遇到的问题。u r l 调度策略主要有动态分配和静态分配， 并行策略又可分为防火墙模式、交叉模式和交换模式【2 2 郊】。 第四，刷新问题。为了保持采集到的页面是最新的，采集系统不得不对已经 采集过的页面进行周期性的更新。c h o 试图用泊松过程( p o i s s o np r o c e s s ) 来描述页 面变化率，并研究和对比了三种页面刷新策略：固定顺序的刷新，随机刷新和纯 随机刷新策略。直觉上，更多的刷新应该分配给更那些更新快的页面。但研究表 明，用较高的频率刷新更新快的页面并不一定是明智之举，对各种页面采用相同 的刷新周期效果更好，而效率最佳的点在这两种刷新策略中间。这是因为，过高 频率的刷新更新快的页面，使得其它页面有较少的刷新机会，反而造成总体刷新 质量下降】。 1 3 研究意义 由于w 曲信息资源的动态性，w 曲信息瞬息万变，产生很多新的网页需要 采集，也使很多已经采集的网页内容成为无效信息，如果对已采集的所有u r l 都重新采集，很多没有变化的网页也被重新采集，这会浪费系统时间和空间。本 文设计并实现了一个结合两种增量更新策略的w 曲信息采集系统。一种增量更 新策略是通过m d 5 算法【2 5 】对采集到的网页内容进行信息摘要，生成重复性很小 的m d 5 值，通过比较新生成的m d 5 值和数据库中的m d 5 值，确定是否要保留 新采集的网页内容和进行后续的处理；另外一种增量更新策略是通过人工神经网 络的b p 算法【2 6 ，2 ”，建立一个学习预测模型，利用大量的样本来学习出网页发生 变化的时间规律，预测网页变化的时间间隔。通过比较实际的采集时间间隔和模 型预测的变化时间间隔来判断网页是否变化。这两种增量更新策略的结合，预测 模型在不下载网页内容的情况下，根据以前采集的历史记录预测出网页变化时间 间隔，而m d 5 能够滤掉预测模型预测出的发生变化但实际没有发生变化的网页， 减少系统对未变化网页的更新处理所花费的系统资源和时间。 1 4 课题来源 本课题来源于北京市科委资助的“校园网可信运行保障系统研究”项目，项 目已通过北京市科委验收。“校园网可信运行保障系统研究”项目，是为了应对 在互联网快速发展的现实情况下，校园网所面对的安全问题而研究实施的。本课 北京工业大学工学硕士学位论文 题作为该项目网络内容监控系统的一部分，主要任务是从校园网中尽可能多地采 集网页信息，包括文本和图像信息，为其它两个模块：文本检测模块和图像检测 模块提供处理的信息。在此项目的基础上，本文设计并实现了一个增量更新的 w 曲信息采集系统。 1 5 本文安排 全文分为五章，其它章节安排如下： 第2 章：w 曲信息采集基本原理和关键算法，首先介绍了w 曲信息采集的 工作原理、基本结构模型。接着介绍w 曲信息采集器c r a w l e r 的工作流程以及相 关算法，包括：页面信息采集、页面解析、超链接u r l 去重。为本文的研究提 供了理论基础。 第3 章：基于m d 5 的增量采集策略，首先介绍了m d 5 算法及其原理，在此 基础上，研究了基于m d 5 的增量更新策略，分析了其设计思想和具体实现，并 通过实验验证了m d 5 在判断网页发生变化的效果。 第4 章：基于人工神经网络的增量更新策略，首先介绍了人工神经网络模型 和b p 算法的基础知识，提出对网页变化时阃间隔建立人工神经网络模型的增量 更新策略，详细介绍了网络模型的设计、实现及实验。 第5 章：设计并实现了一种基于人工神经网络和m d 5 相结合的增量更新的 w e b 信息采集系统。 第2 章w 曲信息采集基本原理和关键算法 第2 章w e b 信息采集基本原理和关键算法 w 曲信息采集是搜索引擎的基础和核心，随着w 曲信息的爆炸性增长，搜 索引擎技术飞速发展，各种搜索引擎应运而生，从而也带动了各具特色的采集技 术的发展。根据应用领域、采用技术、面向用户类型等等因素的不同，每个实际 的w 曲信息采集系统都有各自的特色，但抽象出它们基础的核心思想来看，存 在很多本质和共性的特征。 2 1w 曲信息采集系统的工作原理 w 曲信息采集( w 曲c m w l i n g ) ，主要是指通过w e b 页面之间的链接关系， 从w 曲上自动的获取页面信息，并且随着链接不断向所需要的w 曲页面扩展 的过程。实现这一过程主要是由w 曲信息采集器( w 曲c r a w l e r ) 来完成的。根 据应用习惯的不同，w 曲信息采集器也常称作w 曲s p i d e r 、w e br o b o t 和w 曲 w o r n l 。粗略的说，它主要是指这样一个程序，从一个初始的u u 集出发，将 这些u r l 全部放入到一个有序的待采集队列里。而采集器从这个队列里按顺序 取出u r l ，通过w 曲上的协议，获取u i 也所指向的页面，然后从这些已获 取的页面中提取出新的u r l ，并将他们继续放入到待采集队列里，然后重复上 面的过程，直到采集器根据自己的策略停止采集。对于大多数采集器来说，到此 就算完结，而对于有些采集器而言，它还要将采集到的页面数据和相关处理结果 存储、索引并在此基础上对内容进行语义分析。 2 2w 曲信息采集系统的基本结构 w 曲信息采集系统一般可以划分为七个部分：u r l 处理器、协议处理器、重 复内容检测器、u i 也提取器、m 咖信息获取器、语义信息解析器和数据库，它 们协调起来从w 曲上获取信息。如图2 1 所示，图中的箭头表示数据走向。 图2 1w 曲信息采集系统结构图 f i g u r e 2 - 1 皿es t m c t u r cc h a r to f w c bc m v 订e rs y s t c m ( 1 ) u i 也处理器u r l 处理器的任务是按照一定的规则给待采集的也 排序，并根据一定的策略向协议处理器分配u r l 。u i 江处理器主要有三个数据 来源：1 ) 初始的种子u r l 集；2 ) 从u r l 提取器传输过来的从已经采集到的页 面中，通过页面分析提取出来的w 曲链接；3 ) 页面的m e t a 、主题以及摘要等信 息，来自m e t a 信息获取器，它们主要用来显示从u i 也提取器中传输过来的 u r l 的重要性，为在这里排序提供依据。另外，u i 也处理器还有一个任务就是 d n s 解析。 ( 2 ) 协议处理器协议处理器处于系统的底层，主要通过各种w 曲协议 来完成数据的采集。一般来说协议包括h 1 v r p 、f t p 、g o p h e r 以及b b s ，也有些 采集系统根据应用的需要采集w 曲c h a t 、i c q 等特殊信息。但从主流上看，仍 以h t t p 为主。 ( 3 ) 重复内容检测器w c b 上存在着大量的镜像页面和内容，重复内容网 页的采集会极大地浪费网络的带宽，影响系统的效率。采用的检测方法，根据系 统的需要，从简单的段落匹配到复杂的相似度比较中选择。 ( 4 ) u r l 提取器网页中除了正文文本外，还存在很多超链接，如u r l 链接、文本链接、图片链接等等需要对其迸行分析、分类并提取，这些任务由 u r l 提取器来完成。首先判别页面类型，对类型为“t e x t 、h t i i l l 、s h t n l l 和h t i i l ” 等的页面进行分析链接。页面的类型可通过分析h r r p 响应消息得出，有些 w w w 站点返回的h r r p 响应消息格式不完整，此时须通过分析页面u r l 中 的文件扩展名来判别页面类型。需要分析的标记包括 、 、 、 、 、 和 等。页面链接中给出的u r l 可以是多种 格式的，可能是完整的包括协议、站点和路径的，也可能是省略了部分内容的， 或者是一个相对路径，通过u r l 提取器，需要将链接转换成统一的格式。 ( 5 ) m e t a 信息获取器m e t a 信息获取器获取的内容包括己采集页面的 m e t a 信息、a m c h o r 信息、页面的标题、页面的摘要等。在没有对页面内容语义 信息进行理解的前提f ，尽可能多的挖掘m e t a 、结构等的语义信息，可以为从 这些页面中提取出来的u r l 的好坏，给出一个度量。度量的结果传输到u r l 处理器，用于指导u i 也处理器对待采集的u i u 进行排序。 ( 6 ) 语义信息鼹析器根据采集策略的不同，有些采集器还有语义信息解析 器。这里所说的语义信息解析就是指对文本内容建立简单的索引。 ( 7 ) 数据库数据库用来存放经过重复内容检测后的页面数据、提取出来 的m c 诅信息、主题和摘要等。对于很多大型的搜索引擎来说，数据库中的内容 将用于建立索引。如果系统有语义信息解析器，则解析出来的内容也存入数据库。 由于数据较多，所以在存入数据库之前，一般要进行压缩，降低空间开销。 2 1 3c r a w l e r 工作流程 各种w 曲信息采集系统的核心都是c r a w l e r ，构造c m w l e r 可以有两种方式： 递归方式和非递归方式 2 8 。递归方式的c r a w l c r 程序运行时，要把每次递归都压 入堆栈，运行多次后会使堆栈变得非常大，可能会耗尽整个堆栈内存终止程序的 运行，而且多线程和递归不兼容，因为每个线程都有自己的堆栈，当一个方法调 用它自身的时候，使用同一个堆栈。因此在实现增量更新的w 曲信息采集系统 采用非递归方式，使用队列来存放和管理u r l 。 在c r a w i e r 程序中我们总共使用了四个队列：等待队列( w a i t l i s t ) 、运行队 列( p r o c e s s l i s t ) 、失败队列( f a i l e d l i s t ) 、完成队列( 觚s b e d l i s t ) 。各个队列的 具体功能为： 等待队列：队列中的u r l 等待c r a w l e r 程序处理，在页面解析中得到的超 链接u r l 经过去重后被加入该队列中； 运行队列：当c r a w l e r 程序处理一个u r l 时，该u 也从等待队列中删除， 放入该队列中。等处理完成，根据处理情况该u r l 将被送到失败队列或者完成 队列： 失败队列：当根据u r l 连接w 曲服务器或下载网页过程中失败时，u 也 将被加入该队列中，c r a w l e r 不会对它作进一步处理。 完成队列：u i u 对应的网页内容被成功下载，该u r l 将被加入该队列中。 同一时间，一个u r l 只能处于一个队列中，并且会随着处理的进行改变u i 也 北京工业大学工学硕士学位论文 图2 3c r a w l e r 流程图 f i 副2 - 3t h ef 1 0 wc h a r to f c f a w l c r 分析了c r a w l e r 程序的工作流程，我们可以看到它大体上可以分为三个部分， 页面信息采集、页面解析和超链接u r l 去重，下面详细说明各部分。 第2 章w 曲信息采集基本原理和关键算法 2 4 关键算法分析 2 4 1 页面信息采集 ( 1 ) u i 也简介页面信息采集主要是根据一定的协议与远程的w e b 信息源 服务器进行通信，将页面下载下来的过程。w 曲页面资源是由u r l ( 统一资源 定位器) 来确定的，u r l 由以下五部分组成： 模式( s c h e m e ) ：是u r l 中指定协议的部分，在这里主要讨论h 1 v r p 协议； 主机名( h o s t n a m e ) ：真正存储文档的服务器； 端口( p o n ) ：u r l 可以选择指定一个端口，如h t t p 默认端口为8 0 ； 路径( p a m ) ：指定真正向服务器请求的文件； 锚点( a n c h o r ) ：指定文档中的某个位置，它是一个短字符串，起着标注作 用。 u i u 结构如图2 - 4 所示 模式 0 主机名( ：端口)路径( 弹锚点) 圈2 - 4 i j i u 结构图 f i g u r e 2 4t h es t r l 咖c t l a r to f u r l ( 2 ) 页面采集采集一个w e b 网页的原理如同通过浏览器访问w 曲网页， 客户机和给定的u r l 相对应的w 曲服务器之间需要建立t c p 连接，连接建立 后，客户机发出h r r p 请求消息( h r i pr e q u e s tm e s s a g e ) 到这个连接上，w 曲 服务器接收到请求后，向客户机返回一个h r r p 响应消息( r - e s p o n s em e s s a g e ) 。 在服务器发送响应信息之后就断开t c p 连接。w 曲服务器和客户机之间的通信 如图2 5 所示。 h t l 甲请求 h t t p 响应 w e b 服务器 图2 5w 曲服务器和客户机间的通信图 f 培u r e 2 51 1 1 ec h a r to f c o m m i l i l i c a 虹o nb e t 、v e e nw e bs c r v e r 锄dw 曲c l i l l e t 在w 曲服务器返回的h 1 v r p 响应消息中，包含了h t r p 状态码，用来显示 在获取网页时客户机和w 曲服务器的状态。一般分为以下几类： 1 x x ：信息响应类，表示接收到请求并且继续处理； 北京工业大学工学硕士学位论文 2 x x ：处理成功响应类，表示动作被成功接收、理解和接受； 3 ) ( ) 【：重定向响应类，为了完成指定的动作，必须接受迸一步处理； 4 x x ：客户端错误，客户机请求包含语法错误或者是不能正确执行； 5 x x ：服务端错误，服务器不能正确执行一个正确的请求。 通过分析w e b 服务器返回的状态码，对采集动作做出不同的响应。如果状 态码为2 ) ( 】( ，则下载u r l 指定的网页内容，将u r l 放入采集完成的u r l 队列； 如果状态码为3 取，则从h r r p 响应消息中提取l o c a t i o n 字段的值，即重定向的 u r l ，根据该u r l 重新进行采集操作，获取相应的网页内容，并将u i 也放入采 集完成的u r l 队列；如果状态码为4 ) ( ) 【或5 x x ，则说明获取网页内容的请求没 有接受，无法下载网页内容，将该u r l 放入采集失败的u r l 队列。 j a v a 提供了很多支持h t e n 衙连接的类，其中u r l 类被广泛应用，该类允 许解析也，或者将其拆成各个组成部分，它所提供的连接能够很容易从内部 的j a v a 程序访问w e b 信息。 使用构造函数创建一个l 也对象： u r lu r l = n e wu r l ( u ) ； 声明以下所需变量： i n p u t s t r e 锄i s ； i n p u t s 骶锄r e a d e ri s r ； b u 脓r e d r e a d e rr ： u r l 类的o p e n s t r c 锄方法打开指定u r l 的连接，并返回一个h l p u t s t r c a m 给调用者。该h l p u t s t r e 锄被赋给变量i s 。i n p u t s 仃e 锄( i s ) 通过b u 位r e d r e a d e r ( r ) 从u r l 读入数据： i s = i l d o p e n s t r e a m ( ) ； i s 产n e wi 印u t s t r e a i i l r e a d e r ( i s ) ； r ：= n e wb u f f e r e d r e a d e “i s r ) ； b u 疵r e d r e a d e r 类能够逐行读取流。通过循环将从缓冲区中读取文本，直到 读完u r l 文档中所有数据，r e a d l i n e 方法返回肌1 1 。 d o s t r = l r e a d l i n e o ； i 坟s t r ! = n u l i ) 写入到本地文本文件中； ) w h i l e ( s t r ! = n u l l ) ； 当提供无效的u r l 时，u r l 类不能解析传递给构造函数的u r l ，将抛出 m a l f o 珊e d u r l e x c e p t i o n 异常；当在连接站点或传输数据的时候出现错误，将抛 出1 0 e x c e p t i o n 异常，必须捕获这些异常并处理。 第2 章w e b 信息采集基本原理和关键算法 2 4 2页面解析 从i n t e m e t 上获取的数据，大部分都存储在h 州l 文档中，所以对于w 曲 信息采集系统来说，采集到的w 曲信息是以h 刑l 文档形式的。如果要从h t m l 文档中获得需要的数据和信息，如超链接u r l 、文本内容、m e t a 信息等等，就 必须对h n 他文档进行解析。 ( 1 ) h 删l 简介h 聊l ( h y p e r t e x tm 砌( u pl a n g u a g e 超文本标记语言