（计算机应用技术专业论文）面向技术信息领域垂直搜索引擎的设计与实现.pdf

中文摘要 随着网络信息资源呈几何级数增长，使用搜索引擎准确、快速的查找所需信 息也变得越来越困难。主要原因有两个，一是传统的搜索引擎很难将所有的网络 资源全都覆盖，做到面面俱到；二是查询结果通常都是成千上万条，真正有用的 少量信息隐藏其中，让用户难以发现。垂直搜索引擎的应运而生，成为搜索引擎 发展史上的一块里程碑。 本文旨在研究垂直搜索引擎基本原理和架构，并实现一个面向技术信息领域 的垂直搜索引擎，包括用于垂直搜索的网络爬行器技术，基于超链接的半结构化 网页的挖掘，倒排索引及全文检索的实现等。主要分为四大方面的工作：1 桌面 元搜索程序的实现，用于采集领域相关的网站网址；2 垂直搜索引擎爬行器的设 计和实现。该爬行器和通用爬行器不同，首先它是领域相关的，只爬行领域相关 的网页。另外，通过对超链接的分析，该爬行器选择爬行具有一定规范结构的网 页，并进行自动分类，便于后续步骤的处理；3 网页的过滤及结构化信息的抽取。 将爬行器所抓取的网页进行进一步的过滤，按字段提取其有效信息，将所有这些 信息以x m l 形式存储在本地硬盘；4 倒排索引的建立以及检索接口的实现。寻找 高效的数据结构建立倒排索引，以缩短索引建立时间和查询所需时间，系统支持 各检索词之间的与或非等基本逻辑关系的组合查询以满足用户的高级检索需求， 实现了实时反馈机制以使用户更快速的找到所需信息。 技术信息所涵盖范围甚广，涉及到各个行业，有着很大的用户需求。本课题 所开发的垂直搜索引擎将为用户提供全面而确切的相关信息，帮助用户不断迎接 新挑战，抢占发展先机，做出正确决策。 关键词：爬行器搜索引擎垂直搜索反馈机制 a b s t r a c t w i t ht h eg e o m e t r i c a l l yi n c r e a s i n go fn e t w o r ki n f o r m a t i o nr e s o u r c e s i th a s b e c o m em o r ed i f f i c u l tt of i n dt h er e q u i r e di n f o r m a t i o na c c u r a t e l ya n dr a p i d l yb y u s i n g s e a r c he n g i n e ，g e n e r a l l yf o rt w or e a s o n s f i r s t ，i ti sd i f f i c u l tf o rt h et r a d i t i o n a ls e a r c h e n g i n et oc o v e ra l lt h en e t w o r kr e s o u r c e s ，a n ds e c o n d ，t h es e a r c hr e s u l t su s u a l l ya r e t h o u s a n d su p o nt h o u s a n d s ，s ou s e rc a n n o tf i n dt h er i g h ti n f o r m a t i o nw h i c hi sh i d d e n i nt h e m t h ee m e r g e n c eo ft h ev e r t i c a ls e a r c he n g i n eb e c o m e sam i l e s t o n eo ft h e h i s t o r yo fs e a r c he n g i n e t h i sp a p e ri n t r o d u c e st h eb a s i ct h e o r ya n da r c h i t e c t u r eo ft h ev e r t i c a ls e a r c h e n g i n ea n dp r e s e n t sav e r t i c a ls e a r c he n g i n eo ft e c h n o l o g yi n f o r m a t i o nd o m a i n o r i e n t e d i ti n v o l v e sw e bc r a w l e rt e c h n o l o g yf o rv e r t i c a ls e a r c he n g i n e ，d a t am i n i go f s e m i s t r u c t u r e dw e bb a s e do nt h eh y p e r l i n k ，t h ei m p l e m e n t a t i o no fi n v e r t e di n d e x i n g a n df u l l t e x ts e a r c h t h ew o r kc a nb ed i v i d e di n t of o u ra s p e c t s ：1 i m p l e m e n ta d e s k t o pm e t a s e a r c hp r o g r a mw h i c hi su s e dt og e tt h ed o m a i nr e l a t e dw e b s i t e su r l 2 t h ed e s i g na n di m p l e m e n t a t i o no fw e bc r a w l e rf o rv e r t i c a ls e a r c he n g i n e t h i s c r a w l e ri sd i f f e r e n tf r o mt h eu s u a lo n e f i r s t ，i ti sd o m a i nr e l a t e da n do n l yc r a w l st h e d o m a i nr e l a t e dw e b s a n d t h e n ，b ya n a l y z i n gt h eh y p e r l i n k s ，t h ec r a w l e rc a t c h e sa n d a u t o m a t i c a l l yc l a s s i f i e st h en o r m a ls t r u c t u r e dw e b sw h i c hw i l lb ep r o c e s s e db yt h e s u b s e q u e n ts t e p s 3 w e bf i l t e r i n ga n ds t r u c t u r e di n f o r m a t i o ne x t r a c t i o n f i l t e rt h e w e bp a g e so b t a i n e db yt h ec r a w l e r , e x t r a c tt h eu s e f u li n f o r m a t i o na c c o r d i n gt ot h e f i e l d ，a n dt h e ns a v et h ei n f o r m a t i o nt ot h el o c a ld i s ki nt h ef o r mo fx m l 4 i n v e r t e d i n d e xe s t a b l i s h m e n ta n dt h ei m p l e m e n t a t i o no fr e t r i e v a li n t e r f a c e t h eg o a li st of i n d e f f i c i e n td a t as t r u c t u r et oe s t a b l i s hi n v e r t e di n d e xi no r d e rt os h o r t e nt h et i m eo fi n d e x a n dq u e r y t h es y s t e ms u p p o r t st h ec o m b i n a t i o no fb a s i cq u e r yl o g i ci no r d e rt om e e t u s e r sd e m a n df o ra d v a n c e dr e t r i e v a la n dr e a l t i m ef e e d b a c km e c h a n i s mw h i c ha l l o w u s e r sf a s t e ra c c e s st ot h ei n f o r m a t i o nt h e yn e e d t e c h n i c a li n f o r m a t i o nc o v e r e saw i d es c o p ea n di n v o l v e sa l ls e c t o r s ，s oi ti s s t r o n g l yn e e d e db ym a n yu s e r s t h ev e r t i c a ls e a r c he n g i n es y s t e mw ep r o p o s e dw i l l p r o v i d eu s e r sw i t hc o m p r e h e n s i v ea n da c c u r a t ei n f o r m a t i o nw h i c hc a nh e l pu s e r s c o n s t a n t l ym e e tn e wc h a l l e n g e s ，s e i z et h ed e v e l o p m e n to p p o r t u n i t ya n dm a k ea c o r r e c td e c i s i o n k e yw o r d s ：c r a w l e r , s e a r c he n g i n e ，v e r t i c a ls e a r c h ，f e e d b a c k 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：侮亥 签字日期： 2 d 。7年6 月1 日 学位论文版权使用授权书 本学位论文作者完全了解：基鲞蠢堂有关保留、使用学位论文的规定。 特授权拳鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：偬苏岘 签字日期：2 d p 年6 月j7e t 导师签名：1 g - - 至蕊 签字日期：2 卯7 年易月j 7 日 第一章绪论 1 1 搜索引擎概述 第一章绪论 随着计算机技术和互联网技术的飞速发展，网络上的信息量也急剧增加，现 在已经成为了人类有史以来资源数量最多，种类最全，规模最大的一个综合信息 库。其信息来源丰富，分布广泛，更新频率快，5 0 的网页平均生命周期大约为 5 0 天”】。那么，如何在互联网这个浩瀚的信息海洋中及时、准确的找到所需要的 信息? 搜索引擎便是承担这个任务的重要工具。据c n n i c2 0 0 6 年7 月公布的第 十八次中国互联网络发展统计报告【2 】于旨出，中国网民中有6 6 3 的人使用搜索引 擎，这个数字已经超过使用电子邮件的人数，使搜索引擎成为网民最常使用的网 络服务。另有调查显示【3 1 ，仅2 0 0 6 年7 月份美国网民在6 0 个搜索引擎网站中总 共进行了约5 6 亿次搜索。很难给搜索引擎下一个明确的定义，一般认为，搜索 引擎是一种用于帮助互联网用户查询信息的搜索工具，它以一定的策略在互联网 上搜集信息，对信息进行处理、存储，为其建立相应索引，并为用户提供检索服 务，从而达到信息导航的目的。 1 2 搜索引擎的发展 早在w e b 出现之前，互联网上便已经存在了许多供人们共享的信息资源了。 这些资源以学术内容及研究性软件居多，它们分布在各个可以匿名访问的f t p 站点上，那时还没有h t m l ，文件通常以纯文本或二进制的方式存储在各站点的 本地硬盘上。为了便于人们在分散的f t p 资源中寻找所需的东西，加拿大麦吉 尔大学( m c g i l lu n i v e r s i t y ) 学生a l a ne m t a g e 于1 9 9 0 年发明了a r c h i e 。a r c h i e 的工作原理与现在的搜索引擎已经颇为接近，它依靠程序自动获取各个f t p 站 点上的文件信息，包括这些资源的文件名、文件长度、创建时间以及所处目录等， 然后对这些信息建立索引，供使用者以一定的方式查询。截止到2 0 0 6 年，i n t e m e t 上约有3 0 多个a r c h i e 服务器，覆盖了遍布在1 2 0 0 个f t p 服务器中的2 0 0 多万 个文件。用户可以使用t e l n e t 或a r c h i e 的客户端程序在l i n u x 系统、u n i x 系统、 m i c r o s o f tw i n d o w s 系统和m a c 系统中访问a i c h i e 服务器以寻找文件。 1 9 9 4 年4 月，斯坦福大学( s t a n f o r du n i v e r s i t y ) 两名博士生，美籍华人杨 第一章绪论 致远和d a v i df i l o 共同创办了y a h o o 。随着访问量和收录超链接数的增长，y a h o o 目录开始支持简单的数据库搜索。因为当时y a h o o 的数据是手工输入的，所以不 能真正被归为搜索引擎，事实上只是一个可搜索的目录，然而查找资源效率明显 提高，使得搜索的概念深入人心，这是y a h o o 对搜索引擎发展的重要贡献。之后 y a h o o 陆续使用a l t a v i s t a 、i n k t o m i 、g o o g l e 提供搜索引擎服务，直到近年来才 开发自己的搜索引擎系统。 现代意义上的w e b 搜索引擎最早出现在1 9 9 4 年7 月。当时卡耐基梅隆大学 ( c a r n e g i em e l l o nu n i v e r s i t y ) 的m i c h a e lm a u l d i n 将j o h nl e a v i t t 的网络爬行器程 序接入到其索引程序中，创建了l y c o s 。除了网页相关性排序外，l y c o s 还提供 了前缀匹配和字符相近限制，并第一个在搜索结果中使用了网页的自动摘要。时 至今日，l y c o s 已发展成了一个门户网站，整合了大量在线服务和其它互联网工 具，其已放弃自己的网页索引数据库，转而使用a s k c o m 的索引数据库，提供网 页、本地、人物、购物、图片和视频搜索等搜索服务。 d e c 公司的a l t a v i s t a 是一个迟到者，1 9 9 5 年1 2 月才登场亮相，但是，大 量的创新功能使它迅速到达当时搜索引擎的顶峰。a l t a v i s t a 最突出的优势是它的 速度，这主要是依靠d e ca l p h a 芯片的强大运算能力。而a l t a v i s t a 的另一些新 功能，则对搜索引擎的发展产生了深远影响。它是第一个支持自然语言搜索的搜 索引擎，是第一个实现高级搜索语法的搜索引擎，也是第一个支持用户自己向网 页索引库提交或删除u r l 的搜索引擎。用户可以用a l t a v i s t a 搜索新闻组的内容 并从互联网上获得文章，搜索图片名称中的文字、搜索网页中的标题、搜索j a v a a p p l e t s 、搜索a c t i v e xo b j e c t s ，还能搜索含有指向某个网址的链接的网站。在用 户界面上，a l t a v i s t a 也作了大量革新。它在搜索框下放了经常更新的“t i p s ”以 帮助用户更好的表达要搜索的内容。如今，其仍然是互联网上重要的搜索引擎之 一，支持多语言的网页、新闻、图片、音频和视频的搜索。 随着w e b 上信息资源的爆炸性增长，搜索引擎的应用价值也越来越高，不 断有更快更强的搜索引擎系统提出。当代搜索引擎技术的杰出代表g o o g l e 发布 于1 9 9 8 年1 0 月，之前它只是s t a n f o r d 大学的一个小项目b a c k r u b 。g o o g l e 在网 页排序、动态摘要、网页快照、每日自动更新、多文档格式支持、词典、地图、 股票、学术搜索、桌面搜索，多语言支持、用户界面等功能上有很大发展，其索 引的信息量大，更新、查询速度快，并利用基于对网页问超链接进行分析的 p a g e r a n k 算法有效的改善了网页排序的效果，对搜索引擎技术的发展起了重要 的作用。 中文搜索引擎虽然起步较晚，但近几年发展迅速。由北大计算机系网络与分 布式系统研究室开发的天网搜索引擎于1 9 9 7 年1 0 月正式在c e r n e t 上提供服 第一章绪论 务。2 0 0 0 年初天网搜索引擎新课题组成立，由国家9 7 3 重点基础研究发展规划 项目基金资助开发，利用教育网优势，收录网页约6 0 0 0 万，提供强大的f t p 搜 索功能。2 0 0 1 年1 0 月百度搜索引擎正式发布，凭借其特有的超链分析技术的优 势，迅速占领市场，成为当今国内访问量最大的商业搜索引擎，其特色还包括： 网页快照、相关搜索词提示、错别字纠正提示、新闻搜索、视频搜索、图书搜索、 大学搜索和文档搜索等。在此之后中搜，搜狗搜索，爱问搜索也相继发布，进一 步加剧了搜索引擎市场的竞争，也推动了技术的进步。 1 3 垂直搜索引擎研究现状 随着网络信息资源呈几何级数增长，使用搜索引擎准确、快速的查找所需信 息也变得越来越困难【4 】【5 1 。主要原因有两个，一是传统的搜索引擎很难将所有的 网络资源全都覆盖，做到面面俱到。据估计，目前整个互联网上的网页数量已经 高达2 0 0 0 亿，最好的搜索引擎由于硬件条件和技术的限制也只能抓取不到十分 之一，并且平均更新周期近一月( 如搜狗搜索引擎索引了1 0 0 亿网页，以每天5 亿的速度进行更新) ，而w e b 的更新却是目新月异，n m u l a s 等人的研究【6 】表明：新 网页在以每周增加8 的速度出现，而网页之间的超链接结构更是变化迅速，每 周的更新率达到2 5 ，一年之后网页之间有8 0 的链接被新链接取代。二是查 询结果通常都是成千上万条，真正有用的少量信息隐藏其中，让用户难以发现。 针对这种情况，分类更细致，数据更全面深入的垂直搜索引擎出现了，成为搜索 引擎发展史上的一块里程碑。垂直搜索引擎是针对某一个行业、某一个主题的专 业搜索引擎，是搜索引擎的细分和延伸，是对网页库中的某类专门信息进行整合， 分字段抽取出需要的数据再以某种形式返回给用户。它收录的是某一行业、某一 主题的信息，因此较传统的搜索引擎门户更有针对性【_ 7 】【8 】( 9 】。这类搜索引擎运用 了特征抽取等智能化策略以及一定的人工分类方法，针对某类信息提供了更简 洁、更快速、更可靠的服务，搜索结果更加准确有效。本文介绍的面向技术信息 领域的垂直搜索引擎即属于此类。 垂直搜索引擎和普通的网页搜索引擎( 也叫水平搜索引擎) 的最大区别是对 网页信息进行了结构化信息抽取，也就是将网页的非结构化数据抽取成特定的结 构化信息数据，好比网页搜索是以网页为最小单位，而垂直搜索是以结构化数据 为最小单位。将这些数据存储到数据库，进行进一步的加工处理，最后分词、索 引再以搜索的方式满足用户的查询需求。 垂直搜索引擎虽然索引的数据量不如通用搜索引擎大，但某些技术层面的要 求反而要高一些。其大体上需要这些技术： 第一章绪论 1 网页采集即网络爬行器技术。 2 网页结构化信息抽取技术或元数据采集技术。 3 分词，索引技术。 4 检索，排序以及其他信息处理技术。 当前垂直搜索引擎发展非常迅速，出现了b l o g 搜索、求职搜索、旅游资讯 搜索、比较购物搜索、住房搜索等，国外目前比较成功的如b l o g 搜索领域的 i c e r o c k e t c o m ，t e c h n o r a t i c o r n ，求职搜索i n d e e d ，国内的论坛搜索如大旗搜索， 生活信息搜索如酷讯，但涉及的领域还不是很全面，在从海量网页信息中获取结 构化信息方面也存在诸多问题，如在抽取的效率和准确率上还有待提高。 1 4 课题意义及本文主要研究内容 本课题基于天津市科技发展计划：面向领域的智能中文搜索引擎 ( 0 4 3 1 0 9 4 1 r ) 。技术信息所涵盖范围甚广，涉及到各个行业，有着很大的用户 需求。本文详细地介绍了搜索引擎的组成结构，工作原理及流程，并给出了一个 为网页评分的概率模型。进一步介绍了垂直搜索引擎的相关概念和特点，用c 编程语言实现了一个面向技术信息领域的垂直搜索引擎。该系统自动抓取并索引 了大量技术需求、技术转让、资金找项目和项目找资金信息，在用户进行搜索时， 以统一样式的页面返回给用户。本课题所开发的垂直搜索引擎将为用户提供全面 而确切的相关信息，帮助用户不断迎接新挑战，抢占发展先机，做出正确决策。 具体各章安排如下： 第二章重点阐述用于垂直搜索引擎的网络爬行器的设计方法，包括整体框架 的可选方案，垂直内容的采集及分类，以及爬行器在抓取网页过程中应注意的问 题和应遵循的规则如i 也p ( r o b o te x c l u s i o np r o t o c a l ) ，并给出了用于主题网站获 取的桌面元搜索引擎设计思路，阐述了经典的定题采集的f i s h s e a r c h 算法【1o j 【1 ， 并对s h a r k s e a r c h 算法【1 2 】进行了一定的改进，引入了对超链接类型的进一步分析， 将其具体实现集成到了所设计的网络爬行器中。 第三章结合通用搜索引擎索引和搜索的一般原理，阐释了面向技术信息领域 的垂直搜索引擎系统对原始网页数据的处理方法，设计了一个基于规则的信息抽 取器对半结构化的网页进行信息抽取，对索引相关的数据结构进行了详细的说 明。在对搜索结果处理方面，详细介绍了结果排序所采用的方法：传统的基于 t f i d f 的方法结合在p a g e r a n k 的随机冲浪模型基础上改进的一种不依赖于查询 词的基于超链接的网页评分概率模型。另外，鉴于传统用户查询反馈机制的不足， 提出了用户查询的实时反馈机制，以更好地帮助用户尽快找到所需要的信息。 第一章绪论 第四章具体介绍整个系统的软件实现，编程采用c 群语言并结合网页设计的 h t m l 语言以及j a v a s c r i p t 脚本语言，为了进一步提升用户的搜索体验，在本系 统中引入了a t l a s 和a j a x 技术实现用户查询辅助功能和实时反馈功能。最后， 给出了相关的实验方案测试本系统的索引建立速度以及搜索速度，同时计算出系 统的查全率、准确率，与通用搜索引擎框架l u c e n e 建立的系统进行了比较，另 外对于实时反馈机制引入后带来的效果也给出了评测。 第五章为全文的总结，概括介绍了所做的工作，提出了本系统中存在的不足， 以及对今后搜索引擎技术发展做了展望。 第二章网络爬行器的设计 第二章网络爬行器的设计 网络爬行器是一种专业化的机器人程序，用于在i n t e m e t 上查找并下载大量 的w e b 页面。程序事先只被给予少数u r l 作为查找的初始点，通过这些u r l 对应页面的内容获取下一个页面的链接，进而访问下一个页面。正是通过这种程 序，g o o g l e 等搜索引擎才得以将i n t e r n e t 上数以十亿计的网页存储到本地数据库， 并建立索引，供互联网用户查询。 2 1 网络爬行器框架 网络爬行器通过使用h t t p 协议来下载网页数据。h t t p ( h y p e rt e x tt r a n s f e r p r o t o c 0 1 ) 是超文本传输协议的缩写，文献【1 3 】对超文本有个简单的定义：具有活 动的交叉链接并且允许读者从一部分内容跳到另一部分的文本信息结点的数据 库。h t t p 是t c p i p 网络模型应用层的一个重要协议，用于传送w e b 形式的超文 本数据，在r f c l 9 4 5 和r f c 2 6 1 6 中分别定义了h t t p l 0 和h t t p l 1 版本【14 l 。h t t p 协议采用了请求响应模型。客户端向服务器发送一个请求，请求包含请求头和 请求内容，请求头包含请求的方法、u 、协议版本、客户信息，而请求内容根 据请求方法的不同或有或无。服务器以一个状态行作为响应，响应的内容包括消 息协议的版本，成功或者错误编码加上包含服务器信息、实体元信息以及可能的 实体内容。 通常，网络爬行器的设计要遵守r e p ( r o b o te x c l u s i o np r o t o c 0 1 ) 即拒绝机 器人协议。网站的管理员有时并不想让自己的某些网页被爬行器获取，并建立索 引出现在某个搜索引擎中供人们搜索从而被广泛关注，这就需要某种机制来明确 告知网络爬行器哪些网页是被允许下载的。r e p 协议就是这样的一种机制。网站 管理员按照约定的格式为自己的站点制作一个r o b o t s t x t 文件，并将其置于站点的 项级目录中，这样访问该站点的网络爬行器首先下载这个r o b o t s t x t 文件，并根据 其中的要求选择抓取被允许访问的页面。之后，网络爬行器分析网页的h t m l 代 码，查找网页中所含有的超文本链接( h y p e r t e x tl i n k ) ，这种链接通常通过属性 h r e f ( h y p e r t e x tr e f e r e n c e ) 来标注。如 天津大学 ，这里网络爬行器仅仅关注h r e f 属性所对应的 值，其它的则忽略。根据h r e f 所包含的数据，爬行器会遇到三种链接。内部链 第二章网络爬行器的设计 接指向的网页与包含该链接的网页在同一台w 曲服务器中。外部链接指向的网页 所在的w e b 站点与包含该链接的w e b 网页所在站点不同。另外第三类链接，即其 他链接，它指向非网页的资源。在获取网页中新的链接后，爬行器将继续沿着新 链接下载网页。构造爬行器可以采用递归结构和列表结构。 2 1 1 递归结构 构造爬行器的一种方式是设计为递归的程序。将互联网上的所有网页看成一 个巨大的连通图，每个网页代表图的结点，网页之间的链接代表图的边，那么递 归形式的爬行器采取的爬行策略即是深度优先的图搜索策略。递归形式的爬行器 通常可以设计为如下结构： v o i dr e c u r s i v e s p i d e r ( s t r i n gu r l ) d o w n l o a dw e b sa c c o r d i n gt ot h eu r l p a r s et h eh t m l t og e tu r l sl i s t d os o m e t h i n go nh t m l ，s u c ha ss a v et h e mt ot h el o c a lf i l e f o r e a c h ( s t r i n gt e m p u r li nl i s t ) r e c u r s i v e s p i d e r ( t e m p u r l ) ； ) 上述代码中，r e c u r s i v e s p i d e r 用来抓取u r l 所对应网页，并从获得的h t m l 代码中解析出新的超链接，之后调用程序本身继续处理。由于递归程序本身的特 点，在运行时会把每次递归的信息( 如返回地址和相关参数) 压入堆栈，这样当 递归的程序很深时，堆栈会变得非常大，可能会耗尽整个堆栈内存而造成程序的 中止。所以这类爬行器只有在抓取的网页深度比较小时或者限制抓取的深度时才 是一个合理的方案，如任凭其在网上蔓延抓取，则程序必定会崩溃。 2 1 2 列表结构 构造一种非递归的网络爬行器的方法是维护一个网址列表。当爬行器发现新 的链接时，将这个链接加入到列表中，而当爬行器处理完当前的页面，则从列表 中获取尚未访问的下一个链接。程序不断循环访问该列表，直到列表中所有网页 都被抓取后停止。根据链接加入到列表的方式不同，采用的图搜索策略也不同。 当每次获得的链接都加入到列表头时，其爬行策略是图的深度优先搜索；当链接 被加入到列表的尾部时，其爬行策略则是图的宽度优先搜索。通常采用深度优先 搜索策略效果要好于宽度优先搜索【15 1 ，只有网页数量比较少，抓取时问比较短时， 宽度优先搜索效果好于深度优先搜索，且更容易发现高质量的网页【1 6 j 【l7 | 。这种 第二章网络爬行器的设计 设计方式很适合实现多线程编程，各线程之间共享的网页列表可以用哈希表来实 现。哈希表的k e y 是s t r i n g 类型的u r l ，而其v a l u e 则表示该链接处于等待，运行， 完成，错误状态中的一种，可以简单的用i n t 型的1 ，2 ，3 ，4 来表示。各状态间 的转换关系如图2 - 1 所示： 图2 1u r l 的状态转换关系图 爬行器会不断重复类似的工作，每次从哈希表中取得一个v a l u e 值为1 的超 链接，将其状态设为2 表示处理中，若有新的链接贝j j ) j n 入到哈希表，v a l u e 值为 1 ，当此页处理完毕后，根据处理结果将其状态设为3 或4 。爬行器直到哈希表 中没有v a l u e 为1 的项才终止，这样哈希表中的所有项最终的v a l u e 或者是3 或 者是4 。此类爬行器的典型流程图如图2 2 所示： 第二章网络爬行器的设计 图2 2网络爬行器的典型流程图 2 2 垂直搜索引擎的网页采集技术 垂直搜索引擎的网络爬行器和通用的爬行器相比更加专业，可定制化、可定 向地采集和垂直搜索领域相关的网页1 8 】【1 9 】，忽略不相关的网页和不必要的网页， 选择内容相关的以及适合做进一步处理的网页进行深度优先采集，对页面有选择 的调整采集频率。采集过程可通过人工设定初始网址和网页分析获取网址方式共 第二章网络爬行器的设计 同进行。本文所阐述的爬行器通过引入元搜索程序，以获得相关主题网站网址， 再辅以人为添加主题网站链接，按这些初始u r l 进行网页抓取并自动分类存储， 达到了较好的网页信息获取效果。 2 2 1 定题搜索的爬行算法 f i s h s e a r c h 算法是早期网页定题爬取的经典算法。该算法将w e b 网页爬取 的过程看作是鱼群觅食的过程。每个u r l 代表一条鱼，每个网页代表食物，鱼 群移动寻找食物并繁殖，子代鱼群的数量很大程度上依赖于找到的食物的数量。 每读取一个网页文档，鱼就繁殖一定数量的后代。文档与主题相关时，鱼就产生 更多后代：不相关时，产生较少的后代，并且活动能力也减弱。若沿某一方向， 鱼经过几条链接仍没有找到相关文档，则会被饿死。若一条鱼读取文档时间太长， 则说明鱼进入污染区，那么停止此方向的网页抓取。 该算法基于这样的假设：主题相关的网页通常聚集在一起，换句话说它们之 间存在链接。这个假设在文献【2 0 】中得到了很好的实验证明，该文验证了有链接关 系的网页比随机网页有高得多的相关度，而且链接文本、链接上下文、标题等和 网页也有很高的相关度。 f i s h s e a r c h 算法有几个重要的参数： w i d t h ：可以看作是鱼产生子代的数量。有些网页包含有很多个超链接，沿着 所有超链接进行抓取将消耗较长的时间，延缓对直接相关的主题网页的抓取。所 以设w i d t h 为从一个网页中选取的最大链接数。若当前网页与主题相关时，可以 适当增大w i d t h 值，多选取一些链接，因为这些主题相关的结点通常都是聚集在 一起的。 d e p t h ：网络上含有大量的不同主题的信息，很可能在一个方向上搜索了相 当长一段时问后仍然没有发现相关的网页，为了避免这种情况，用d e p t h 来限制 从当前结点开始跟踪的链接数。当发现相关网页时，可以适当增加d e p t h 的值， 否则对于每个网页d e p t h 值递减。这个值可以看作是鱼在没有食物的情况下的生 存时间。 r a t e ：用来表示访问某网站的速率( 单位：b y t e s s e c ) 。算法倾向于访问外部 链接指向的网站中访问速率较高的网站。访问速率慢的网站意味着是被污染的水 源，鱼在这里后代少而且生存周期短。 f i s h s e a r c h 工作机制如下： 1 初始化一个列表，将搜索的开始结点加入到列表中。结点信息包括u r l 、 d e p t h 、f l a g ，其中f l a g 取值为1 或0 ，1 代表此u r l 为相关结点的子代， 0 代表此u r l 为不相关结点的子代。从列表中取出结点，抓取其所对应 第二章网络爬行器的设计 的网页。 2 分析当前结点页面内容，根据网页是否含有指定的主题信息来判断网页 是否相关，并且将网页中所含的超链接抽取出来。 3 若当前结点d e p t h 小于0 ，则抓取停止。否则，对于这些超链接： 如果当前结点与主题相关，那么取d 木w i d t h 个子节点( d 暂取为1 5 ) ， 将其f l a g 设为1 ，d e p t h 设为一个常数值d ( 此为初始网页的d e p t h 值) ，加入n y d 表前端。如果当前结点与主题无关，那么取w i d t h 个 子节点，将它们的f l a g 值设为0 ，d e p t h 设为当前结点的d e p t h 一1 ， 加入到列表中t t a g 为1 的结点后面。 没有被选中的结点被加到列表的尾部。 超链接的选则并不是完全随机的：指向其它网站的链接优先被选中， 这就使得抓取范围的分布更趋广泛。 对于选中的链接，如果列表中已经存在，且新链接将被插在列表的 头部，并优先于旧链接被处理时，则删除旧链接所对应结点，将新 链接结点加入到列表。否则不加入新结点，修改旧结点的d e p t h 值使 其为新旧结点d e p t h 值中的较大值。 4 在列表中查找指向与当前网页所处网站不同的网站的超链接结点。如果 这个链接在列表的前3 木w i d t h 范围内，将其从列表中移除，抓取该链接 所对应网页内容；如果不在这个范围内，则移除列表中的第一个链接， 抓取其对应的网页，记录下这次抓取的数据传输率并更新这个站点的平 均传输率。新抓取的结点成为当前结点，算法执行转到步骤2 。 5 当列表为空或指定抓取网页的数量、抓取时间到时，算法结束。 该算法取得了很好的定题采集效果，集成到了当时的m o s a i c 浏览器中，但 它也存在这一些明显的不足： 1 它只是粗略的将网页分为相关和不相关，进而指定其所含链接要抓取的 优先程度为1 或0 ，并没有对其所含链接所指网页内容与主题的相关程 度进行进一步的细分。 2 对于判断当前网页与主题相关与否，仅通过查找网页中是否含有指定主 题相关的关键字或正则表达式的匹配来实现，这种方法在判断的准确性 上有待商榷。 3 设置变量w i d t h 限制抓取的子网页数，这样虽然节省了时间，也可能导 致漏采集一些相关网页。 i b m 开发的s h a r k s e a r c h 算法对f i s h s e a r c h 算法进行了很多重要改进。 首先，在计算网页和主题的相关度方面采用了向量空间模型，将相关度量化 第二章网络爬行器的设计 为从0 到1 之间的连续值。进而使得处在列表中的链接的潜在相关度值有了更大 程度的区分，而不仅仅是0 和1 了。 其次，它通过考虑链接文本( 或称锚文本) 和链接上下文以及父网页与主题 的相关度对子网页与主题相关度的影响，来综合评价链接所对应页面与主题的潜 在相关度。即是说，虽然当前页面( 父网页) 与主题不是很相关，但是若链接文 本或链接上下文与主题很相关，则链接所指向的网页仍然有一个较大的潜在相关 度，这会使得它较早的被抓取。 s h a r k - s e a r c h 算法与f i s h 。s e a r c h 算法类似，也是维护一个动态的网址列表， 通过计算每个网址的潜在相关度分数值( p o t e n t i a ls c o r e ) ，将它们在列表中降 序排列，每次取出潜在相关度分数值大的链接进行抓取，分析。完整的 s h a r k s e a r c h 算法如下： 获取一些参数，包括初始结点u r l ，搜索深度d ，要抓取的网页数量s 和时间限制以及主题字符串。 设置初始结点的d e p t h = d ，将其插入到空的列表中。 w h i l e 列表不为空且处理的网页数少于s ，且没有到限制的时问 1 弹出列表中的头结点，将其设为当前结点。 2 计算当前结点与主题的相关度，利用向量空间模型。 3 i fd e p t h 0 ： 对每一个子节点： 1 1 计算子节点的遗传分数： i fr e l e v a n c e ( c u r r e n tn o d e ) 0 ( 当前结点是与主题相关的) t h e n i n h e r i t e d s c o r e ( c h i l d n o d e ) = a 宰s i m ( q ，c u r r e n t n o d e ) ( 么是预先定义的衰减因子，介于0 到1 之间) e l s e i n h e r i t e d s c o r e ( c h i m n o d e ) = a 木i n h e r i t e d s c o r e ( c u r r e n t n o d e ) 2 ) 设置a n c h o rt e x t 为指向c h i l dn o d e 的链接的链接文本内容， a n c h o rt e x tc o n t e x t 为链接上下文的内容。 3 ) 计算链接文本与主题的相关度： a n c h o r s c o r e = s i m ( q ，a n c h o r t e x t ) 4 ) 计算链接上下文与主题的相关度： i fa n c h o r s c o r e 0 t h e n a n c h o r c o n t e x t s c o r e = 1 e l s ea n c h o r c o n t e x t s c o r e = s i m ( q ，a n c h o r t e x t c o n t e x t ) 5 ) 计算n e i g h b o r h o o d s c o r e ，作为链接文本和链接上下文对链接的 第二章网络爬行器的设计 潜在分数值的贡献： n e i g h b o r h o o d s c o r e = b 木a n c h o r s c o r e + ( 1 一b ) 幸a n c h o r 一亡o n t e x t s c o r e ( b 是一个预先定义的常量，介于0 到1 之间) 6 ) 计算子结点的潜在分数值： p o t e n t i a l s c o r e ( c h i l d n o d e ) = c i n h e r i 纪d s c o r e ( c h i l d n o d e ) + ( 1 - c ) 宰n e i g h b o r h o o d s c o r e ( c h i l d n o d e ) ( c 为一个预先定义的常量，介于0 到l 之间) 7 1i fc h i l dn o d e 已经在列表中 t h e n 曲找出列表中对应结点的潜在分数值和当前子结点的潜在分 数值的最大者。 b ) 替换列表中的分数值，使其取上述最大值。 曲将结点c h i l dn o d e 移动到列表中合适的位置，按照潜在分数 值降序排列。 e l s e 将结点c h i mn o d e 插入到列表中合适的位置。 8 ) 计算结点c h i l d n o d e 的d e p t h ，即d e p t h ( c h i l d n o d e ) ： a ) i fc u r r e n tn o d e 是与主题相关的 t h e n d e p t h ( c h i l d n o d e ) = d e l s e d e p t h ( c h i l d n o d e ) = d e p t h ( c u r r e n t n o d e ) - 1 b 1i fc h i l dn o d e 已经出现在列表中 t h e n 找出列表中相应结点的d e p t h 和当前子结点c h i l d n o d e 的 d e p t h 值中的最大值。 替换列表中相应结点的d e p t h 值，使其等于上述最大值。 e n d w h l i e 2 2 2 基于s h a r k s e a r c h 算法的改进爬行器 大多数网页中相关的链接和文本通常连续出现，s h a r k s e a r c h 算法正是利用 了这一特征，把链接文本和链接上下文文本作为计算p o t e n t i a l s c o r e 的重要因 素，以此来衡量待访问链接与特定主题可能的相关度。