（计算机系统结构专业论文）面向论坛页面的增量搜集技术研究.pdf

_ _ _ _ 原创性声明和关于论文使用授权的说明y 17 9 1 327iiiiiiiiiiiiiiiiiiiiiiiiiiiilullliillliiiliiiiii 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：垫圭埴日期： 2 2 1 2 ：量：兰三 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丝童埴导师签名： 日期：2 鱼! 垒：篁：墨； 一0，i， t l， p，i 山东大学硕士学位论文 目录 摘要i a b s t r a c t 第一章绪论1 1 1 研究背景及意义1 1 2 相关研究及发展2 1 3 本文的主要工作4 1 4 本文的组织5 第二章w e b 增量搜集技术6 2 1 增量搜集的基本概念6 2 1 1 周期式搜集6 2 1 2 增量式搜集6 2 2 增量搜集技术8 2 2 1 网页变化规律的研究8 2 2 2 传统的增量搜集技术1l 2 3 论坛爬虫研究1 3 2 4 论坛增量搜集技术1 5 第三章论坛结构和特性1 6 3 1 论坛结构1 6 3 2 论坛页面的变化规律1 7 3 2 1 增量式变化1 7 3 2 2 帖子列表页的特点1 8 3 2 3 局部时间特性1 9 第四章论坛增量搜集策略2 l 4 1 基本概念2 l 4 2 基于版块的增量抓取算法2 4 4 2 1m d r 自动抽取算法2 4 4 2 2 增量抓取算法2 5 4 3 基于版块的增量调度算法2 6 4 3 1 分配抓取资源2 6 4 3 2 确定抓取时间点2 7 4 4 实验与结果分析3 0 4 4 1 论坛数据集3 0 4 4 2 增量抓取算法实验结果3 l 4 4 3 增量调度算法实验结果3 5 第五章总结与展望4 0 参考文献4 2 致i 射4 7 攻读学位期间发表的学术论文目录4 8 山东大学硕十学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e 1 a b s t r a c ti ne n g l i s h c h a p t e r1i n t r o d u c t i o n l 1 1b a c k g r o u n d 1 1 2r e l a t e dw o r k s 2 1 3m a i nc o n t r i b u f i o n s 4 1 4o r g a n i z a t i o n 5 c h a p t e r2w e bi n c r e m e n t a lc r a w l i n g 6 2 1c o n c e p t i o n so f i n c r e m e n t a lc r a w l i n g 6 2 1 1p e r i o d i cc r a m 6 2 1 2i n c r e m e n t a lc r a w l 6 2 2i n c r e m e n t a lc r a w l i n g 8 2 2 1e v o l u t i o no f w e bp a g e s 8 2 2 2t r a d i t i o n a li n c r e m e n t a lc r a w l i n g 1 l 2 3f o r u mc r a w l e r 1 3 2 4f o r u mi n c r e m e n t a lc r a w l i n g 1 5 c h a p t e r3s t r u c t u r ea n df e a t u r e so f w e bf o r u m 1 6 3 1w e bf o r u ms t r u c t u r e 1 6 3 2f e a t u r e so f f o r u mp a g e se v o l u t i o n 1 7 3 2 1i n c r e m e n t a le v o l u t i o n 1 7 3 2 2t h ef e a t u r eo f l i s t o f - t h r e a dp a g e 1 8 3 2 3l o c a lt i m e 1 9 c h a p t e r4i n c r e m e n t a lc r a w l i n gp o l i c yf o rf o u r m s 2 1 4 1m a i nc o n c e p t i o n s 2 1 4 2ab o a r d b a s e di n c r e m e n t a lc r a w l i n ga l g o r i t h m 2 4 4 2 1 皿ra u t o m a t i ce x t r a c t i o na l g o r i t h m 2 4 4 2 2i n c r e m e n t a lc r a w l i n ga l g o r i t h m 2 5 4 3ab o a r d b a s e ds c h e d u l i n ga l g o r i t h m 2 6 4 3 1a l l o c a t ec r a w lr e s o u r c e s 2 6 4 3 2d e t e r m i n et h ec r a w lt i m e s 2 7 4 4e x p e r i m e n t a lr e s u l t s 3 0 4 4 1f o r u md a t as e t 3 0 4 4 2r e s u l t so fi n c r e m e n t a lc r a w l i n ga l g o r i t h m 3l 4 4 3r e s u l t so fi n c r e m e n t a ls c h e d u l i n ga l g o r i t h m 3 5 c h a p t e r5c o n c l u s i o n sa n df u t u r ew r o r k 一4 0 r e f e r e n c e s 4 2 a c k n o w l e d g e m e n t s 4 7 p a p e r sp u b l i s h e d 2 1 8 i一 山东大学硕士学位论文 摘要 网络论坛是用户创建和讨论话题的平台，每天都有数以百万的用户发表各种 话题。论坛数据通常包含大量高价值的知识和信息，已经成为重要的数据源。有 些商业搜索引擎利用论坛数据来改善搜索结果的质量，还有些研究试图从论坛数 据中挖掘有用的信息。无论何种w e b 应用，最基本的步骤是从各种论坛站点中 抓取数据，建立本地网页库，并维持对本地网页库的增量搜集。 增量搜集技术的核心理论依据是网页的变化规律和以此为基础的最优化调 度策略。论坛站点有一些不同于通常站点的特征：结构复杂且存在许多重复链接； 较长的帖子分布在多个页面上，链接深度大；论坛的内容变化更加频繁而且内容 增量式更新。传统增量搜集技术以单个页面作为基本调度单位，研究的是单个页 面的变化规律，并不适于对论坛数据进行增量搜集。 本文主要研究论坛的增量搜集问题，主要贡献有以下几点： 1 在论坛中属于同一主题的信息通常分布在多个页面上，本文摒弃传统增量 搜集技术中以单个页面为增量搜集的基本单位的做法，将属于同一信息的页面集 合作为增量搜集的基本单位。页面集合主要有两种类型：属于同一版块的页面集 合和属于同一帖子的页面集合。 2 通过对论坛结构的观察和对版块变化规律的统计分析，提出了基于版块 的论坛增量搜集策略。策略主要包含两种算法： 1 ) 基于版块的增量抓取算法：在大多数论坛中，版块页面即帖子列表页中 的帖子是按照最后回复时间进行排序列表，即新发布的帖子或者有新回复的帖子 会排列在帖子列表的前部。增量抓取算法利用m d r 自动抽取算法，抽取列表页 中的帖子链接和最后回复时间，然后判断是否为新发布帖子或者有新回复的帖 子。 2 ) 基于版块的增量调度算法：通过对版块页面集合变化规律的统计分析， 发现不同的版块内容变化频率相差很大，并且版块的变化频率与当天的局部时间 相关，具有局部时间规律。算法根据变化频率为不同的版块赋予不同的权重，然 后根据权重分配版块的抓取次数，同时根据版块变化的局部时间规律，确定每次 的抓取时间点。 山东大学硕士学位论文 实验结果表明本策略的带宽利用率为1 ，能够保证对发生变化的帖子的覆盖 率接近百分之百，同时能够大幅减小系统总延迟，与平均调度方法相比系统总延 迟最高可减小4 2 。 关键词：增量搜集；论坛爬虫：延迟；版块变化 n 山东大学硕士学位论文 a b s t r a c t w e bf o r u mi saw e ba p p l i c a t i o nf o rh o l d i n gd i s c u s s i o n sa n dp o s t i n gu s e r - c r e a t e d c o n t e n t ，m i l l i o n so fi n t e m e tu s e r sd i s c u s sv a r i o u st o p i c se v e r yd a y f o r u md a t a u s u a l l yh a sp l e n t yo fh i 曲l yv a l u a b l ek n o w l e d g ea n di n f o r m a t i o n ，a n db e c o m e sa n i m p o r t a n tr e s o u r c eo nt h ew e b s o m ec o m m e r c i a ls e a r c he n g i n e sh a v eb e g u nt o l e v e r a g ei n f o r m a t i o nf r o mf o r u m st oi m p r o v et h eq u a l i t yo fs e a r c hr e s u l t s ，a n di ti s a l s on o t i c e dt h a ts o m er e c e n tr e s e a r c he f f o r t sh a v et r i e dt om i n ef o r u md a t at of i n do u t u s e f u li n f o r m a t i o n h o w e v e r , w h a t e v e rt h ea p p l i c a t i o ni s ，t h ef u n d a m e n t a ls t e pi st o f e t c hd a t ap a g e sf r o mv a r i o u sf o r u ms i t e sd i s t r i b u t e do nt h ew h o l ei n t e m e ta n d m a i n t a i nal o c a ld a t a b a s eo fw e b p a g e s t h em a i nt h e o r yo fi n c r e m e n t a lc r a w l i n gt e c h n i q u e si st h ee v o l u t i o no fw e bp a g e s a n dt h eo p t i m a ls c h e d u l i n gs t r a t e g yb a s e do np a g ee v o l u t i o n f o r u ms i t eh a ss o m e d i f f e r e n tc h a r a c t e r i s t i c sf r o mo t h e rg e n e r a lw e b s i t e s ：i th a sc o m p l e xs t r u c t u r ea n d m a n yd u p l i c a t el i n k s ；l o n gd i s c u s s i o nt h r e a di su s u a l l yd i v i d e da n ds h o w ni nm u l t i p l e p a g e s ；c o n t e n to fw e bf o r u m su s u a l l yc h a n g e sm o r ef r e q u e n t l ya n di tu s u a l l yc h a n g e s i n c r e m e n t a l l y t h er e v i s i t i n gs t r a t e g yo ft r a d i t i o n a li n c r e m e n t a lt e c h n o l o g i e si s u s u a l l yb a s e do ni n d i v i d u a lp a g e ，s ot h e s et e c h n o l o g i e sa r en o ts u i t a b l ef o rc r a w l i n g f o r u ms i t e si n c r e m e n t a l l y t h i st h e s i sd o e sas t u d yo fi n c r e m e n t a lc r a w l i n gf o rw e bf o r u m s ，a n dt h em a i n c o n t r i b u t i o n so ft h i st h e s i sa r ea sf o l l o w s ： 1 i nt h ef o r u mat o p i ci su s u a l l yd i s t r i b u t e di nm o r et h a no n ep a g e ，t h i st h e s i s a b a n d o nt h et r a d i t i o n a li n c r e m e n t a lt e c h n o l o g yw h i c hu s eas i n g l ep a g ea st h eb a s i c u n i to fi n c r e m e n t a lc r a w l i n g ，a n dd e f i n et h ep a g e so ft h es a m ei n f o r m a t i o na st h e b a s i cu n i tf o ri n c r e m e n t a lc r a w l i n g ，p a g es e th a st w om a i nt y p e s ：p a g es e tw h i c h b e l o n g st ot h es a r r l eb o a r da n dp a g es i t eb e l o n g i n gt ot h es a l t l et h r e a d 2 b a s e do nt h es t a t i s t i c a la n a l y s i so nt h ee v o l u t i o no fb o a r di nm a n yw e b f o r u m s ，a n o v e la n db o a r d - b a s e di n c r e m e n t a lc r a w l i n g s t r a t e g yi sp r o p o s e d t h i ss t r a t e g y m a i n l yc o n s i s t so ft w ok i n d so fa l g o r i t h m s ： i i i 山东大学硕士学位论文 a ) ab o a r d b a s e di n c r e m e n t a lc r a w l i n ga l g o r i t h mf o rf o r u m s ：i nm o s tw e bf o r u m s ， i nt h et h r e a dl i s tp a g e ，t h et h r e a dl i s ti ss o r t e db yt h el a s tr e p l yo ft h r e a d i tm e a n st h a t t h en e wr e l e a s et h r e a do rn e wr e p l i e dt h r e a dw i l lb ea r r a n g e di nt h ef r o n to ft h et h r e a d l i s t t h ei n c r e m e n t a lc r a w l i n ga l g o r i t h mu s e st h em d ra u t o m a t i ce x t r a c t i o na l g o r i t h m t oe ) 【t r a c tt h et h r e a dl i n ka n dt h el a s tr e s p o n s et i m e ，a n dt h e nd e t e r m i n ew h e t h e ra t h r e a di nn e wr e l e a s e do rn e wr e p l i e d b ) as c h e d u l i n ga l g o r i t h mf o ri n c r e m e n t a lc r a w l i n go ff o r u m ：t h r o u g ht h es m t i s t i c a l a n a l y s i so nt h ee v o l u t i o no fb o a r di nm a n yw e bf o r u m s ，w ef o u n dt h a tt h ec h a n g e f r e q u e n c yo fd i f f e r e n tb o a r dv a r i e dw i d e l ya n dt h ec h a n g ef r e q u e n c yh a ss o m ew o r k s w i t ht h el o c a lt i m eo fad a y t h i sa p p r o a c hl e v e r a g e st h eb o a r dw e i g h t sa n dl o c a lt i m e d i s c i p l i n et oa l l o c a t ec r a w lr e s o u r c e sa n dd e t e r m i n et h ec r a w lt i m e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eb a n d w i d t hu t i l i z a t i o no ft h es y s t e mi s1a n dt h e c o v e r a g ef o rt h en e w l yp u b l i s h e da n du p d a t e dd i s c u s s i o nt h r e a d si s c l o s et o10 0 p e r c e n tb a s e do nt h i ss t r a t e g y , a n dt h eo v e r a l ls y s t e md e l a yi sm a x i m a l l yd e c r e a s e db y 4 2 a sc o m p a r e dw i t l le v e ns c h e d u l i n gm e t h o d k e y w o r d s ：i n c r e m e n t a lc r a w l i n g ；f o r u mc r a w l e r ；d e l a y ；b o a r de v o l u t i o n 一 ； l ， 山东大学硕+ 学位论文 第一章绪论 本章主要介绍论文的研究背景、相关工作的研究现状、论文的主要工作以及 整篇文章的组织结构。 1 1 研究背景及意义 随着网络的不断发展，论坛作为一种w e b 信息交流共享平台，拥有数以百 万的用户。论坛数据通常包含大量高价值的知识和信息，已经成为许多w e b 应 用的重要数据源【l 】。用户和社区的力量是论坛数据高质量的源泉，例如消费者喜 欢在论坛上分享他们关于某些产品的评价和经验，使得论坛上的评论较为公正和 可信。大部分的商业搜索引擎如g o o g l e ，y a h o o 和百度已经开始利用论坛数据来 改善搜索结果的质量 2 1 ，尤其是对问答式查询效果更明显。最近还有一些研究试 图从论坛数据中挖掘有用的信息，如商业知识和商业智能等。无论何种w e b 应 用，基本的步骤是从各种论坛站点中抓取页面并建立本地索引库。论坛内容具有 频繁变化的特点。通常情况下新增的数据比较老的数据拥有更大的价值，因此必 需使用一种高效的增量搜集策略来对论坛站点进行增量搜集，以维持对本地数据 索引的时新性，保证检索结果的质量和实时性。 传统的增量搜集技术是针对普通的静态页面【3 l ，研究信息变化的基本单位是 单个页面【4 】【习或者是页面内更小粒度的信息块嘲，在对论坛页面进行增量搜集的 效率会很低。这是因为论坛站点有一些不同于普通站点的特征：第一，为了帮助 用户方便的浏览，论坛通常提供了许多指向相同内容的快捷链接，这些链接经常 有不同的u r l 。在论坛抓取中不加区分的抓取这些快捷链接将会导致许多重复 页面。第二，大多数论坛都有访问控制来保护隐私，有一些链接对于非注册用户 如爬虫是禁止访问的，这些链接会重新跳转到一些设置好的特殊页面上如登陆页 面等。第三，论坛中存在分页问题即属于同一主题的信息分布在多个页面上。例 如论坛站点通常由一组版块组成，每个版块包含一组帖子。而属于同一版块和属 于同一帖子的信息通常都分布在多个页面上。第四，论坛的内容比普通网站变化 的更加频繁，爬虫需要保持高频率的增量抓取，才能维持本地数据索引的时新性。 最后论坛的帖子还具有页面内容增量变化的特点，例如当有新的帖子发布时，将 山东大学硕士学位论文 可能导致属于该版块的所有页面发生变化，而传统的增量爬虫会抓取变化的所有 页面但真正的新增的信息却只出现在几个页面上。 由于以上特点，传统的增量搜集技术并不适于进行论坛数据的增量搜集。因 此，寻找新颖的论坛增量搜集算法具有重要的学术和应用价值。 1 2 相关研究及发展 随着互联网的发展，网络中的网页数量呈指数级增长，网页数量的急速增长 为搜索引擎的爬虫系统带来巨大的挑战。网页数量巨大，需要尽可能抓取更多的 网页。爬虫的带宽资源有限，需要对网页按照重要度进行排序，优先抓取价值较 高的网页。在这种情况下，传统的大规模周期性抓取方式已经不再适用，而增量 搜集方式仅抓取已经发生变化的网页，避免抓取未发生变化的页面，从而能够大 量节省带宽资源和时间，增量搜集方式在网页抓取方面具有更高的效率。增量搜 集方式能够快速感知发生变化的页面，使得本地网页库保持较高的时新性。 传统增量搜集技术主要研究网页的变化规律，并根据得出的网页变化规律进 行调度。在调度时通常以提高本地网页库的时新性为总目标，研究在此目标上的 最优调度策略。目前针对网页变化规律研究已经非常成熟，主要包含下面两种方 式：一种方式是选择互联网中的某些网页作为样本，然后通过抓取记录样本的历 史变化轨迹，得出样本网页的变化规律，进一步推出整个网络中网页的变化规律 1 7 - 1 3 。另一种方式是从理论角度进行分析，认为网页的变化规律符合某种数学模 型。然后采用某些网页样本进行实际实验，利用实验数据来训练得出数学模型中 的相关参数，最后通过训练得到的数学模型来预测页面的变化规律0 4 q s 。在当 前的大部分研究中网页的变化过程通常被认为是泊松过程 3 1 ，即网页两次变化之 间的时间间隔服从指数分布。以此为网页变化过程建模，然后就要通过实验数据 来估计数学模型的参数【4 】，根据训练好的数学模型就可以推测页面的变化规律。 实验数据的获取需要记录页面的历史变化记录，由于系统的资源有限，无法获取 网络中所有页面的变化时间，因此需要估计网页的变化频率。估计网页变化频率 主要有两种方法：直接估测每个页面的变化频率和估计网页所属类别的变化频 率。在进行估计的过程中，为了准确获得每个页面的变化频率需要进行很长时间 的抓取检测，并且需要记录每个页面的所有变化时间。而需要估计的网页数量较 2 山东大学硕士学位论文 大，需要大量的资源才能完成估测，将严重影响估测效率。为进一步提供估测效 率，有的研究【1 8 】不再为所有网页建立模型，而是选取网页样本，为每种样本建立 模型。例如按照域名分组，为每组页面建模并计算该模型的相关参数。增量搜集 技术的调度策略通常需要决定网页的抓取频率和网页抓取的顺序。根据网页的变 化频率来决定对它的抓取频率，保证网页的时新性；根据网页的重要度决定网页 之间的抓取顺序。这样同时保证了本地页面库的重要性和时新性。最优调度策略 就是要最大化网页的重要性加权后的时新性。 文献【6 】中使用页面中的信息块的变化作为增量搜集的依据，这是一种新的思 路。但在论坛中同一信息通常不在一个页面内，而是包含于多个页面中。论坛页 面的变化是增量式变化，新增内容被追加到页面上，而不是像普通页面那样替换 原有的内容。因而文献【6 】中的算法不适用于论坛的增量搜集。 当前针对论坛爬虫的研究还较少。文献1 1 9 】研究了论坛抓取问题，它使用一组 启发式规则作为抓取策略，只能处理一些特定组织结构的论坛。而在现实中存在 数百种论坛结构，无法为这些论坛制定一个普遍的启发式规则。文献【2 0 】中提出了 一种基于结构化驱动的爬虫，通过人工选择目标页面的一个样本，使用该样本页 面的d o m 树作为目标的描述，即使用页面的d o m 树作为模板，通过计算页面与 模板的相似度来确定页面是否为目标页面，这种方式的本质是对比网页的布局结 构是否相同。这样对站点进行少量的深度抓取，就可获得该站点主页面到目标页 面的所有路径的集合。但这种方法是为普通网站设计的，仅仅关注如何找到通往 目标页面的遍历路径，并不能找到最优路径。在论坛中，通常有多条路径通往目 标页面，这些路径的大部分是快捷链接方式，这种路径不能涵盖所有的目标页面。 文献【2 0 】中的方法没有提及寻找最优路径的方法，因此并不适于进行论坛抓取。除 此之外，在论坛中一些在视觉上布局相似的网页可能包含不同数目的广告、图片 甚至一些复杂的嵌在用户帖子中的子结构。这样尽管页面布局是相似的，但它们 的d o m 树就会有很大不同。因此使用页面的d o m 树作为模板的方式不够健壮。 文献【lj 提出了智能化的论坛爬虫i r o b o t ，该爬虫首先下载一些目标论坛的样 本页面，将网页按照布局特征表示成向量，然后使用聚类算法对网页进行聚类。 这样具有相同布局特征的网页聚成簇，再通过u r l 规则进行分类细化簇。这样就 在样本上构建出了论坛站点的结构图，在该图上从全局角度考虑找到最优遍历路 3 i l i 东大学硕士学位论文 径。该爬虫与传统爬虫相比取得了较好的效果。文献【2 】提出了一种自动探测遍历 路径的策略，使用骨干链接来指导爬虫抓取有价值的页面，从而避免重复和无效 链接，使用分页链接来指导爬虫完整地获取一个长帖子，该帖子分布在多个页面 上。与以前的相关工作以及一些通用的商业爬虫相比，该策略可以获取更多有价 值的页面。 文献【2 1 1 提出了一种论坛增量搜集方法，是一种基于列表的策略。将帖子列表 页和帖子展示页看作是一种列表。在帖子列表页上，是帖子链接的列表。而在帖 子展示页中，则是针对给帖子主题的回帖的列表。当有新发布的帖子时，则帖子 列表页面发生变化。当有新回帖时，对应的帖子展示页面发生变化。通过对帖子 列表页和帖子展示页的历史变化记录的研究，从中抽取相应的时间特征，一共使 用了九种特征。利用一种计算简单、可以高效地在线处理的线性回归模型来预测 页面变化时间。首先利用从历史数据中抽取出来的特征进行训练。训练时，对帖 子列表和帖子展示两种不同形式的列表分别进行训练，得到两个模型。使用这两 个模型，分别预测新增帖子和帖子下次发生变化的时间。这种基于列表的策略取 得了较好的效果，但是预测准确性不高。 综上所述，现有的增量搜集技术的研究主要集中于普通网页方面，可以说目 前针对普通页面的增量搜集研究已经进入了一个较为成熟的阶段。另一方面，除 了文献【2 1 1 中的工作外，以往的工作都未涉及论坛的增量搜集问题，关于论坛增量 搜集技术的研究还很少且很不成熟。 1 3 本文的主要工作 通过观察多个论坛，我们发现属于同一主题的信息通常分布在多个页面上， 例如同一帖子会分成许多页，同一版块也会分为多个页面。并且论坛中的内容更 新是增量式的。这样进行增量搜集时，调度抓取的基本单位应该是属于同一信息 的一组页面而非单个页面。因此本文提出的增量搜集策略是以一组页面作为调度 的基本单位。 一 在论坛中，帖子一般是按照发布或最新回复时间排列在版块列表页上，新增 和新回复的帖子必然出现在版块页面的前部。进行增量搜集时，只需要对版块页 一 面进行抓取分析，就能保证获取所有的新增和新回复的帖子。普通页面的变化周 4 l i i 东大学硕士学位论文 期和生命周期稳定并且有规律，如果有较长的历史数据统计，则可以比较准确的 预测页面的下次变化时间。但是帖子不同于普通网页，刚创建的帖子通常会有频 繁的变化，创建时间越长则变化频率则会越低。帖子的变化存在很大的不确定性， 而版块变化则相对稳定。因而本文提出一种基于版块的增量搜集策略，以版块作 为基本调度单位。通过对论坛版块变化规律的统计，发现不同的版块更新速度不 同，据此我们提出了一种版块权重的计算公式，给予不同版块不同的权重，以此 来确定对版块的抓取频率；提出一种确定抓取时间点的算法，根据版块变化时刻 的特性来确定对版块的抓取时间点。 全文的主要贡献有： 1 以版块为基本单位进行增量调度而不是像现有大多数爬虫以单个页面为 调度单位，版块指的是属于该版块的所有帖子列表页集合。 2 提出了基于版块的增量抓取算法，获得很高的带宽利用率和覆盖率。 3 提出了基于版块的抓取调度算法，大幅减小系统总延迟。 1 4 本文的组织 全文的章节安排： 第一章介绍了研究的目的和意义，回顾了相关的研究现状，并概括了本文 的主要工作。 第二章介绍w e b 增量搜集技术的基本概念、原理及相关工作。 第三章介绍了论坛的特性，包括在历史数据集上统计出的规律。 第四章介绍本文提出论坛增量搜集策略，详细介绍该策略的原理以及它所 包含的算法，并展示本文提出的论坛增量搜集策略的实验结果。 第五章总结全文的工作，并对下一步研究工作进行展望。 山东大学硕士学位论文 第二章w e b 增量搜集技术 2 1 增量搜集的基本概念 搜索引擎系统需要能够获取互联网中的重要数据，能够及时地获取网络中新 增的页面保证本地网页库的时新性。对商业的搜索引擎而言，重要新颖的信息能 够提高用户满意度，增强该搜索引擎的竞争力。随着互联网的发展，网页数量呈 指数级增长，这对搜索引擎的搜集子系统产生了巨大的挑战。通常搜索引擎的搜 集方式有两种：周期式搜集方式和增量搜集方式。 2 1 1 周期式搜集 在一个搜集周期内，搜索引擎对互联网中的网页进行全网搜集，然后建索引 和提供服务。这种方式的优点是数据覆盖全并且易于实现，缺点是系统具有信息 滞后性无法保证本地网页库的时新性。搜集系统的搜集能力有限，抓取完网页后 还要进行网页去噪、分词、建立索引等步骤。当需要抓取的网页数量巨大时，搜 集周期会很长。对于在这个期间发生变化的网页，搜集系统无法获得。而对于搜 索引擎来说，本地网页库的时新性是非常重要的，这将直接影响搜索结果的质量。 因而周期式搜集通常不能满足系统的时新性需要。 2 1 2 增量式搜集 增量搜集是指在以前搜集的大规模网页数据基础上，采用某种增量搜集策 略，预测页面的下次变化时间。根据网页的变化规律，在合适的时刻再去抓取网 页信息，并把发生变化和新增的网页保存到本地。这种搜集方式通常需要记录网 页的历史变化信息，根据页面的变化规律采用某种预测算法进行抓取。 增量搜集还有另外一种形式：先进行周期式搜集，然后在此基础上进行增量 搜集。等一个搜集周期结束后再次集中搜集互联网中的网页，然后在这个数据集 上进行增量式搜集。在这种增量搜集形式中一个搜集周期内包括两个阶段：周期 式搜集和增量搜集。当前许多搜索引擎采用的是这种方式。 互联网中网页总量快速增长，使得传统的周期式搜集方式很难保证本地网页 6 山东大学硕士学位论文 索引库的时新度。与传统的周期式搜集方式相比增量搜集方式仅抓取已经发生变 化的网页，避免抓取未发生变化的页面，从而能够大量节省带宽资源和时间，增 量搜集方式在网页抓取方面具有更高的效率。增量搜集方式还能够快速感知发生 变化的页面，使得本地网页库保持较高的时新性。在现有网页数据集的基础上， 采用某种更新策略，抓取互联网中变化和新增的网页，从而有效地保证搜索引擎 中数据的时新性。 增量搜集系统负责决定网页的采集频率以及采集次序。根据网页的变化频率 决定网页的采集频率，根据网页的重要性来决定网页的采集次序。在某个时刻， 将需要进行抓取的所有网页按照重要度排序决定网页的抓取顺序，从而生成u r l 抓取列表。在进行抓取时，抓取一个网页然后判断该网页是否被抓取过。如果曾 经抓取过该网页，进一步判断网页是否发生变化。 通常情况下，增量搜集系统分为爬虫和增量调度两部分。目前关于爬虫部分 已经有很多成熟的研究工作。现存有大量成熟的搜集系统 2 2 - 2 引，这些系统利用网 页间的链接关系来抓取互联网中的网页 2 9 - 3 1 1 ，这些研究工作涉及爬虫的整体架构 和抓取算法，如分布式爬虫等等。另外还有大量的研究工作【3 7 1 对诸如网页去噪、 网页消重、抓取路径策略和分布式搜集等爬虫系统的技术细节进行研究。但以上 的研究没有涉及新增页面和网页变化的问题，只是针对爬虫系统的研究。 增量调度部分主要研究网页的变化规律，然后根据已有的网页变化规律基础 上进行抓取调度。通常情况下网页的变化过程被视为泊松过程，采用泊松过程来 描述页面的变化规律，也就是说页面的两次变化之间的时间间隔符合指数分布。 目前大部分的增量搜集研究都是据此估计网页的变化周期和下次变化时间。而调 度策略根据页面的变化规律决定每个网页的抓取频率，按照这个频率来重抓取页 面，保证本地网页库的时新性。由于不同的网页重要度不同，重要度越高的网页 所包含的信息价值越高，当调度系统决定一组页面需要进行抓取时，还需要按照 网页价值决定网页的搜集顺序，优先抓取价值较高的网页。恰当的增量调度策略 可以同时提高本地网页库的数据重要性和时新性。增量搜集系统的资源有限，调 度策略应尽可能提高根据网页的重要性加权后的平均时新度，不同的调度方式采 用不同的标准来衡量本地网页库时新度，能够达到理论上最优值就是最优策略。 7 山东大学硕士学位论文 2 2 增量搜集技术 2 2 1 网页变化规律的研究 目前已经有大量网页变化规律研究，并且这些研究已经相当成熟。在当前的 研究中主要包含下面两种方式：一种方式是选择互联网中的某些网页作为样本， 然后通过抓取记录样本网页的变化时间，得出样本网页的变化规律，进一步推出 整个网络中网页的变化规律【7 13 1 。另一种方式是从理论角度进行分析，认为网页 的变化规律符合某种数学模型。采用某些网页样本进行实际实验，利用实验数据 来训练得出数学模型中的相关参数。通过训练得到的数学模型来预测页面的变化 规律1 1 4 - 1 8 1 。当前的网页变化规律研究可以概括为以下五个方面： 1 数学模型 在目前的大部分研究中，网页的变化过程一般被视为泊松过程。假定网页p 的变化频率是a ，并且网页尸的下次变化时间是n 那么r 的概率密度函数为： 川卟傺。篡善 协- ， 则网页p 在区间( o ，f ) 内发生变化的概率为： m r t f = f l ( t ) a t = l e ( 2 - 2 ) 否 据此我们可以为网页的变化过程建模，根据该模型预测网页的变化规律，可 以在该模型基础上使用时新性和年龄两个指标来评价增量搜索系统所维护的本 地网页集合。 2 参数估计 上面提出了网页变化的基本数学模型，还需要通过搜集网页数据来估计其参 数，以获得网页的变化频率并计算网页的下次变化时间。然而系统的带宽资源有 限，无法获取网络中所有页面的变化时间，因此需要估计网页的变化频率。对网 页变化规律的估计方