（计算机应用技术专业论文）搜索引擎分析——基于page+rank算法的研究与改进.pdf

摘要 伴随互联网爆炸性的发展，网上信息浩如烟海，普通网络用户想找到所需的 资料难于大海捞针，所以迫切需要一种优异的搜索服务，将网上繁杂的内容整理 成为可方便获取的信息。搜索引擎技术为解决这一难题做出了突出贡献，搜索引 擎提供的结果集中页面质量的好坏以及高质量的页面能否在结果集中有较好的排 名，对搜索引擎用户来说具有重要意义，同时也是衡量搜索引擎技术优劣的关键 指标，所以对页面进行重要性评估并按重要性排序是搜索引擎要解决的技术核心。 本文首先介绍了搜索引擎的组成、原理、工作流程以及发展现状，分析了其 存在的优缺点；然后对w e b 挖掘的三个方面：内容挖掘、结构挖掘和使用挖掘做 了简要分析。 其次，本文在介绍p a g e r a n k 与h i t s 两种基于链接结构的搜索引擎排序算法 的基础上，就链接和被链接的数量、对象以及w e b 自身的链接结构模式对这两种 算法进行了对比分析，并重点研究了p a g e r a n k 算法的思想和计算方法。 最后，通过深入分析p a g e r a n k 算法后，本文提出了改进的s p p a g e r a n k 算法， 并对算法所用到的内外存交换原理做了比较深入的研究，利用j a v a 语言实现了基 于数据预取的p a g e r a n k 与s p p a g e r a n k 计算平台。在搜狗实验室提供的3 个链接 数据集上进行了实验，实验结果表明，基于数据预取的p a g e r a n k 与s p p a g e r a n k 算法比未使用数据预取的时候在计算效率上有较大提高。 关键词：搜索引擎；数据预取；p a g e r a n k ；s p p a g e r a n k 分类号：t p 3 0 1 6 a bs t r a c t w i t ht h ee x p e n s i v ed e v e l o p m e n to ft h ei n t e r n 乩t h ec o n t e n t so nt h ew e ba r e i n c r e a s i n ge x p o n e n t i a l l y o r d i n a r yi n t e r n e tu s e r sw h ow a n tt o f i n dt h en e c e s s a r y i n f o r m a t i o na r ev e r yd i f f i c u l tt of i n dt h e m t h e r e f o r e ，t h e r ei sa i lu r g e n tn e e df o ra s u p e r i o rs e a r c hs e r v i c e ，w h i c hi s t of a c i l i t a t et h ec o m p l i c a t e dc o n t e n t sa c c e s st o i n f o r m a t i o n s e a r c he n g i n et e c h n o l o g y 嬲t h es o l u t i o nt ot h i sp r o b l e mh a sm a d e o u t s t a n d i n gc o n t r i b u t i o n s ，b u ti t i ss i g n i f i c a n tt ot h eu s e r so fs e a r c he n g i n et h a tt h e s e a r c he n g i n er e s u l t so nt h eq u a l i t yo ft h ep e r f o r m a n c ea n db e t t e rq u a l i t yo ft h ep a g e s c a nr e s u l ti nab e t t e rp o s i t i o n , w h i c hi sa l s ot h ek e yi n d i c a t o rt om e a s u r et h es e a r c h e n g i n et e c h n o l o g y s oo np a g ea s s e s s m e n to ft h ei m p o r t a n c ea n dt h ei m p o r t a n c eo f s e a r c he n g i n e sa r et h es o r to f t e c h n o l o g yt os o l v e f i r s t ，t h i sp a p e rg i v e sab r i e fo nt h ec o m p o s i t i o no fs e a r c he n g i n e s ，p n n c i p l e s ， p r o c e s s e s ，t h ed e v e l o p m e n to ft h es t a t u sa n dt h ee x i s t e n c eo ft h ea d v a n t a g e sa n d d i s a d v a n t a g e s ；w e bm i n i n gi n c l u d e st h r e ea r e a s c o n t e n tm i n i n g , s t r u c t u r em i n i n g , u s i n gm i n i n g s e c o n d l y , t h r o u g ht h ea n a l y s i sa n dr e s e a r c ho fp a g e r a n k , h i t s ，t h et w o a l g o r i t h m sa r ec o m p a r e d o nt h el i n ka n dt h en u m b e ro ft h el i n k sa n dt h e i ro w n w e bl i n k s t r u c t u r em o d e l t h i sp a p e rm a i n l yr e s e a r c h e st h ec u r r e n tm a i n s t r e a mo ft h ep a g e r a n k a l g o r i t h m ，f o c u s i n go nt h ef o r m a t i o no fi d e a s ，c a l c u l a t i o nm e t h o d s f i n a l l y , t h r o u g ha n a l y z i n gt h ef e a t u r e so ft h ep a g e r a n kt oi n t r o d u c et h ei m p r o v e d a l g o r i t h ms p p a g e r a n k , a n did e e p l ys t u d yt h ep r i n c i p l eo nt h ee x c h a n g eo fi n t e r n a l m e m o r ya n de x t e r n a lm e m o r y a tl a s t , ia c h i e v eap l a t f o r mo fp a g e r a n ka n d s p p a g e r a n kw h i c ha r eb a s e do nd a t ap r e f e t c h i n gw i t hj a v al a n g u a g e t h ee x p e r i m e n t s a r ec a r r i e do n3l i n kd a t a s e t sf r o mt h es o g o ul a b ，a n dt h ee x p e r i m e n t a lr e s u l t ss h o w t h a tp a g e r a n ka n ds p p a g e r a n ka l g o r i t h mb a s e do nd a t ap r e f e t c h i n ga r em o r ee f f i c i e n t t h a nn o tu s i n gd a t ap r e f e t c h i n g k e y w o r d s ：s e a r c he l l 季n e ；d a t ap r e f e t c h i n g ；p a g e r a n k ；s p p a g e r a n k c l a s s n o ：t p 3 0 1 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：旃烈糊导师签名：秒引代磋 签字日期：哮7 月乎日签字日期：喈年7 月矿1 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月日 致谢 本论文的工作是在我尊敬的导师黄厚宽教授的悉心指导下完成的，从论文的 选题，论文的撰写，一直到论文的最终定稿，黄老师一直给予我细心的指导和无 尽的关怀。黄老师严谨的治学态度和科学的工作方法给了我极大的帮助和影响。 在此衷心感谢两年来黄厚宽老师对我的关心和指导。 瞿有利老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 同时要感谢田风占老师，他在平时学习和生活中给予我极大地帮助，对我们 的项目进行指导，使我的实际动手能力有了极大提高。 我要感谢和我一起参加讨论班的博士生和硕士生：刘大伟、王丽丽、王春锋、 李博、冯奇、王银利、张颜锋、李广群等，通过我们在讨论班的学习和积极讨论， 使我对很多问题有了更深入的了解和理解。他们给了我很多好的建议，同时也拓 宽了我的视野，接触到了很多其他领域的相关知识。感谢大家在各个方面给予了 我很大的帮助。我祝愿你们以后取得更大的成绩。同时也要特别感谢一起参加项 目开发的李博、王春锋等同学，通过实际开发，让我对于j a v a 知识更加巩固。 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 多批评指正，并提出宝贵的意见。 1 1 研究背景和意义 1 引言 随着因特网的迅猛发展、w e b 信息的增加，用户在信息海洋里查找信息就像 大海捞针一样。一方面，互联网络上的信息越积越多；一方面，人们在互联网络 上找到自己想要的信息却变得越来越困难，甚至渐渐变成一种灾难。互联网络上 有人们需要的知识，但更多的是人们不需要的知识。对一个互联网络使用者来说， 他仅仅用到了这个互联网络1 的信息量，但却要在这9 9 的无效信息中苦苦搜寻， 无疑是大海捞针、苦不堪言。同时，由于在传统的电子商务活动中，许多企业、 商家己经积累了大量诸如客户信息、交易记录、访问记录等数据，也没有充分地 加以利用，无法提升企业的核心竞争力。为了能在残酷的商场上立于不败之地， 越来越多的企业、商家想要将这些数据转换成为有用的信息和知识，为他们的电 子商务决策提供有力支持，以期占领商业竞争的制高点。搜索引擎技术恰好解决 了这一难题( 它可以为用户提供信息检索服务) 。目前，搜索引擎技术正成为计算 机工业界和学术界争相研究、开发的对象。搜索引擎是随着w e b 信息的迅速增加， 于1 9 9 5 年开始逐渐发展起来的技术。据统计，w e b 已经拥有1 0 0 亿左右的静态 网页和5 5 0 亿左右的动态网雨【。 搜索引擎正是为了解决这个“迷航”问题而出现的技术。搜索引擎以一定的 策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用 户提供检索服务，从而起到信息导航的作用【2 】。搜索引擎提供的导航服务已经成为 互联网上非常重要的网络服务，搜索引擎站点也被美誉为“网络门户。搜索引擎 已成为一个新的研究、开发领域。因为它要用到信息检索、人工智能、计算机网 络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理 论和技术，所以具有综合性和挑战性。又由于搜索引擎有大量的用户，有很好的 经济价值，所以引起了世界各国计算机科学界和信息产业界的高度关注。 1 2 本文的主要工作 ( 1 ) 本文介绍了互联网和搜索引擎的发展历史，搜索引擎在不同历史条件下的 典型代表，并从客观的角度分析了搜索引擎的发展趋势。同时对搜索引擎的各个 组成部分做了综述，从底层的网页抽取、网页预处理、索引入库，到查询的实现、 搜索引擎的语法表达、用户接口、排序显示等，做了充分的叙述。 ( 2 ) 本文对数据挖掘方面的知识进行了简单的介绍，包括数据挖掘的分类，并 由结构挖掘引出了基于链接结构的排序算法。 ( 3 ) 对基于链接结构的搜索引擎结果排序的两种算法h i t s 以及p a g e r a n k 进 行了分析研究。并着重分析了p a g e r a n k 算法的特点以及存在的不足，以及前人对 p a g e r a n k 的改进算法。并深入分析原始算法后提出了自己的改进算法 s p - p a g e r a n k 。 ( 4 ) 利用内外存交换及多线程技术实现了基于数据预取的p a g e r a n k 与 s p p a g e r a n k 计算平台。通过实验，对比了使用数据预取前后的计算效率问题。 1 3论文的组织结构 本文是对基于p a g e r a n k 算法的研究与改进，全文共分六章，论文结构按如下 的方式进行组织： 第二章，搜索引擎及数据挖掘综述。介绍互联网的发展和搜索引擎产生的必 然联系，阐述了搜索引擎的发展历史和各个历史条件下具有代表性的搜索引擎的 特征。搜索引擎的分类和模块组成。对w e b 挖掘的三个方面：内容挖掘、结构挖 掘和使用挖掘做了简要的分析，本文主要涉及到的是w e b 结构挖掘。 第三章，对基于链接结构的搜索引擎排序算法h i t s 和p a g e r a n k 做了对比分 析，从原理到算法的缺点。重点研究了p a g e r a n k 算法的原理，优化策略，以及前 人提出的一些改进算法。 第四章，对内外存交换技术进行了比较深入的研究，引入了i o 优化的方法一 数据预取，最后根据原始算法的特点提出改进的算法s p p a g e r a n k 。 第五章，在前面理论的基础上，用j a v a 编程语言实现了基于数据预取的 p a g e r a n k 与s p p a g e r a n k 计算平台，通过实验表明了数据预取方法在计算比较大 数据量的时候的有效性。 第六章，总结所做的工作，并对下一步的研究工作进行了展望。 2 2 搜索引擎及w e b 挖掘综述 2 1搜索引擎的发展历史和分类 在互联网发展初期，网站相对较少，信息查找比较容易【3 j 。然而伴随互联网爆 炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大 众信息检索需求的专业搜索网站便应运而生。这直接导致了信息检索课题的产生 和发展，尤其是在互联网领域对信息检索的依赖，使得信息检索一搜索引擎成为 人们工作和生活不可或缺的工具。搜索引擎是通过采集标引众多网络站点来提供 全局性网络资源控制与检索机制，通过整合全球互联网信息资源，并将其合理的 重组，从而方便用户查找所需要的信息。 2 1 1搜索引擎发展历史 搜索引擎主要经历了如下几个时期【3 】： ( 1 ) 起源和萌芽时期 所有搜索引擎的祖先，是1 9 9 0 年由m o n t r e a l 的m e g i l lu n i v e r s i t y 学生a l a n e m t a g e 、p e t e rd e u t s c h 、b i l lw h e e l a n 发明的a r c h i e ( a r c h i ef a q ) 。当时w o r l dw i d e w e b 还未出现。a r c h i e 是第一个自动索引互联网上匿名f t p 网站文件的程序，但 它还不是真正的搜索引擎。a r c h i e 是一个可搜索的f t p 文件名列表，用户必须输 入精确的文件名搜索，然后a r c h i e 会告诉用户哪一个f t p 地址可以下载该文件。 a r c h i et 作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜索网上的 文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由于a r c h i e 深 受用户欢迎，受其启发，美国内华达s y s t e mc o m p u t i n gs e r v i c e s 大学于1 9 9 3 年开 发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索引文件外，已 能检索网页。 ( 2 ) 逐步发展时期 随着互联网的发展，一种专门在网络间爬来爬去，检索信息的机器人程序出 现了，这就是后来搜索引擎用来爬取网页的蜘蛛程序一网络蜘蛛。当时，“机器人 一词在编程者中十分流行。电脑“机器人”( c o m p u t e rr o b o t ) 是指某个能以人类无 法达到的速度不问断地执行某项任务的软件程序。由于专门用于检索信息的“机 器人”程序像蜘蛛一样在网络间爬来爬去，因此，搜索引擎的“机器人 程序就 3 被称为“蜘蛛 程序。世界上第一个用于监测互联网发展规模的“机器人 程序 是由m i tm a t t h e wg r a y 开发的w o r l dw i d ew e bw a n d e r e r 。用于追踪互联网发展规 模。刚开始它只用来统计互联网上的服务器数量，后来则发展为也能够捕获网址 ( u r l ) 。与w a n d e r e r 相对应，m a r t i nk o s t e r 于1 9 9 3 年1 0 月创建了a l i w e b ，它 是a r c h i e 的h t t p 版本。a l i w e b 不使用“机器人”程序，而是靠网站主动提交 信息来建立自己的链接索引，类似于现在我们熟知的y a h o o 。随着互联网的迅速发 展，使得检索所有新出现的网页变得越来越困难，因此，在m a t t h e wg r a y 的 w a n d e r e r 基础上，一些编程者将传统的“蜘蛛”程序工作原理作了些改进。其设想 是，既然所有网页都可能有连向其他网站的链接，那么从跟踪一个网站的链接开 始，就有可能检索整个互联网。到1 9 9 3 年底，一些基于此原理的搜索引擎开始纷 纷涌现，其中以j u m ps t a t i o n 、t h ew o r l dw i d ew e bw o r m 和r e p o s i t o r y - b a s e d s o f t w a r ee n g i n e e r i n g ( r b s e ) s p i d e r 最负盛名。然而j u m ps t a t i o n 和w w ww o r m 只 是以搜索工具在数据库中找到匹配信息的先后次序排列搜索结果，因此毫无信息 关联度可言。而r b s e 是第一个在搜索结果排列中引入关键字串匹配程度概念的 引擎。 ( 3 ) 第一代搜索引擎 无论是纯技术型的搜索引擎还是分类目录，都可以认为是互联网上的第一代 搜索引擎。最早现代意义上的搜索引擎出现于1 9 9 4 年7 月。当时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 。 同年4 月，斯坦福( s t a n f o r d ) 大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e r r y y a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。从 此搜索引擎进入了高速发展时期。据统计，1 9 9 6 年，互联网已有十几个大型综合 性搜索引擎，各种专用的搜索引擎也达七十多个。在中文网页世界，由于汉字处 理的特殊性和中文信息资源站点正处于初步发展时期，中文搜索引擎相对出现得 比较晚，在1 9 9 7 年，首个中文网络搜索引擎g o y o y o 在香港问世，随后中文搜索 引擎才陆续在网上发布。这些被后人称为第一代搜索引擎。代表：y a h o o ，a l t a v i s t a 和i n f o s e e k 。当时网页的数量还不是很多，被索引的数据也不超过1 0 0 万个网页。 搜索结果的好坏往往用反馈结果的数量来衡量，也就是说，第一代搜索引擎“求 全。 ( 4 ) 第二代搜索引擎 1 9 9 8 年，以g o o g l e 和d i r e c th i t 为代表的第二代搜索引擎出现在互联网上， 这些搜索引擎的主要特点是提高了查准率，可以用“求精”来描述，在这个目标 指导下，进行了新的检索技术的研发，因此这个时期的搜索引擎着重考虑用户对 搜索引擎和搜索结果的体验，网页结果的排序质量又是影响结果的最重要指标之 4 一。g o o g l e 的p a g er a n k 排序算法在很大程度上解决了这一难题，关于p a g er a n k 算法的探讨，下面的章节会有详述。第二代搜索引擎规模是在互联网数据库极大 丰富的背景下产生的，也是在互联网信息过载和信息迷向的时期到来，搜索引擎 在一定程度上缓解了这些问题，但互联网数据依然在增加，信息过载的问题，时 刻对搜索引擎带来冲击。 ( 5 ) 下一代搜索引擎 新一代的搜索引擎主要解决搜索引擎和用户之间的语义沟通问题，必须能够 表达和处理语义信息。所以，下一代搜索引擎的数据模型必须是语义数据模型。 而语义网( s e m a n t i cw e b ) 是这种语义模型的最好的选择。语义网采用 x m l + r d f + o n t o l o g y 三个层次描述信息资源，构成了计算机理解内容的基础。围 绕着建立语义网，将会发展一系列的技术，将是下一代搜索引擎所必须的。比如， 自动标注技术，信息抽取技术等等。因此，从这种意义上讲，下一代搜索引擎将 是智能化的。而如何为用户的学习和工作营造一个个性化的信息空间，是未来搜 索引擎应该追求的方向，这里包括如何表达信息需求，如何展示浏览搜索结构， 如何对个性化的信息需求建立模型等等。从这种意义上讲，下一代搜索引擎又将 是个性化的。 2 1 2 搜索引擎的分类 搜索引擎按其工作方式主要可分为三种【4 】，分别是目录索引类搜索引擎( s e a r c h i n d e xd i r e c t o r y ) 、全文搜索引擎( f u l lt e x ts e a r c he n g i n e ) 和元搜索引擎( m e t as e a r c h e n g i n e ) 。 ( 1 ) 目录索引类搜索引擎 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅 是按目录分类的网站链接列表而已。它需要更多的人工干预，其数据库由人工建 立1 5 j 。用户完全可以不用进行关键词( k e y w o r d s ) 查询，仅靠分类目录也可找到需要 的信息。目录索引中最具代表性的莫过于大名鼎鼎的y a h o o 雅虎。其他著名的还 有o p e nd i r e c t o r yp r o j e c t ( d m o z ) 、l o o k s m a r t 、a b o u t 等。国内的有搜狐、新浪、 网易搜索也都属于这一类。 ( 2 ) 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、 f a s t a l l t h e w e b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百度( b a i d u ) 。 它们都是通过从互联网上提取的各个网站的信息( 以网页文字为主) 而建立的数据 库中，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回 5 给用户，因此他们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种，种是拥有自己的 检索程序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人 ( r o b o t ) 程序，并自建 网页数据库，搜索结果直接从自身的数据库中调用，如上面提到的几家引擎；另 一种则是租用其他引擎的数据库，并按自定的格式排列搜索结果，如l y c o s 引擎。 ( 3 ) 元搜索引擎 这类搜索引擎没有自己的数据，而是将用户的查询请求同时向多个搜索引擎 递交，将返回的结果进行重复排除、重新排序等处理后，作为自己的结果返回给 用户。服务方式为面向网页的全文检索。这类搜索引擎的优点是返回结果的信息 量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能，用户需要做更多 的筛选。元搜索引擎在接受用户查询请求时，同时在其它多个引擎上进行搜索， 并将结果返回给用户。著名的元搜索引掣8 】有d o g p i l e ( w w w d o g p i l e c o r n ) ，综合了 o o o g l e ，y a h o os e a r c h ，m s ns e a r c h 的搜索结果，v i v i s i m o ( w w w v i v i s i m o c o r n ) 等。 在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如d o g p i l e ，有的则按 自定的规则将结果重新排列组合，如v i v i s i m o 。 ( 4 ) 几种非主流形式的搜索引擎 1 、集合式搜索引擎。如h o t b o t 在2 0 0 2 年底推出的引擎。该引擎类似m e t a 搜索引擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的4 个引擎当中选择，因此叫它“集合式搜索引擎更确切些。 2 、门户搜索引擎。如a o ls e a r c h 、m s ns e a r c h 等虽然提供搜索服务，但自 身即没有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。 3 、免费链接列表( f r e ef o r a l ll i n k s ，简称f f a ) 。这类网站一般只简单地滚动 排列链接条目，少部分有简单的分类目录，不过规模比起y a h o o 等目录索引来要 小得多。 2 2搜索引擎的基本组成 搜索引擎主要由搜索器，索引器，检索器，用户接口组成【6 】，示意图2 1 充分 表达了搜索引擎的各个模块组成。 6 2 2 1搜索器 图2 1 ：搜索引擎的结构示意图 f i g u r e 2 1 ：t h es t r u c t u r eo f s e a r c he n g i n e 搜索器俗称为网络蜘蛛( s p i d 盯) j ，也称为机器人( r o b o t ) ，爬行者( c r a w l e r ) 或 者蠕虫( w o r m ) ，其本质是一种计算机程序，按照某种策略自动在在互联网上爬行 并搜集互联网上的资料，它要尽可能多的搜集各种类型的新信息，同时由于网上 的信息更新很快，需要定期更新己经搜集过的资料，防止出现链接无效和链接信 息更换的情况，因此要求搜索引擎抓取网页具有持续性和周期性，并且周期不能 太长( g o o g l e 公司一般2 8 天重复一次查询) 。 涉及到如何具体抓取网页，可以有不同的考虑。其中常见的方法是：将w e b 视作为一张有向图，搜索过程如下：首先给定起始u r l 集合s ( 根节点集合) 开 始，沿着网页中的链接( 新的u r l 节点) ，按照不同的策略遍历( 深度优先或宽 度优先或两者结合) ，不停的从s 中移除u r l ，下载相应的网页，解析出网页中的 超链接u r l ，看是否己经被访问过，将未访问过的那些u r l 加入集合s 。整个过 7 程可以形象地想象为一个蜘蛛( s p i d e r ) 在蜘蛛网( w 曲) 上爬行( c r a w l ) 。 2 2 2索引器 网络机器人将遍历得到的页面存放在临时的数据库中。索引器的作用就是对 搜索器采集到的信息建立索引库以供查询 6 1 。索引一般按照倒排文件的格式存放。 在搜索引擎中一般有以下几类索引：内容索引( c o n t e n ti n d e x ) 和结构索引 ( s t r u c t u r ei n d e x ) 或链索弓l ( 1 i n ki n d e x ) 。这些索引在建立时涉及到索引的结构、索引 的可扩展性和分布特点、索引生成的并行化等技术问题。 l i l l l ( 索引，为了对超链创建索引，被抓取的网页看成是有节点和边的有向图。 其中节点为页面，边为超链。超链结构索引必须是可扩展和高效的。最通用的结 构信息是相邻信息。例如网页p ，获取p 所指向的网页以及指向p 的网页。如何有 效地处理这些大规模的有向图也是一个热点研究课题。 文本索引，即使超链索引所带来的功能很有效，但文本索引始终是搜索引擎 判断一篇文档是否与查询相关的主要方法。英文主要是基于词的索引，汉语有基 于词和基于字的两种情况。为了处理汉字与英文的混合查询，如“甲a ”等关键 词，也有学者将中文英文统一处理。这方面有比较成熟的算法，在此不作详细讨 论。 其它索引，有些搜索引擎允许对某一特定领域或特定站点进行检索，此时需 要建立站点索弓 ( s i t e i n d e x ) 。该站点索引将某一域名映射为属于那个域名的网页。 还可以建立其它类似的索引( 如地域、语种等) 用来改善或增加搜索引擎的功能。 索引文件通常占有相当大的空间。如何存储大容量索引并且要求存取快捷方便， 也是一个热点问题。有许多研究者提出了基于压缩的二或三级索引的方案。在保 证响应速度的前提下，该方案可以大大减少索引文件的空间。 2 2 3检索器 检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询 的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制引。 检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型四 种。 8 2 2 4用户接口 用户接口的作用是为用户提供可视化的查询输入和结果输出界面，提供用户 相关性反馈机制【8 1 。在输出界面中，搜索引擎将检索结果展现为一个线性的文档列 表，其中包含了文档的标题、摘要、所在u r l 等信息。用户需要逐个浏览以寻找 出所需的文档。用户接口的设计和实现使用人机交互的理论和方法，以充分适应 人类的思维习惯。 2 2 5搜索结果处理 搜索引擎通常会对一个查询返回大量的结果列表，混合着相关文档和不相关 文档，为提高查询效率对结果列表进行处理的技术包括以下几个方面。 ( 1 ) 文档摘要 搜索引擎向用户返回结果时给出文档的摘要帮助用户决定是否进一步查看此 文档。文档摘要算法的关键技术有采用词性标注进行语义分析；用统计方法提取 高频词( 去除停用词之后) ，以确定摘要，或者对开始句和结束句中出现的短语给 予较高的权重；通过寻找关键短语，确定重要句子如结论句等；使用中心文档来 代表文档集合，使用中心词汇来表示文档的方法。 ( 2 ) 检索结果排序 对检索结果文档进行排序可以提高用户查询效率。 l 、基于内容的相关度排序考虑用户所查询的词条在文档中的出现情况，包 括词条频率，逆文档频率，词条位置等因素，根据文档相关度决定其在检索结果 集中的位置。 2 、基于超链的相关度排序考虑一个页面被其它站点引用的次数，这基本上反 映了该页面的受欢迎程度( 重要性) ，超链中的标记文本( a n c h o r ) 对链宿页面也起到 了概括作用。s t a n f o r d 大学研究的p a g er a n k 算法，不仅考虑w e b 页上的标题或 文本，还考虑与之相连接的其他网站，通过为w e b 页面构造引用图，综合页面的 被引用次数，以及链源页面的重要性来判断链宿页面的重要性，能够查询与用户 请求相关的“权威”页面。 ( 3 ) 检索结果的联机聚类 用户查询相关的文档通常会聚类的比较近，而远离与查询无关的文档。因此 可利用聚类技术将结果文档集合分成若干组，同一组的文档内容相似度尽可能地 大，组问相似度尽可能地小，用户只需考虑他所选择的文档所在的组。 ( 4 ) 推测用户最终目的 9 通过各种技术推测用户没有在查询语句中表达出来的查询目的，如使用智能 代理跟踪用户检索行为，分析用户模型，通过同类用户的行为记录推荐相关页面； 使用相关度反馈机制，通过对查询请求的不断修正以提高系统搜索结果的精确度 等。 2 3搜索引擎的性能指标及发展趋势 互联网上的搜索引擎众多，各具特色，要合理评价一个搜索引擎的性能优劣 并不是一件容易的事，因为搜索引擎涉及的因素很多，且各因素之间相互影响， 不管是强调哪方面都势必会忽略另一个方面的作用。 2 3 1搜索引擎的性能指标 ( 1 ) 查全率 查全率( r e c a l l ) 3 l 称召回率，是对所需要信息被检出的程度的量度，用来表示 信息系统能满足用户需求的完备程度。指检索出的相关文档和文档中所有的相关 文档数的比率网，查全率的表示如下： 查全率( 尺) = 被检出相关文献数目系统中相关文献数目x 1 0 0 ( 2 1 ) ( 2 ) 查准率 查准率( p r e c i s i o n ) 3 l 称精确度，是衡量信息系统拒绝非相关信息的能力的一个 量度，表征系统能对信息的精确定位能力。指检索出的相关文档数与检索出的文 档总数的比率9 1 ，查准率的表示如下： 查准率僻) = 被检出相关文献数目被检出的文献总和1 0 0 ( 2 2 ) ( 3 ) 漏检率 漏检率表示系统丢失正确信息的概率，指未被检出相关文献数目和文档中所 有的相关文档数的比率，漏检率的表示如下： 漏检率俾) = 未被检出相关文献数目系统中相关文献数目1 0 0 ( 2 3 ) ( 4 ) 误检率 误检率表示描述系统检出错误文献的概率，指被检出非相关文献数目和检索 出的文档总数的比率，误检率的表示如下： 1 0 误检率僻) = 被检出非相关文献数目被检出的文献总和x1 0 0 ( 2 4 ) 2 3 2搜索引擎的发展趋势 搜索引擎已成为一个新的研究投资热点，它要用到信息检索、人工智能、计 算机网络、数据库、数据挖掘、数字图书馆、自然语言处理、多媒体信息处理等 多领域的理论和技术，具有综合性和挑战性。由于互联网络的急速发展，越来越 多的用户需要用到搜索引擎，搜索引擎带来了巨大的商机，成为现代电子商务发 展的一个必不可少的条件。现在搜索引擎已经引起了世界各国计算机科学界和信 息产业界的高度关注，g o o g l e 、微软、y a h o o 、i b m 等信息产业巨头目前都投入巨 资对其进行研究、开发，迅速推动搜索引擎技术朝前发展。在这个过程中，也出 现了很多值得注意的问题和研究动向，主要有如下几个方面。 ( 1 ) 注意提高信息查询结果的精度，提高检索的有效性 用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，用户最 关心的是搜索的相关性。现在任何一个搜索引擎都意识到了相关性对于用户检索 的重要性，都在致力于减少不相关搜索结果的出现。搜索引擎可以通过各种方法 获得用户没有在查询语句中表达出来的真正用途，其方式包括：使用智能代理跟 踪用户检索行为，分析用户模型；使用相关度反馈机制，使用户告诉搜索引擎哪 些文档和自己的需求相关( 及其相关的程度) ，哪些不相关，通过多次交互逐步求 精等。 ( 2 ) 进行信息过滤，提供个性化服务 利用自动获得的领域模型( 如w e b 知识、信息处理、与用户兴趣相关的信息 资源、领域组织结构) 、用户模型( 如用户背景、兴趣、行为、风格) 知识进行信 息搜集、索引、过滤( 包括兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、 对用户有用的信息提交给用户。搜索引擎可以不断学习、适应信息和用户兴趣动 态的变化，从而提供个性化的服务。微软将要推出的新操作系统v i s t a 可以跟踪记 录用户的所有操作信息，包括打开的每一个文件、每幅图片、m p 3 、电子图书 等，在用户上网检索时，搜索引擎可以根据平时记录的信息来过虑搜索结果，从 而大大提高相关性。虽然这样可能会泄露一些用户的私人信息，但相比较由此带 来的更高相关性的搜索结果，相信大多数用户还是愿意接受的。 ( 3 ) 提供基于内容的多媒体信息搜索服务 目前基于内容的多媒体搜索引擎技术仍然相当不成熟，理论上和实用上均有 许多问题亟待解决，尤其在系统模型优化、通用性设计、图像声音特征相关性研 究及在i n t e m c t 上实用化等方面，还是目前需要着力加强研究的地方。基于内容的 多媒体信息搜索是未来搜索引擎发展的必然趋势，随着技术的发展，相信不久的 将来我们就可以在方便的使用搜索引擎进行多媒体信息的检索。 ( 4 ) 在用户常用软件或工具中提供搜索服务 y a h o o 、h o t m a i l 在其用户邮箱的每一个页面上都有一个搜索框，使得用户在 收到邮件时如果想搜索什么时可以方便的进行。g o o g l e 在此基础之上则更进一步 发展了这一方面的技术，它可以根据邮件内容特点，在界面上显示一些用户可能 会感兴趣的付费广告，或者提供一些链接到相关内容的站点上。 2 4w e b 挖掘理论基础 2 4 1w i e b 挖掘的定义 w e b 挖掘( w e bm i n i n g ) 是数据挖掘在w e b 上的应用，是一项综合技术，涉及 网络、数据挖掘、计算机语言学、信息学等多个领域，不同研究者从自身的领域 出发，对w e b 挖掘的含义有着不同的理解，项目开发也各有其侧重点。数据挖掘 是指从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐 含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程【l0 1 。w e b 挖掘主要是指从互联网及其相关的资源和行为中抽取有用的模式和隐含信息【1 1 1 。 w e b 挖掘的对象是指互联网上的资源，以及和互联网相关的资源，包括存在于互 联网上的所有w e b 文档及w e b 服务器上的日志文件以及用户资料，其本质是一种 知识发现的手段。w e b 挖掘是针对w e b 页面内容，站点拓扑结构，用户访问信息， 用户注册信息及电子商务交易信息等在内的各种数据，应用数据挖掘方法以发现 有用的知识的过程。它可以帮助人们从互联网中发现知识，改进站点设计，提供 个性化服务。 2 4 2w e b 挖掘的分类 w e b 挖掘是从w w w 资源上挖掘有趣的、潜在的、有用的模式及隐藏的信息 的过程【1 2 1 ，它是将数据挖掘技术和理论应用于对w w w 资源进行挖掘的一个新兴 的研究领域。目前在该研究领域中，由于w e b 上信息的多样性决定了w e b 挖掘任 务的多样性，r a y m o n dk o s a l a 1 3 1 等人指出，w 曲挖掘包含以下三个领域的研究内 容：w e b 内容挖掘，w e b 结构挖掘和w e b 使用记录挖掘。如图2 2 所示。 1 2 图2 2 - w e b 挖掘的分类 f i g u r e 2 2 ：c a t e g o r i e so f w e bm i n i n g ( 1 ) w e b 内容挖掘 自从i n t e r n e t 产生以来，上网的用户和网上的信息就呈指数形式飞速增长。然 而当单个用户面对整个i n t e r n e t 的海量信息时，用户往往感到很难找到他真正需要 的有用信息。搜索引擎是当前广泛被采用的一项技术，每天都有无数的i n t e m e t 用 户通过搜索引擎查询他们需要的信息。但是搜索引擎一般只对网上的静态信息进 行“抓取”，而对于由用户提问动态生成的结果或存储于后台w e b 数据库中的信息 却无能为力，这也正是网络内容挖掘研究的重点所在。 w e b 内容挖掘是指对w e b 页面内容进行挖掘，从文本，图像，音频，视频等 各种形式的网络资源中发现所需的特定化信息。用户在网上能看到的主要是文本 和图像信息，随着i n t e m e t 的进一步延伸，w e b 数据越来越庞大，种类越来越繁多。 除了数字图书馆及政府部门提供的相关数据信息，也有各商用公司自己组建的数 据仓库，其中既有文本数据信息，也有图像、声频、音频等多媒体数据信息，既 有来自于数据库的结构化数据，也有用h t m l 标记的半结构化数据及无结构的自 由文本数据信息。 w e b 内容挖掘包括了对w e b 文本的总结、分类、聚类、关联分析、以及利用 w e b 文档进行自动推荐等。w e b 内容挖掘可以看作是w e b 信息检索( i r ) 和信息抽 取( q e ) 的结合。对w e b 内容挖掘主要集中在利用词频统计、分类算法、机器学习、 元数据( m e t ad a t a ) 。部分h t m l 结构信息发现、数据间隐藏的模式发现并生成抽 取规贝1 j ( e x t r a c t i o nr u l e ) ，从页面中分离出概念( c o n c e p t ) 和实体( e n t i t y ) 的数据。同 时对文本的挖掘不仅仅包括信息检索中文档的信息提取，同时也包含了文档集合 分析。文本挖掘包括对文本的分类、归类，还涉及到决策树等算法。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘