（计算机应用技术专业论文）智能信息采集搜索策略研究.pdf

摘要 近年来，如何在w e b 海量信息中尽可能多地获取与用户兴趣相关的页面是 搜索引擎领域研究的热点之一。本文通过改善网络蜘蛛的自适应性来提高搜索 效率，对基于主题的网络蜘蛛的搜索策略进行较为深入的研究。 本文首先介绍了现阶段网络蜘蛛的研究进展，在分析和比较现有基于主题 的网络蜘蛛搜索策略的优缺点的基础上，探讨了如何提高网络蜘蛛的自适应性 和预测链接价值的准确性，以此来提高搜索的效率。 为了提高网络蜘蛛的自适应性，本文提出一种基于综合价值的搜索算法， 通过结合链接的立即价值和未来价值，分析这两者相应的变化趋势来判断待搜 索页面集与主题的相关性，依此动态调整这两种价值的权值关系，产生适合实 际搜索情况的最优搜索策略。实验结果表明，新算法在整体性能上明显优于采 用单一链接评价方法的网络蜘蛛搜索算法。 为了提高链接价值预测的准确性，本文针对传统的p a g e r a n k 算法存在的主 题漂移现象，提出基于主题分块的p a g e r a n k 算法，利用信息抽取的方法对网页 建立d o m 层次树，按照网页结构对网页进行分块，依照各块与主题的相关性大 小对块中的链接传递不同的p a g e r a n k 值，并根据已访问的链接对块进行相关性 反馈。实验结果表明新的算法能较好地改进搜索结果的精确度。 本文还提出一种基于遗传算法的网络蜘蛛搜索策略，将遗传算法引入网络 蜘蛛搜索策略，将父页面，链接文本，链接的u r l 以及兄弟链接等信息的不同 组合作为不同的基因序列，通过交叉、变异操作使w e b 信息的组合方式可以随 着w e b 资源的实际情况而动态变动，得到符合w e b 情况的较优搜索策略1 。实验 结果表明，新的算法具有较高的搜索效率。 最后，本文利用提出的算法和相关技术，实现了个可采用多种搜索策略 的计算机相关论文专业搜索引擎网络蜘蛛系统原型。 关键词：网络蜘蛛；专业搜索引擎；搜索策略；p a g e r a n k ；遗传算法 a b s t r a c t i nr e c e n ty e a r s ，t h eh o t s p o ti nt h er e s e a r c ho fs e a r c he n g i n ei sh o wt og e tm o r e a n dm o r ew e b p a g e so nt h eu s e r s i n t e r e s t si nt h ew e br e s o u r c e s i nt h i sp a p e r ，w e c a r r yo nt h er e s e a r c hj nt h es e a r c h i n gs t r a t e g yo ft o p i cw e bc r a w l e rm a i n l ya i m i n ga t t h ep r o b l e mo fi n c r e a s i n gt h es e a r c h i n ge f f i c i e n c yt h r o u g ht h ei m p r o v e m e n to nt h e w e bc r a w l e r ss e l f a d a p t a b i l i t y f i r s to fa l l ，w ei n t r o d u c et h ec u r r e n ta c h i e v e m e n t so fr e s e a r c hi nw e bc r a w l e r a f t e r t h ec o m p a r eo ft h ea d v a n t a g e sa n dd i s a d v a n t a g e s + o fs o m ec u r r e n ts e a r c h i n g s t r a t e g i e s ，w ec o n c l u d et h a tt h ek e yp r o b l e mi ni n c r e a s i n gt h es e a r c h i n ge f f i c i e n c y l i e so n i m p r o v i n go n t h ew e bc r a w l e r s s e l f - a d a p t a b i l i t ya n dt h ev e r a c i t y i n p r e d i c t i n gt h el i n k a g e s i m p o r t a n c e t oi m p r o v eo nt h ew e bc r a w l e r ss e l f - a d a p t a b i l i ty t h ea l g o r i t h mb a s e do n c o m b i n e dl i n k a g e s r e w a r di s p r o p o s e d ，w h i c hc o m b i n e st h el i n k a g e si m m e d i a t e r e w a r da n dt h ef u t u r er e w a r dt oe v a l u a t el i n k a g e s i m p o r t a n c e m o r e o v e r ，w eu t i l i z e t h ec h a n g e so fr e w a r d st os p e c u l a t ea b o u th o wr e l e v a n tt h ec a n d i d a t ep a g e - s e tj st o t o p i c s ，b a s e do nw h i c ht h ec r a w l e rc a nd y n a m i c a l l ya d j u s tt h er e l a t i o n s h i pb e t w e e n t h e s et w or e w a r d sr e s u l t i n gi na c h i e v i n gt h es e a r c h i n gs t r a t e g ym o s ts u i t a b l ef o r t h e a c t u a ls e a r c h i n gs t a t e o u re x p e r i m e n t ss h o wt h a tc o m p a r e dw i t hs o m et r a d i t i o n a l a l g o r i t h m s ，t h i sa l g o r i t h mh a sb e t t e rp e r f o r m a n c e t om o r ea c c u r a t e l yp r e d i c tt h el i n k a g e s v a l u ea n dr e s o l v et h ep r o b l e mo f t o p i c - d r i f ti n t r a d i t i o n a lp a g e r a n k ，a ni m p r o v e dp a g e r a n ka l g o r i t h mb a s e do n t o p i c a ls e g m e n t si sp r o p o s e d t h i sa l g o r i t h ms e g m e n t st h ew e bp a g ei n t ob l o c k sa n d p a s s e st h ep a g e sp a g e r a n kt oo u t l i n k si ne a c hb l o c ki np r o p o r t i o nw i t ht h eb l o c k s r e l a t i v i t yt o t h eg i v e nt o p i c m o r e o v e r ，i tr e g a r d st h ev i s i t e do u t l i n ka sf e e d b a c kt o m o d i f yt h eb l o c k sr e l e v a n c e t h ee x p e r i m e n ti nw e bc r a w l e rs h o w st h a tt h en e w a l g o r i t h mh a sb e t t e rp e r f o r m a n c e m o r e o v e r ，i nt h i sp a p e r aw e bs e a r c h i n gs t r a t e g yb a s e do ni n h e r i t a n c e a l g o r i t h mi sp r o p o s e d ，w h i c hi n t r o d u c et h ei n h e r i t a n c ea l g o r i t h mi n t ot h ew e b c r a w l i n g i tl o o k st h ev a r i o u sc o m b i n a t i o no fw e bi n f o r m a t i o na b o u tp a r e n tw e b p a g e s 、s i b l i n gw e bp a g e s 、t h et e x t i n l i n k a g e s a n dt h eu r lt o k e n sa st h ev a r i o u s g e n es e q u e n c e t h r o u g hs o m eg e n e t i co p e r a t i o nl i k ec r o s sa n dm u t a t i o n ，t h em o d e o fc o m b i n a t i o no fw e bi n f o r m a t i o nc a nd y n a m i c a l l yc h a n g ew i t ht h ea c t u a lw e b r e s o u r c e ，r e s u l t i n gi nt h eb e s ts e a r c h i n gs t r a t e g y o u re x p e r i m e n t ss h o wt h a tt h en e w a l g o r i t h mh a sh i g h e rs e a r c h i n ge f f i c i e n c y f i n a l l y ，t oc o m p a r ed i f f e r e n ta l g o r i t h m s ，ap r o t o t y p eo f w e bs p i d e ro n c o m p u t e rp a p e r si sd e s i g n e db a s e do nt h ec o m b i n a t i o no fa l g o r i t h m sa b o v e k e yw o r d s ：w e bs p i d e r ；s p e c i f i cs e a r c he n g i n e ；s e a r c h i n gs t r a t e g y ； p a g e r a n k ；g e n e t i ca l g o r i t h m i i 插图索引 图1 1 全文的结构图l l 图2 1 专业搜索引擎网络蜘蛛模型1 2 图2 2h u b 和a u t b o rj t y 页面示例1 5 图2 3w e b 链接结构示意图1 6 图3 1 基于未来回报的网络蜘蛛访问顺序示意图2 1 图3 2 基于巩固学习的网络蜘蛛训练阶段的工作流程2 l 图3 3 基于巩固学习的网络蜘蛛搜索阶段的工作流程2 2 图3 4 三种算法的目标发现率比较图2 5 图3 5 三种算法的搜索精度比较图2 5 图4 1w e b 页面举例2 9 图4 2d o m 树的表格表示3 0 图4 3u r l 为w w w d m o z o r g s c i e n c e 时，三种算法的搜索精度比较图3 2 图4 4u r l 为a r c h i v e f i c s a u i u c e d u 时，三种算法的搜索精度比较图3 2 图5 1 两种算法的适应度函数值比较图4 1 图6 1 系统体系结构图4 2 图6 2 网络蜘蛛初始界面4 4 图6 3 网络蜘蛛搜索状态4 4 图6 4 网络蜘蛛搜索结果的报告4 5 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 裂管 日期：寸年月曰 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团 ( 请在以上相应方框内打“”) 作者签名：欲弦 别谧备翦 。+ 燮7 日期：2 寸年f 月 日 日期：砂寸年f 月j7 日 1 1 研究背景 第1 章绪论 所有搜索引擎的祖先，是1 9 9 0 年由m c 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 程序又被称为网络蜘蛛。 世界上第一个网络蜘蛛，是m i tm a t t h e wg r a y 的w w w ( w o r l dw i 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 ，这些通用搜索引擎长期以来为 人们查找信息提供了全丽而高效的服务。但随着近年来用户需求的不断变化和互 联网规模的不断扩张，传统的通用搜索引擎正面临巨大的挑战。挑战之一是因特 网上w e b 信息资源的指数级增长，搜索引擎无法索引所有的页面。据统计，到 2 0 0 1 年1 月，w e b 上的静态页面的数量超过4 0 亿个，而且这一数量还在以平均 每天7 3 0 万个页面的速度递增。在过去的几年中，尽管各种通用搜索引擎，如 g o o g l e 、f a s t 、a l t av i s t a 和g o t o 等在索引技术、索引数量上有所提高，但远远 无法跟上w e b 本身的增长速度，即使是目前全球最大的搜索引擎g o o g l e 系统和 w i s e n u t 系统，其索引的页面数量也不到w e b 总量的8 0 。 挑战之二是w e b 信息资源的动态变化，搜索引擎无法保证对信息的及时更 新。近年来的研究表明，w e b 上的页面平均5 0 天就有约5 0 的页面发生变化，而 目前通用搜索引擎更新的时间至少需要数星期之久”1 。 挑战之三是传统的搜索引擎提供的信息检索服务，不能满足人们日益增长 的对个性化服务的需要。传统的搜索引擎设计的目的是满足普通人群对“公共” 信息查询的需要，主要根据用户输入的“查询串”与索引页面匹配程度的高低返 回页面，这种检索方式不但带回大量的无关页面，而且缺乏个性，不能满足特定 人群对特定信息的需要。 面对这些挑战，各类适应各类适应特定人群需要的“专业搜索引擎” ( f o p ics p e c i f i cs e a r c he n g 【n e ) 应运而生，并越来越受到人们地关注与青咪 1 “。刘f 专业搜索引擎，其搜索的内容只限于专门领域，传统的广度优先搜索 策略已不再适用。以何种顺序访问w e b ，以提高搜索效率，是近年来专业搜索； 擎研究的焦点之一。 1 2 研究进展 在早期的通用搜索引擎中，网络蜘蛛的任务是将w e b 上的信息尽可能多的 收集起来，保存到本地索引库中，满足广大用户广泛的信息查询需求。加上通用 搜索引擎一般都有较丰富的硬件资源，网络蜘蛛采用的是最普通的广度优先搜索 策略，即按照发现顺序顺次访问w e b 上的超链接，抓取其所指向的网页。这种 网络蜘蛛算法简单，容易实现，但对硬件要求较高，另外考虑问题不全面，不能 满足专门搜索引擎领域的特定搜索需求。 为了设计出更为高效的网络蜘蛛，研究者们对w e b 上的信息和网络蜘蛛的 工作方式进行了分析，总结出设计高性能的网络蜘蛛所要解决的关键问题。 1 2 1 w e b 信息采集中的关键问题 1 2 1 1w e b 资源的特点 w e b 资源和传统的信息资源相比，具有以下几个显著特点：( 1 ) 信息量巨 大。( 2 ) 高链接性。平均每个页面有超过8 个链接指向其他页面。( 3 ) w e b 的动 态性，w e b 的内容和结构都在不断地发生着更新和变化。( 4 ) w e b 信息的重复 性。最近的研究表明，将近3 0 的页面是重复的。( 5 ) w e b 的异构性。w e b 中 包含的文件类型是多种多样的，包括文本、图像、声音、程序等。这些特点为 w e b 信息采集带来了技术上的困难。 1 ：2 1 2w e b 信息采集中的关键技术问题 从技术角度上来看，需要解决的关键问题有：第一，w e b 上的信息量如此 巨大，采集器不可能采集到所有的页面，而且搜索引擎的数据库也没有那么大的 容量。所以，必须尽可能提高采集器的搜索效率，即通过访问较少的不相关页面 来获得较多的相关页面。这是最关键的一个问题，特别是对于基于主题的信息采 集，需要采取较优的搜索策略，对待采集页面评分，以此选择高质量的页面优先 采集。目前，有五种常用的评价页面质量高低的方法：1 ) 、s i m i l a r i t y ，包括已 采集页面和链接与采集主题之间的相似度。2 ) 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 a g e r a n k 值为此页面的p a g e r a n k 值除以它的链出页面数，即这页的出度。3 ) l o c a t i o n ，根据页面在w e b 中所处的局部位置得到。4 ) b a c k l i n k ，根据页面的入 度大小得到。5 ) f o r w a d l i n k ，根据页面的出度大小得到。 第二，并行性问题。页面的采集速度一直是影响采集性能的主要因素。凶 为w e b 页面数量巨大，加之网络硬件资源有限所导致的网络速度的缓慢，采集 系统需要采取并行工作的方式来提高采集效率。然而，这带来了许多新的问题： 1 ) 重复性。多个采集线程在同一时间采集增加了页面重复的可能性。2 ) 质量问 题。单个采集者能够根据获得的全局信息调整搜索策略从而采集到全局最优的页 面。而若采取并行，每个采集线程只能采集到局部最优的页面，必定影响到采集 页面的质量。3 ) 通信代价。为了并行，各采集线程之间必不可少地需要信息交 互，这样就必然会增加用于通信的带宽代价。 第三，信息更新问题。为了保持采集到的页面是最新的，采集器必须对已采 集页面进行周期性的更新。但由于w e b 上的信息量巨大且更新速度快，经统计， 1 4 的搜索引擎提供的页面是过期无效的。c h o 研究和对比了三种页面刷新策 略：固定顺序的刷新，随机刷新和纯随即刷新策略。直觉上，更多的刷新应该分 配给那些更新快的页面。但研究表明，对各种页面采取相同的刷新周期效果反而 更好，这是因为用过高频率刷新更新快的页面，使得其它页面有较少的刷新机会， 反而造成总体刷新质量的下降。 1 2 2w e b 采集技术的发展及现状 为了解决w e b 采集的关键问题，研究者们经过不断地研究与实践，将网络 蜘蛛由最早期单纯的基于整个w e b 的网络蜘蛛发展到可满足不同需要的多种采 集技术的网络蜘蛛。归纳起来，大致可以分为以下几种类型“3 ： 第一种是早期的基于整个w e b 的网络蜘蛛。主要是指目标为从一些种子 u r l 扩充到整个w e b 的网络蜘蛛，这种网络蜘蛛通常是作为门户站点搜索引擎 和大型的w e b 服务提供商的数据采集部分。这类信息采集由于目标是采集整个 w e b ，因此对内存和硬盘等硬件的要求比较高，对采集页面的顺序要求相对较低。 第二种是增量式的网络蜘蛛。传统的w e b 采集器根据自己的需要采集足量 的信息后停止采集，当过一段时间这些数据过时后，它会重新采集一遍来代替先 前的信息，称为周期性w e b 采集器。而增量式的网络蜘蛛对待就的页面采用增 量式更新，即采集器在需要的时候采集新产生的或已经发生了变化的页面，而对 没有变化的页面不进行采集。和周期性信息采集相比，增量式信息采集能极大地 见效数据采集量，从而极大地减少了采集的时空开销。但是，增量式信息采集在 减小时空开销的同时，却增加了算法的复杂性和技术难度。 第三种是基于主题的网络蜘蛛，是指选择性地搜寻那些与预先定义好的主 题相关的页面的采集器。和基于整个w e b 的网络蜘蛛相比，它并不采集那些与 主题无关的页面，所以极大地节省了硬件和网络资源，保存的页面也由于数量少 而更新快。加之它可以很好地满足一些特定人群对特定领域信息的需求，成为时 f 研究的热门重点。但它的问题也是显而易见的，例如如何定义有实际意义的主 题，如何在采集时判定页面与主题的耷日天性以及如何提高系统的搜索精度和完全 度等。 第四种是基于用户个性化的网络蜘蛛。不同的用户对一个搜索引擎提交同 一个检索词，他们期待的结果是不尽相同的。而通用的搜索引擎却只能返回相同 的检索结果，这显然不完全符合用户的需要。而基于用户个性化的网络蜘蛛是 种轻量级的采集系统，它的目标就是通过用户兴趣制导或与用户交互等手段来采 集信息，给用户提供个性化服务。 第五种是基于a g e n t 的网络蜘蛛。随着智能a g e n t 技术的发展，a g e n t 与信 息采集相结合的技术也逐渐热门起来。智能a g e n t 由于能在一定的环境下灵活自 主地活动，具有_ 定的自治性与反应能力，它在面临诸如基于主题的采集和用户 个性化采集时，相对于传统方法，更具方便灵活和适应能力强等优势。 第六种是迁移的网络蜘蛛。这种采集器并不像其他采集器一样在本地向 w e b 站点服务器发送页面请求，而是将自己上载到它所要采集的服务器中，在当 地进行采集，并将采集结果压缩后，再回传到本地。这样做大量地节省了w e b 资源，大量的剪裁工作将在被采集对象的服务器上完成。 第七种是基于元搜索的网络蜘蛛。它对用户的提交的查询请求通过多个领 域或门户搜索引擎搜索，并将结果整合后返回给用户。一般元搜索引擎并不保存 w e b 页面的索引文件，但对于一些负载的元搜索引擎，它要保存为它服务的每个 搜索引擎的信息特征，一般以后根据用户请求做出选择。作为搜索引擎首要部件 的采集器在元搜索引擎中功能有所退化，但仍作为w e b 采集的个研究方向， 日q 做基于元搜索的信息采集。 1 2 3 基于主题的网络蜘蛛搜索策略研究 虽然目前网上有许多优秀的搜索引擎，例如g o o g l e ，y a h o o ，a l t a v i s t - a 等， 但由于信息量的不断增长和快速更新，通常的搜索引擎信息覆盖率在不断降低， 即使是目前全球最大的搜索引擎g o o g l e ，其索引的页面数量仅占w 曲总量的 4 0 。另外，传统的信息检索方式已经不能满足特定人群对特定信息的需要。 专业搜索引擎是目前解决上述问题的较好方法，它的出现也是一种技术趋 势，它只针对某一主题进行检索，提供关于此主题较为全面而准确的信息。它对 网络蜘蛛的搜索效率提出了更高的要求，需要它有选择性地搜寻那些与预先定义 好的主题相关的页面。 1 2 3 1 专业搜索引擎网络蜘蛛模型 专业搜索引擎中网络蜘蛛的任务是在尽可能短的时间内，搜集尽可能多的 主题相关信息，尽可能少的无关信息。搜索进行过程中，路径选择是最为关键的 问题，直接影响搜索的质量和速度。它通常从一个“种子集”( 如用户查询、种 子链接或种子页面) 出发，根据给定的搜索深度条件以迭代的方式通过h t t p 度等。 第四种是基于用户个性化的网络蜘蛛。不同的用户对一个搜索引擎提交同 个检索词，他们期待的结果是不尽相同的。而通用的搜索引擎却只能返回相同 的检索结果，这显然不完全符合用户的需要。而基于用户个性化的网络蜘蛛是一 种轻量级的采集系统，它的目标就是通过用户兴趣制导或与用户交互等手段来采 集信息，给用户提供个性化服务。 第五种是基于a g e n t 的网络蜘蛛。随着智能a g e n t 技术的发展，a g e n t 与信 息采集相结合的技术也逐渐热门起来。智能a g e n t 由于能在一定的环境下灵活自 主地活动，具有_ 定的自治性与反应能力，它在面临诸如基于主题的采集和用户 个性化采集时，丰目对于传统方法，更具方便灵活和适应能力强等优势。 第六种是迁移的网络蜘蛛。这种采集器并不像其他采集器一样在本地向 w e b 站点服务器发送页面请求，而是将自己e 载到它所要采集的服务器中，在当 地进行采集，并将采集结果压缩后，再回传到本地。这样做大量地节省了w e b 资源，大量的剪裁工作将在被采集对象的服务器上完成。 第七种是基于元搜索的网络蜘蛛。它对用户的提交的查询请求通过多个领 域或l 、j 户搜索引擎搜索，并将结果整合后返回给用户。一般元搜索引擎并不保存 w e b 页面的索引文件，但对于一些负载的元搜索引擎，它要保存为它服务的每个 搜索引擎的信息特征，一般以后根据用户请求做出选择。作为搜索引擎首要部件 的采集器在元搜索引擎 ，功能有所退化，但仍作为w e b 采集的一个研究方向， 叫做基于兀搜索的信息采集。 1 2 3 基于主题的网络蜘蛛搜索策略研究 虽然目前网j ：有许多优秀的搜索引擎，例如g o o g l e ，y a h o o ，a l t a v i s t a 等， 但由于信息量的不断增长和快速更新，通常的搜索引擎信息覆盖率在不断降低， 即使是目前全球最大的搜索引擎g o o g l e ，其索引的页面数量仅占w e b 总量的 4 0 。另外，传统的信息检索方式已经不能满足特定人群对特定信息的需要。 专业搜索引擎是目前解决上述问题的较好方法，它的出现也是一种技术趋 势，它只针对某一主题进行检索，提供关于此主题较为全面而准确的信息。它对 网络蜘蛛的搜索效率提出了更高的要求，需要它有选择性地搜寻那些与预先定义 好的主题相关的页面。 1 2 3 1 专业搜索引擎网络蜘蛛模型 专业搜索引擎中网络蜘蛛的任务是在尽可能短的剐问内，搜集尽可能多的 主题相关信息，尽可能少的无关信息。搜索进行过程中，路径选择尾擐为关键的 问题，直接影响搜索的质量和速度。它通常从一个“种子集”( 如用户查询、种 子链接或种子页面) 出发，根据给定的搜索深度条件以迭代的方式通过h t t p 子链接或种了页面) 出发，根据给定的搜索深度条件以迭代的方式通过h t t p 协议请求并f 载w e b 页面，分析页面并提取链接。搜索过程中，未访问的链接 被暂存在一个称为“搜索前沿”( c r a w lf r o n t i e r ) 的队列中，网络蜘蛛按照某种 策略选择下一个要访问的链接。如图1 1 所示： w e b 链接 w e b 结构信息i专业l 搜索引擎中页面信息 链接价值计算与优先 权控制器 ；控制优先权 。 出队，；西磊五百云五丌链接入队 图1 1 专业搜索引擎网络蜘蛛模型 通用搜索引擎的网络蜘蛛通常采用图的遍历算法f 如广度或深度优先策略) 搜索w e b 。与通用搜索引擎不同，专业搜索引擎服务于特定人群，索引的内容仅 限于特定主题或专门的领域，因而在搜索过程中无须遍历整个w e b ，只需选择与 主题相关的页面进行访问。因此网络蜘蛛需要对网页进行评级，其搜索性能的关 键在于采取何种顺序访问超级链接，通过访问较少的不相关页面来获得较多的相 关页面。 1 2 3 2 几类搜索策略的研究 针对这一问题，国内外的学者进行了深入研究，提出了许多切实可行的搜 索算法，归纳起来大致可分为四种类型： 第一种是基于文本内容的搜索算法。主要是根据主题信息( 如：关键词、 主题相关文档) 与页面或链接文本“语义”的相似度来评价链接价值的高低。链 接文本是指当一个网页中具有指向另一个网页的链接时，与此链接相对应的描述 文字。有这样一个基本假设：链接文本是用来描述它所指向的文档的，而不是用 来描述它所在的当前文档。根据这一假设，我们可以在链接文字和其目标文档之 脚建立联系以辅助搜索。更进一步地，链接文字周围的上下文信息也和其目标有 着较为密切的相似性关系。网页或链接文本和主题的相似度评价通常采用以下公 式 s i m ( q ，p ) ； 删，厶 压了琢 其中，q 代表主题关键词集合，p 代表页面链接文本集合，允代表币词k 出 现在集合d 中的频率。若考虑到不同啦词具有不同的重要程度，( 1 1 ) 可以改为： 警耋一 纠 卜 匕 面刊 塑 s i m ( q ，p ) a 删， 屈i 丽 ( 1 2 ) e d e b r a 等人首次提出成为“f i s h s e a r c h “的定题搜索算法，c r a w l e r 动态 维护一个按搜索优先权值排序的未搜集u r l 列表，并根据它选择下一步搜集目 标“3 。在信息搜索过程中，相关网页包含的超链接被赋予比不相关网页包含的链 接更高的优先权值，插入到未搜索u r l 列表中。文献 3 提出了用主题信息来表 示用户兴趣的方法及根据搜索实际情况动态调整搜索主题的策略。文献 4 模仿 鲨鱼捕食的过程，形成了鲨鱼算法，其基本思想是给网络蜘蛛设定一个搜索层次， 当访问的当前页面是和主题相关时，保持此搜索层次继续访闯上面的镶接，当此 页面和主题不太相关时，将搜索层次降低，对上面的链按进行访问，当搜索层次 降为零h 于，不再对其上的链接进行访问。文献 5 利用已分类的实例集训练分类 器，来衡量页面与主题的相似度，并用于指导搜索顺序。基于内容评价的网络蜘 蛛起子文本检索中对文本相似度的评价，优点是计算简单。但是，w e b 页面不同 于传统的文本，它是一种半结构化的文档，包含许多结构信息；页面中的链接指 示了页面之间的相互关系。这一类算法的缺陷是没有充分利用搜索过程中获得的 链接结构等有用信息。s m u k h e o e a 设计的w t m s 中采用的c r a w l e r 在信息搜 索开始之前，分析给定的其实页面集，生成一个特征表示向量”1 。搜索过程中， 分析被搜索的网页，计算其与特征向量之间的相似度。相似度超过预定值的页面 包含的超链加入待搜索u r l 列表中。同时，引入启发规则提搜索效率：只搜索离 相关页面近的页面( 父节点，兄弟节点和子节点) ；有限搜集包含关键词的u r l 对应的页面；设立阀值，对一些相关度低于阀值的目录放弃搜索。 这一类算法的缺陷是没有充分利用搜索过程中获得的链接结构等有用信 息。而且单纯地依靠对网页文档信息的分析是不够的。这是因为对网页内容的分 析计算是很耗费计算机处理时间的，而w w w 上的网页量又十分巨大。并且由 于网页上的内容一般是自然语言，因此对其处理结果也不是十分精确。 第二种是基于w e b 结构的搜索算法，即通过分析w e b 页面问链接结构及相 互引用的关系来确定链按的重要性。链接分析算法可以用来提高搜索引擎的查询 效果。可以发现w w w 上的重要的社区，可以分析某个网站的拓扑结构，声望，分 类等，可以用来实现文档的自动分类等。归根结底，能够帮助用户在w w w 海量 的信息单准确找到需要的信息。链接分析算法大体上可以分为三类，基于随机漫 游模型的，比如p a g e r a n k ，r e p u t a t i o n 算法，机遇h u b 和a u t h o r i t y 相互加强模型 的，如h i t s 及其变种，基于概率模型的，如s a l s a ，p h i t s ，基于贝叶斯模型 的，如贝叶斯算法及其简化版本。 p a g e r a n k 方法最初用于搜索引擎信息检索中对查询结果的排序过程，近年 被应用于网络蜘蛛对链接重要性的评价”1 。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 ) 吖。手“1 - y 卜三，岗 ( 1 3 ) 其中，r 为计算中的页面总量，yc 1 是阻尼常数因子，m r p ) 为所有指向p 的页面的集合，o u t ( rj 为页面r 出链的集合。 p a g e r a n k 方法最初用于搜索引擎信息检索中对查询结果的排序过程，近年 被应用于网络蜘蛛对链接重要性的评价”1 。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 a g e r a n k 方法一样，h i t s 方法也是根据链接结构和页面之问的引用关 系决定页面重要性的方法。h i t s 方法定义了两个重要概念：a u t h o r i t y 和h u b ”3 。 a u t h o r i t y 表示一个权威页面被其它页面引用的数量，即该权威页面的入度 值。网页被引用的数量越大，则该网页的a u t h o r i t y 值越大；h u b 表示个w e b 页面指向其它页面的数量，即该页面的出度值。网页的出度值越大，其h u b 值 越高。由于通常h u b 值高的页面都提供了指向权威页面的链接，因而起到了隐 含说明某主题权威页面的作用，见图1 2 。 q 0 1 一 o o j 舢恤o r n 脓鄞曲髓绷崂a 铆l p 鬻h q h p ；刮门艄撒下列醐蜮懑 】= ： 】 r 14 、 】= ：川q 】( 1 5 1 其中，为所有指向页面p 的页面鬃掌f 为被页面p 中链接指向的页面集 由于h i t s 算法也存在“主题漂移”问题，b h a r a t 等对其进行了改进“3 ，利 用查询主题与页面的相关性计算每个页面p 的主题权重w p 】，并用p 1 ，n p 】 代替h f p 】计算a u t h o r i t y 权重，改进的计算公式如下： 爿”( 。酱g 】。如p ( 1 6 ) h i p l 。乏爿m x w h a b ( q ，p )( 1 7 ) 其中，m 为所有指向页面p 的页面集合，。( 毋p ) 为指向p 的页面留的 a u t h o r i t y 权重；n 页面p 中链接指向的页丽集合，矽施国，p ，p 中链接指向的 页面口的h u b 权重。 基于h i t s 方法的网络蜘蛛在搜索过程中，每搜索到新的页面，需要重复计 算每个页面的a u t h o r i t y 权重和h u b 权重，以此决定下一次将访问哪个页面中的 链接。与p a g e r a n k 方法相比，改进的h i t s 算法将页西的文本信息与链接的结 构信息相结合，在预测的准确性方面具有一定优势。 m a r c h i o r i 在文献 1o 中介绍了一种利用网络链接及所链接网页的重要性来 评价网页重要性的方法。他认为网页的重要性包括两个方面：网页内容的重要性 和其链接网页的重要性，即i n f o r m a t i o n ( a ) = t e x t l n f o ( a ) + h y p e r l n f o ( a ) 。 i n f o r m a t i o n ( a ) 表示从a 出发k 距离内的信息重要性( 包括a ) 。首先考虑在单路 径链接中的情况。设a o a l a 2 一a i ，a o ，a k 都是网页结点，链接重要 性h y p c r l n f o l m ( a ) 为f 和i n f o r m a t i o n l k ，l 】( a i + 1 ) 的乘积，其中f 是消退因子，0 f i ， 它表示在链接路径中，下一个结点重要性对上一结点重要性的影响。于是： i n f o r m a t i o n ( a o ) = t e x t l n f o ( a 0 ) + f ( t e x t l n f o ( a 1 ) + f ( t e x t l n f o ( a 2 ) ) + f ( t e x t l n f o ( a k ) ) ) ) = t e x t i n f o ( a o ) + ft e x t l n f o ( a 1 ) + f 。t e x t l n f o ( a 2 ) + + f k t e x t l n f o ( a k ) 。这是因为距离a 的结点越远的结点对a 结点重要性的影响越小。 如果结点a o 同时链接到多个结点a t ，a 2 ，a k ，可以这样考虑，用户 一般会先点击比较重要的网页结点，因此各个结点的信息重要性对a 结点的影 响是不同的。假设t e x t l n f o ( a 1 ) t e x t l n f o ( a 2 ) t e x t l n f o ( a k ) ，则 l n f o r m f i t i o n ( a o 、= t e x t l n f o ( a o ) + ft e x t l n f o ( a 1 ) + f 2t e x t l n f o ( a 2 ) + + f t e x t l n f o ( a k ) 。在实际的w e b 链接结构中，可以结合这两种方法来计算网页的重 要性。例如：在图1 3 所示的w e b 链接结构中，假设t e x t l n f o ( a ) t e x t i n f o ( b ) t e x t l n f o ( c ) ，t e x t l n f o ( e ) t e x t l n f o ( d ) ，则选择序列为a ，b ，c ，e ，d ， i n f o r m a t i o n ( a 、= t e x t l n f o ( a ) + ft e x t l n f o ( b ) + f 。t e x t i n f o ( c ) + f t e x t l n f o ( e ) + f 9 t e x t l n f o ( d ) 。 图1 3w e b 链接结构示意图 这 类方法的特点是考虑了链接的结构和页面之间的引用关系。但忽略页 面与主题的相关性，在有些情况下，会现搜索偏离主题的现象“。并且w e b 链 接结构信息也是非精确的。在实际情况中，在个聚簇内的网页结点并不一定就 是属于同一主题的，它们也可能同属于一个大范围的主题，而各自属于相对小范 围内的主题。在链接中也可能出现一些不相干的页面链接，例如在网页上可能会 有商业广告链接，而这些链接与网页内容完全不相干。另外，在一个好的h u b 结点指向的结点之间也很有可能内容不相关，它们可能分属于不同的主题。因此， 单纯地对w e b 链接结构信息进行分析具有很大的偏差。 第三种是基于智能代理体的搜索算法。m 。d i l i g e n t i 等人将网页之间的链 接关系表示成层次关系“。根据给定起始页面集，建立