（教育技术学专业论文）主题蜘蛛的研究及实现.pdf

摘要 随着i n e r n e t 的迅猛发展，网络资源呈几何式增长，人们越来越不满足于大型搜索引 擎所提供的服务，开始关注各种各样的主题式搜索引擎。主题式搜索引擎主要针对某一特定 领域、某一特定主题或某一特定人群，提供内容集中而深入的信息与服务。主题蜘蛛作为主 题式搜索引擎的重要部分，它的好坏直接关系到所搜集到资源的质量，因此如何设计一个高 质量的主题蜘蛛就成为了主题式搜索引擎研究的一个重要课题。 本文主要针对的是主题蜘蛛的研究和实现，其主要研究内容如下：通用蜘蛛与主题蜘蛛 的设计结构比较、设计时需要注意的性能瓶颈分析、主题搜索策略及主题相关度计算算法的 研究等等。取得了以下一些成果： ( 1 ) 研究并设计了适合主题搜索引擎需要的分布式、动态配置、可扩展的主题蜘蛛体 系结构； ( 2 ) 针对主题搜索引擎的需要并结合种子网站的概念，提出了如何快速、高效搜集种 子网站的方案； ( 3 ) 根据系统的需求，改进了空间向量模型算法； ( 4 ) 在理论研究的基础上，开发了适合主题搜索引擎的主题蜘蛛的程序。 关键词：主题蜘蛛、搜索策略、预处理、中文分词、相关度计算 a b s t r a c t i n t e r n e ta l o n gw i t ht h er a p i dd e v e l o p m e n to fn e t w o r kr e s o u r c e si nt h eg e o m e t r i cg r o w t h p e o p l ea r en o tm o r es a t i s f i e d 诵mt h es e r v i c e sp r o v i d e db ym a j o rs e a r c he n g i n e s s e a r c he n g i n e s b e g a nt op a ya t t e n t i o nt ot h et o p i c s p e c i f i cs e a r c he n g i n e i tp a y sa t t e n t i o n st oal i g h to fa p a r t i c u l a ra r e a ，as p e c i f i cg r o u po ras p e c i f i ct h e m ea n dp r o v i d e sf o c u s e da n di n - d e p t hi n f o r m a t i o n a n ds e r v i c e s t h et o p i cs p i d e ra sa r ti m p o r t a n tp a r to ft h et o p i c s p e c i f i cs e a r c he n g i n e ，i th a sa d i r e c tb e a r i n go nt h eq u a l i t yo ft h ec o l l e c t e dr e s o u r c e s s ot h et h e m eo fh o wt od e s i g na h i g h - q u a l i t yt o p i cs p i d e rr e s e a r c ho nt h es u b j e c th a sb e c o m ea ni m p o r t a n tt o p i c t h i sp a p e ri st h em a j o rt h e m eo ft o p i cs p i d e ra n dr e a l i z a t i o no fi t sm a i nc o n t e n t sa r ea s f o l l o w s ：t h ed i f f e r e n c e sb e t w e e nt h et r a d i t i o n a lw e bs p i d e ra n dt h et o p i cs p i d e ro ns t r u c t u r a l d e s i g n ，d e s i g na t t e n t i o nt ot h ep e r f o r m a n c eb o t t l e n e c ka n a l y s i s ，s e a r c hs t r a t e g i e sa n dt h e m e s r e l a t e dt ot h et h e m e so fc a l c u l a t i o na l g o r i t h ms t u d y a c h i e v e dt h ef o l l o w i n gr e s u l t s ： ( 1 ) d e s i g na n ds t u d yat o p i cs p i d e ro fd i s t r i b u t e d ，d y n a m i ca l l o c a t i o n ，s c a l a b l e a r c h i t e c t u r e ； ( 2 ) t h ed e f i n i t i o no ft h ec o n c e p to fs e e d sw e b s i t e a n dh o wf a s ta n de f f i c i e n ts e e d c o l l e c t i o ns i t e ； ( 3 ) c o n s i d e rt h es y s t e mn e e d s ，i m p r o v ev e c t o rs p a c em o d e la l g o r i t h m ； ( 4 ) o nt h eb a s i so ft h e o r e t i c a ls t u d i e s ，d e v e l o p e dat o p i cs p i d e rf o rt h et o p i c s p e c i f i c s e a r c he n g i n e k e y w o r d s ：t o p i cs p i d e r , t h es e a r c hs t r a t e g y , p r e t r e a t m e n t ，c h i n e s ew o r ds e g m e n t a t i o n ，r e l e v a n t c a l c u l a t i o n i i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 ，、 作者签名：自星型 日期：望21 巨玉2 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名：鲤匡旦 日期： 7 修；秒 1 1 研究背景 第一章前言 随着网络信息的迅速膨胀，人们对搜索引擎的首要关注是怎样从许多相关信息找剑准 确、有效的信息，查准率成为搜索引擎的首要目标。这也是人型搜索引擎面临的展人挑战。 它们通常查准率极低，返回给心户是成千上万的查询结果，而有效结果可能只有几个甚至根 本没有。由于客观存在的各种约束，查准率问题对于门户型搜索引擎来说是较难解决的，因 为它们要在数秒内为数万刖户同时服务，在上亿记录中查找出符合用户需求的信息。信息量 大、时间短、语言的二义性等给门户型搜索引擎带来极人的挑战性。如何解决这个问题? 借 鉴专题型网站的出现、发展和成熟，我们认为搜索引擎朝着主题化的方向发展应该是解决问 题的一条思路。 主题式搜索引擎，就是专fj 为查询某一学科或主题的信息而山现的壳洵一i ：具，其设计 思路是围绕着某一主题而展开的。借助丁| 领域专家的经验和知识，可以提高内容编排的质量。 对解决主题领域内的专业信息卉询，主题式搜索引擎要比门户型搜索引擎有效得多。这种高 度目标化、专业化的搜索引擎最丈的优势在丁，能够把具有相同兴趣点的人f j 集中在一个“主 题社区”内，不仅集中提供各种专业资源，而且给人家提供了一个相互交流、共享经验和教 训，展望行业发展前景的机会利场合，冈此受剑越来越多刚户的欢迎。 网络蜘蛛即w e bs p i d e r 是一个形象的名字，把互联网比喻成一个蜘蛛网，那么w e b s p i d e r 就是在网上爬来爬去的蜘蛛。它是通过网页的链接地址米寻找网页，从网站的某一个 页面( 通常是首页) 开始，读取网页的内容，找剑该网页中的所有链接地址，然后通过这些 链接地址寻找下一个网页，这样一直循环下去，直至0 把这个网站进而整个互联网上所有的网 页都抓取完为止。主题蜘蛛是主题式搜索引擎的一个重要组成部分。由丁主题式搜索引擎只 提供主题领域内的信息查询，也就是说，非主题领域内的信息对其而言是无效信息。这就要 求搜索引擎在进行网上信息采集时，必须采用主胚式搜索策略。搜索引擎按照管理员预先漫 定的主题去采集网上相关信息，可以减少被采集的信息数量，提高索引数据库中的信息质量。 在主题蜘蛛的相关研究上涉及到许多方面，比如，相关土题的种子网站的选取，采川什 么样的分布策略最大限度的搜集资源，主题相关度的确立等等。这些因素都会直接影响到主 题蜘蛛的好坏。 主题式搜索引擎本身所具有独特优势，使得它能够解决门户搜索引擎无法解决或很难 解决的问题。我们相信，主题式搜索引擎的出现将会成为今后搜索引擎的发展新动向，而主 题蜘蛛作为主题式搜索引擎的重要组成部分，必然也会得到更多研究者的重视。 1 2 国内外相关研究现状 目前，主题搜索引擎的研究发展迅速，已经成为人们关注的热点。在国外，已经有相应 的系统，下面介绍一些典型的系统： 1 e l s e v i e r 的s c i r u s 系统 s c i r u s 科学搜索引擎是一种专为搜索高度相关的科学信息而设计的搜索引擎，获得2 0 0 1 年搜索引擎观察授予的“最佳专业搜索引擎”奖。s c i r u s 是目前互联网上最全面、综合 性最强的科技文献门户网站之一。它只面向包含有科学内容的网站，如大学和作者个人主页 以及e l s e v i e r 自己的数据库。 2 n e c 研究院的c i t e s e e r c i t e s e e r 是因特网上使川最广泛的针对计算机领域的科学论文检索系统。c i t e s e e r 的核 心是a c i ( a u t o m a t i c a l l yc i t a t i o ni n d e x ) ，它可以自动地对网上的电子文件( p o s t s c r i p t 和p d f 等格式) 进行索引并分类。 3 b e r k e l e y 的f o c u s e dr r o j e c t 该系统通过两个程序来指导爬行器：一个是分类器c l a s s i f i e r ，刚米计算下载文档与预 订主题的相关度。另一个程序是净化器d i s t i l l e r ，川米确定那些指向很多相关资源的页面( 在 h i t s 算法中，称之为中心网页) 。 在国内，研究主题搜索引擎的团队也越来越多。现在开始研究该领域的主要是一些大学 的研究机构和一些搜索引擎公司。比如，北京化一f ：大学就推出了关于化： 方面的专业搜索引 擎，其他方面如医药、林业等也有相麻的产品。百度等多家搜索引擎提供商也相麻的推出了 图片搜索、m p 3 搜索、行业搜索，这些都可以看作是主题式搜索引擎的应用。 1 3 主要研究内容 ( i ) 主题蜘蛛系统架构设计。如何设计一个结构合理、可扩展配置、分布式并行的系 统。 ( 2 ) 种子网站的选取。针对某一个特殊专业的领域，怎么样快速、高效的确定首先进 行搜索的种子网站，在主题蜘蛛遍历搜索的过程中，怎样去不断的扩充种子网站，使主题蜘 蛛持续的运行下去，搜集到更多的相关网页内容。 ( 3 ) 确定主题蜘蛛的搜索策略。分析了传统搜索策略和主题式搜索策略的各自的特点， 重点分析了主题式搜索策略中基于内容的策略、基丁二链接结构的策略以及基于综合价值的搜 索策略等等，提出了本系统将要采取的搜索策略。 ( 4 ) 主题相关度算法的实现。土要对空间向量模型算法( v s m ) 的研究和分析。 2 1 4 研究成果与创新之处 作为理论与实践相结合的研究课题，主要取得了以下一些成果： ( 1 ) 研究并设计了适合主题搜索引擎需要的分布式、动态配置、可扩展的主题蜘蛛体系 结构： ( 2 ) 针对主题搜索引擎的需要并结合种子网站的概念，提出了如何快速、高效搜集种子 网站的方案； ( 3 ) 根据系统的需求，改进了空间向量模型算法； ( 4 ) 在理论研究的基础上，开发了主题式搜索引擎的主题蜘蛛的程序。 i 5 本文的组织结构 本文用绕如何设计一个快速、稳定、精确度商的主题蜘蛛展开研究，具体的篇章结构 如f ： 第一章主要简单介猁了本文的研究背景、国内外相关研究现状、研究内容、研究成果 和创新之处以及文章组织结构。 第二二章分析了主题式搜索引擎的一些相关概念，讨论了传统通删蜘蛛与主题蜘蛛之间 的异同，以及设计主题蜘蛛时所要考虑的性能方面的要求。 第三章研究了种子网站的概念、特征，f ：分析比较了人1 ：选取和通过元搜索引擎选取 的优缺点，综合两者的优点设计了快速选取种子网站的方案。同时，还分析了传统蜘蛛与主 题蜘蛛的搜索策略。 第四章如何进行网页预处理，分析了h t m l 语言结构特点，指出了主题蜘蛛工作所依 据的标记，通过u r l 和关键词过滤链接的机制，机器人排斥标准及如何实现的。 第五章研究了中文分词的现状及几种中文文本分词的方法，并给出了本系统实现分词 的算法。然后又着重分析主题相关度的计算方法，介绍了向量空问模型、特征提取、权重计 算的基本概念，指出了向量空间模型计算主题相关度的优缺点，并提出了自己的改进算法。 第六章主要分析了主题蜘蛛的系统应如何实现的，程序基本流程、数据库的设计及实 验效果的分析。 第七章对以上工作的总结以及下一步工作的展望。 3 第二章主题蜘蛛概述 当人们还在津津乐道的谈论搜索引擎( 诸如b a i d u ，g o o g l e ) 给我们带来的方便的同时， 往往确面l 临着另一个问题如何从浩瀚的信息中寻找一些有价值的东西。传统人型搜索引 擎返同的查询信息不仅数量大，而且质量参次不齐，还有许多无效的信息，往往给人造成厌 烦的心理。针对这个日益突出的问题，人们的兴趣开始逐渐注意剑主题领域上，开始研究主 题式搜索引擎。不论传统大型搜索引擎，还是主题式搜索引擎，网络蜘蛛都是其关键的组成 部分。本章主要研究并比较了传统人型搜索引擎中使h 的网络蜘蛛与主题式搜索引擎所采用 的网络蜘蛛设计结构上的异同，最后还分析了设计一个一个好的网络蜘蛛麻当注意的些性 能问题。 2 1 通用蜘蛛 人型搜索引擎般包括：搜索器、索引器、检索器和刚户接1 3 四个部分组成。我 j 把 一般大型搜索引擎中的搜索器称之为通j l i j 蜘蛛。通用蜘蛛是一种专门。卜载w e b 网页的程序。 在一个给定的种子u r l s 集合s 下它不断从s 中移走一个u r l ，然后f 载对应的网页，并从 该网页中抽取所有的u r l s ，将来访问过的u r l 加入s 中。在具体的实现中义可以分为以下 几个部分：页面采集模块、页面预处理模块、链接提取模块以及相应的数据库存储模块。各 个模块组成的系统结构如下： 2 1 1 页面采集模块 图2 1 通用蜘蛛的系统结构图 该模块是网络蜘蛛和i n t e m e t 之间的接1 3 ，主要功能是通过各种w e b 协议( 如h t r p 、 4 f t p 等，这里主要考虑小1 1 p 协议) 来完成对网页数据的采集和分析。具体地，我们还可以 细化为几个功能：u r l 处理模块、协议处理模块、网页下载模块。 1 u r l 处理模块 这个模块主要对待搜索的u r l 排序，并通过一定的策略给搜索器分配u r l 。按照系统设 计规模的大小，u r l 可以是多个u r l 搜索队列，也可以是一个u r ls e r v e r 。如g o o g l e 搜索 引擎系统就是采用的是u r ls e r v e r ，以达到更快的处理速度。u r l 处理模块主要有三个数据 来源：1 ) 初始的种子u r l 集；2 ) 从u r l 提取模块传输过来的u r l 集合，它们是从已经采集剑 的页面中提取出来的；3 ) 通过中页面的m e t a 、主题以及摘要等中提取信息，它 j 主要川来 显示从u r l 提取器中传输过来的u r l 的重要性，为在这里排序提供依据。另外，u r l 处理模 块还有一个任务就是d n s 解析。 2 协议处理模块 目前流行的协议有h t l ef r p ，g o p h e r 等。一般大型的搜索引擎主要关心的是h t t p 协 议的内容，还有专门处理f t p 协议的搜索引擎。因此，协议处理模块就是根据需要得剑相 应的内容。对于一般的搜索系统米说，就是保留h r r p 协议的内容。 3 网页下载模块 为了便丁进行分析，需要将网页- 卜载剑本地系统中。在j a v a 语言中，可以通过s o c k e t 网络编程实现。我们可以创建一个u r l 对象，然后通过它读取w w w 资源，这时我们将使 用u r l 的方法o p e n s t r e a m 0 ，具体运川如下： p u b l i cv o i dg e t c o n t e n t ( s t r i n gs ) u r lu r l = n e wu r n ( h t t p ：w w w a j n u e d u c | l | ) ；构建一u r l 对象 b u f f e r e d r e a d e ri n = l l e wb u f f e r e d r e a d e r ( n e wi n p u t s t r e a m r e a d e r ( u r l o p e n s t r e a m 0 ) 1 使朋o p e n s t r e a m 得到一输入流并由此构造一个b u f f e r e d r e a d e r 对象 s t r i n gi n p u t l i n e ； w h i l e ( ( i n p u t l i n e = i n r e a d l i n e 0 ) f - n u l l ) 从输入流不断的读数据，直到读完为j r s y s t e m o u t p r i n t l n ( i n p u t l i n e ) ； 把读入的数据打印剑屏幕上 i n c l o s e ( ) ；关闭输入流 ) 同样，我们也可以利用类似的方法将网页信息保存为文本文件或是数据库中。 2 1 2 网页预处理模块 这个模块的主要功能有两个：一是净化网页，提取网页中核心部分正文内容。一般 网页中含有过多的广告信息。如果这些信息也被记录下来，将会影响主题相关度计算的精度， 同时这些无效的链接信息被w e bs p i d e r 分析，也会造成不必要的资源浪费代价。二是重复 内容检测，因为w e b 上存在着大量的镜像页面和内容，最近的研究表明，将近3 0 的页面 是重复的，这极大的浪费了网络带宽利影响了系统的效率。所以，重复内容检测构成了搜索 引擎，特别是大型的搜索引擎系统的重要组成部分。目前采用的检测方法，根据系统的需要， 可从简单的段落匹配剑复杂的相似度算法中选择。 5 2 1 3 链接提取模块 对于搜集到的页面，经过重复内容检测后，需要分析其中的链接，并对链接进行必要的 转换( 统一格式化) ，这些任务是由u r l 提取模块来完成。首先判断页面类型，对于类型为 “t e x t 、h t m l 、s h t m l 和h t m ”等的页面进行抽取链接分析。页面类型可由应答头分析得出， 有些网页返l 亓l 的应答信息格式不完整，此时可以通过分析页面u r l 中的文件扩展名米判别 页面类型。网页中需要抽取分析的标记包括 ， ， ， ， ， 和 等。页面链接中给出的u r l 格式可以是多种多样的，可能是完整的包括协议、 站点和路径，也可能是省略了部分内容的，或者是一个相对路径。为处理方便，需要将它们 全部转化为统一的格式。另外，考虑这个模块的设计时，往往使其还带有分析页面的m e t a 信息、a n c h o r 信息、页面的标题、页面的摘要等信息的功能。获取它们主要是为了在没有 对页面内容进行分析的时候，尽可能挖掘m e t a 、结构信息等的语义信息，从而对页面中提 取出来的u r l 的女r 坏，给出一个度量。度量的结果传输剑u r l 处理模块，用丁排序。 2 1 4 数据库存储模块 这个模块主要设置数据存储规范。对丁任何搜索引擎系统来说，存储一定的数据是必 要的，特别是大型搜索引擎系统更是如此。如何设计好一个能够存储海量数据，高效方便的 维护数据是系统的关键。因此，设计这个模块的时候，需要考虑以下几方面：1 ) 经过通用 蜘蛛爬行分析后需要下载的页面、从页面分析得到的u r l 链接、链接文字等信息以什么格 式存储到数据库中，以备以后使1 l 】。2 ) 对数据库中存储的内容还要建立相应的索引，以便 提高效率。3 ) 如果信息量人的内容，在向数据库中存储前，有必要对这些内容进行压缩。 2 2 主题蜘蛛 主题蜘蛛，顾名思义就是专门针对某一个领域、主题进行搜索的，是主题式搜索引擎的 重要组成部分。它除了具有通j l j 蜘蛛的特点外，还具有本身特有的特点。其关键的组成部分 可以分为：中文分词、主题过滤模块( 特征提取和主题相关度计算) 等。因此，在它的系统 结构设计中就要有相应的部分。 6 2 2 1 中文分词 图2 - 1主题蜘蛛的系统结构图 顾名思义，就是将中文文章分解成一个个中文词组。相对英文分词比较复杂，英文分词 可以根据单词之间的空格分开，而中文文章中各个词组之间，f ：没有空格。中文分词白8 0 年 代以来得到广泛的关注，目前以产生多种不同的分词算法。对于基丁采用网页相关度分析的 主题蜘蛛来说，中文分词模块是必不可少的。这个模块设计的好坏也会关系到整个w e b s p i d e r 的性能，因为分词最直接的方法就是运_ l j 字典进行，而中文词语有十多万个，这就需 要很人的内存开销。如何设计一个赢效的分词模块将会在第四章中重点介绍。 2 2 2 主题过滤 在主题过滤模块中，我f f j 的主要目的是为了保证主题蜘蛛得到的网页能够尽量向主题靠 拢，系统对爬行到的网页按不同主题进行相关性评价，将属丁二某类主题的网页保存到本地数 据库中，而将主题相关度较低的网页( 小于设定的阙值) 剔除，这样就不会在下一步爬行中处 理该页面中的链接。因为一个页面的主题相关度如果很低，说明该网页很可能只是偶尔山现 某些关键词或者直接与某个主题没有太人的关联。采用主题蜘蛛得剑网页的方式与普通蜘蛛 方式有根本区别：普通蜘蛛采取的爬行方式是根据指定的u r l 进行搜索，对所有链接进行 分析处理，结果返同了大量无川的网页，而且进一步增加了系统开销；主题蜘蛛爬行方式则 是计算每个网页与某个主题的相关度，然后根据主题相关度的高低，选取较高相关度的网页 进行爬行并存储，那些相关度低的网页直接抛弃，因为其中的链接与主题关联的意义不大。 在主题过滤模块中可采用的主题算法很多，我们将采用的是向量空间模型的算法，另外还会 涉及到其他一些关键技术如特征提取、权重计算等等，将会在第五章中详细讲解。 7 2 3 性能瓶颈分析 w 曲s p i d e r 是搜索引擎和信息检索系统的信息搜集代理，是系统中相当重要的组成部 分。w e bs p i d e r 的实现原理很简单，一个w e bs p i d e r 的基本工作流程如上所述，可参照图 2 1 和图2 2 。 但设计和实现一个好的、有实用价值的w e bs p i d e r ，面临着许多方面挑战的。这包括： 设计一个高度优化的系统结构( 实现高性能) 、提高希i 网络利用的效率，保证系统的稳定 性和健壮性。几乎所有大型通用搜索引擎的w e bs p i d e r 都有一个高度优化的系统结构，因 为现在的w e b 静态网页规模非常巨大，w e bs p i d e r 的爬行速度直接决定了搜索引擎的服务 质量，即索引网页数据库的覆盖率和新鲜度。目前，大型通用搜索引擎均采圳分布式的w e b s p i d e r ，利用多机并行工作，极大提高w e bs p i d e r 的爬行速度。对于研究主题式搜索引擎的 研究人员来讲，也需要一个良好设计的w e bs p i d e r ，因为研究人员设想的许多好的爬行策略 都需要一个犬的数据集来验证。一f 面是在设计时需要考虑的几个方面。 2 3 1 网络通信延迟 在下载网页时，w e bs p i d e r 通过网络向w e b 服务器发送h ，r r p 服务请求，w e b 服务器 处理该请求后，将数据包传输给w e bs p i d e r 所在的土机。这一过程在稃序中的实现是通过 调川操作系统的加操作来完成的。对于阻塞式操作，w e bs p i d e r 进程将被阻塞，以等 待操作的完成。在这种情况下，对于每一个h t r p 服务请求，c p u 和网络都要有一段时 间的空闲。为了避免阻塞在一个操作上，我们采用多线程机制，让w e bs p i d e r 同时启动 多个线程，这样就可以并发地向多台w e b 服务器发送请求并且并发地处理w e b 服务器的返 回响应，从而大大提高了w e bs p i d e r 的爬行速度弗且充分利t l j 网络带宽。 除了上述采_ h j 的多线程机制外，还可以像g o o g l e 的w e bs p i d e r 采用单线程与异步 操作来并发执行多个请求，但这种设计的程序结构比较复杂。不过两种技术殊途同归，都能 得到同样的效果。 在j a v a 语言中设计多线程机制比较方便，因此我们将采_ 【 j 多线程技术米提高w e b s p i d e r 爬行效率。 2 3 2 礼貌爬行闯题 所谓礼貌爬行问题就是当一个w e bs p i d e r 向同一个w e b 服务器同时发出多个h r r p 请 求( 即同时建立多个t c p 连接) 或在短时间内下载人量数据时，将会造成该w e b 服务器的负 载过大，这样有可能导致w e b 服务器的崩溃或拒绝服务( 因为有些w e b 服务器内运行了入侵 监测系统，对同时过多的来自同一主机的t c p 连接会被认为是入侵行为) 。为避免这个问题 的发生，在设计w e bs p i d e r 时，必须限制w 曲s p i d e r 并发地向同一w e b 服务器发出h r r p 请求的数量。 在本文的w e bs p i d e r 设计时，将采取两方面的措施：一是为每个： 作线程( 专门负责发 8 送h t r p 请求并下载网页的线程1 设置一个待访问u r l 队列，所有主机地址都相同的u r l 放入同一个队列中，即每个队列的u r l 指向同一w e b 服务器，这样可以保证在任意时刻只 有一个工作线程和某一特定的w e b 服务器连接；二是在蜘蛛管理器( 负责监控所有的工作线 程) 所维护的工作线程状态表中增加一项“通信时间间隔”项，用来记录某个工作线程与它 所连接的w e b 服务器的通信时间间隔，并监控每个工作线程的通信时间间隔，如果通信时 间间隔小于事先规定的值时，将对应的一i ：作线程暂时放入j ：作线程的等待队列中，以等待时 间间隔人于事先规定的值后，唤醒等待的工作线程继续与所迮接的w e b 服务器进行通信， 这样可以防止短时间内从某一w e b 服务器上去下载大量数据。 2 3 3 域名解析 一个w e bs p i d e r 在与一个w e b 服务器建立连接前，必须使用域名解析服务( d n s ) 将w e b 服务器的主机名映射为一个i p 地址。另外，每次新发现的u r l s 在进行u r l 是否已访问的 判断前，也要通过d n s 米获取u r l 的主机名。在多线样的机制f ，许多一l ：作线程都向本地 d n s 服务器发出d n s 请求，会给本地d n s 服务器造成很人负荷。这样，域名解析也就可 能成为系统的性能瓶颈。解决这个问题的方法，一般是在w e bs p i d e r 土机上建立缓存区存 放d n s 结果米缓解这个问题。另外，许多w e bs p i d e r 都编写了自己的d n s 解析器，如康 柏系统研究中一5 , ( s r c ) 的m e r c a t o r 就是使用自己编写的多线程d n s 解析器，极人缩减了每 个工作线程在d n s 查找上所花的时间，从而使域名解析不再成为一个性能瓶颈。 本文的w e bs p i d e r 在实现时，也是采取了d n s 结果缓存机制，即在解析u r l 时，先 在本机的缓存区中查找，如果朱命中，才向本地d n s 服务器发出d n s 请求。 9 第三章主题搜索策略 主题搜索引擎的资源搜索范围限于特定的范围，因此其w e bs p i d e r 的搜索策略是希望 能在相对较少的采集次数中获得尽可能多的本领域相关资源。本章所需要解决的问题有：一 是种子页面的获取，它的好坏关系到主题蜘蛛采集资源的精确度：二是采_ l i j 什么样的搜索策 略，比较了传统丈型搜索引擎采刚的策略和主题搜索目前比较流行的策略。 3 1 种子页面的选取 种子页面即主题蜘蛛爬行的起始页面，每个种子页面是这样的一个网页，它的整个内 容比较集中的反映了某一个领域、主题的相关知识，既可以是一个网站的首页，也可以是网 站下的子页面。这里叫“种子页面”而不是“种子站点”，就是为了突出爬行起点的专指性， 缩小爬行范同，提高爬行效率。种子页面的选择将直接影响主题蜘蛛搜索的质量，为此，要 求种子页面具有较高的主题相关性以及主题链接的中心度。目前，常用的有3 种方法可以生 成种子页面：人- j ：指定，即由某个领域的权威专家给山相关的种子页面，也称为样板页面 ( s a m p l e u r l ) ：白动生成，根据_ l j 户指定的部分关键词( 如：“信息技术”、“氧化反应”、 “匀速运动”等) ，并将这些关键词提交给通用搜索引擎( 如g o o g l e ) ，从检索结果中抽取 前n 个页面作为种子页面：混合模式，即人工指定与自动生成相结合，首先利_ h j 通用搜 索引擎获得部分相关页面，然后经人：i ：筛选、过滤、合并、评价，形成一个能充分反映主题 特征的种子页面集1 。 构造种子页面是一个复杂的过程，以上方法也有一定的局限性，最好的策略是增加土题 蜘蛛的学习能力。通过建立各个领域的主题种子页面库，并对检索历史、用户反馈信息进行 分析的基础上，动态优化的产生相应主题的种子页面集。 3 2 搜索策略概述 w e bs p i d e r 对w e b 的搜索是一个循环迭代的过程：w e bs p i d e r 首先从一个“种子页面 集”( 如用户查询的关键字、种子链接或种子页面) 出发，通过 r r r p 协议请求并下载w e b 页面：预处理器负责解析w e b 页面、链接u r l s 、提取链接文本和有关结构信息；链接评价 器按照某种评价方法( 如链接文本与预先定义的主题集合的相关度) 米计算山每个链接的价 值；暂时未被访问的链接被暂时存放在一个u r l 优先权队列中，u r l 的优先权由控制器按 照某种策略决定，继续下一步要访问的u r l ；当网络蜘蛛获得新选定的链接时，以上过程 重复进行 李春旺，w e b 信息主题采集技术研究，图书情报工作，2 0 0 54 1 0 3 2 1 传统搜索策略 传统的网络蜘蛛都是非常依赖于图算法，如广度优先或深度优先遍历来搜索w e b ，因 为它最终的目标是遍历整个互连网，所以网页的内容很少被注意，如图3 - 1 为传统的网络蜘 蛛沿着每个链接，典型地应用宽度优先策略，如果网络蜘蛛从离目标文档第i 步的一个初始 文档开始，那么从初始文档起的i 1 步的所有文档应该己经下载完毕。 1 深度优先策略 这种搜索策略是从初始种子页面山发，一直搜索到那些不包含任何超级链接的页面为 止，这算是一个完整的过程，然后再返回其中的一个页面，再继续选择该文档中的其它所有 超级链接，循环往复。它结束的标：占是所有搜索剑的页面部不再有含有其它超级链接。深度 优先策略能够产生较好的页面分布，更容易发现页面之间的结构。因为w e b 结构相当复杂， 而且每天的增加量也1 常惊人，因此深度优先搜索策略在实现上所需要_ l j 的空间开销及函数 调_ l i j 的时间开销非常惊人。 2 i 度优先策略 在广度优先搜索中，先搜索完一个w e b 页面中所有的超级链接，然后再继续下一层的 搜索，直剑最底层为止。具体实现做法是：取得u r l 对列中的一个u r l 地址，下载该网页 并进行相应的预处理，在该网页中找出所有指向其它网页的链接，将找剑的链接与屏敞的 u r l 地址列表作比较，如果不是搜索范围内的地址，则丢弃，否则看该地址是否己被搜索 过，若己被搜索过，对其引_ | j 计数值加l ，形成下一次搜索时的待搜索地址的优先权加权值， 若还朱被搜索过，则将该地址加入到近期已搜索的w e b 站点地址列表或待搜索的地址列表 中。广度优先策略能找到两个w e b 页面之间的最短路径，可以跟踪当前页面中的每一个 u r l ，所以能覆盖尽可能多的网页。这种策略的缺点是对丁深层次的w e b 页面往往要花很 长的时间才能剑达。2 3 有限深度j “度优先算法 针对以上两种策略各自的优缺点，可采取有限深度矿度优先策略，在检索过程中限制 采集的厂度或深度，是种比较实_ h j 的遍历策略。 3 2 2 主题搜索策略 主题式搜索引擎的网络蜘蛛的设计目标是搜索与特定主题相关的网页，它一般基于内容 和链接来有效地指引搜索。主题蜘蛛每搜索分析完一个页面之后，将会从该页面中得到很多 的u r l ，但是并不是所有的u r l 所对应的页面都是与主题相关的。因此，为了在搜索主题 资源的同时需要进行有效地剪枝，我们就需要对己有的相关信息进行分折和处理，用米预测 u r l 所对应的页面的主题相关度，根据最终所得的相关度值对u r l 进行排序或者剔除。由 于主题式搜索引擎搜索的内容只限丁特定主题或专门领域，因而被通用搜索引擎所广泛采【 j 的基于图的遍历搜索策略( 如广度或深度优先算法) 已不再适朋。以何种策略访问w e b 成 为近年米主题式搜索引擎的网络蜘蛛研究的热点之一。近年来，研究人员发明了不少实用的 2 洪光宗，王皓，搜索引擎r o b o t 技术实现的原理分析，现代图书情报技术，2 0 0 2 1 主题搜索策略的算法，下面介绍几种比较流行的算法。 1 基于内容评价的搜索策略 由于w e b 检索类似于传统信息检索中的文本检索，有些学者考虑利用文本相似度的计 算方法评价页面文本与主题集合之间的相似程度。d eb r a 3 等将这一思想引入网络蜘蛛的搜 索策略，提出算法f i s h - s e a r c h 。它将用户输入的查询关键词或短语作为主题，将包含查询串 的页面看作与主题相关，且仅搜索主题相关页面。这种方法的局限性在于不能评价页面与主 题相关程度的高低，h e r s e o v i c 对f i s h s e a r c h 算法进行了改进，采用基于连续值的相似度函 数计算链接价值，这样不但可以计算出哪些页面与主题相关，还可得出相关性的大小。类似 地，c h o4 提出了b e s t - f i r s t 算法，利_ i j 向量空间模型计算页面与主题的相似度，相似度的评 价采_ i j 以下公式： s i m ( p ，g ) = 蛔1 p 压了忑了 ( 3 - 1 ) 其中，q 代表主题关键词集合，p 代表页面链接文本集合，w k d 代表集合d 中单词k 对某一 主题的重要程度，w k d 通常采删公式t f * i d f 计算。 2 基于链接结构评价的搜索策略 考虑到w e b 页面是一种半结构化的文档，其中包含许多结构信息，有些学者尝试利_ i j 这些结构特征来评价链接的重要性。p a g e r a n k 方法最初圳于搜索引擎信息检索中对查询结 果的排序过程，近年米被应用于网络蜘蛛对链接重要性的评价。在p a g e r a n k 方法中，页面 的价值通常用页面的p a g e - r a n k 值表示，若殴页面p 的p a g e r a n k 值为p r ( p ) ，则p r ( p ) 采_ l f j 如一1 - 迭了记公式计算： p r ( a ) = ( 1 - d ) + d ( p r ( t1 ) c ( t1 ) + + p r ( t n ) c ( t n ) ) 在此p r ( a ) 是网页a 的p a g e r a n k ；t l 是链点指向网页a 的网页； p r ( t 1 ) 是网页t l 的p a g e r a n k ； c ( t 1 ) 是自网页t l 的外向链接的数量； d 是权重因子，取0 d l ，通常取0 8 5 ； p r ( t n ) c ( t n ) 为链接指向网页a 的网页t n 与网页a 的网页级别值，亦称m i n i p a g e r a n k 。 因此，某一网页a 的p a g e r a i l i c 为其它网页t n ( 链接指向网页a 的网页) 的p a g e r a i l l c 除去t n 网页外向链接的数量后的总和。 基于p a g e - r a n k 方法的网络蜘蛛在搜索过程中，通过计算每个已访问页面的值米确定页 面的价值，并每次选择p a g e r a n k 值大的页面中的链接进行访问。 3 b r a dp h o u b e n q k o m a t z k yc ta 1 i n f o r m a t i o n r e t r i e v a l i n d i s t r i b u t e d h y p e r t e x t s c i n ：p r o c o f t h e 4 r i a o c o n f e r e n c e , 1 9 9 4 4 c h o j , g a r c i a - m o l i n a h p a g e l e f f i c i e n t c r a w l i n gt h r o u g h u r l o r d e r i n g j c o m p u t e r n e t w o r k s ，1 9 9 8 ，3 0 ( i - 7 ) ：1 6 1 1 7 2 1 2 另一种利用w e b 结构特征评价链接价值的方法是h i t s ( h y l x t l i n k 2 i n d u c e dt o p i cs e a r c h ) 方法。1 9 9 9 年k l e i n t c r 9 5 提出了h i t s 算法来评定网页内容的重要性。他认为网页的重要性 应该依赖于用户提出的检索主题，而且对每一个网页应该将其a u t h o r i t y 权重( 由网页的 o u t l i n k 决定) 和h u b 权重( 由网页的i n l i n k 决定) 分开来考虑。根据页面之间的超链接结 构，将页面分为h u b 页和a u t h o r i t y 页，其中h u b 页是一个指向权威页的超链接集合的w e b 页，而a u t h o r i t y 页是被许多h u b 页指向的权威的w e b 页。因此，一个h u b 页应该指向 许多好的权威页，而被许多h u b 页指向的一定是权威页。这种h u b 与权威页面之间的相互 作用，可用于权威页面的挖掘和高质量w e b 结构和资源的自动发现。具体算法描述如下： 首先，h i t s 由用户的检索主题得到一初始结果集，构成算法的根集( r o o ts e t ) 。比如由 基于索引的搜索引擎进行查询。一般地，根集页面取2 0 0 个左右即可。 其次，将根集进一步扩展为基本集( b a s es e t ) ，它包含了所有由根集中的页面所指向的 页，以及所有指向根集页面的页。可以为基本集设定一个上线，指明扩展的尺度。 最后，按熙公式( 1 ) 、( 2 ) 递归地计算基本集中每个页面的a u t h o r i t y 权重a d 和h u b 权 重l l p 其中，a p 和l l p 值初始为同一个常数。根据线性代数理论，可以证明a p 和h p 与权 重的初始设置无关。 a p o ) _ h 。o ( 3 1 ) v q ：q - - p h p o “) _ 函“1 ( 3 - 2 ) 坳：，_ q 其中，p q 是指由页面p 指向q 的超链接。 两类策略的共同点是利用页面之间的引用关系确定链接的重要性，本文闪此称其为基丁 链接结构评价的搜索策略。这类搜索策略的优点是考虑了链接的结构特征，但也存在一些缺 陷：一是忽略了页面与主题的相关性，在某些情况卜，会出现搜索偏离主题的“主题漂移” 问题6 ；二是在搜索过程中需要重复计算p a g e r a n k 值或a u t h