（计算机软件与理论专业论文）搜索引擎中主题爬虫算法的研究.pdf

搜索0 f 擎中丰题爬虫算法的研究 计算机软件与理论 刘涌锋 印鉴教授 摘要 搜索引擎技术的研究已成为当今瓦联网研究领域的大热点。它以网络技术、并 行系统、机器学习、数据挖掘、模式识别、图像技术、自然语言处殚等理论为摹础， 同时具有很强的工程实践性。 本文酋先介绍了我们开发的一个内部网信息检索系统，然后介绍了本文在该系 统中设计的网络爬虫( w e bc r a w i e r ) 模块的体系结构，该结构考虑到了如何优先采 集“重要”网页和如何根据网页的变化频率调整更新网页的策略。最后基于经典丰题 爬虫算法s h a r k - s e a r c h 算法，通过引入网页重要度的概念，提出了一个基于重要 度的丰题爬虫算法。 实验结果表明，应用该算法采集到的网页的丰题相关度比应用s h a r k s e a r c h 算 法好，而且能优先采集“更重要”的网页这是s h a r k s e a r c h 算法没有考虑的。 【关键词】搜索引擎、书题爬虫、重要度、相关度 f o c u sc r a w i e rr e s e a r c h i n gi ns e a r c he n g i n e c o m p u t e rs c i e n c c l i u l y b n g f e n g y i n j i a n a b s t r a c t t h er e s e a r c ho fs e a r c he n g i n et e c h n o i o g yi sah o 中o ti nw w w r c s e a r c h i ti sb a s e d o nn e t 、v o r kt e c h n o i o g y p a r a l l e ls y s t e m ，m a c h i n el e a 玎l i n g ，d g t am i n h 昏m o d e le l a s s i 母i n g ， n a t u r el a n g u a g ep m c e s s ，i m a g et e c h n o l o g ye t c i tj s a i s oab i gc h a i | e n g ei ns o f t w a f e n g i n e e “n g t h i sp a p e rf i r s tg j v e sabr e fa r c h i t c c t u o fa ni n t m n e ts e a r c he n g i n es y s t e mw e b u i i ta n dt h e ni n t r o d u c e st h es t 九i c t u 他o fw e bc 豫w l e rw h i c hc a nd o w n l o a d “i m p o r t a n t - w e bp a 留e sf i r s ta n du p d a t ew e bp a 孕e sb a s e do nt h ep a g e sc h a n g ef e q u e n c y a tl a s t b y i n t r o d u c ei n t 0t h et t i m p o r t a n t - v a l u e ”，w eg i v eaf o c u sc m w l e ra i g o r i t h mw ed e s l g n e d t h i sa l g or t h m i m p r o v e s t h et r a d i t i o n a lf o c u sc m w l e ra l g or i t h m 一一s h a r k 。s e a r c h a l g o r i t h m e x d e r i m e n ti n d i c 8 t e st h a to u ra i g o r i t h mc a nn o to n i yd o w n l o a dt o p i cw e bp a g e s m o r er e i e v a n tt h a ns h a r k s e a r c ha i g o r i t h m ，b u ta l s od o 、w l i o a d “i m p o r t a n t ”w e bp a g e s f i f s t ，w h i c hs h a r k s e a r c ha l g o r i t h md i d n t t h i n ka b o u t 【k e y w o r d s 】s e a r c he n g i n e ，t o p i cc r a w l e li m p o a n tw e bp a g e ，r e l e v 锄tw e b p a g e n 引言 像蒸汽机和电的发明样，瓦联网的出现和蓬勃发展对人类牛活的影响是革命 性的，因为它彻底改变了人们获取信息的方式，人们越来越多地通过网络来获取信 息，同时它也改变了我们的牛活方式。 为了使人们能快速、准确地从百联网上获取信息，搜索引擎诞牛了，从分类目 录检索到全文检索，搜索引擎给人们带来了巨大的便利。它是真正的瓦联网门户， 全球各大著名搜索引擎网站的访问量都居前列。当今，瓦联网上的数据量呈现出指 数级的增长趋势，并且网页不定期地发牛变化，这给搜索引擎带来了巨大挑战。晟 大的搜索引擎也只能覆盖互联网上的部分网页，而且并不能保证建索引的网页和现 实网页都是同步的，因此优先采集“重要”网页和制定有效的更新策略成了搜索引擎 中的信息采集模块网络爬虫( w e bc m w l e r ) 必须考虑的问题。研究人员在如何 评价网页重要度上作了大量研究，这些对网页重要度的评价算法丰要基于对网络链 接结构的分析，比如著名的p a g e r 柚k 技术。 另外，搜索引擎也不能完全满足人们获取个性化丰题信息的需求。搜索引擎很 难回答诸如“我的竞争对予当当书店网站昨天都有什么新上架? ”这样的问题。为 了解决这些问题，就需要个能在客户端运行的信息采集程序，该程序能满足用户 对信息的个性化需求，因此出现了一种称为丰题爬虫( t o p i cc m w l e r ) 的技术。 本文首先介绍了搜索引擎设计技术和网络爬虫技术，然后在这些技术的基础上 刚述我们开发的一个内部网信息采集系统。本文对该系统的爬虫模块进行了设计， 并提出了通过使用等比队列来优化爬虫更新网页的策略，使得爬虫能对变化频率快 的网页进行更快的更新，该结构还考虑到了如何优先采集“重要”网页。然后论文介 绍了丰题爬虫技术以及相关算法，提出了一个基于重要度的丰题爬虫算法，该算法 将网络爬虫技术中计算网页重要度的理论应用到丰题爬虫算法当中也就是通 过引入由链接结构和网页u r l 结构计算得到的网页重要度值，改进了经典的丰题爬 虫算法s h a r k - s e a r c h 算法。 实验结果表明，应用该算法采集到的网页的主题相关度比应用s h a r k s e a r c t l 算 法好而且该算法能优先采集“更重要”的丰题相关网页这是s h a r k s e a r c h 算法 没有考虑的。 第1 章概述 1 1 互联网信息检索技术面临的挑战 当今，瓦联网上的信息量呈指数级增长，每4 个月翻一番，网上的数据信息爆 炸式地增长，其规模已从1 9 9 3 年的几千个网页快速增长到2 0 0 3 年的至少8 0 亿个网 页和5 6 0 亿个超链接，现在网页数和链接数已远远超出这个统计数字，而g o o g l e 现在能检索的网页量还是8 0 亿。而且因特网上的文档是分布的、异构的、无结构或 半结构的。用户要在信息海洋里查找信息，就像大海捞针一样，因此怎样快速、有 效、经济地检索信息，就成了一个十分热门的课题，同时也是一个大难题! 搜索引擎是在可_ 联网上检索信息最重要的工具，它以一定的策略在百联网中搜 集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从 而起到信息导航的作用。搜索引擎提供的导航服务已经成为瓦联网上非常重要的网 络服务，搜索引擎站点也被美誉为”网络门户”。 搜索引擎技术因而成为计算机工业界和学术界争相开发研究的对象。这当中有 着大量的技术难题有待解决，开发搜索引擎系统需要理论研究和工程实践紧密结合。 它的研究融合了信息检索、并行计算、图论、数据挖掘、机器学习、自然语言处珲、 图像技术、网络技术等众多理论。这增加了研究的难度，同时也会产牛大量的研究 成果。由于各大公司和高校投入大量的研发力量，搜索引擎技术成长迅速，f u 是要 达到能从百联网上快速、准确地获取信息，还是远远不够的。 它面临着如下诸多挑战：如何从海量百联网数据当中优先采集重要数据：如何使自 己的网页数据库、索引能尽量保持和网页更新的同步；如何返回给用户最有用的信 息：如何准确理解用户输入的含义，甚至能回答用户的提问等等。 除了服务器端的搜索引擎以外，还有客户端的信息采集工具能帮助用户从瓦联 网上获得想要的信息，这当中丰要用到丰题爬虫技术。这些工具能根据用户的个性 化设置，到网上采集相关的信息。已经有很多公司开发出了类似的系统，比如新闻 采编系统里面会有专门负责新闻信息采集的模块，还有采集跟踪竞争对手网站的程 序。丰题爬虫技术在百_ 联网信息检索上是搜索弓i 擎的有力补充，它能完成一些搜索 引擎不能完成的信息获取需要。同时丰题爬虫技术也会应用在搜索引擎上，比如在 类目里面的搜索和特定丰题信息的优先更新等。 丰题爬虫技术丰要研究的是怎样采取一个好的策略( 沿着一条好的“路径”) 采 集相关度高的网页，同时又能有效地避免不相关的网页，这当中主要用到了数据挖 掘、机器学习等理论。它往往结合文本分类、文本聚类、w c b 挖掘等技术，但还远 未成熟。 同样它也面临着诸多挑战：如何对采集到的信息很好地进行丰题分类：如何使 这些信息聚类成有丰题意义的类；爬虫在采集的过程中如何根据反馈优化自己的采 集策略等等。 1 2 目前国际上的研究状况 文献【2 是1 9 9 8 年9 0 0 9 l e 的两位创始人s b r i n 和l - p a g e 写的g o o g l e 系统的设 计原型，其中介绍了搜索弓i 擎设计中的幸要技术以及他们是如何实现的，还介绍了 g o o g l e 成功的法宝计算网页重要度的p a g e m n k 算法。由于搜索引擎的设计结构 往往是各大公司的机密，因此文献很少。文献【3 价绍了c o m p a qs y s t e m sr e s e a r c h c e n t e r 开发的个称为m e r c a t o r 的网络爬虫的设计结构，m e r c a t o r 被用在著名的搜 索引擎a i t a v i s 协上。 s t 锄f b r du n i v e r s i t y 的w 曲b a s ep m i e c t 【4 1 对搜索引擎开发所用的技术进行了比较 全面的研究，包括采集网页、存储、建索日l 和海量数据库中的查淘等技术。其中： 文献【5 】研究了优先采集重要网页的技术，它比较了c m w i e r 在分别采取几种不同的 网页重要度评价方法时在采集重要网页上的性能。在网页更新技术方面，文献【6 】研 究了如何计算网页的更新频率；文献【7 】研究了瓦联网上网页的变化规律以及比较了 根据网页的更新频率采取的几种不同的采集策略的优劣，最后给出了一个能优先采 集重要网页并有网页更新策略的c 哺w l e r 的设计架构；文献【8 】研究了网页数据库的 更新策略，如何使得网页数据库有较大的刷新率。文献【9 】对如何设计并行c r a w i e r 进行了研究，提出了一个并行c m w i e r 的设计结构。文献【i o 】研究了建索引的技术。 文献】研究了如何存储和更新海量的网页，给出了个设计结构，比较了几种网 页的存储、访问方式。文献【1 2 】研究了如何采集动态生成的网页。 在丰题爬虫技术方面，文献【1 3 】中的f l s hs e a r c h 算法是最早提出的一个经典算 法，该算法体现了丰题爬虫技术的摹本思想，之后i b mh a i f ar e s e a r c hl a b o 忸t o r y 提出了一个s h a 良s e a r c h 算法【1 4 】对其进行了重大改进，0 i 入了文本相似度理论和链 接文本分析技术。此后研究者在丰题爬虫算法的研究上大量使用了机器学习( 丰要 有增强学习、遗传算法等) 和数据挖掘理论( 主要是w e b 挖掘技术，包括文本分类、 聚类还有w e b 架构挖掘等技术) 。文献【1 5 】通过调用搜索弓i 擎找到已知丰题网页的路 径来建立c o n t e x tg m p h s 进行采集策略的学习，从而提高了算法性能。文献【1 6 删用 了增强学习的方法使a g e n t 在采集网页的过程中动态地调整采集策略来提高效率。 文献f 1 7 】通过结合用户的反馈信息来调整访问策略。文献【1 8 】给出了一个丰题爬虫系 统的设计结构并阐述里面用到的主要技术。 1 3 本文的工作 本文以搜索引擎技术研究为背景，开发了一个内部网信息检索系统，重点对网 络爬虫模块进行了设计。然后重点介绍了丰题爬虫技术及其重要的算法，提出了一 个基于重要度的丰题爬虫算法，该算法将网络爬虫技术中网页重要度的殚论应用到 丰题爬虫算法上。最后通过实验证明了该算法不仅能采集丰题相关的嘲页，而h 能 优先采集“更重要”的丰题相关网页。 1 4 本文的组织 本文章节组织如下： 第l 章为概述，简要介绍了互联网信息检索技术和面临的挑战，甘前国际上在 该领域的研究状况，以及本文所做的工作。 第2 章介绍了搜索引擎的历史和未来发展趋势，并对搜索引擎的设计技术做了 介绍。 第3 章介绍了网络爬虫技术，丰要包括如何优先下载重要的网页和如何处理网 页的更新问题。 第4 章在前两章对搜索技术和网络爬虫技术研究的基础上，给出了一个我们开 发的内部网信息检索系统，在此基础上介绍了本文设计的网络爬虫模块。 第5 章首先讲述了现有搜索弓i 擎系统的一些局限性，引出了能弥补这些局限的 丰题爬虫技术，然后介绍了辛题爬虫技术的经典算法f i s hs e a r c h 算法、s h a r k s e a r c h 算法和其他丰题爬虫算法。最后介绍丰题提取算法。 第6 章提出了一个摹于重要度的丰题爬虫算法，给出了提出该算法的背景。然 后介绍了该算法用到的丰要技术网页重要度网页相关度的评价方法，中文分词 技术，在此基础上给出了算法描述。 第7 章是算法实现，给出为了测评摹于重要度的丰题爬虫算法而设计的系统流 程、丰要的；a v a 类、最后给出了测试结果。 第2 章搜索引擎技术 本文开发的内部网信息检索系统和提出的基于重要度的丰题爬虫算法都是以搜 索引擎技术的研究为摹础的。本章重点介绍搜索引擎的简史、分类和技术，作为本 文的背景。 2 1 搜索引擎的简史 1 9 9 1 年，c e r n ( 欧洲粒予物理研究所) 的科学家t i mb e m e r s l e e 开发出了万 维网( w or i dw i d ew e b ) ，他还开发出了极其简单的浏览器。此后瓦联网开始向社会 大众普及。正是w w w 的诞牛和普及促进了搜索引擎技术的发展。 1 9 9 0 年，m c g u n i v e r s i t y 的a l a ne m t a g e 、p e t e r d e u t s c h 、b i | 1w h e e i 锄发明了 a r c h i e ( a r c h i ef a q ) 。它是第一个自动索引互联网上匿名f t p 网站文件的程序，t u 它 还不是真正的搜索引擎，因为当时因特网还未出现，可以说它是搜索引擎的祖先。 之后m l t 的m a t t h e wg b a y 开发的w o r l dw i d ew c b 、a n d e r e l 。世界上第一个专门 用于下载信息的爬虫程序，用于追踪耳联网发展规模。刚开始它只用来统计瓦联网 上的服务器数量，后来则发展为也能够捕获网址( u r l ) 。 1 9 9 3 年1 0 月m a r t j nk o s t c r 台q 建了a l l w e b ( m a r t i nk o s t e ra n n o u c e st h e a v a i l a b i l i t y o f a l i w e b ) ，它相当于a r c h i e 的h t t p 版本。a l l w e b 不使用网络爬虫， 如果网站辛能；们希望自己的网页被a l l w e b 收录，需要自己提交每一个网页的简介 索引信息。1 9 9 3 年底，一些基于此原理的搜索引擎开始纷纷涌现。 1 9 9 4 年4 月，s t 锄f o r d 两名博士牛，美籍牛人j e 叫y a n g ( 杨致远) 和d a v i df i i o 共同创办了y a h o o ! 。随着访问量和收录链接数目的增长，y a h o o ! 目录开始支持简 单的数据库搜索。因为、铀o o ! 的数据是下工输入的，所以不能真正被归为搜索引擎， 事实上只是一个可搜索的目录。搜索效率明显提高。 1 9 9 4 年4 月2 0 日，w a s h i n g t o nu n i v e r s t y 的b r i a np i n k e r t o n 等人开发的 w e b c r a w i e r 是耳联网上第个支持搜索文件全部文字的全文搜索引擎，在它之前， 用户只能通过u r l 和摘要搜索，摘要一般来自人工评论或程序自动取正文的前1 0 0 个字。 1 9 9 5 年1 2 月，a l t a v i s t a 登场亮相，大量的创新功能使它迅速到达当时搜索引 擎的顶峰。a l t a v i s t a 晟突出的优势是它的速度。同时a l t a v i s t 8 的一些新功能永远改 变了搜索引擎的定义。a l t a v i s 诅是第一个支持自然语言搜索的搜索引擎，a l t a v i s t a 是第一个实现高级搜索语法的搜索引擎( 如a n d o r ，n o t 等) 。用户可以用 a l 协v i s t a 搜索n e w s g r o u p s ( 新闻组) 的内容并从互联网上获得文章，还可以搜索图 片名称中的文字、搜索t i t l e s 、搜索j a v aa p p l e t s 、搜索a c t j v e xo b i e c t s 。a l t a v i s t a 也 声称是第一个支持用户自己向网页索引库提交或删除u r l 的搜索引擎，并能在2 4 小时内上线。 1 9 9 9 年出现的9 0 0 9 l e 。g o o g l e 在p a g e r a n k 、动态摘要、心页快照、d a i l y r e 盹s h ( 每日更新) 、多文档格式支持、地图股票词典寻人等集成搜索、多语言支持、用户 界面等功能上的革新，象a i t a v i s t a 一样，再一次永远改变了搜索引擎的定义。 之后，搜索引擎渐渐成为了可联网经济的亮点，各大公司都投入了大量的研发， 竞争激烈，据不完全统计，目前因特网上已有上百个的商用搜索0 i 擎。除了g o o g l e 之外，全球丰要的搜索引擎还有微软的m s n ，它以微软研究院强大的科研能力作支 撑；去年y a h o o ! 花了将近2 0 美元收购了i n f o s e e k 等搜索引擎公司，从而白卞研发 搜索引擎，不再使用g o o g l e 提供的技术。有技术统计显示后两者搜索引擎的功能已 经和g o o g l e 很接近。搜索引擎的设计也融合了更多技术，如数据挖掘、机器学习、 模式识别、自然语言处殚等，使之更智能、更人性化。而且搜索的领域从文字扩展 到了多媒休领域，如图像搜索，如i b m 开发m a r v e l 搜索引擎，真正地开始分析图 像，而不仅仅只是分析图像的说明文字。 在国内，1 9 9 6 年张朝阳创立的s 0 h u 公司提供了和y a h 0 01 类似的分类目录检索 服务，是中国出现的最早的提供互联网信息检索的公司；1 9 9 7 年l o 月2 9 目，“天 网”搜索引擎正式在c e r n e t 上提供查询服务受到了学术界广泛好评。2 0 0 0 年1 月，前i n f o s e e k 资深工程师李彦宏与好友徐勇归国创业，创立了百度( b a d u ) 公司， 从开始时只为其它门户网站搜狐、新浪、t o m 等提供搜索引擎技术服务到2 0 0 1 年 1 0 月2 2 日正式发布b a i d u 搜索引擎，它是目前最大的中文搜索引擎。最近国内搜 索引擎市场的竞争也趋于白热化，有y a h o o ! 收购3 7 2 l 之后建立的一搜网，高举民 族搜索旗帜的慧聪公司的中搜，s o h u 与m 1 t 多媒体实验室合作开发的搜索引擎搜 狗，新浪网白丰研发的搜索引擎等等。 搜索引擎技术也成了学术界研究的一个热点，n e c 美国研究所的s t e v e l a w r e n c e 和c l e eg i l e s1 9 9 8 年和1 9 9 9 年连续两年在自然和科学杂志上撰 文对搜索引擎技术的研究进行评述。著名的信息检索会议t r e c 也从1 9 9 8 年开始 增加了w e b t r a c k 课题，以考察w e b 文档与其它类型文档在检索性质上的不同之处， 并将测试在大规模的w e b 库上进行信息检索的算法性能。另外如i e e e 丰办的国际 万维网会议、人机交互会议也有越来越多关于搜索引擎技术研究的文章发表。此外 关于w e b 挖掘、机器学习、自然语言处理、图像技术、模式识别等领域的研究给搜 索引擎的设计提供了源源不断的理论基础。 6 2 2 搜索引擎分类 搜索引擎按其工作方式丰要可分为三种，分别是全文搜索_ i 擎( f u i l t e x ts e a r c h e n g j n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r c c t o f y ) 和元搜索引擎( m e t as e a r c h e n g i n e ) 。 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具有代表性的有g o o g l e 、 f a s 似l | t h e w e b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 。 它们都是通过从互联网上提取的各个网站的信息( 以网页文字为丰) 而建立的数据 库中，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给 用户，因此他们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索0 i 擎又可细分为两种，一种是拥有自己的检 索程序( i n d e x e r ) ，即俗称的“蜘蛛”( s p i d e r ) 程序或“机器人”( r 0 b o t ) 程序，并自 建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的7 家引擎；另 一种则是租用其他引擎的数据库，并按白定的格式排列搜索结果，如l y c o s 引擎。 l ：n 心i 。l e u j e 。嘿 v j s 如 二i 燃瓤。f 册& 。0 i 盛搿鬻 目录索引 日录索引虽然有搜索功能，仳在严格意义上算不上是真正的搜索引擎，仅仅是 按目录分类的网站链接列表而已。早期通过人工分类，后来通过对概念的特征提取、 文本分析等方法可以自动分类【1 9 】。用户完全可以不用进行关键词查询，仅靠分类 目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的y a h o o ! 。其 他著名的还有o p c n d i r c c t o 叫p 喇e c t ( d m o z ) 、l o o k s m a r t 、a b o u t 等。国内的搜狐、 新浪、网易搜索也都属于这一类。同时，通过自丰研发或使用g o o g i e 、百度等专业 搜索引擎公司的技术，这类公司大多已推出自己的全文搜索引擎系统。 元搜索引擎( m e l as 姐k he n g i n e ) 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果返 回给用户。著名的元搜索引擎有l n f o s p a c e 、d o g p i e 、v i s i m o 等，中文元搜索引擎 中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜 索结果，如d o g p i i e ，有的则按自定的规则将结果重新排列组合，如v i v i s i m o 。 2 3 搜索引擎技术简介 本文介绍的是第一种基于关键词的全文搜索引擎的技术。下面通过介绍优 秀的搜索引擎g o o g i e 的设计原型【2 】来介绍搜索引擎技术，下图是旱期9 0 0 9 l e 搜索 引擎的系统结构： 图2 1 早期g o o g i e 搜索引擎的系统结构 图2 1 所描述的g o o g l e 的设计流程是：u r ls e r v e r 传递u r l 给c r a w l e r ，c r a w l e r 根据传来的ur l 下载网页成功后，通过s t o r es e r v e r 压缩存储在r e p o s t l d f y 中。j n d e x e r 从r e p o s i t o r y 中取得网页，进行两种操作：一是通过a n c h o r 提取网页的链接给u r l s e r v e r 处理后交给c m w l e r 继续抓新的网页；二是存到b a 雌l s 中( 形式有所变化) ， 由s o r t e r 对其建索引。然后由s e a f c h e r 根据用户提交的关键词返回搜索结果，搜索 结果排名由p a g e 豫n k 计算出。 从上面可以看出搜索引擎设计中的几个关键技术： 网络爬虫技术 网络爬虫丰要完成从因特网上获取网页和超链接结构信息的工作，它丰要涉及 怎样高效地从互联网上并行采集网页，更新网页，优先下载重要网页等问题，下一 章将作重点介绍。 网页存储技术 从因特网上收集下来的网页和超链接结构信息一般保存在搜集端数据库或者是 专门的存贮文件结构中，等待网页分析部分的程序对这些数据进行分折。难点有怎 样有效地存储海量的网页数据，并提供高效检索。我们需要建立和维持一个巨大的、 并行共享的网页数据库来有效地存储、检索和更新数以亿计的网页和超链接【l l 】， 同时提供快速的随机访问和批量访问。 网页分析技术 网页分析是根据因特网上数据的特点，按照一定的算法对已经收集获得的网页 和超链接信息进行分析，从中提取和用户检索相关的网页描述信息( 如：网页标题、 网页关键词、网页的编码类型、网页的文件类型、网页大小、被其他网贞链接次数 等) ，并将提取所得的网页描述信息交给索引器建立索弓i 的过程。这个过程中通常也 进行排除相似网页的运算。 建索引技术 网页分析步骤分析所得的网页描述信息，都是从页面到页面的描述数据的正排 表。索引建立的丰要工作就是重新整理、编排这些网页描述信息，对必要的描述数 据项建立倒排表( 包括关键词到网页的倒排表、站点到网页的倒排表等) ，为提供用 户的检索功能做准备。我们需要为巨大的网页数据库建立一个并行的倒排索引，并 且在网页数据库更新时保持索引的同步更新【1o 】。 前端检索技术 前端检索用于响应用户的检索请求并跟踪用户的检索行为。当用户提交一个请 求后，前端检索部分从索0 i 倒排表中通过描述数据项得到相关的网页信息，再根据 一定的相关度算法或者是已经计算好的相关值对这些数据进行排序，然后组合输出 给用户。典型的技术是g g i e 的p a g e r 锄k 技术【2 1 。用户得到结果页面后，会对这 些结果进行一定操作( 如访问结果页面中的某一个网页) ，这些操作信息都由前端检 索部分予以跟踪，并记录在用户数据库中，以准备以后提高用户检索的质量。 9 第3 章网络爬虫技术 网络爬虫是一个从瓦联网上提取网页并保存的程序，经常是为一个搜索引擎服 务的。和它类似的程序还有s p i d e r ，w o r m ，w a n d e r c lg a t h e r e 等等，它们都称为s e a r c h e n g i n er o b o t s 2 0 。 本文丰要涉及网络爬虫的设计和丰题爬虫算法的研究，因此奉章重点介绍网络 爬虫技术。 3 1 网络爬虫的基本流程 网络爬虫程序往往是基于这样一种想法：如图3 1 所示，w w w 可以看作是一 张有向图g = ( v ，e ) 组成，v 表示网页的u r l ，e 表不两个网页之间存在的超链搂， 即一个网页中有另一个网页的u r l ，有很多文章对w w w 的图结构( 曲g r a g h ) 作了 研究【2 i 】【2 2 】【2 3 】。假设存在集合v s ，其中包含的u r l 称为种了u r l ( s e e d ) ，那么 网络爬虫的工作可以看作是从集合v s 出发，发现有向图g 中v 的过程，即图的遍 历。按照不同的访问策略，可分为深度优先遍历、宽度优先遍历【2 4 】f 2 5 】年u 最优优先 遍历。 图3 一1 w e b g m p h 程序的基本流程如下，是一个循环往复的过程： 0 1 ) 程序从几个种了ur 1 开始，它们相当于图遍历的出发顶点，这个种了ur l 通常被 称为s e e d 或m o t ，它们首先被放到ur l 对列中等待处殚。 2 ) 将待处理的ur | 按一定策略分配给下载线程。 3 )下载线程根据h t t p 等协议采集网页。 4 ) 提取网页链接，按一定策略过滤后，将新的ur | 加入到u r l 对列中等待处殚。 u 是作为搜索引擎的网络爬虫将远不止这么简单，由于百联网上网页的飞速增 长和快速变化，网络爬虫的设计面临以下难题，这同时也是爬虫技术研究剃开发的 重点。 3 2 优先采集重要网页问题 网络爬虫优先采集“重要”网页丰要基于以下几个原因：首先，由于瓦联网上网 页增长飞速，由于存储的限制，而且可能很难对所有的网页进行分析、建索引，因 此再强大的搜索引擎也只能采集部分网页。其次，c f a w i e r 采集网页需要时间，采集 亿计的网页往往要几个月的时间。因此对于需要重新访问的网页，c m w l e r 律律很难 跟上所有这些网页的变化速度，因为很多网页变化很快，将近2 5 的网页在i 天之 内变化f 7 1 。因此c r a w l e r 非常必要优先采集“重要”网页。 这是一个采集策略问题，丰要包括宽度优先、深度优先、利最优优先策略，可 参照图的遍历算法。已证明了宽度优先策略优于深度优先和随机策略【2 4 】，可以更 早地发现“熏要”网页。最优优先则是根据特定的需要而制定的策略，这就涉及到网 页重要度的计算，方法有以下几种： 1 b a c k i i n kc o u n t ( i b ( p ” 该法认为链向它的链接多的网页被认为更重要。 文献【5 】证明了该方法有聚集效应，偏向于深度优先遍历。原因是当用该重要度 作评价采集网页时，当访问到某网页，它能迅速找到个网页聚类，聚类当中的网 页相瓦指向对方，如下图3 2 所示。 图3 - 2 聚集效应 文献 2 4 】证明了宽度优先有利于优先发现丰题相关的网页。因此小适合用作丰 题爬虫算法的重要度评价指标。 2 p a g e r a n k ： p a g e r a l l k 【2 】【2 6 】【2 7 】算法的基本思想是如果网页u 有一个指向网页v 的链接， 那么网页u 隐式地传递一些“重要度”给网页v 。它是这么计算的：如果一个贞面没 有链出链接，则我们假设它对所有的网页都有个链出链接。然后，假设页面p 被 页面t 1 ，t n 所链接( 指向p ) ，令c i 是页面t i 的链出链接数，令d 是削弱因了， 那么网页p 的加权a c k l i n kc o u n t 值为：i r ( p ) = ( 1 _ d ) + d 1 r ( t 1 ) c 1 + + i r ( t n ) c n l 。 由于开始并不知道各网页的j r ( p ) 值，我们给它们都赋初值l ，然后通过迭代 计算，每次用新计算得的j r ( p ) 值代替旧的i r ( p ) 值，直到收敛，得到各网页的 p a g e m n k 值。具体计算时是通过大型稀疏链接矩阵的反复迭代相乘收敛得到。 假定用户一开始随机地访问网页集合中的一个网页，以后跟随网页的链出链接 向前浏览网页，不回退浏览，有时该用户会厌倦，随机跳到另一个网页，这样浏览 下一个网页的概率就是被浏览网页的p a g e r 卸k 值。 虽然该方法对于评价重要度有最好的效果，f u 是它的时间代价是最大的，而且 它是每次用一个大时间段同时计算出矩阵中所有网页的p a g e r a n k 值，该方法计算的 重要度往往用在搜索引擎给用户返回搜索结果的排名中，不适合用在本文丰题爬虫 算法这种实时计算重要度的环境中。 3 - 。o r w a r dl i n kc o u n t ：o f 。( p ) ) 包含链出链接数多的网页更重要，通常和其他方法配合。对于链出链接数，该 值假设包含链出链接多的网页更重要，我们看到多数重要网页都会包含很多的链按， 它往往是丰页或者目录页。显然，加上算法中对链接文本信息的分析，这种网页对 于我们寻找丰题网页是很重要的，而且该值从网页自身就能得到。因此，我们的丰 题爬虫算法采用该值作为重要度的一个度量。 4 l 眦a t i o nm e t r i c ：( i l p ) ) 通过网页的u r l 分析重要度，比如c o m 结尾比其它的更重要；包含字符h o m e 的更重要；包含垆少的更重要。对于网页u r l ，考虑ur j 中包含的v ”数( ? 号也当p 处王 i ! ) ，多数时候，少的网页比，多的网页重要，尤其在同一域名网站的网页之 间 。比如 ，我们认为网页 h 丛驻型殴盘! i 丛：鲤地墨n 焦f 比 h 娅型s p q 琏耋：i n g ：女q m ! n 鱼纽h n 曲世血盘苎! 业地! 重要，因为前者是焦点体育专题首页， 而后者是一则焦点体育新闻。对于结构好的网站，ur i 的“广数是嘲贞重要度的一个 重要指标。 如果我们的丰题爬虫只负责采集各网站丰页，则ur i 中包含i n d e x h t m ；d e f a u i t + ： h o m e h t m 等字符的网页将很重要。 分析ur i 的开销很小。无需链接信息。提取u r l 后马上可以计算。我们采用该值 作为重要度的另一个度量。 我们开发的内部网信息检索系统中采用了宽度优先策略，因为它不需要在把刚 提取出的u r l 放入下载队列前进行重要度计算，而且性能和其它方法差距不大，在 丰题爬虫中性能比其它方法还好。对于面向局域网的搜索引擎，采集的目标往往确 定，因此“性价比”最高! 而在我们更新模块的设计中则采用了简单的ur 1 分析法得到 一个大概的重要度值。 本文提出的丰题爬虫算法则结合了方法3 ( f o n v a r dl i n kc o u n t ：( i f ( p ) ) ) 和方法 4 ( l o c a t i o nm e t r i c ：( 1 l ( p ) ) ) 计算网页重要度。 3 3 网页更新问题 爬虫采集了网页后，它需要重新采集这些网页来检查这些网页是否发牛了变化， 然后更新网页数据库。因为网页各自变化的频率往往很不同，爬虫必须随时决定碰 到的网页当中哪些网页需要重新采集而哪些网页需要跳过来保持最好的刷新率。对 于搜索引擎来说，如果没有跟上网页的变化，那么索0 l 数据库中存放的还是旧的索 引，这样的索引就会产牛误导的搜索结果；再或者，已经被删除的网页没有及时发 现，搜索结果中将返回死链接。 更新问题的中心思想是根据网页的变化频率确定更新网页的策略，为的是在现 有系统性能条件下尽量保持和网页的变化同步，否则会产牛返回的搜索结果包含死 链接和不相关网页等情况。更新问题是本文设计网络爬虫时遇到的丰要难题， s t a n f o r dw 曲b 嬲ep m j e c t 对更新问题作了系统的研究，文献【2 8 】研究了中国网站变化 的情况。下面将从网页变化研究、网页变化频率测量和更新策略三个方面加以刚述。 我们内部网信息检索系统爬虫模块更新策略的设计应用了这些研究并结合实际进行 了创新。 3 3 1 网页变化研究 网页是有牛命周期的，它表示网页存在的时问。 文献【7 】通过对网页的变化进行测试，结果如下： ijc n 】、r | le 1 n j l b 图3 - 3 网页变化频率的分布 上图中( a ) 图表示在某个时间间隔内网页发牛变化的比例，( b ) 图表示各种类 型网站网页在各时间间隔内发牛变化的比例。我们从中可以看到2 3 的网页在】天 之内就发生了变化，而在所有类型的网站中，c o m 网站变化最快，4 0 以上在l 天 之内变化，因此追踪这些变化对搜索弓l 擎来说是必要的。 而且还发现网页变化的概率分布服从泊松分布，如下图3 4 所示： i n ) o v p l 川lt 1 i ) m 嘶3 图3 - 4 网页变化的泊松分布 该图x 轴表天数，y 轴表期间未变化的网页比例。 泊松过程常常用来对一些以一定频率独立发牛的事件建模。例如意外事故的发 生，要求服务的顾客到达服务站等。 设x ( t ) 表示在时间间隔( o ，t j 内某个时间出现的次数，如果事件以一定同定的平 均速度九独立、随机的发牛，我们称之为频率为九的泊松过程。给定一频率为x 的泊松 过程，t 是下次事件发牛的时间，那么t 的概率密度函数是： 棚，= k 掣 b ” 根据上式我们可以计算出某个网页p 在时间( 0 ，t ) 内变化的概率： p ( e ) = p 丁，) = 胁( f ) 馥= 3 3 2 网页变化频率的计算 o ( 3 2 ) 我们首先需要测定网页的变化频率，这当中的难点有：网页变化的历史不完整， 访问网页的时问间隔往往无规律，各网页自身提供的信息有时会不同。对网页变化 频率的测量可分为以下几种情况f 6 】 2 9 】： 1 当用固定访问频率去访问网页时： 假设n 表示对网页的更新次数，x 表示检查出改变的次数；r 是网页变化频枣 和更新网页频率的比值。我们很直观地得到下式： r = x n ：( 3 3 ) 事实上，我们不一定捕捉到每次网页的变化可能在两次访问网页的时间间隔 内，网页变化了两次，而我们只检测到了一次。文献f 6 】通过下式减少测量的误差： 一l o g ( 湍) 2 当不以固定访问频率访问网页时，通过下式计算网页变化频率 ( 3 - 4 ) 上式中，t 。i 表示我们检测到网页第i 次变化时的时间间隔，t u j 表示我们第j 次没检测到网页变化的时间间隔，m 表示我们在经过n 次访问时检测到网页变化的 次数，x 是网页变化频率，我们能够通过解该方程式求九。 “ p一 = 出 m k。 一 = ；一一上扣m 3 贝叶斯分类法 有时c r a w i e r 访问网页的频率固定地分为几类，此时我们玎i 需要知道确切的网 页变化频牢，只需要知道当本次访问网页时是否变化，然后根据贝叶斯分类法确定 它属于哪个类的概率最大，然后将其放到这个类中，举例如下： 假设c r a w l e r 变化网页时只分两种情况：每月完全更新网页一次和小部分网页 每周更新一次。那么我们不会关心一张网页的变化频率是7 天一次还是l o 天一次， 我们只关心根据网页的变化历史，该网页应该放在哪个更新的类中，即是放在每周 更新次的网页类( c 。) 中还是每月更新一次的网页类( c 。) 中，令p p c 。 和p p c 。) 分别代表网页属于两个类的概率。 开始时，我们没有任何网页“该如何更新的信息，因此，我们假设 p p g 2 p p 巳) 。o 5 。 假设5 天后c m w i e r 访问p ，发现p 变了，这里我们用e 代表网页发牛变化事件 f 代表网页没有变化事件，那么根据朴素贝叶斯分类方法，p 属于每周变化一次的类 的概率计算如下： 尸t psc 。ie ，= j i i t ；i 石_ 丢姜暑! ；：；j ；j ；i ：；i ；丽c 。_ s ， 因为网页的变化概率服从泊松分布，公式中p ei p c 。 表示当该网页在每周 访问次的类中时，网页p 在5 天内发牛变化的概率，根据公式( 2 ) ，得出概率为 1 一p 5 ”，前面我们已经假设了p p c 。 = p p c 。) = o 5 ，因而 砌酣朋 = 正式篙地， 尸 p e c 。i e ) = i i 二i j i j ；a 。z 。 显然，p p c 。1 e ) p p c 。l e ) - 根据贝叶斯分类，p 属于c 。类。 如果5 天后c r a w i e r 发现p 没变，此时，公式( 6 ) 中的事件e 由f 替代，p f i p c 。) 表示当该网页在每周访问一次的类中时，网页p 在5 天内不变的概率，为概率为l 一 ( 1 p “7 ) = p “7 ，因而 p p c 。l ，) = i 孑j i i i ；* 0 3 ， 尸 p 巴i ， = i 乒玎弓；蔫m 。s 。 6 显然，p 尸e e p p c 。j e ，根据贝叶斯分类，p 属于巳类。 从编程的角度看崩不等时间间隔更新网页时，网页变化频率的计算公式( 3 5 ) 不大容易实玑；而文献 7 通过实验显示贝叶斯分类法只有在更新网页频牢处于两个 类的更新频率之间时才能达到好的效果。因此应用等间隔时间更新网页