（计算机应用技术专业论文）主题搜索引擎爬行策略的研究.pdf

湖北工业大学硕士学位论文 摘要 随着互联网信息的持续爆炸性增长，通用搜索引擎的信息覆盖率和检索精度 都在不断下降，发展主题搜索引擎已经成为趋势。由于主题搜索引擎搜索的内容 只限于特定主题或专门领域，被通用搜索引擎所广泛采用的基于图的遍历搜索策 略( 如广度或深度优先算法) 已不再适用，因此，以何种策略访问w e b ( 即主题爬行 策略) 已成为近年来主题搜索引擎研究的关键问题之一。 本文从提高主题爬虫的搜索效率和搜索精度出发，在以下四个方面对主题搜 索引擎的爬行策略进行了较为深入的研究。 首先，本文基于现阶段国内外网络爬虫的研究进展，在分析和比较现有主题 网络爬虫搜索策略的优缺点的基础上，探讨了网络爬虫主题价值预测的准确性、 重要性及主题网络资源覆盖度的搜索策略，以提高主题爬虫的自适应性和搜索效 率。 其次，为了提高网络爬虫预测链接价值的准确性，本文提出了s h a r k 改进算 法，其主要思想是：通过改进s h a r k 算法来提高搜索相关网页的能力以及降低优 先排序空 自j 复杂度和时间复杂度，提高搜索效率、节约大量时间和资源。 再次，为了提高网络爬虫的自适应性，本文针对传统网络爬虫存在的价值评 价标准单一的问题，提出了一种基于综合价值的综合爬行策略，此策略根据不同 的搜索阶段选择采用符合实际情况的最优搜索策略。 最后，本研究采用改进的s h a r k 算法和自行设计的综合爬行策略相结合，实 现了一个基于多种搜索策略的主题搜索引擎网络爬虫系统原型。本系统综合了网 页的相关性和重要性两方面的需要，不仅能够准确、自动地爬行到主题相关网页， 从而提高信息搜索的效率，而且还可节约网络带宽，具有良好的稳定性。另外， 本系统u r l 的优先级侧重点是可调和，具有很强的灵活性。 关键词：主题搜索引擎，综合爬行策略，爬行算法，内容分析，链接分析 湖北工业大学硕士学位论文 a b s t r a c t w i t hc o n t i n u a lv o l a t i l ei n c r e a s eo fi n t e r n e t1 n f o r m a t i o n i n f o r m a t i o no v e r c a s tr a t e a n ds e a r c h i n gp r e c i s i o no fu n i v e r s a ls e a r c h i n ge n g i n ew e r eb o t hf a l l i n gc o n t i n u a l l y , d e v e l o p m e n to ff o c u s e ds e a r c h i n ge n g i n eh a db e c o m et r e n d a l lo v e rs e a r c h i n gs t r a t e g y b a s e do nc h a r t ，w h i c hw a sw i d e l yu s e db yu n i v e r s a ls e a r c h i n ge n g i n e ，i sn ol o n g e r a p p l i c a b l eb e c a u s ec o n t e n to ff o c u s e ds e a r c h i n ge n g i n ei sl i m i t e di ns p e c i f i cs u b j e c to r s p e c i a l i z e df i e l d w h i c hs t r a t e g yi su s e dt ov i s i tw 曲h a sb e c o m eap r i m a r yp r o b l e mo f s t u d y i n gf o c u s e ds e a r c h i n ge n g i n el a t e l y , t h i so n e i ss t u d yo fc r a w ls t r a t e g yo ff o c u s e d c r a w l e r 1 1 1 et b l l o w i n gw o r ka b o u ts e a r c h i n gs t r a t e g yo ff o c u s e ds e a r c he n g i n ei ss t u d i e d i nt h i sp a p e rw i t h4a s p e c t s ，i no r d e rt oe n h a n c es e a r c h i n ge f f i c i e n c ya n ds e a r c h i n g p r e c i s i o no ff o c u s e dc r a w l e r f i r s t l y , t h i st h e s i si n t r o d u c e di n v e s t i g a t i o no f w e bs p i d e rn o w a d a y s ，a n d d i s c u s s e d h o wt oi r e p r o v ea d a p t a b i l i t yo fw e bc r a w l e ra n dv e r a c i t yo ff o r e c a s tl i n kv a l u ei no r d e r t oe n h a n c es e a r c h i n ge f f i c i e n c y , a l lo f t h e s ea r eb a s e do na n a l y s i sa n dc o m p a r i s o na b o u t t r a i to f w e bc r a w l e rs e a r c h i n gs t r a t e g yw h i c hi sb a s e do ns u b j e c t t l l i st h e s i sp r e s e n t e ds h a r ki m p r o v e da r i t h m e t i cb a s e do ne n h a n c i n gv e r a c i t yo f f o r e c a s tl i n kv a l u e m a i nt h o u g h to fi m p r o v e da r i t h m e t i ci st oi m p r o v ea b i l l t yo f s e a r c h i n gi n t e r r e l a t e dw e ba n dt op l a yd o w nt i m ec o m p l e x i t yo rs p a c ec o m p l e x i t yo f p r i o r i t yt a x i s ，s oc a nw ee c o n o m i z eal o to f t i m ea n dr e s o u r c e c o n v e n t i o n a lv a l u em e t e w a n do fw e bc r a w l e rw a ss i n g l e ，a i m i n ga tt h i sq u e s t i o n t h i st h e s i sp r e s e n t e das e a r c h i n ga r i t h m e t i cb a s e do ni n t e g r a t e dv a l u ei no r d e rt o i m p r o v ea d a p t a b i l i t yo fw e bs p i d e r , t h i ss t r a t e g y c a l lc h o o s ei n t e g r a t e ds t r a t e g y a c c o r d i n gt od i f f e r e n ts e a r c h i n gp h a s e ，i ns h o r t , i tc a ns e l e c tt h eb e s ts e a r c h i n gs t m t e g y w h i c hi sa c c o r d e dw i t ht h ea c t u a ls i t u a t i o n f i n a l l y , t h i ss t u d yd e s i g n e daw e bc r a w l e rs y s t e ma r c h e t y p eo fp r o f e s s i o n a l s e a r c h i n ge n g i n e ，w h i c hc o u l da d o p tm u l t i s e a r c h i n gs t r a t e g y , t h i sd e s i g na d o p t e d i m p r o v e de f f i c i e n tc r a w la r i t h m e t i ca n dc r a w ls t r a t e g yo ff o c u s e dc r a w l e r t h es y s t e m c a ns y n t h e s i z et h en e e d so fw e br e l a t i v i t ya n de s s e n t i a l i t y , p u tu pw e l ls t a b i l i t y , e c o n o m i z en e t w o r kb a n d 埘d t l la n di m p r o v ee f f i c i e n c yo fi n f o r m a t i o ns e a r c h i n g s a v e i n t e r n e tt a p ew i d t ha n ds h o ws p l e n d i ds t a b i l i t y a tt h es a m et i m e ，t h i ss y s t e mo fu r l p r i o r i t yi sr e c o n c i l a b l ea n df l e x i b l e k e y w o r d s ：f o c u s e ds e a r c h i n ge n g i n e ，i n t e g r a t i v es e a r c h i n gs t r a t e g y , c r a w l i n ga l g o r i t h m ， c o n t e n ta n a l y s i s ，h y p e f l i n ka n a l y s i s 诹 l 亡工繁失罄 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名：吴圣玮 日期：羽年f 月；日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名：昊安埔 日期：劲籽月序日 指导教师签名 日期：加口解6 月彦日 湖北工业大学硕士学位论文 1 1 研究背景 第1 章引言 所有搜索引擎的祖先，是1 9 9 0 年由m e g i l l 大学的学生a l a ne m t a g e 、p e t e r d e u t s c h 、b i l lw h e e l a n 发明的a r c h i e 。搜索引擎中专门用于信息的r o b o t 程序像蜘 蛛一样在网络问爬来爬去，因此，搜索引擎的r o b o t 程序又被称为“网络蜘蛛s p i d e r 、 网络爬虫w e bc r a w l e r 、徘徊者w a n d e r e r 、网络机器人w e br o b o t ”等。世界上第一 个网络蜘蛛，是m i tm a t t h e wg r a y 的w w wfw o r l d 晰d ew e b ) w a n d e r e r ，用于追 踪互联网发展规模。刚开始它只用来统计互联网上的服务器数量，后来则发展为 能够抓取w e b 上的网页。 互联网的迅速发展使得检索所有新出现的网页变得越来越困难，因此，在 w a n d e r e r 基础上，一些编程者将传统的s p i d e r 程序工作原理作了些改进。其设想 是，既然所有网页都可能有连向其他网站的链接，那么从一个网站开始，跟踪所 有网页上的所有链接，就有可能检索整个互联网，于是导致了通用搜索引擎的出 现，其中最负盛名的有y a h o o 、g o o g l e 、l y c o s 、b a i d u 、a l t a v i s t a ，这些搜索引擎 通常使用一个或多个资源采集器从i n t e m e t 上收集各种数据( 如w w w 、f t p 、 e m a i ! ) ，然后在本地服务器上为这些数据建立索引，当用户检索时根据用户提交的 检索条件从索引库中迅速查找到所需的信息。这些采集器被叫做：s p i d e r s ， c r a w l e r s ，w e br o b o t s ，w a n d e r e r s 。本论文在后面章节将统一使用“爬虫”作为 采集器的标准术语。这些通用搜索引擎长期以来为人们查找信息提供了全面而高 效的服务。但随着近年来用户需求的不断变化和互联网规模的不断扩张，传统的 通用搜索引擎诈面临巨大的挑战。 挑战之一是因特网上w 曲信息资源的指数级增长，通用搜索引擎无法索引所 有的页面。据统计，中国2 0 0 5 年的网页数比2 0 0 4 年翻了一翻，通用搜索引擎渐 渐力不从心，即便是现在最大的搜索引擎也只能覆盖网络内容的3 0 4 0 川。 挑战之二是w e b 信息资源的动态变化，搜索引擎无法保证对信息的及时更新。 近年来的研究表明，w e b 上的页面平均5 0 天就有约5 0 的页面发生变化1 2 j ，而目 前通用搜索引擎更新的时间至少需要数星期之久【3 j 。面对如此巨大的数据量，数据 存储及索引、检索，无论是软件还是硬件都面临着巨大的挑战。 挑战之三是传统的搜索引擎提供的信息检索服务，不能满足人们日益增长的 湖北工业大学硕士学位论文 个性化服务的需要。传统的搜索引擎设计的目的是满足普通人群对“公共”信息 查询的需要，主要根据用户输入的“查询串”与索引页面匹配程度的高低返回页 面，搜索引擎返回的查询结果往往动辄上百万，加上普通用户大都不能十分准确 的描述需要的资料，给出的关键字不准确，结果就是用户真f 能用到的返回结果 很少，尤其是遇到某些需要专业背景的资料时，更是大海捞针。 面对这些挑战，各类适应特定人群需要的“主题搜索引擎”应运而生，并越 来越受到人们地关注与青睐。对于主题搜索引擎，传统的广度优先或深度优先搜 索策略己不再适用。以何种顺序访问w e b ，以提高搜索效率，是近年来主题搜索引 擎研究的焦点之一”“。 为了提高返回结果的利用率，人们开始缩小搜索的范围。主题搜索引擎 ( f o c u s e ds e a r c h i n ge n g i n e ) 应运而生，对于主题搜索引擎，其搜索的内容只限于专 门领域。采用主题搜索算法的爬虫程序仅对给定主题相关的网页文档进行搜集， 搜索算法在访问页面之前进行预测分析，从而识别出这些页面是否与主题相关， 决定是否采集或者制定采集的优先顺序。主题爬虫可以有效地减少采集页面的数 量，增加了采集页面的规整程度，同时也节约了网络带宽，提高信息搜索的效率。 因此开展对主题爬虫的研究是很有必要的。 1 2 主题搜索引擎的特点 所谓主题搜索引擎就是以构筑某一专题或学科领域的i n t e m e t 网络信息资源 库为目标，智能地在互联网上搜集符合这一专题或学科需要的信息资源，能够为 包括学科信息门户、专业信息机构、特定行业领域、公司信息中心、行业专家等 在内的信息用户提供整套的网络信息资源开发方案。 主题搜索引擎与通用搜索引擎存在着很大的差别： 1 ) 服务目的不同 通用搜索引擎面向任何用户提供对任何信息的查询，而主题型搜索引擎则面 向专业用户向他们提供对其所在专业的信息检索。 2 ) 搜索方式不同 通用搜索引擎对网络进行逐页的爬行，试图遍历整个w e b 。而主题型搜索引 擎则采用一定的策略预测相关网页的位置，动态的调整网页爬行方向，使系统尽 可能的在与主题相关的网页集中的地方爬行，这将节约大量的网络资源。， 3 ) 对硬仁二和网络的要求不同 湖北工业大学硕士学位论文 通用搜索引擎需求过大，而主题型搜索引擎由于没有遍历整个w e b 节约了大 量的网络资源，而且没有自己的大型索引数据库所以硬件需求也比较低。 主题搜索引擎的实现难点有两点：第一，起始种子站点和词库的设置。因为 该引擎并不遍历整个w e b ，所以起始站点集合就显得格外重要。词库作为评价网 页是否相关的标准的关键词的集合，它的合理配置直接影响到检索结果的准确性。 这两个方面的设置是否合理共同决定了引擎能否找到所有的相关内容。第二，既 然是有选择陡的抓取信息，那么这个有选择性的遍历w e b 的算法就直接影响了这 类引擎的工作效率。此外，信息的表示、信息抽取、信息过滤和下一个搜索站点 的选择策略都是系统实现的难点。 1 3 国内研究现状 主题搜索引擎大都处于研究和试验阶段，利用它搜索的结果再经过专业人士 的加工而形成的面向某一学科、领域的网络垂直门户网站也已经出现。目前面向主 题的网络信息搜索主要有两种技术： 一是基于内容的搜索。这类搜索方式是传统的信息检索技术的延伸。它的主 要方式就是在搜索引擎内部建立一个针对主题的词表，搜索引擎的爬行器根据其内 设的词表对网上的信息进行索引。 二是基于链接分析的检索。9 0 年代末期，国外信息检索界开始以s o c i a l n e t w o r k 为模型对互联网进行模拟。一些学者认为网页之间的链接指引关系同社会网络中 的关系有相似之处，特别是与传统的引文索引非常相似。通过对链接进行分析， 可以找出各个网页之问的引用关系，由于引用网页与被引用网页间内容上一般部 比较相关，所以就可以很容易地按照引用关系将大量网页分类。在美国，很多基 于这种超链接分析的检索系统原形已经产生，应用于他们的数字图书馆系统中。 目前在国外，有关主题型搜索引擎的研究正在成为一个热点。在1 9 9 4 年，出 现了最早使用查询来指导爬虫爬行的系统f i s h 搜索系统( f i s hs e a r c hs y s t e m ) “1 。 后来相继在l ) 9 8 年和1 9 9 9 年分别出现y s h a r k 搜索系统( s h a r ks e a r c hs y s t e m ) ”1 和主 题爬虫( f o c u s e dc r a w l i n g p 。如今，主题爬虫又有了新的发展，国外典型的系统 有c o m “0 1 、i b m f o c u s e d c r a w l e r ”1 、c o n t e x t g r a p h s f o c u s e d c r a w l e r s ”“等，国内的研 究与国外相比还处于一个初步发展阶段，主要侧重于整个系统功能的实现，在自动 主题搜索上研究的层次还很浅，j t h s t i p “、i - k n o w “、i d g s “、北大天网“。 湖北工业大学硕士学位论文 1 3 1c o r a 系统 c o r a 。“1 是美国卡内基梅隆大学的a k m c c a l l u m 和m n i g a m 等人于1 9 9 9 年针对计算机科学设计的一个主题型搜索引擎。它利用机器学习( m a c h i n e l e a r n i n g1 技术，在w e b 上搜索与计算机科学相关的论文，当时它只能搜索p s 格 式的论文。如果一篇文章含有题名、作者、摘要和参考文献，它就认为是一篇学 术论文。然后将p s 文件转换成文本文件，利用隐式马尔可夫模型来找出题名、作 者、摘要和参考文献，利用统计型文本分类算法将其按照y a h o o 分类体系进行分 类。现在的c o r a 站点地址是h t t p ：c o r a w h i z b a n g c o r n 。c o r a 思想比较先进， 很容易扩展成为其它学科主题的搜索引擎，对w e b 垂直门户网站资源自动建设具 有相当重要的意义。但是，c o r a 没有在预测u r l 与主题的相关度上作深入研究， 也没有对w e b 网页进行采集分析。实际上，由于论文的结构清晰，有很多明显特 征，用词舰范，所以对p s 等格式的论文采集的难度耍略低于对w e b 网页进行页面 主体采集的难度。 1 3 2i b mf o c u s e dc r a w l e r 系统 i b mf o c u s e dc r a w l e r ”3 是印度理工学院的学者s c h a k r a b a r t i 在伯克利大学计 算机系读博士期间从事的一个项目。在该项目中，作者提出了一种新的w e b 资源 爬行系统，即主题爬虫( f o c u s e dc r a w l e r ) 。它对主题的定义即不是采用关键词也 不是加权矢量，而是一组具有相同主题的网页。尽管称为主题爬虫，但它实际上 是一整套关于特定资源的自动建设方案，用来建设w e b 主题资源。 该系统的早期版本0 3 采用了两个模块：一个是分类器，用来计算下载文档与主 题的相关度，同时也用来指导爬行器优先爬行的相关资源：另一个是净化器，用 来确定哪些是中心页面。在该系统的改进版本”。中，作者将分类器分成两个，一个 用来指导爬行，一个用来计算下载网页与主题的相关度。从而使系统有了更好的 性能。 1 3 3c o n t e x tg r a p h sf o c u s e dc r a w l e r 系统 c o n t e x tg r a p h sf o c u s e dc r a w l e r “”是由d i l i g e n t i 等人研究设计的一种主题爬 虫。他们提出了一种通过建立上下文图( c o n t e x tg r a p h s ) 来学习网页间相互关系的 方法。他们先给系统提供一组种子主题页面，然后利用g o o g l e 提供的反向链接( 通 过在g o o g l e 中键入“l i n k ：u r l 就可以获得所有指向该页面的页面链接，如：“l i n k ： w w w q i a n l o n g t o m ”) 服务来寻找到所有拥有指向种子页面链接的页面。所有拥有 湖北工业大学硕士学位论文 指向种子页面链接的页面被称作第一层页面，而所有拥有指向第一层页面链接的 页面被称作第二层页面，依次类推。页面的层数根据用户参数的改变而改变。见 图( 1 1 ) 展示了一个深度为2 的上下文图。 s e e dd o c m n e n t 镶j 8 y “ld “。“t l a y e r2 d o c u m e n t 图1 1 深度为2 的上下文图 当每一个种子页面都建立好一个上下文图后，研究人员将不同的上下文图的相 应各层进行合并，形成一个合并上下文 ( m e r g e dc o n t e x tg r a p ho 同时为每一层 训练一个贝叶斯分类器。在爬行过程中，分类器被用来确定所要爬行的页面应该 属于哪一层。一旦页面的所属层次被确定，那么该页面所包含的链接就会被加入 到与该层相对应的队列中。然后再从靠前的非空队列中提取所要爬行的页面u r l 。 1 3 4s t i p 系统 i n t e m e t 科技信息门户网站s t i p ( s c i e n c ea n dt e c h n o l o g yi n f o l l n a t i o np o r t a l ， s t i p ) i l “是中科院文献情报中心实施中科院文献信息共享系统的一个子课题，旨 在开发和利用i n t e r n e t 上的科技信息资源，它通过搜索、发现、组织、加工、整理 i n t e m e t 上的科技信息资源并借助i n t e r n e t 网络向用户提供网络资源导航、检索等 信息服务。该系统有一个类似于自动主题搜索系统的科技信息资源采集系统，该 系统采用通用爬行器模型来实现资源采集，为资源建设者提供一种方便灵活的接 口，利用人工来判断是否与主题相关、标引相关数据。该项目在自动主题搜索上 面，基本上没作深入研究，但它所提供的功能体系还是具有一定的先进性。 1 3 5 网络智钱知识服务系统i - - k n o w 网络智能知识服务系统i - - k n o w 3 是一个完整的网络智能知识服务系统，i k n o w 系统是一整套针对专业用户的智能知识服务系统，它的信息资源采集子 系统i - - r o b o t 是i k n o w 的核心子系统，负责信息的采集和处理并最终形成索 引。后来在l k n o w 的基础上，进一步发展为万方数据竞争情报计算机系统 湖北工业大学硕士学位论文 ( w f i s ) ，该系统旨在综合采集各种可以获取( 网络资源、电子文档、印本文档等) 的信息资源并进行统一的组织、整理、加工，最终服务用户。该系统服务于专业 人员的情报加工工作，可以为最终用户提供情报相关产品。 t - - k n o w 系统最早是采用通用爬行器模式来实现自动主题搜索的，后来采用了 f i s h 算法来提高主题搜索的性能“。简单地说，该系统在自动主题搜索上只是采 用了f i s h 算法。 1 3 6 南京大学的i d g s 南京大学软件新技术国家重点实验室张福炎、潘金贵教授等设计了一个互联 网数据采集系统( i n t e r n e td a t ag a t h e rs y s t e m ，i d g s ) “。该系统旨在对w e b 上 中英文技术资料进行自动搜集。i d g s 根据用户提交的挖掘目标样本，在w e b 上自 动查找用户所需的信息，它采用向量空间模型和基于词频统计的权重评价技术， 由特征提取、源站点查询、文档采集、模式匹配等4 个部分组成。 该系统的关键技术在干它的一个模式匹配模块，其任务是计算实际采集到的 网页与用户兴趣之间的相关度。它的文档采集模块相当于一个爬行器，采用了兴 趣漫游的模型，其基本思想是：如果某网页满足用户兴趣，则继续往下找，否则 就终止该方向的查找。该模型类似于f i s h 算法，“哪儿有草，鱼儿就注哪儿游”。 但它只是简单地利用父结点的主题相关度来判断是否下载孩子结点，并且只在用 户给出的有限种子站点基础之上爬行，搜索的深度很有限，更多地强调准确度， 在一定程度上忽视了覆盖度。 1 3 7 北大天网 北京大学计算机科学技术系计算机网络与分布系统实验室“”研制开发的“天 网”中英文搜索弓i 擎系统是国家“九五”重点科技攻关项目“中文编码和分布式 中英文信息发现”的研究成果，并于1 9 9 7 年1 0 月2 9 日正式在c e r n e t ( c h i n e s e e d u c a t i o n r e s e a r c hn e t w o r k ) 上向广大i n t e m e t 用户提供w e b 信息导航服务， 致力于探索和研究中英文搜索引擎系统的关键技术，以便向广大用户提供更为快 速、准确、全面、时新的海量w 曲信息导航服务。天网从最早提供简单的网页信 息查询服务以来，不断推出文件搜索服务、天网目录服务、天网主题服务，同时 f 在研制个性化服务。其中“天网主题”就是致力于特定领域、地域、特定主题 的资源搜索搜集。值得注意的是，北大天网是继“天网目录”服务推出之后才推 出了“天网主题”服务。他们解决的关键技术是网页分类技术。 6 湖北工业大学硕士学位论文 1 4 课题研究的内容 本文主要针对基于主题的网络爬虫，围绕提高主题网络爬虫的主题价值预测 的准确度、重要性及主题网络资源搜索的覆盖度来对主题网络爬虫的搜索策略问 题进行了深入研究。具体研究的内容包括以下几个方面： i 、在分析现有主题网络爬虫搜索策略的基础上，探讨了如何提高网络爬虫自 适应性和预测链接价值准确性的搜索策略，以此来提高搜索的效率。 2 、分析了基于内容的启发爬行算法s h a r k 的缺点，并提出了s h a r k 改进算法。 3 、为了提高网络爬虫的自适应性，本文针对传统网络爬虫存在的价值评价标 准单一的问题，提出了一种基于综合价值主题爬行策略。 4 、本文研究了基于内容评价和基于w e b 链接评价的搜索策略相结合的多种方 案，并在从理论上分析各种方案的优劣，提出了主题爬虫的最佳综合爬行策略方 案，此方案根据不同的搜索阶段选择采用符合实际情况的最优搜索策略。 5 、本研究采用改进的s h a r k 算法和白设计的综合爬行策略，实现了一个基于 多种搜索策略的主题搜索引擎网络爬虫系统原型。本系统综合了网页的相关性和 重要性两方面的需要，不仅能准确地自动爬行到主题相关网页，从而提高了信息 搜索的效率，而且还节约了网络带宽，具有出良好的稳定性。 1 5 课题研究的目的和意义 随着i n t e m e t 的快速发展，特别是w w w 技术的飞速进步，网络已成为全球 最大的分布式的信息知识库。一方面这为信息资源的共建共享提供了一个良好的 平台，但另一方面又大幅度地提升了信息检索和知识获取的成本，使得信息查询 和索取越来越难，出现了“富数据，穷信息”、“信息迷航”、“信息过载”等问题 和现象。人们迫切希望可自动地搜索w e b 上的主题资源，为科研人员和相关用户 提供高质量的信息资源和信息服务，这无疑对网络爬虫的搜索效率和搜索精度提 出了巨大挑战，因此对主题爬虫爬行策略的研究具现实意义。 一旦主题搜索最优爬行策略研究成功，它不但能作为实现自动主题搜索的最 佳方法，提高某个主题的资源覆盖度以及主题爬虫的搜索效率，而且使得主题爬 虫所下载的网页尽可能地与所需的主题相关，从而有效地提高主题爬虫的爬行性 能、节约网络带宽及爬行时间。 湖北工业大学硕士学位论文 第2 章主题网络爬虫概述 2 1 主题搜索引擎基本工作原理 主题搜索引擎是以构筑某一专题或学科领域的i n t e m e t 网络信息资源库为目 标，智能地在互联网上搜集符合这一专题或学科需要的信息资源。 主题搜索引擎的搜索任务本质上是一个顺序决策过程，其目标是寻找一个最 优的行动选择序列，使得按这一序列访问w e b 获得的主题相关页面数( 简称“回 报”) 最大。主题搜索引擎中，搜索w e b 并获取页面的任务通常由一“智能化”的 软件一一嘲络爬虫( 或称网络、代理体) 来完成。主题搜索引擎包括网络搜 索、索引、检索三大模块，如图2 1 三个虚线框所示： 网络搜索模块 网络搜索模块通常称为w e b “蜘蛛”( s p i d e r ) 、“爬虫”( c r a w l e r ) 或“机器 人”( r o b o t s ) 。它以一个初始的u r l 列表为起点，利用标准协议遍历w w w 空间， 包括w e b 页面里的所有链接( 1 i n k ) ，进行网页信息采集，并将其存储在网页数据 库中，以备索引模块进行标引处理，提取概念。 图2 1主题搜索引擎系统结构图 湖北工业大学硕士学位论文 索引模块 索引模块主要是用于对网络搜索模块采集到的网页信息进行处理，然后编制 索引入库以备用户检索使用。处理网页主要包括以下几个部分：文档特征提取、 相关度分析、网页筛选、标引、归类和最后的入库。 检索模块 检索模块主要从索引数据库中检索满足用户要求的w e b 网页，作为搜索引擎和 用户之阳j 的接口，检索模块首先要分析给出的查询式，然后访问索引数据库通过 匹配算法获得检索结果，然后根据相关度进行排序提交给用户。 本课题重点研究的就是主题搜索引擎中的网络搜索模块，即网络爬虫。 2 2 主题爬虫 爬虫在设计之初，其目的是在给定爬行周期内，尽可能多地下载w e b 网页。 但当面临着w e b 网页发展规模和数量成几何增长的现实时，通用爬虫要想在爬行 网页时既保证网页的质量和数量，又要保证网页时效性显然已经是力不从心了。 于是，爬虫的设计目的就变成了在给定的爬行周期内尽可能多地爬行高质量的网 页，并且保持网页的时效性。而主题爬虫在上述设计目的的基础上，还考虑了网 页与主题的相关度，尽可能多地下载相关网页，尽可能少地下载无关网页，提高 主题资源的覆盖度。 一个好的爬虫需要达到以下两个要求“”：它必须要有一个好的爬行荒略， 即决定下一步要爬行哪些网页的策略。它必须要有一个高度优化的系统结构， 且健壮性、可控性良好。对于主题爬虫而言，它还必须对下载的网页进行与搜索 主题的相关度分析，以决定其是否符合主题搜索的要求。因此要有一个好的分析 方法。 由于相关主题资源的规模相对整个因特网来说要小得多，也相对容易控制和 掌握，所以主题爬虫可以提供更精确的搜索结果。 2 2 1 主题爬虫的原理 假设一个用户的w e b 信息检索表示为一组目标主题集合：t = t 1 ，t 2 ，t 。 ， 每个主题t i 分别由主题爬虫来处理。我们可以用一组关键词k = k l ，k z ，k 。 来表示一个主题的关键特征，而用一系列样本集w 来详细描述一个主题，其中 w = 1 1 1 i 是一个样本u r l ；l i = 0 或1 ，是该u r l 的正反例标号 。l i 值为1 表示u 与主题相关，为0 表示与主题不相关。主题爬虫一般从一组种子u r l 开始 湖北工业大学硕士学位论文 沿着己爬行页面中的超链接遍历w e b 以搜集更多的主题相关页面。对于主题爬虫 来浇，k 与v ，是它的初始学习资源。 整个w e b 从逻辑上可以看作一个有向图g = ( v ，e ) ，其中图的节点集v 表 示页面的集合，有向边集e 表示页面之间的超链接。给定一个目标主题，根据页 面内容与目标主题的相关度，节点集v 可以分为两部分；相关集v + 和不相关集 v 一。主题爬虫的爬行过程可以看作对一个有向图的遍历过程，即从一组节点f 种子 节点) 出发，尽可能多地搜索到那些属于v + 集合的节点，同时尽可能避免搜集到那 些属于v 一的节点。 简单来说，主题爬虫就是指具有识别主题功能的爬虫，它尽可能多地爬行与 某个主题相关的w e b 资源，扩大该主题资源的覆盖度。 主题爬虫的基本思路是按照事先给出的主题，分析超链接和己经下载的网页 内容，来预测下一个要爬行的u r l ，保证尽可能地多下载与主题相关的网页、尽 可能少下载无关网页。因此，主题爬虫需主要解决以下三个关键问题“。 ( 1 ) 怎样判断一个己经下载的网页是否与主题相关? 对于已经下载的网页，因 为我们可以知道它的文字内容，可以采用传统的文本挖掘技术来实现。 ( 2 ) 怎样提高爬行效率? 即怎样决定u r l 的访问次序? 主题爬虫需要解决如何 从待爬行u r l 队列中挑出最可能包含主题相关信息的网页进行爬行。许多主题爬 虫是根据己下载的网页的相关度，按照一定的原则，将相关度进行衰减，分配给 该网页中的超链接，而后插入到优先级队列中。此时的爬行次序就不是简单的以 深度优先或者广度优先为序，而是按照相关度大小排序，优先访问相关度大的 u r l 。不同主题爬虫之间的主要区别也就在于它是如何决定u r l 的爬行次序。 ( 3 ) 怎样提高主题爬虫的覆盖度呢? 这个问题要解决的就是如何穿过质量不够 好( 与主题不相关) 的网页得到我们所感兴趣的网页，从而提高主题资源的覆盖度。 2 2 2 主题爬虫的结构 主题爬虫是在普通爬虫的基础上发展起来的，最早的主题爬虫是在通用爬虫 的基础上改造而成的，其结构见图( 2 2 ) 。 湖北工业大学硕士学位论文 图2 2 主题爬虫结构示意图 设计者只是为爬虫提供了主题关键字，并在存储之前增加了一个主题识别步 骤( 相关度判定) ，若页面与主题相关就存储，否则就丢弃。尽管这样的爬虫也能实 现对主题资源的爬行，但它在爬行中依然要遍历整个网络，并没有提高爬行的效 率。网页爬行的数量和范围也依然严重依赖于给定种子站点的数量和质量。同时， 这种爬虫还会下载很多与主题无关的资源，然后丢弃，造成对带宽和网络资源的 严重浪费。 为解决以上的不足，研究者们采用了很多轻巧的算法和策略，来保证爬虫尽 可能多地爬行相关网页，尽可能少地爬行无关网页，并且确保网页有较高的质量。 研究的主要工作集中在如何将待爬行的u r l 按一定策略进行排序，使得与主题相 关且质量高的u r l 优先爬行。从第三章开始，本文将详细研究并讨论u r l 排序 的启发策略。 主题爬虫发展到现在，其结构要比原始的复杂得多，也有效得多。一个主题 爬虫一般包括以下三个关键组成部分： ( 1 ) 页面相关度评价器。该模块主要特点是引入了文本分类的思想。在系统爬 行之初，页面相关度评价器根据用户输入的关键字和初始文本信息进行学习，训 练一个页面相关度评价模型。当一个被认为是主题相关的页面爬行下来之后，该 页面就被送入页面相关度评价器计算其主题相关度值，若该值大于或等于给定的 某阈值，则该页面就被存入页面库，否则丢弃。 ( 2 ) 超链接评价器。该模块是主题爬虫的核心模块，主要用于评估从主题相关 页面解析出束的u r l 与主题的相关度，并提供相关的爬行策略用以指导爬虫的爬 行过程。u r i 的超链接评价得分越高，爬行的优先级就越高。反之，若通过一定 湖北工业大学硕士学位论文 的评价策略，发现某链接与主题无关，则将该u r l 及其所有隐含的子链接一并去 除，这个过程本文称之为剪枝。通过剪枝，爬虫就无需遍历与主题不相关的页面， 从而保证了爬行效率。但是，剪枝的行为也可能将潜在的与主题相关的页面也剪 掉。因此，超链接评价器所用的评价策略的好坏直接影响着爬虫的爬行效率以及 爬行质量。 ( 3 ) 爬行器( 页面采集模块) 。陔模块是任何爬虫都不可或缺的通用模块。该模块 承担着连接超链接评价模块和页面相关度评价模块的重任。首先，爬行器从待爬 行u r l 队列中取出超链接得分最高的u r l ，将该u r l 相应的网页爬行到本地， 然后，将该页面交由页面相关度评价器处理。在整个爬行过程中，爬行的次序和 爬行策略都考超链接评价器提供。 2 3 主题页面的分布特征 w e b 与传统的信息媒介相比，具有许多的不同点：信息容量的巨大性； 动态性，整个w e b 的内容和结构每时每刻都在改变；异构性，w e b 中所包含的 文件类型各式各样，包括图像、图片、声音、文本等；w e b 页面的重复性，最 近的研究表明，将近3 0 的页面是重复的：高链接性，一项研究表明平均每个 页面有超过8 个链接指向别的页面；多语性，w e b 上所用语言是多种多样的， 目前页面语种超过了1 0 0 种。 虽然整个w e b 充满了半结构化的和非结构化的各类信息，显得杂乱无章。但 它也是有一定的规律可循的，我们可以将主题页面的分布规律总结为以下几个基 本特征“4 ”“、“8 “：中心页面特性、主题关联特性、主题聚集特性、隧道特 眭。 2 3 1 中心页面特性 在整个w e b 中大量存在着这样一类页面，它们不但含有许多指向其他页面的 链接，而且这些链接还趋向于同一主题。也就是说，这类页面是指向相关主题页 面的中心，我们称之为中心页面或h u b 页面。另外，w 曲中还有这样一类被许多 网页都认为与某一主题相关的有价值的网页，我们称之为权威页面或a u t h o r i t y 页 面。存在链接关系的页面间，其描述的主题一般都比较相似。一般的，一个好的 中心页砸会指向多个权威页面，一个好的权威页面会被多个中心页面指向。据于 这个思想，美国康奈尔大学的教授j o n m k l e i n b e r gj 丕提出了h u b a u t h o r i t y 算法“， 这个算法将在第三章介绍。 湖北工业大学硕士学位论文 2 3 2 主题关联特性 在内容关联特性的基础上，科研人员又对w 曲结构进一步深入的观察和研究， 提出了主题关联特性，即每个页面所包含的链接都趋向于链接到与它本身同主题 的页面：对于链接到某一主题页面的页面，它所包含的其它链接也趋向于链接到 该主题。这个结论实际上是从网页设计者的角度考虑的，一个网页的设计者趋向 于将本页面指向于与本页面主题相关的其它页面；同时也趋向于将本页面链接在 与本页面主题帽关的页面之后。 2 3 3 主题聚集特性 研究人员还发现，每一个非门户的普通站点都趋向于说明一个或几个主题， 而且那些相同的主题页面之间会有紧密的内部链接，但是不同的主题之间却很少 有相互问的链接。产生这种现象主要原因应该是网站的设计者在设计网站时都有 预定的设计目标和定位，而这种目标往往就集中在一个或几个主题上。同时，对 于网页浏览者来说，他们在上网时一般也趋向于浏览同一主题的页面。为适应上 网者的需求，网站设计者也需要将相关内容相互链接。这样在w e b 中就出现了一 个一个主题团。这个特性为主题爬虫的剪枝操作的可行性提供充分的理论依据。 2 3 4 隧道特性 尽管在w e b 中存在很多主题页面所聚集而成的主题页面团，但在这些页面团 之间，有时往往需要经过较多的无关链接才能够到达。这些无关的链接就像长长 的隧道样连接着两个主题页面团，因此，这种现象被称为“隧道现象”。在主题 爬虫的运行