（计算机应用技术专业论文）基于pagerank算法的搜索引擎优化策略研究.pdf

基于p a g e r a n k 算法的搜索引擎优化策略研究 专业：计算机应用技术 研究生：张巍指导教师：李志蜀 f 摘要1 随着网络技术的迅猛发展，w w w 已成为信息发布、交互及获取的主要工 具，它涉及瓿闻、广告、消费、金融、教育、电子商务等许多领域。w e b 具有 四个特点：庞大性、动态性、异构性、半结构化的数据结构环境。此外，w e b 还包含卡富和动态的超链接资源。面对w e b 这些固有特点，人们要从这些海量 的数据中查找数据和信息，使用最多的就是搜索引擎技术。 w e b 挖掘包含三个方面的内容：内容挖掘、结构挖掘和使用挖掘，本文主 要涉及到其中的w e b 结构挖掘。结构挖掘是从w w w 的组织结构、w e b 文档 结构和链接关系中推导知识。就搜索引擎技术领域来说，可以通过分析一个网 贞或整个网站链接和被链接的数量、对象，建立w e b 自身的链接结构模式，通 过分析和研究p a g e r a n k 、h i t s ，t s p r 等基于链接结构的搜索结果排名算法， 可以指导网站链接结构优化，有组织，有规划地提高网页在搜索结果中的排名， 避免盲目处理造成的混乱结果。本文主要针对目前主流的p a g e r a n k 算法，集 中研究了该算法的形成思路、计算方法，并分析该算法在独立网站、包含索引 页面、包含入站链接和出站链接等几种模型下的效果，提出了相应的优化策略。 然后概要介绍了j a v a 版p a g e r a n k 计算程式的大体思路，并给出了通过本程序 验证这些优化策略的实验结果。最后通过总结p a g e r a n k 算法的优缺点，引入 了t o p i cs e n s i l i v ep a g e r a n k ，h i l l l o p 等算法并做厂简要介绍。 w e b 挖掘是知识时代人们对于从大量信息中获取知识的需要。对于搜索引 擎来说，w e b 挖掘技术( 要是内容挖掘和结构挖掘) 对第三代搜索引擎的发 眨起黄重的作用，同时也促进融络信息获取技术向高精度、智能化方向发展。 关键词：搜索引擎；w e b 结构挖掘；超链接；p a g e r a n k r e s e a r c ho no p t i m i z i n gs t r a t e g i e so fs e a r c he n g i n e b a s e do np a g e r a n ka l g o r i t h m s p e c i a l t y ：c o m p u t e ra p p l i c a t i o n m a s t e rc a n d i d a t e ：z h a n gw e ia d v i s o r ：l iz h i s h u 【a b s t r a c t a l o n gw i t hr a p i dp r o g r e s so fc o m p u t e rn e t w o r kt e c h n o l o g y , 唧n h a sb e c o m e t h em a i nf a c i l i t yt h a tp e o p l eu s e dt or e l e a s e ，i n t e r c h a n g ea n dr e t r i e v ei n f o r m a t i o n i t i si n v o l v e di nm a n yf i e l d ss u c ha sn e w s ，a d ，c o n s u m p t i o n ，f i n a n c e ，e d u c a t i o na n d e b u s i n e s s f o u rc h a r a c t e r i s t i c so fw e ba l et h ef o l l o w i n g ：b i gs c a l e ，d y n a m i c ， l s o m e r o u sa n dh a l f - s t r u c t u r e dd a t ac o n d i t i o n w e ba b o u n d sw i t h h y p e r l i n k r e s o u r c e sa sw e l l d u et ot h e s ec h a r a c t e r s ，w ec a n u s es e a r c he n g i n et e c h n o l o g yt o g e ti n f o r m a t i o na n dd a t af r o mw e b t h r e em a i nc o n t e n t so fw e bm i n i n g 辩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 ga n d u s a g em i n i n g w e bs t r u c t u r em i n i n gi st od e d u c es o r t i eh n do fk n o w l e d g ef r o m s t r u c t u r e so fw 州w e bd o c u m e n t sa n dh y p e r l i n k s a sf o rs e a r c he n g i n e ，w ec a n e s t a b l i s hal i n k i n gs t r u c t u r ep a t t e r nb ya n a l y z i n gq u a n t i t ya n dt a r g e t so faw e bp a g e o rw e b s i t e si n l i n k sa n do u t l i n k s b ys t u d y i n gs u c ha l g o r i t h m sb a s e do nh y p e r l i n k a s p a g e r a n k ，h i t sa n dt s p r ，w ec a ng u i d eo u rl i n k i n go p t i m i z a t i o na n d c o n t i n u o u s l yi m p r o v et h ew e b s i t e sr a n k a v o i db a dr e s u l t so fb l i n d n e s s t h ea r t i c l e f o c u s e so nt h ep a g e r a n k , a n a l y z e st h ei d e aa n dc a l c u l a t i n gm e t h o do ft h ea l g o r i t h m ， e s t a b l i s h e sd i f f e r e n tm o d e l sa n da d v a n c e sr e l a t e do p t i m i z i n gs t r a t e g i e s f u r t h e r m o r e ， s o m ep r o g r a mi sm a d ei nj a v at ov a l i d a t et h er e s u l ta sw e l l f i n a l l y ，t h ea r t i c l e c o n c l u d e st h ed i s a d v a n t a g e so ft h ep a g e r a n ka n di n t r o d u c e st s p r ( t o p i cs e n s i t i v e p a g e r a n k ) ，h i l l t o p w e bm i n i n gi so u rr e q u e s ti ng a t h e r i n gi n f o r m a t i o nf r o mb i gs c a l ek n o w l e d g e a sf o rs e a r c he n g i n e ，w e bm i n i n gt e c h n o l o g yp l a y s a l l i m p o r t a n tr o l e i n d e v e l o p m e n to ft h et h i r dg e n e r a t i o no fs e a r c he n g i n e ，a n dm e a n w h i l e ，i tp r o m o t e s t h en e t w o r ki n f o r m a t i o na c q u i r i n gt e c h n o l o g yt oah i g hp r e c i s i o na n di n t e l l i g e n t w a y k e yw o r d s ：p a g e r a n k ；s e a r c he n g i n e ；w e bs t r u c t u r em i n i n g ；h y p e r l i n k 四川大学碗上学位论文 1 引言 近年来，i n t e r n e t 已成为计算机领域最热门的一项技术i n t e r n e t 的普及使人 们可以突破空间、地域的限制，方便地共享资源。 w e b 已经成为人们获取信息的重要手段。据发表在科学杂志1 9 9 9 年7 月的文章w e b 信息的可访问性估计，全球的网页超过8 亿，有效数据超过 9 t ，并且仍以每9 个月翻一番的速度增长。而到目前为止，w e b 页面数目已超 过l o 亿，处在i n t e r n e t 上的数据以每天新增一百万个页面的速度增长，不到 4 个月的时间文档总数就会翻一番 2 】。 用户要在如此浩瀚的信息海洋里寻找信息，必然会“大海捞针”无功而返。 如何在w e b 这样的分布式环境中找到对自已有价值的信息，并从中提取出知识 内容已经成为目前信息检索、数据挖掘和知识管理等研究领域的重要课题。 搜索引擎( s e a r c he n g i n e ) 正是为了解决这个“迷航”问题而出现的技术。 搜索引擎是随着w e b 信息的迅速增加，从1 9 9 4 年开始逐渐发展起来的。 一般来说，搜索引擎是互联网提供公共信息检索服务韵w e b 站点，它是以一定 的技术和策略在互联网中搜集，发现网络信息，并对网络信息进行理解、组织 和处理，并为用户提供检索服务，从而起到信息导航的目的。 1 1 搜索引擎技术分析 根据搜索引擎的检索形式、对象或范围等，可以将搜索引擎服务区分为多 种不同的类型。如以检索形式划分，则可将其分为关键词检索和分类检索；以 检索对象划分，可分为新闻检索、w e b 检索、黄页服务、自页服务以及特殊搜 索服务。搜索引擎提供的导航服务已经成为互联网上非常熏要的网络服务，搜 索引擎站点也被美誉为“网络门户”。搜索引擎技术因而成为计算机工业界和学 术界争相研究、开发的对象。 四川大学硕士学位论文 同时目前搜索引擎领域的商业开发非常活跃，各大搜索引擎公司都在投巨 资研制搜索引擎系统，也不断地涌现出新的具有鲜明特色的搜索引擎产品，搜 索引擎已经成为信息领域的产业之一。在这种情况下，对搜索引擎技术相关领 域的学术研究得到了大学和科研机构的重视。如s t a n f o r d 大学在其数字图书馆 项目中开发了g o o g l e 搜索引擎，在w e b 信息的高效搜索、文档的相关度评价、 大规模索引等方面作了深入的研究，取得了很好的成果。n e c 美国研究所的 s t e v el a w r e n c e 和c l e eg i l e s1 9 9 8 年和】9 9 9 年连续两年在自然和科学 杂志上撰文对搜索引擎技术的研究进行评述。著名的信息检索会议t r e c 也从 1 9 9 8 年开始增加了w e b t r a c k 课题，以考察w e b 文档与其它类型文档在检索性 质上的不同之处，并将测试在大规模的w e b 库( 如1 0 0 g 字节) 上进行信息检 索的算法性能【3 】。由美国n f o r n o t i c s 公司主办的搜索引擎国际会议从1 9 9 6 年 开始，每年举行一次，对搜索引擎技术进行总结、讨论和展望，参加者有著名 的搜索引擎公司、大学和研究机构的学者，对搜索引擎技术起到了很好的推动 作用。另外像i e e e 主办的国际万维网会议、人机交互会议已有越来越多关于 搜索引擎技术研究的文章发表。 国内先后有北京大学、清华大学、国家智能研究中心等高校和研究单位对 搜索引擎技术开展研究，并开发出了几个较好的系统。如由北京大学计算机系 网络研究室开发的“天网”中英文搜索引擎，在系统规模及系统性能方面达到 了国外中型搜索引擎系统的技术水平，为国内用户提供了很好的互联网搜索服 务，受到了用户的好评【4 】。 1 1 1 分类 搜索引擎为人们提供了检索w e b 上相关信息的方法，搜索引擎对w e b 上的 文档进行索引并进行分类，为人们提供一个w e b 内容的层次化的目录结构；有 的搜索引擎对w e b 上的页面进行全文索引，提供基于关键词的检索。总的来说 可以将搜索引擎分为三类【5 】： 四川大学硕士学位论文 1 1 1 1 基于r o b o t 的搜索引擎 基于r o b o t 的搜索引擎一般由r o b o t 、分析器、索引器、索引数据库、检索 器和用户接口组成 5 】。 r o b o t 就是搜索器其功能是在互联网中漫游，发现和搜集信息，也叫s p i d e r 或c r a w l e r 。它常常是一个程序，从事先制定好的u r l 列表出发自动访问w e b 站点，以广度优先或深度优先的方法从w e b 上下载页面：它要尽可能多、尽可 能快地搜集各种类型的新信息，同时因为互联网上的信息更新很快，所以还要 定期更新已经搜集过的旧信息，以避免死连接和无效连接。目前有两种搜集信 息的策略： 从一个起始u r l 集合开始，顺着这些u r l 中的超链( h y p e r l i n k ) ，以 广度优先、深度优先或启发式方式循环地在互联网中发现信息。这些起始u r l 可以是任意的u r l ，但常常是一些非常流行、包含很多链接的站点( 如y a h o o ! ) 。 将w e b 空间按照域名、m 地址或国家域名划分，每个搜索器负责一个 子空间的穷尽搜索。 搜索器搜集的信息类型多种多样，包括h t m l 、x m l 、n e w s g r o u p 文章、 矸p 文件、字处理文档、多媒体信息。 搜索器的实现常常用分布式、并行计算技本，以提高信息发现和更新的速 度。商业搜索引擎的信息发现可以达到每天几百万网页。 分析器对下载页面的内容进行分析以用于索引，具体包括分词、过滤、转 换等工作。 索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示 文档以及生成文档库的索引表。 索引器将文档表示为一种便于检索的方式并存储在索引数据库中，一般采 用的方法有矢量空间模型( v e c t o r s p a c e m o d e l ) 、倒l j 文档、概率模型等； 索引项有客观索引项和内容索引项两种：客观项与文档的语意内容无关， 如作者名、u r l 、更新时间、编码、长度、链接流行度( l i n kp o p u l a r i t y ) 等等： 四川大学硕士学位论文 内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内 容索引项可以分为单索引项和多索引项( 或称短语索引项) 两种。单索引项对 于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符( 空格) ： 对于中文等连续书写的语言，必须进行词语的切分。 在搜索引擎中，一般要给单索引项赋与一个权值，以表示该索引项对文档 的区分度，同时用来计算查询结果的相关度。使用的方法一般有统计法、信息 论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。 索引表一般使用某种形式的倒排表( i n v e r s i o nl i s t ) ，即由索引项查找相应 的文档。索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索 引项之间的相邻或接近关系( p r o x i m i t y ) 。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必 须实现即时索弓i ( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息量急剧增加的速度。 索引算法对索引器的性能( 如大规模峰值查询时的响应速度) 有很大的影响。 一个搜索引擎的有效性在很大程度上取决于索引的质量。 i n d e x 是一个数据库，r o b o t 采集到的网页信息全部存于其中。数据库的规 模直接影响了系统查询的查全率。有些记录了网页的全部内容，对整个h t m l 文件的所有单词都建立索引，有的只记录网页的地址、标题、关键词、摘要等 信息，还有的能处理h t m l 文件中的m e t a 的标记或其它不可见的特殊标记。 检索器的功能是根据用户的查询在索引库中快速检出文档，实现用户查询 关键词和目标文档匹配度的计算，根据计算结果所有符合查询要求的页面u r l 按照相关度递减的顺序排列，并实现某种用户相关性反馈机制。 检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合 模型四种。 用户接口为用户提供一个输入查询请求，定制查询结果的w e b 页面并将查 询结果格式化后返回给浏览器。 用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机 制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得 4 网j l l 大学硕上学位论文 到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以 充分适应人类的思维习惯。用户输入接口可以分为简单接口和复杂接口两种。 简单接口只提供用户输入查询串的文本框；复杂接口可以让用户对查询进 行限制，如逻辑运算( 与、或、非；+ 、一) 、相近关系( 相邻、n e a r ) 、域名 范围( 如e d u 、c o m ) 、出现位置( 如标题、内容) 、信息时间、长度等等。目 前一些公司和机构正在考虑制定查询选项的标准。 1 1 1 2 目录搜索引擎 目录搜索引擎比r o b o t 搜索引擎需更多的人工干预，其数据库由人工建立。 编辑人员先访问某个w e b 站点，根据内容归类，再把网址、简介、类别等描述 信息存入库中。查询时，搜索软件只需检索这些描述。目录界面一般采用分级 结构，用户从基本的大类入口一级级向下访问，直至找到中意的内容；用户也 可利用目录提供的搜索功能直接查询关键词。由于目录依靠人工分类，因此搜 索出的结果往往比r o b o t 搜索引擎更精确，但目录只在保存的站点描述中进行 搜索，站点本身的变化不会反映到搜索结果中。由于目录和基于r o b o t 的搜索 引擎有各自的优缺点，很多搜索引擎都同时提供目录和基于r o b o t 的搜索服务， 以便尽可能地提供全面准确的查询结果。 1 1 1 3 元搜索引擎 元搜索引擎也叫m e t a 搜索弓l 擎。严格说来，m e t a 搜索引擎不是真正的搜 索引擎，只能算作一种用户代理。它自己不进行w w w 的遍历，也没有自己的 索引数据库【6 】。当用户查询一个关键词时，它把查询请求转换为其它搜索引擎 的命令格式，分别向其它搜索引擎提交，然后汇总这些搜索引擎返回的结果， 组织后返回用户浏览器【3 l 】。利用m e t a 搜索引擎，查询范围可涉及多个搜索引 擎的数据库。由于不同的元搜索引擎挂接的独立搜索引擎各不相同，且各独立 搜索引擎的查询语法差别较大，所以元搜索引擎一般仅支持a n d ，o r ，n o t 等 四川太学硕士学位论文 较简单的语法操作。与独立搜索引擎相比，大多数元搜索引擎不能灵活控制结 果的输出。不过，最近元搜索引擎提高了自身的功能，可按站点、域名来排列 结果，还可以选择独立搜索引擎，并对输出结果进行精选等【7 】。 1 1 2 搜索引擎性能指标 衡量w e b 搜索引擎的性能指标，主要由以下几个方面组成： 1 ) 收录范围 每种搜索引擎都有特定的收录对象与方针。选择搜索系统必须先对以下资 料特性加以了解。 首先是资料量的大小。虽然数量多并不能确保查询质量也能一样好，但查 询结果可能会较完整。就收录项目而言，许多搜索引擎不仅收集一种资源，有 时还收录多种不同资源供使用者选取查询。一般来说，收录项目越多对于查询 就越方便，因为使用同一套指令就可以查询多种数据库。就索引深度而言，有 些系统是将全文建立索引，有些则选择其中部分信息建立索引，索引深度越深 查询就能越详尽。就新颖性及更新频率而言，所收录的资源是否新颖及是否经 常更新，都会影响到查询结果的正确性。因此若搜索系统更新索引的频率不高， 最好就不要使用，以免查到一些陈旧甚至是错误的信息。就索引建立方式而言， 现有的搜索系统多半采取自动化的索引建立方式，因此在资料维护上可节省人 力；但以目前的技术而言，想要以自动他的方式做到去其糟粕取其精华还有一 段距离，而以人工建立索引的方式在数据质量上较易掌握。如分类目录这类搜 索系统就无法完全依赖自动化索引系统。自动化的索弓l 程序只能协助前半部的 资料收集工作，之后还是得由人工逐一筛选。就处理语言丽言，i n t e m e t 上的资 源是属于多国语言，若搜索系统能处理多种语言，如查询时可以以使用者熟悉 的语言文字输入，系统再将相关的信息不论语种一并找出，并以输入时的语言 文字输出结果，则对查询会有很大帮助。就提供评论丽言，某些搜索系统提供 了资源的评论，这对使用者而言或许会有些参考价值。虽然评论可能流于主观， 6 四川大学硕士学位论文 但至少提供摘要性介绍，以免仅凭资源名称来判断其内容。 2 ) 检索功能 i n t e r n e t 资源搜索系统所提供的检索功能，其实和传统网上数据库大同小异， 前者虽然缺乏某些复杂的功能，但也具备某些先进的功能。每种搜索引擎所提 供的检索功能虽略有不同，但大致包含布尔逻辑、词组查询、相近检索、限制 字段、重复资料检测等功能，或进一步提供相似性反馈信息、关键词检索、自 然语句输入等较先进功能，同时对于大小写及特殊符号等处理每个系统也略 有差异 2 4 】。 3 ) 检索结果的显示 查询结果的输出方式也是评价的重点之一，因为输出方式不好会阻碍浏览 的效果。 例如相关性排序，i n t e r n e t 上资源庞大，若查询结果只能按字母顺序显示， 势必耗费大量时间和精力去浏览。目前一些搜索系统所采用的方式，即是根据 资源与查询的相关性来排序，最相关的资料就会排在最前面。又如有些系统允 许使用者自定义资料显示的数量，可节省浏览时间。而显示资料的详细程度也 会影响资料的参考价值【2 5 】。 此外，目前的搜索系统在查询结果时都会以h y p e r l i n k 方式展现，如此使用 者可在查到结果后，立即链接获取原始文件或档案。 4 ) 检索效率 虽然居前搜索系统的检索速度都相当快，但检索效率并不一定能有相同表 现。在评价检索效率时可由召回率( r e c a l lr a t i o ) 、精度( p r e c i s i o nr a t i o ) 、反 应时间( r e s p o n s e t i m e ) 及联机容易程度( a c c e s s i b i l i t y ) 等方面加以考虑。召 回率是检索出的相关文档数和文档库中所有的相关文档数的比率，衡量的是检 索系统( 搜索弓i 擎) 的奁全率；精度是检索出的相关文档数与检索出的文档总 数的比率，衡量的是检索系统( 搜索引擎) 的查准率。对于一个检索系统来讲， 一般召回率和精度不可能两全其美：召回率高时，精度低，精度高时，召回率 低。所以常常用1 1 种召回率下1 1 种精度的平均值( 即点平均精度) 来衡量 四川大学硕士学位论文 个检索系统的精度f 4 】。对于搜索引擎系统来讲，因为没有一个搜索引擎系统 能够搜集到所有的w e b 网页，所以召回率很难计算。目前的搜索引擎系统都非 常关心精度。 5 ) 使用者接口 使用者接口的设计也是评价搜索引擎一个相当重要的因素，因为设计不良， 即使查询功能再多、再好，也可能无法吸引大众使用。一般而言，搜索系统的 使用者接口是否优良，可从直观上判断其是否易于使用。此外，其是否提供辅 助说明( 如指令的使用) ，是否提供f a q 之类的文件( 如介绍系统特色) ，是否 考虑到文字模式的使用者环境等都是参考因素【3 4 】。 事实上，在运用搜索引擎时，我们会发现相同查询需求，在不同的搜索引 擎上执行，很少会有相同的查询结果。这主要还是因为每种搜索引辇的软件设 计方法都不大相同。此外，每种查询需求所适用的范围也不相同。如想查询某 个单位w w w 网站地址，就不太适合利用a l t av i s t a 这类资源庞大的大站，因 为很容易就找到太多资料，反雨不如乖j 用w e b c r a w l e r 让查询范围缩小而变得 较好找。因此，所谓的最佳搜索引擎可随着应用以及检索技巧而异。 影响一个搜索引擎系统的性能有很多因素，最主要的是信息检索模型，包 括文档和查询的表示方法、评价文档和用户查询褶关性的匹配蘸略、查询结果 的排序方法和用户进行相关度反馈的机制。 1 2i n t e r n e t 搜索引擎发展演化历史 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网 爆炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满 足大众信息检索需求的专业搜索网站便应运丽生了。 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明的a r c h i e 。虽然当时w w w ( w o r l d w i d e w e b ) 还未出现，但网络中文件传输 还是相当频繁的，而且由于大量的文件散布在各个分散的却主机中，查询起 四川大学硕士学位论文 来非常不便，因此a l a n e m t a g e 想到了开发一个可以以文件名查找文件的系统， 于是便有了a r c h i e 。a r c h i e 工作原理与现在的搜索引擎已经很接近，它依靠脚本 程序自动搜索网上的文件，然后对有关信息进行索引，供使用者以一定的表达 式查询。由于a r c h i e 深受用户欢迎，受其启发，美国内华达s y s t e mc o m p u t i n g s e r v i c e s 大学于1 9 9 3 年开发了另一个与之非常相似的搜索工具，不过此时的搜 索工具除了索引文件外，已能检索网页。 当时，“机器人”一词在编程者中十分流行。电脑“机器人”( c o m p u t e rr o b o t ) 是指某个能以人类无法达到的速度不问断地执行某项任务的软件程序。由于专 门用于检索信息的“机器人”程序象蜘蛛一样在网络闾爬来爬去，因此，搜索 引擎的“机器人”程序就被称为“蜘蛛”程序( s p i d e r ) 。 世界上第一个用于监测互联网发展规模的“机器人”程序是m a t t h e wg r a v 开发的w o r l dw i d ew e bw a n d e r e r 。刚开始它只用来统计互联网上的服务器数量， 后来则发展为能够检索网站域名。 与w a n d e r e r 相对应，m a r t i n k 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 。 1 ) 第一代搜索引擎l1 9 9 4 年至1 9 鳃年 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因 此，在m a t t h e wg r a y 的w a n d e r e r 基础上，一些编程者将传统的“蜘蛛”程序 工作原理作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接， 那么从跟踪一个网站的链接开始，就有可能检索整个互联网。到1 9 9 3 年底，一 些基于此原理的搜索引擎开始纷纷涌现，其中以 u m p s t a t i o n 、t h e w o r l d w i d e w e b w o r m 和r e p o s i t o r y - - b a s e ds 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 p s t a t i o n 和w w ww o r n l 只是以搜索工具在数据库中找到匹配信息的 先后次序排列搜索结果，因此毫无信息关联度可言。而r b s e 是第一个在搜索结 果排列中引入关键字串匹配程度概念的引擎。 最早现代意义上的搜索引擎出现于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 。 l y c o s 是搜索引擎史上又一个重要的进步。1 9 9 4 年7 月2 0 日，数据量为5 4 ，0 0 0 的l y c o s 正式发布。除了相关性排序外，l y e o s 还提供了前缀匹配和字符相近限 制，l y c o s 第一个在搜索结果中使用了网页自动摘要，而最大的优势还是它远胜 过其它搜索引擎的数据量：1 9 9 4 年8 月3 9 4 ，0 0 0 篇文档；1 9 9 5 年1 月1 5 0 0 万 篇文档；1 9 9 6 年1 1 月超过6 0 0 0 万篇文档。( 注：1 9 9 9 年4 月，l y c o s 停止自己 的s p i d e r ，改由f a s t 提供搜索引擎服务) 。 同年4 月，斯坦福大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e r r y y a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心。 从此搜索引擎进入了高速发展时期。 i n f o s e e k 是另一个重要的搜索引擎，虽然公司声称1 9 9 4 年1 月已创立，但 真到年底它的搜索引擎才与公众见面。起初，i n f o s e e k 只是一个不起眼的搜索 s l 擎，它沿袭y a h o o ! 和l y c o s 的概念，并没有什么独特的革新。但是它的发展 史和后来受到的众口称赞证明，起初是否第一个登台并不总是很重要。i n f o s e e k 的友善用户界面、大量附加服务使它声望日隆。而1 9 9 5 年1 2 月与n e t s c a p e 的 战略性协议，使它成为一个强势搜索引擎：当用户点击n e t s c a p e 浏览器上的搜 索按钮时，弹出i n f o s e e k 的搜索服务，而此前由y a h o o ! 提供该服务。( 注：i n f o s e e k 后来曾以相关性闻名，2 0 0 1 年2 月，i n f o s e e k 停止了自己的搜索引擎，开始改 用o v e r t u r e 的搜索结果) 1 9 9 5 年，种新的搜索引擎形式出现了元搜索引擎。用户只需提交一 次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引 擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理展再返回给用 户。第一个元搜索引擎，是w a s h i n g t o n 大学硕士生e r i cs e l b e r g 和o r e n e t z i o n i 的m e t a c r a w l e r 。但元搜索引擎概念上好听，搜索效果始终不理想，所以没有哪 个元搜索引擎有过强势地位。 d e c 的a l t a v i s t a 是一个迟到者，1 9 9 5 年1 2 月才登场亮相。但是，大量的创 新功能使它迅速到达当时搜索引擎的顶峰。a l t a v i s t a 最突出的优势是它的速度。 1 0 四川大学硕士学位论文 而a l t a v i s t a 的另一些新功能，则永远改变了搜索引擎的定义。a l t a v i s t a 是第一个 支持自然语言搜索的搜索引擎，a l t a v i s t a 是第一个实现高级搜索语法的搜索引 擎( 如a n d ，o r , n o t 等) 。用户可以用a l t a v i s t a 搜索n e w s g r o u p s ( 新闻组) 的内容 并从互联网上获得文章，还可以搜索图片名称中的文字、搜索t i t l e s 、搜索i a v a a p p l e t s 、搜索a c t i v e x 。a l t a v i s t a 最有趣的新功能之一，是搜索有链接指向某个 u r l 的所有网站。在面向用户的界面上，a l t a v i s t a 也作了大量革新。它在搜索框 区域下放了“t i p s ”以帮助用户更好的表达搜索式，这些小卸经常更新，这样， 在搜索过几次以后，用户会看到很多他们可能从来不知道的的有趣功能。这系 列功能，逐渐被其它搜索引擎广泛采用。1 9 9 7 年，a l t a v i s t a 发布了一个图形演 示系统l i v e t o p i c s ，帮助用户从成千上万的搜索结果中找到想要的。2 0 0 3 年2 月 1 8 日，a l t a v i s t a 被o v o r t r r e 收购。 然后到来的是i n k t o m i 。1 9 9 5 年9 月2 6 日，加州伯克利分校计算机科学系 助教e r i cb r e w e r 、博士生p a u lg a u t h i e r 创立了i n k t o m i ( l i eb e r k e l e ya n n o u n c e s i n k t o m i ) ，1 9 9 6 年5 月2 0 日，i n k t o m i 公司成立，强大的h o t b o t 出现在世人面 前。声称每天能抓取索引1 千万页以上，所以有远超过其它搜索引擎的新内容。 h o t b o t 也大量运用c o o k i e 储存用户的个人搜索喜好设置。h o t b o t 曾是随后几年 最受欢迎的搜索引擎之一，后被l y c o s 收购。 n o r t h e m l i g h t 公司于1 9 9 5 年9 月成立于马萨诸塞州剑桥，1 9 9 7 年8 月， n o r t h e r n l i g h t 搜索引擎正式现身。它曾是拥有最大数据库的搜索引擎之一，它没 有s t o pw o r d s ，它有出色的c u r r e n tn e w s 、7 ，1 0 0 多出版物组成的s p e c i a lc o l l e c t i o n 、 良好的高级搜索语法，第一个支持对搜索结果进行简单的自动分类。 2 ) 第二代搜索引擎：1 9 9 8 年至今 1 9 9 8 年1 0 月之前，g o o g l e 只是s t a n f o r d 大学的一个小项目b a c k r u b 。1 9 9 5 年博士生i _ a r r yp a g e 开始学习搜索引擎设计，于1 9 9 7 年9 月1 5 日注册了 g o o g l e c o m 的域名，1 9 9 7 年底，在s e r g e yb r i n 和s c o t th a s s a n 、a l a ns t e r e m b e r g 的共同参与下，b a c h r u b 开始提供d e m o 。1 9 9 9 年2 月，g o o g i e 完成了从a l p h a 版到b e t a 版的蜕变。g o o g l e 公司则把1 9 9 8 年9 月2 7 日认作自己的生日。 四川大学硕士学位论文 g o o g l e 在p a g e r a n k 、动态摘要、网页快照、d a i l y 刷新、多文档格式支持、 地图股票词典寻人等集成搜索、多语言支持、用户界面等功能上的革新，象 a | t a v i s t a 一样，再一次永远改变了搜索引擎的定义。 在2 0 0 0 年中以前，g o o g l e 虽然以搜索准确性备受赞誉，但因为数据库不如 其它搜索引擎大，缺乏高级搜索语法，所以推广并不快。直到2 0 0 0 年中数据库 升级后，又借被y a h o o 选作搜索引擎的东风，才一飞冲天。 值得提的是2 0 0 3 年1 1 月1 6 日，g o o g l e 与以往相比有了显著的变化。这 些变化不光体现在搜索界面上，实际上某些排名结果与以前有了很大的不同： 某些商业站点排名骤跌。此外，在g o o g l e 的这此调整中引入了关键词词干 ( k e y w o r ds t e m m i n g ) 技术。换言之，如果在搜索框中键入“d i e t a r y ”，那么也 会得到一些基于“d i e t 的搜索结果。关于这一点还是请大家看看g o o g l e 的解释 “g o o g l e 目前使用了词根还原技术”。也就是说，它不再拘泥搜索与输入查 询完全相同的词语，亦会向用户提供与部分或所有查询词语相近的搜索结果。 例如，对于查询词语“p e tl e m u rd i e t a r yn e e d s ”，g o o g l e 也会显示 p e tl e m u rd i e t n e e d s ”及其它词性变化形式的搜索结果。而且对于搜索结果页上出现的查询词 本身及其不同的变化形式，g o o g l e 会以粗体突出表示。”【3 】 f a s t ( a l l t h e w e b ) 公司创立于1 9 9 7 年，是挪威科技大学( n t n u ) 学术研究的副 产品。1 9 9 9 年5 月，发布了自己的搜索引擎a l l t h e w e b 。f a s t 创立的目标是做世 界上最大和最快的搜索引擎，几年来庶几近之。f a s t ( a l l t h e w e b ) 的网页搜索可 利用o d p 自动分类，支持f l a s h 和p d f 搜索，支持多语言搜索，还提供新闻搜索、 图像搜索、视频、m p 3 、和邱搜索，拥有极其强大的高级搜索功能。( 2 0 0 3 年 2 月2 5 日，f a s t 的互联网搜索部门被o v o r t u r e 收购) g i g a b l a s t 由前i n f o s e e k 工程师m a t tw e l l s 刨立，2 0 0 2 年3 月展示p r e - - b e t a 版，2 0 0 2 年7 月2 1 日发布b e t a 版。g i g a b l a s t 的数据库目前仍偏小，但也提供 网页快照，一个特色功能是即时索引网页，你的网页刚提交它就能搜索。 关于中文搜索引擎 o p e n f i n d 创立于1 9 9 8 年1 月，其技术源自台湾中正大学吴升教授所领导的 四川大学硕士学位论文 g a i s 实验室。o p e n f i n d 起先只做中文搜索引擎，鼎盛时期同时为三大著名门户 新浪、奇摩、雅虎提供中文搜索引擎，但2 0 0 0 年后市场逐渐被b a i d u 和g o o g l e 瓜分。2 0 0 2 年6 月，o p e n f i n d 重新发布基于g a i s 3 0p r o j e c t 的o p e n f i n d 搜索引擎 b e t a 版，推出多元排序( p o l y r a n k t m ) ，宣布累计抓取网页3 5 亿，开始进入英文 搜索领域，此后技术升级明显加快。 在教育网使用最为频繁的北大天网，是国家“九五”重点科技攻关项目“中 文编码和分布式中英文信息发现”的研究成果，由北大计算机系网络与分布式 系统研究室开发，于1 9 9 7 年1 0 月2 9 日正式在c e r n e t 上提供服务。2 0 0 0 年初 成立天网搜索引擎新课题组，由国家9 7 3 重点基础研究发展规划项目基金资助 开发，收录网页约6 0 0 0 万，利用教育网优势，有强大的f 砸搜索功能。 2 0 0 0 年1 月，两位北大校友，超链分析专利发明人、前i n f o s e e k 资深工程 师李彦宏与好友徐勇( 加州伯克利分校博士后) 在北京中关村创立了百度 ( b a i d u ) 公司。2 0 0 1 年8 月发布b a i d u c o m 搜索引擎b e t a 版( 此前b a i d u 只为 其它门户网站搜狐新浪t o m 等提供搜索引擎) ，2 0 0 1 年1 0 月2 2 日正式发布b a i d u 搜索引擎，专注于中文搜索。b a i d u 搜索引擎的其它特色包括：百度快照、网页 预射预览全部网页、相关搜索词、错别字纠正提示、r a p 3 搜索、f l a s h 搜索。2 0 0 2 年3 月闪电计划( b l i t z e np r o j e c t ) 开始后，技术升级明显加快。 随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗已无法适应 目前的市场状况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的 搜索引擎技术和搜索数据库服务提供商。 总的来说，第二代搜索引擎虽然比第一代在搜索速度、针对多种语言信息 的扩展等方面有所改进，在以自然语言为查询语言方面也做了一些探索。然而， 随着i n t e m e t 的强势发展，网上庞大的数字化信息和人们获取所需信息能力之 问的矛盾日益突出。在2 0 0 1 年下半年公布的一份报告表明，前期被大肆宣传为 “使用简便易用，搜索结果丰富”的搜索引擎技术正在被信息更集中的局域网 取代，因为大多数搜索系统的表现与用户的期