（计算机应用技术专业论文）主题搜索引擎中网络蜘蛛搜索策略研究.pdf

浙江大学硕十学位论文摘璺 摘要 随着w e b 上多元化信息的增长，传统的搜索引擎，即通用搜索引擎已经不 能满足人们对个性化信息检索服务日益增长的需要。近年来，面向主题的搜索引 擎应运而生，以提供分类更细致精确、数据更全面深入、更新更及时的凶特网搜 索服务。 在主题搜索引擎中，网络蜘蛛以何种搜索策略访问w e b ，以提高效率，是近 年来主题搜索引擎研究中的热点问题之一。而w e b 的动态性、异构性和复杂性 要求网络蜘蛛能够高效率地实现w e b 信息提取，以保证信息的实时性和有效性。 该文对主题搜索引擎中的网络蜘蛛搜索策略进行了详细的分析，在深入分析 主题页面在w e b 上的分布特征与主题相关性判别算法的基础卜，提出了一个面 向主题搜索的网络蜘蛛模型，对模型的组织结构进行了详细阐述。 作为主题网络蜘蛛搜索策略的核心部分，主题相关性判断算法是刚络蜘蛛能 够围绕设定丰题进行聚焦检索的关键。在u r l 的j 二题相关性判别过程中，引入 了链接文本及相关链接属性分析，提出了一种薪颖的u r l 主题相关性剪枝算法 一e p r 算法。而对于网页的主题相关性判别，则使用目前较为常用的向量空间模 型进行判别。 主题搜索引擎对数据实时性的要求要远远高于通用搜索引擎，因而，增量 w e b 信息提取算法也是主题网络蜘蛛搜索策略的重点。该文提出了一种全新的基 于索引页的增量w e b 信息提取算法，能够有效地发现w e b 上新增加的网页。 实验结果表明该文的工作是相当有效的，尤其是提出的e p r 算法和基于索 引页的增量w e b 信息提取算法，具有相当的创新性和实际应用价值。 关键词：搜索引擎，网络蜘蛛，搜索策略，主题提取，索引页，增量提取 浙江犬学硕 学位论文a b s t r a c t a b s t r a c t w i t hw e bi n f o r m a t i o nc o n t i n u i n gt oe x p l o d ei na l ld i r e c t i o n s ，t r a d i t i o n a ls e a r c h e n g i n e c a n t k e e p u pw i t h t h em o t ea n dm o r er i g o r o u sa n dp r o l i f i cs e a r c h r e q u i r e m e n t sf r o md i f f e r e n tu s e r s r e c e n t l y , t o p i c d r i v e ns e a r c he n g i n ei sp r e s e n t e dt o p r o v i d ean e w s e a r c hs e r v i c e ，w h i c hi sb e t t e rc l a s s i f i e d ，c o n t a i n i n gm o t ep r o f o u n da n d f o c u s e dd a t a ，a n db e i n gu p d a t e di nt i m e n o w a d a y s ，t h ew e bs e a r c hs t r a t e g yo ft h ew e bs p i d e ri nt o p i c d r i v e ns e a r c h e n g i n e a r c h i t e c t u r ei s r e a l l y h o ti nr e s e a r c h t h e d y n a m i c ，c o m p l e x ，a n d s e m i - s t r u c t u r e dp r o p e r t i e so fw e br e q u i r et h ew e b s p i d e rt og a t h e rd a t ae f f i c i e n t l yt o k e e pt h ei n f o r m a t i o nu p d a t e da n dv a l i d b a s e do no u ri n d e p t hr e s e a r c hi nt h es e a r c hs t r a t e g yi nt o p i c - d r i v e ns e a r c h e 1 【g i n ea n dt h et o p i cr e l a t i v i t yj u d 百n ga l g o r i t h m s ，t h i sa r t i c l ep r e s e n t sas t r u c t u r e d e s i g nm o d e lo ft h et o p i c - o r i e n t e dw e bs p i d e ra n dt h e na n a l y z e si ti nd e t a i l a st h ek e yc o m p o n e n to fs e a r c hs t r a t e g yi nt o p i c - o r i e n t e dw e bs p i d e r , t h et o p i c r e l a t i v i t yj u d g i n ga l g o r i t h m se n s u r et h ef o c u s e dw e bc r a w l i n gp r o c e s so ft h es p i d e r i n t h ep r o c e s so fr e l a t i v i t yj u d g i n gb e t w e e nu r la n dt o p i c ，an o v e lu r lp r u n i n g a l g o r i t h m - e p ra l g o r i t l m li sp r e s e n t e db a s e do nt h ea n a l y s i so na n c h o rt e x ta n do t h e r p r o p e r t i e s t h ep o p u l a rv e c t o rs p a c em o d e li su s e dt oc t a s s i f yh t m lp a g ef r o m d i f f e r e n tt o p i c s t o p i c d r i v e ns e a r c he n g i n ei ss u p p o s e dt op r o v i d et h eu p d a t e dw e bi n f o r m a t i o n ， s ot h ei n c r e m e n t a lw e bc r a w l i n gi sa l s ov e r yi m p o r t a n ti nt h es e a r c hs t r a t e g yo f t o p i c o r i e n t e dw e bs p i d e r i nt h i sa r t i c l e ，an o v e li n c r e m e n t a lw e bc r a w l i n ga l g o r i t h m b a s e do ni n d e xp a g ei sp r e s e n t e dt of i n dn e wa d d e dw e bp a g e s q u i c k l y t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h er e s e a r c hw o r ko ft h i sa r t i c l ei se f f e c t i v e ， e s p e c i a l l yi ne p ra l g o r i t h ma n dt h ei n c r e m e n t a lw e bc r a w l i n ga l g o r i t h mb a s e do n i n d e xp a g e ，w h i c ha r er e a l l yc r e a t i v ea n dv a l u a b l ei nr e a la p p l i c a t i o ne n v i r o n m e n t k e y w o r d s ：s e a r c he n g i n e ，w e bs p i d e r , s e a r c hs t r a t e g y , t o p i cd i s t i l l a t i o n ， i n d e xp a g e ，i n c r e m e n t a lc r a w l i n g 2 浙江人学硕_ 学位论文第一章绪论 1 1 背景 第一章绪论 随着i n t e m e t 的快速发展，网络正在深刻地影响着我们的生活。而在网e 发 展最为迅速的w w w ( w o r l dw i d ew e b ) 技术，以其直观、简单、高效的使用方式 和丰富的表达能力，已逐渐成为i n t e r n e t 上最重要的信息发布和交互方式。随着 信息时代的到来和发展，w e b 上的信息j 下在飞速地增长。截止到2 0 0 3 年7 月， i n t e m e t 上的网页数量就已经超过3 0 亿，上网用户数量超过5 2 亿，而且网页还 在以每天7 0 0 万的速度增加，这带给了人们前所未有的丰富的信息资源。 然而，w e b 信息的急速增长，在给人们提供丰富信息的同时，却在w e b 信 息的高效便捷使用方面给人们带来巨大的挑战：一方面w e b 上的信息种类繁多、 丰富多彩，而另一方面却很难找到真正有用的信息。 1 1 1 通用型搜索引擎 为此，人们发展了以w e b 搜索引擎为主的w e b 搜索服务。为了解决网上信 息检索的难题，人们在信息检索领域进行了大量的研究，开发出了各种搜索引擎 ( 如g o o g l e ，a l t a v i s t a ) 。这些搜索引擎关注广大用户的搜索需求，因而也被称为 通用搜索引擎。它们通常使用个或多个的w e b 信息提取器( 网络蜘蛛) 从 i n t e r n e t 上收集各种数据( 如w w w , n e w s ，e m a i l ，f 1 1 p ) ，然后在自身服务器上为 这些数据创建索引，当用户搜索时根据用户提交的查询条件从索引库中迅速查找 出所需的信息返回给用户。 1 1 1 1 通用搜索引擎分类 目前通用的搜索引擎就查询方式的不同，可以分为两类： 1 、关键词检索 关键词检索使用的是全文检索技术，它将w e b 看作一个大规模的全文数据 库。在其中，张网页对应多个关键词。然后采用关键词匹配进行信息检索。它 通常由网络蜘蛛s p i d e r ( 也叫r o b o t ，c r a w l e r ) 提取网页信息，加以处理后入库。用 户搜索使用时非常方便，只需要输入关键词即可，搜索引擎检索网页数据库后返 回查询结果，结果中一般包括了w e b 页面标题和u r l 信息，同时根据相关性进 行了降序排列，以便于用户选择。由于关键词索引是直接从原文中抽取的，加之 每个人对于一个主题的描述存在着很大的差异，而且关键词之间又没有语义的联 系，所以关键词检索在查询特定概念时效果不好，准确性差。关键词搜索引擎的 典型代表是a l t a v j s t a 。 浙江人学硕j ：学位论文第一章绪论 2 、目录浏览检索 这类搜索引擎提供了一份按类别编排好了的互联网网址目录，在各类目下排 列着属于该类的网站站名和u r l 信息，y a h o o ! 是它们最著名的代表。这类搜索 引擎并不收录网页的全部内容，而是由人工摘录一些核心信息。在搜索时用户通 过浏览目录获得自己所需信息。它有着目录结构清晰、内容准确的突出优势，尤 其适用于那些希望了解某一方面信息而不希望通过关键字进行检索的用户。由于 采用了人工分类，缺点也是显面易见的，在这类搜索引擎中，分类体系不规范、 交叉类目容易遗漏、数据更新不及时的现象比较多见。 l 112 通用搜索引擎基本工作原理 现在实际使用的搜索引擎都综合了上面提到的两种检索方式。搜索引擎通常 由三个子系统组成，如图1 1 所示 i 信息采集 l l 信息处理 1 分析查啕1 s p i d ”i + l 建立索引 l 7 弋 一尝 j r 一 ， ( 兰y 一 围习 乡 剌库f u 图1 1 搜索引擎工作流程图 1 、网络蜘蛛s p i d e r 网络蜘蛛s p i d e r ( 也称为r o b o t 或c r a w l e r ) 实际上是一个基于w e b 的程序， 它从一个初始网页集出发，遍历i n t e r n e t 自动地采集网络信息。特别的，当s p i d e r 打开某个h t m l 页面时，它会分析h t m l 标记结构来获取信息，并获耿指向其 它页面的超级链接，然后通过既定的搜索策略选择下一个要访问的站点。从理论 上讲，如果为s p i d e r 指定一个适当的初始文档集和一个适当的网络搜索测罗，它 就可以遍历整个网络。 2 、索引模块 索引模块对网络蜘蛛提取的网页进行处理，创建索引后入库，以备用户检索 使用。处理网页的过程主要包括这几部分：文档特征向量提取、网页筛选、相关 度分析、文档分类和入库操作。 3 、检索模块 检索模块是搜索引擎和用户之间的接口，其首先获取用户查询条件并加以分 析，然后访问索引数据库进行匹配后获得检索结果，然后根据设定的相关度进行 降序排序处理后返回给用户。 浙江大学硕卜学位论文第一章绪论 1 1 1 3 元搜索引擎 元搜索引擎是一种调用其它独立搜索引擎的引擎，它是用户同时利用多引擎 进行网络搜索的中介。元搜索引擎不需要网络蜘蛛遍历i n t e m e t 提取信息，也不 需要维护页面索引数据库。 在检索时，元搜索引擎根据用户提交的检索请求，调用源搜索引擎( 各个独 立的搜索引擎) 进行搜索，对搜索结果进行汇集、筛选、删并等优化处理后，以 统一的格式在同一界面集中显示。总之，元搜索引擎是对多个独立搜索引擎的整 合、调用、控制和优化利用。典型的元搜索引擎应用框架结构如图1 2 所示： l 搜索引擎1 卜、j 查询式处理l 。人 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ i 搜索引擎2 卜一 w e b 、 龆卜 l 用 + | 户 处理 、 结果生成 接口 。 i 搜索引擎。p 图1 2 典型的元搜索引擎框架 元搜索引擎系统既没有网络蜘蛛也无需网页索引数据库，因而大大降低了对 硬件的要求。由于综合采用了多个搜索引擎的搜索服务，元搜索引擎的查询结果 在一定程度上可以弥补单个搜索引擎的不足，但这并不能使网上信息检索技术得 到质的飞跃。元搜索引擎只是提供了搜索结果的重新组织，它本身的发展也遇到 了很多的困难。 首先，元搜索引擎在向各个源搜索引擎提交查询要求前，需要处理查询格式， 将其转变为各个源搜索引擎能够识别的格式。但是大部分搜索引擎的查询格式互 不兼容，这使得查询格式处理变得异常复杂。 其次，各个源搜索引擎返回的结果格式不一，结果中的相关度排序算法也各 不相同，这就使得元搜索引擎对最后的结果综合处理上变得非常的困难复杂。 1 1 1 4 通用搜索引擎的发展趋势 在网络最初发展的发展阶段，大量功能相似的搜索引擎不断涌现。后来由于 商业运作上的考虑，大多都发展成为了网络门户网站，同时提供了许多其它的内 容例如新闻等。后来随着人们对网络经济的过高预期，人们对门户网站非常热衷。 相比之下，搜索引擎的开发成本相当高，而且开发的产品用户面不广，仅仅是为 少数几家公司提供搜索服务。所以很多公司放弃了对搜索引擎技术的开发，专注 于经营门户网站，并取得了很大的成功。y a h o o ! 就是一个非常成功的例子。 第二代搜索引擎中的代表是g o o g l e ( w w wg o o g l c c o r n ) 。随着网络规模的进一 浙江人学硕j ：学位论文第一章绪论 步扩大，搜索引擎变得越来越被人们所需要。g o o s e 由s t a n f o r d 大学的l a r r yp a g e 和s e r g e y b r i n 设计，1 9 9 9 年正式开始商业运营，由于g o o g l e 提供了简单易用的 用户界面并保证了返回结果和用户搜索需求的高度相关性，它取得了极大的成 功。g o o g l e 提供了一系列革命性的新技术，包括完善的文本对应技术和先进的 p a g e r a n k 排序技术，后者保证了人们能够在返回结果的前1 0 个中找到需要的信 息，正是p a g e r a n k 技术使得g o o g l e 大受欢迎。y a h o o ! 后来宣布不再采用i n k t o m i 提供的搜索服务，而转而采用g o o g l e 的搜索引擎服务，此举更强化了g o o g l e 在 搜索领域的领先地位。 随着第二代搜索引擎的逐步成熟，目| j i ，第三代引擎也进入了研制阶段。第 三代搜索引擎的最大特点就是大量智能化信息处理技术和个性化搜索服务理念 的引入，网络搜索服务将步入知识检索和知识服务的领域。数据、信息、知识是 属于三个不同层面的概念。知识是和用户能力及经验紧密结合的、能够用于解决 问题和创造新知识的信息组织。现代搜索引擎的发展目标就是要把散落在互联网 上的不相关的数据搜集起来，经过筛选、组织和分析，发现知识并返回给用户。 在数据库层面的知识发现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 早己出现，如何 将k d d 的现有技术和理论移植到w e b 知识搜索上，是摆在我们面前的一个难题， 也是第三代搜索引擎的发展方向【韩家炜等2 0 0 1 】。 w e b 自面世以来短短的1 0 年期间之所以如此蓬勃发展，其中的大原因就 是它上面蕴涵了包括图形、图像、声音、影像等大量的多媒体资源。多媒体信息 较之普通文本信息而言，信息量更大，表现上更为形象，对用户的说服力和吸引 力也更强。目前由于大量多媒体资源的表现形式非常复杂，而且形式各异，当前 多媒体信息的搜索系统没有达到令人满意的地步。 w e b 信息挖掘的一个新兴方向就是自然语言( n l ) 分析技术的应用。现在的 n l 技术已经能够分析良结构( w e u d e f i n e d ) 的句子 w m o 笋a d1 9 8 3 1 ，较好地消除 多义词歧义，在连续文本中标记出词。眭( p a r t o f - s p e e c h ) 信息，并可以写出规范的 机器可识别的自然语言文档 s c h a n k r i e g e r1 9 8 5 和进行自然语言翻译。自然语 言和信息检索技术的结合可以用来自动生成超链 c a t e n a z z i g i b b1 9 9 5 1 ，用相 关词汇扩展查询。但由于计算机在非确定性逻辑处理技术上的还存在着待突破的 瓶颈，流行的w e b 搜索引擎在这些方面进展缓慢。显然而见，更好的语义理解 是搜索引擎今后发展的一个必然趋势。 1 1 2 主题性搜索引擎 1 1 2 1 产生背景 通用搜索引擎的出现很大程度上解决了人们在互联网上查找信息的困难，但 由于其覆盖一切、追求普适的设计目标，已经不能满足人们对个性化信息检索服 9 浙江人学硕士学位论文 第一章绪论 务同益增长的需要。目前，通用搜索引擎在使用中面临着较多待解决的问题： 1 、超大规模的分布式数据源。基于w 曲的自身特点，大量的数据分布在数 以亿计的计算机互联网上，搜索起来非常困难。一般而言，搜索引擎的索引数据 库的覆盖率都低于3 0 ，很难索引所有w e b 资源。业界领先的搜索引擎，如 a l t a v i s t a 和h o t b o t ，1 9 9 9 年2 月时爿索引了不到1 8 的w e b 页面 l a w r e n c e g i l e s1 9 9 9 】，而这个数字，在1 9 9 7 年为3 5 b h a r a t & b r o d e r1 9 9 8 1 。 2 、w e b 信息的质量问题。互联网上的信息无论从数量和类型都呈现出指数 增长的趋势，这导致搜索引擎的实时性很难保证。而大量信息的有效期却在缩短， 这使得搜索引擎的及时性很低，造成搜索引擎返回的结果为无效的( 链接己经删 除) 或过时的( 同一个u r l 指向的页面发生了改变) 。在另一方面，网上大量的 镜像站点和简单应用拷贝电使搜索引擎返回大量无用的信息。这就造成“信息爆 炸，资源匮乏”的现象。 3 、异构的数据。网上搜索需要处理大量的媒体信息，即便是文本信息，其 格式也大不一样。相对于严格定义的结构化数据关系表相比，h t m l 文档是一种 半结构化的数据，其更关注数据的自然表示，而不是数据的内部逻辑处理。h t m l 文档数据的半结构化特点使得w e b 数据挖掘同经典的数据仓库中的数据挖掘明 显区别丌来 j e o n g o h2 0 0 1 1 。同时网上信息还存在多语种问题，例如，亚洲语 言字符的检索一直就是信息检索界的一大难点。 4 、搜索需求的精确表达问题。在信息搜索领域，一个突出的问题就是，用 户很难简单地用关键字来准确表达他所真正需要搜索的内容，表达的困难将导致 检索结果的不理想，同时也使得用户对搜索引擎的搜索服务质量产生不良印象。 5 、搜索引擎的硬件需求越来越高。例如著名搜索引擎a l t a v i s t a 的s c o o t e r 就运行在一个拥有4 个5 3 3 m h z 的c p u ，内存为1 5 g b ，装配有3 0 g br a i d 磁 盘的a l p h a s e r v e r 4 1 0 0 5 3 0 0 服务器上。它的一个索引服务器，则是拥有2 个 5 3 3 m h zc p u ，配有2 g b 内存，1 8 0 g br a i d 硬盘的a l p h a s e r v e r 4 1 0 0 5 3 0 0 服 务器。 随着信息社会的进一步发展，人们对信息的需求又发生了新的变化。近些年 来，科学技术相对于国民经济发展的带动作用越来越显著。高科技企业不断出现， 各个产业的科技含量也越来越高。如何为科技工作者提供最新的科技信息，如何 为商业决策者提供最新的行业相关新闻，对科技的发展和企业的经营壮大，都是 至关重要的。 面对通用搜索引擎发展所遇到的种种困难和人们对信息搜索的新需求，人们 对搜索引擎提出了新的要求： l 、搜索引擎能运行在常规的软硬件设备之上： 2 、只要搜集某一特定学科领域或特定专题的h t e m e t 信息资源即可： 1 0 浙江大学碗上学位论文第章绪论 3 、能够方便地进行搜集主题和学科的自定义配置。 为了满足这些新的搜索要求，主题搜索引擎应运而生。主题搜索引擎只提供 关于某一主题或者领域的w e b 信息，其索引更小，且更易于管理，同时对于专 门领域，却有着强大的搜索功能。 1 1 2 2 主题型搜索引擎 所谓主题型搜索引擎就是以构筑某1 专题领域或学科领域的因特网信息资 源库为目标，智能地在互联网上搜集符合设定专题或满足学科需要的信息资源， 能够为包括专业信息机构、特定行业领域、学科信息门户、行业专家、公司信息 中心等在内的用户，提供一整套的网络信息资源服务解决方案。 主题型搜索引擎和通用搜索引擎存在着巨大的差别： 1 、不同的服务目的 通用搜索引擎面向大众用户，提供对普遍主题信息的查询，而主题搜索引擎 则面向专业用户提供对特定专业领域的信息搜索服务。 2 、不同的搜索方式 通用搜索引擎对网络进行海量的提取，以遍历整个w e b 为目标，而主题型 搜索引擎则采用一定的策略预测对相关网页进行预测，动态调整网络蜘蛛的爬行 方向，使系统尽可能地围绕设定主题进行爬行，从而节约网络资源。 3 、不同的硬件和网络要求 通用搜索引擎的硬件需求通常都很大，而主题型搜索引擎不对整个w e b 进 行遍历，不仅节约了网络资源，而且不需要维持一个大规模的索引数据库，所以 硬件需求相对也比较低。 主题型搜索引擎的实现上存在这两个难点： 第一，起始种子站点和词库的设置。因为主题引擎并不遍历整个w e b ，所以 起始站点集合就显得非常重要。词库作为评价网页是否主题相关的标准关键词的 集合，它的合理配置将对检索结果的准确性产生直接影响。这两个方面的设置是 否合理就决定了主题引擎能否找寻到所有主题相关的w e b 信息。 第二，主题搜索效率的考虑。由于要进行有选择性的w e b 信息提取，那么 由此带来的主题性相关性判断会直接影响主题搜索引擎的工作效率。此外，主题 信息的表示、信息的抽取、主题信息的过滤和主题相关性站点的选择策略都是系 统实现的难点。目前主题搜索引擎大都处于研究和试验阶段，随着研究的不断深 入发展，面向某一学科、领域的网络垂直门户网站已经出现并提供服务。 进行面向主题的网络信息搜索主要有两种技术： 1 、基于内容的搜索。 此类搜索方式是传统信息检索技术的延伸。它的主要方式就是在搜索引擎内 部建立一个主题对应的关键词表，搜索引擎的爬行器根据其内设的关键词表对网 1 1 浙江大学硕士学位论文第一章绪论 上的信息进行索引。各个不同的系统关键词表建设的复杂度也大不相同。现在这 种关键词表的设置越来越多地引入了知识表示的方法。 基于本体论( o n t o l o g y ) 的搜索引擎开始现 p r e t s c h n e re ta l1 9 9 9 】。一个本体 强调相关领域的本质概念，同时也强调概念之间的本质联系。以o n t o l o g y 为基础 建立的关键词表能更好地显示一个领域主题中各个概念( 即搜索系统的检索词) 之间的关系，从而更好地表现一个主题。在主题信息检索应用中，o n t o l o g y 通常 作为用户感兴趣领域的领域模型，同时还可作为文档统镒：释的知识表示语言。 一些学者提出了概念空间的理论，用概念空间来实现语义索引f c h e ne ta l 1 9 9 7 。所谓概念空间是某个领域中一组抽象概念的集合，并且在这组概念之间， 存在着一定的语义上的关联。基于概念空间的文本检索系统较好地解决了信息检 索过程中的词汇不匹配的问题和信息过载问题，极大提高了信息检索的效率和质 量。 2 、基于链接结构分析的检索。9 0 年代末期，国外信息检索界开始以s o c i a l n e t w o r k 为模型对互联网进行检索。一些学者认为网页之间的链接关系同社会关 系网络中的人际关系有着相似之处，特别地与传统的引文索引非常相t 以 g r e c oe t a l2 0 0 2 。 通过对链接结构进行分析，可以找出网页之间的引用关系。由于引用网页与 被引用网页间内容上一般都比较相关，所以就可以很容易地按照引用关系将大量 网页分类。例如在美国，很多基于超链结构分析的检索系统原型己经出现，并应 用于数字图书馆系统中。 1 1 2 3 目前的研究状况 目前，有关主题搜索引擎的研究正在成为一个热点研究领域，f 面介绍一些 较具有代表型的主题搜索引擎系统。 1 e l s e v i e r 公司的s c i r u s 系统 s c i r u s 科学搜索引擎是一个专门为搜索高度相关的科学信息而设计的主题搜 索引擎。s c i r u s 是目前互联网上最全面、综合性最强的科技文献门户网站之一。 它的搜索领域只面向包含有科学内容的网站，如大学和作者个人主页以及 e l s e v i e r 公司自己的数据库。 2 b e r k e l e y 大学的f o c u s ep r o j e c t 这个系统由一个印度裔的科学家s c h a r k r a b a r t i 带头从事开发。该系统通过 两个程序来指导主题网络蜘蛛，一个是主题分类器c l a s s i f i e r ，用来计算下载的文 档与预定主题的相关程度。另一个则是净化器d i s t i l l e r ，用来确定那些链接指向 很多相关资源的页面。 3 、美国的国家科学数字图书馆的c o l l e c t i o n b u i l d i n g p r o g r a m ( c b p ) 该项目旨在为科学、数学、工程和技术创建大规模的在线数字图书馆，试图 浙江大学碗上学位论文 第一章绪论 研究在某一主题资源上自动建设数字图书馆的可能性。c b p 具有三个突出的特 点：第一，由于c b p 项目面向教育、教学，主题精确度( p f e c i s i o n ) 比覆盖度( r e c a l l ) 更为重要；第二，c b p 并不存储资源原文，只是提供资源的u r l 。第三，c b p 只需要用户输入少量信息，如关键词，系统就可以自动的将有关该主题的最相关 的u r l 返回给用户。 1 1 3 网络蜘蛛 作为搜索引擎的基础组成部分，网络蜘蛛起着举足轻重的作用，随着应用的 深化和技术的发展，网络蜘蛛越来越多的应用于站点结构分析、内容安全检测、 页面有效性分析、用户兴趣挖掘以及个性化信息获取等多种服务中。 网络蜘蛛在采集w e b 信息时，通常从一个“种子集”( 如用户查询、种子链 接或种子页面) 出发，通过h t r p 协议请求并下载w e b 页面，分析页面并提取 链接，然后再以循环迭代的方式访问w e b 。网络蜘蛛的搜索策略与搜索引擎的性 质和任务密切相关 a g g a r w a le ta 1 2 0 0 1 1 。为了获得较高的w e b 覆盖率，通用搜 索引擎网络蜘蛛通常采用图的遍历算法( 如广度或深度优先策略) 搜索w e b ，见 图1 3 ( a ) 所示。 与通用搜索引擎不同的是，面向主题的搜索引擎服务于特定人群，其索引的 页面内容仅限于特定主题或专门领域，其在搜索过程中无须对整个w e b 进行遍 历，只需选择与主题页面相关的页面进行访问，见图1 - ：3 所示。主题搜索引擎 网络蜘蛛在搜索w e b 时，需要对站点的主题相关性作出预测和删选，并对网页 的主题相关性作出判断。以何种策略访问w e b ，以提高搜索效率，是近年来主题 搜索引擎研究中的主要问题之 r e n n i e & m c c a l l u m1 9 9 9 。本文的研究重心就 是对主题搜索引擎中的搜索策略进行了详细分析，并提出一个优化的主题搜索网 络蜘蛛模型。 、 f 一( 、口 ( a ) 通用搜索引擎网络( b ) 专业搜索引擎网络 蜘蛛搜索顺序蜘蛛搜索顺序 ( 白框代表主题无关页面，黑框代表主题相关芙页面， 虚线代表链接，实箭头代表访问顺序) 图1 - 3 两类搜索引擎网络蜘蛛搜索顺序比较示意图 浙江大学硕士学位论立第一章绪论 研究在某一主题资源上自动建设数字图书馆的可能性。c b p 具有三个突出的特 点：第一，由于c b p 项目面向教育、教学，_ _ j _ = 题精确度( p r e c i s j o n ) 比覆盖度( r e c a i i ) 更为重要；第二，c b p 并不存储资源原文，只是提供资源的u r l 。第三，c b p 只需要用户输入少量信息，如关键词，系统就可以自动的将有关该主题的最相关 的u r l 返回给用户。 1 1 3 网络蜘蛛 作为搜索引擎的基础组成部分，网络蜘蛛起着举足轻重的作用，随着应用的 深化和技术的发展，网络蜘蛛越来越多的应用于站点结构分析、内容安全检测、 页面有效性分析、用户兴趣挖掘以及个性化信息获取等多种服务中。 网络蜘蛛在采集w e b 信息时，通常从一个“种子集”( 如用户查询、种子链 接或种子页面) 出发，通过h t 邛协议请求并下载w e b 页面，分析页面井提取 链接，然后再以循环迭代的方式访问w c b 。网络蜘蛛的搜索策略与搜索引擎的性 质和任务密切相关 a g g a r w a le t a l 2 0 0 1 1 。为了获得较高的w e b 覆盖率，通用搜 索引擎网络蜘蛛通常采用图的遍历算法( 如广度或深度优先策略) 搜索w e b ，见 图1 - 3 f a l 所示。 与通用攫索引擎不同的是，面向主题的搜索引擎服务丁特定人群，其索引的 贞向内容仅限于特定主题或专门领域，其在搜索过程中无须刘整个w e b 进行遍 历，只需选择与主题页面相关的页面进行访问，见图1 - 3 ( b ) l 昕示。主题搜索引擎 网络蜘蛛在搜索w e b 时，需要对站点的主题相关性作出预测和删选，并对网页 的主题相关性作出判断。以何种策略访问w e b ，以提高搜索效率，是近年来主题 搜索引擎研究中的主要问题之- - r c n n i e m c c a l l u m1 9 9 9 1 。本文的研究重心就 是对主题搜索引擎中的搜索策略进行了详细分析，并提出个优化的主题搜索网 络蜘蛛模型。 ( a ) 通j h 搜索引擎网络( b ) 专业搜索引擎网络 蜘蛛搜索顺序蜘蟓搜索顺序 白框代表主题无关贾面，黑框代表主题相关笑页面， 虚线代表链接，实箭头代表访问顺序) 图1 - 3 两类搜索引擎网络蜘蛛搜索顺序比较示意图 图1 - 3 两类搜索引辈网络蜘蟾搜索顺序比较示意图 川一一、一 导、：j 浙江大学硕士学位论文第一章绪论 i n t e r n e t 信息的分散存储、动态变化和异构的特性也是网络蜘蛛进行w e b 信 息提取时必须考虑的问题。由于信息源随时可能发生变化，网络蜘蛛必须经常地 刷新数据，但仍无法避免己提取页面失效的情况。以通用搜索引擎为例，由于待 刷新页面数量的巨大，使得刷新一遍数据需要数周到一个月的时问【a g g a n a le l a 1 2 0 0 1 ，这就使得页面的失效率变的非常地大。 1 2 本文的工作 本文在深入分析主题页面在w e b 上的分布特征与主题相关性判别算法的基 础上，对主题搜索引擎中的搜索策略进行了详细的分析，提出了个面向主题搜 索的网络蜘蛛模型，对模型的组织结构进行了详细阐述。工作的核心是对主题相 关性判别算法和增量w e b 信息提取进行研究。 在u r l 的主题相关性判别过程中，引入了链接文本及相关链接属性分析， 提出了一种新颖的u r l 主题相关性剪枝算法- - e p r 算法。对于网页的主题相关 性判别，则使用目前较为常用的向量空间模型进行判别。为满足主题搜索引擎对 数据实时性的较高要求，本文提出了一种全新的基于索引页的增量w e b 信息提 取算法，能够有效地发现w e b 上新增加的网页。 最后基于提出的模型原型系统进行测试，对基于宽度的遍历算法、p a g e r a n k 算法和改进的e p r 算法进行了详细的比较和说明，并对基于索引页的增量w e b 信息提取算法的实际应用和整个系统的性能测试结果做了详细说明。 1 3 本文的组织 第一章概述了搜索引擎的发展历史和它的基本原理，指出了通用搜索引擎的 缺陷，概述了主题搜索引擎的产生背景以及它的优势和当前的研究状况，进而指 出了进行面向主题的网络蜘蛛搜索策略研究的必要性。 第二章概述了网络蜘蛛的基本原理与结构、网络蜘蛛搜索策略的分类、w e b 信息提取所面临的主要困难和相应的技术手段，论述了构建面向主题的网络蜘蛛 进行面向主题的w e b 信息提取的重要性。第三章讨论了基于主题的w e b 信息提 取的基本问题，重点是对主题页面在w e b 上的分布特征和主题相关性判定算法 的研究。 第四章给出了我们设计的面向主题的网络蜘蛛的系统模型，并就搭建主题网 络蜘蛛所面临的关键问题和相应对策做了简单的描述，对结构模型中的主要部分 主题选择、页面提取与分析、u r l 和页面的主题相关性判别以及增量w e b 信息 提取分别作了较为详细的论述，并给出了我们的设计方案和算法。 第五章，我们给出了系统的实现情况、u r l 主题相关性判别算法的测试结 1 4 浙江大学硕士学位论文 第一章绪论 果、基于索引页的w e b 增量信息提取算法应用分析和整体系统的性能分析。 最后，在第六章对本文作了总结，并就进一步需要研究的问题和研究方向进 行了展望。 浙江大学硕士学位论文第二章嘲络蜘蛛w e b 信息提取概述 第二章网络蜘蛛w e b 信息提取概述 2 1 网络蜘蛛的基本原理与结构 w e b 信息提取，主要是指依赖w e b 页面之间的链接关系，从w e b 上自动地 获取页面信息，并且随着链接不断向所需要的w e b 页面进行扩展的过程。实现 这一过程，主要是由网络蜘蛛( w e bs p i d e r ) 来完成的。根据应用习惯的不同，网 络蜘蛛也常称作w e bc r a w l e r 、w e br o b o t 和w e bw o r m 。粗略地说它主要是指这 样一个w e b 应用程序，从个初始的u r l 集合出发，将这些u r l 全部放入到 一个有序的待提取u r l 队列里。而w e b 信息提取器从这个队列里按顺序耿出 u r l ，通过w e b 上的协议，获取u r l 所指向的页面，然后再从这些已获取的页 面中分析提取出新u r l ，并将它们继续放入到待提取u r l 队列里，然后重复上 述过程，直到w e b 信息提取器根据自己的搜索策略停止采集为止。 如图2 - 1 所示，网络蜘蛛基本上可以划分为七个部分：u r l 处理器、w e b 信 息提取器、网页去重检测器、u r l 提取器、标签信息获取器、数据库，它们协 作从w e b 上获取信息。 2 1 1u r l 处理器 图2 - 1 网络蜘蛛基本结构 这个部件主要给待提取的u r l 进行排序，并根据一定的策略向w e b 信息提 取器分配u r l 。按照网络蜘蛛系统规模的不同，u r l 可以是多个采集队列，也 可以是一个u r l 服务器。例如，g o o g l e 搜索引擎中的网络蜘蛛构建中就使用了 u r l 服务器来缓存u r l ，以达到更快的处理速度。u r l 处理器主要有三个数据 浙江人学硕上学位论文 第一章网络蜘蛛w e b 信息提取概述 来源：1 ) 初始的种子u r l 集合；2 ) 从u r l 提取器传递过来的新发现的u r l 集 合，它们是从已提取页面中分析得来的；3 1 页面的m e t a 信息、主题以及摘要等 信息，来自标签信息获取器，它们主要用来显示从u r l 提取器中传递过来的u r l 的重要性，为在队列中进行排序提供依据。另外，为了加快页面提取速度，u r l 处理器通常自带了d n s 解析功能。 2 1 2w e b 信息提取器 这个部件处于系统的底层，主要通过各种w e b 协议来完成网络数据的采集。 一般来说，协议包括 唧、g o p h e r 、b b s 以及f r r p 等，也有些w 曲信息提取 系统会根据实际需要获取w e bc h a t 、i c q 等特殊网络信息。 2 1 3 网页去重检测器 w e b 上存在着大量的镜像页面和重复的页面内容，最近的研究表明，有大约 3 0 的页面是重复的。如不进行网页重复内容的检测过滤，将极大地浪费了网络 带宽和系统的运行效率。因此，蘑复内容检测是网络蜘蛛中的重要组成部分，特 别是在大型的搜索引擎中尤为如此。在进行重复内容检测时，一般可以采用简单 的段落匹配方法或者相对复杂的相似度匹配方法。 对于中文网页的去重算法，文献张刚等2 0 0 1 g 至过大量的网页分析后，得 出了一种快捷可靠的大规模网页去重算法，即通过寻找到页面中出现的第一个中 文句号，然后在句号前后取5 个中文字符作为网页内容的唯一识别码。经过实验 测试结果表明，该去重算法在中文网页的去重计算中有着良好的应用效果。 2 1 4u r l 提取器 对于采集到的页面，通过网页去重检测后，需要分析其中的链接，并对链接 进行必要的转换以获取真实的u r l ，这些任务就是由u r l 提取器来完成的。 首先需要判别页面类型，仅需要对类型为“t e x t ，h t m l ，s h t m l 和h t m ”等的页 面进行分析即可。页面的类型可在对h t t p 应答头的分析中得出，有时也可以通 过分析u r l 中的文件扩展名来判别页面类型。 随后，需要分析的h t m l 标记包括 ， ， ， 等。页面链接 中给出的u r l 的格式可能是不一样的，既可能是完整的绝对路径u r l ，也可能 是一个相对路径。为方便处理，需要先将其规格化为统一的绝对路径u r l 格式。 2 1 5 标签信息获取器 这里所要获取的信息包括已提取页面的m e t a 信息、作者信息、页面的标题、 页面的摘要等。主要目的是在没有对页面内容进行语义信息理解的前提下，尽可 浙江大学硕士学位论文 第二章网络蜘蛛w e b 信息提取概述 能多的挖掘出h t m l 标签、结构等的信息，对从页面中提取出来的u r l 质量的 好坏给出一个度量，然后再传输到u r l 处理器，对待提取u r l 队列进行排序。 2 1 6 数据库 通过网页去重检测后的页面数据、提取出来的m e t a 信息、作者信息、主题 和摘要等均需存入数据库中，以备使用。例如，进行分析建立索引等。由于w e b 页面规模的庞大，提取的相关数据在存入数据库之前，一般要进行压缩处理。 2 2w e b 信息提取中的主要技术问题 和传统的信息媒介相比，w e b 主要有以下几个特点：1 1 信息容量的超大规模， 截止到2 0 0 3 年7 月，i n t e m e t 上的网页数量就已经超过3 0 亿，上网用户数量超 过5 2 亿，而且网页还在以每天7 0 0 万的速度增加；2 ) w e b 的动态性，w e b 的内 容和结构每天都在变化着：3 ) w e b 的异构性，w e b 中包含的文件类型各种各样， 包括文本、声音、图像、图片以及活动脚本等：4 ) 页面内容的重复性，最近的研 究表明，有大约3 0 的页面是