（计算机应用技术专业论文）一种自治的分布式信息采集与检索系统.pdf

网j n 大学计算机学硫2 0 0 3 缀硕士学位论文 一种自治的分布式信息采集与检索系统 计算机应用专业 研究生：王放指导教师：袁道华教授 随着以通讯、互联网为主的科学技术的发展，信息的获取和剥雳越来越方 便和快捷，使得信息技术正在静悄悄改变我们的生活，改变我们的世界。 但是，海量信息的出现也使得人们越来越迷失方向。人们渴望找到一种能 方便获取信怠的方式。搜索弓l 擎的出瓒，在一定程序上解决了这个闻越。现在， 搜索引擎已经是人们使用得最多的互联网服务之一。 但是，在集中式的搜索引擎实现方案中，系统在健壮性和扩展性都存在不 足，这会导致系统服务经常停止，并带来了很高的系统运 亍维护成本。而且， 随着互联网发展到以“个性化”那“互动性”为特征w e b 2 0 对代，搜索引擎 也显露出了自身的不足。 针对以上的不足，本文提出了一种基于搜索引擎技术的分布式信息采集与 捡索服务体系模整。首先，这是一种基于搜索弓l 辇技术的系统，它能够实对监 控指定信息源，在第一时间采集到最瑟的信息，对信恩进行处理，供用户检索； 其次，本系统是分布式的，通过多个后台结点间的相互合作，使得系统具有良 好的健壮性和扩展性；再次，在系统设计中还融入了自治思想，把系统在正常 运行嚣对维护人员的依赣降到了最低，大大降低了系统运行维护成本；最露， 系统不仅能够支持常规的网页查询服务方式，也能支持信息主动推送的工作方 式，使得信息服务更加个性化。 本文首先研究了相关的理论，介绍了搜索引擎技术的发展与原理、分布式 系统的基本概念和垂治系统戆思想。然后提出信息采集与检索系统的体系模 型，并从其体系结构、系统策略、各功模块设计思想等方顽进行了深入而广 qj i l 大学计算讥学院2 0 0 3 级硕圭学位论文 泛的讨论。最后，对系统进行了性能评测。 关键词：搜索弓l 擎，分布式系统，自治系统，w e b 2 0 h 四川大学计算机学院2 0 0 3 级硕士学位论文 a na u t o n o m o u sa n dd i s t r i b u t e ds y s t e mo ni n f o r m a t i o n c o l l e c t i n ga n dr e t r i e v a l m a j o r ：c o m p u t e ra p p li c a t i o n s t u d e n t ：w a n gf a n g a d vis e r ：p r o f y u a nd a o h u a t h ed e v e l o p m e n to ft h es c i e n c ea n dt e c h n o l o g yi n t h ef i e l do f c o m m u n i c a t i o na n di n t e r n e tp r o v i d e sm o r ec o n v e n i e n ta c c e s st ot h e a c q u i s i t i o na n du t i l i t yo fi n f o r m a t i o na n dp r o d u c e sp o t e n t i a li n f l u e n c e o no u rl i v i n gs t y l ea n dt h ew o r l dg r a d u a l l y n o r m a l l y ，o n et e n d st of e e lh e l p l e s sa tt h eh u g ea m o u n to fi n f o r m a t i o n t h u s ，i ti sp r o m p t e dt os e e kam e t h o db yw h i c hw ec a l lg e tt h er i g h t i n f o r m a t i o nc o n v e n i e n t l ya n di n s t a n t l y p r e s e n t l y , s u c he x p e c t a t i o ni s r e a l i z e dt oac e r t a i nd e g r e eb ys e a r c h i n ge n g i n e ，o n eo f t h em o s t i m p o r t a n tw e ba p p l i c a t i o n s h o w e v e r ，s e a r c h i n ge n g i n e b u i l to nc e n t r a l i z e ds y s t e ms t r u c t u r e d i s p l a y ss o m ed e f e c t si nr o b u s t n e s sa n de x p a n s i b i l i t y ，l e a d i n gt o d i s c o n t i n u o u ss y s t e ms e r v i c e sa n dh i g hm a i n t e n a n c ec o s t m o r e o v e r ，w h e n t h ei n t e r n e t g o e s i n t o w e b 2 0 ， w h i c hi sc h a r a c t e r i s t i co f i n d i v i d u a t i o n a n di n t e r a c t i o n ，i n s u f f i c i e n c yo nc a p a b i l i t yw a s d i s c l o s e dw i t h i ns e a r c h i n ge n g i n ei t s e l f t os o l v ea f o r em e n t i o n e dp r o b l e m s ，ad i s t r i b u t e ds y s t e ms e r v i c e a r c h i t e c t u r ef o ri n f o r m a t i o nc o l l e c t i o na n dr e t r i e v a l ，b a s e do n s e a r c h i n ge n g i n et e c h n o l o g y i se s t a b li s h e d f i r s t l y 。t h i ss y s t e m m o n i t o r sp a r t i c u l a ri n f o r m a t i o ns o u r c e si nr e a lt i m e ，d e t e c t sa n d d o w n l o a d st h en e w l y - r e l e a s e do n ea ss o o na sp o s s i b l ea n dm a k e si n d e x f o ri n f o r m a t i o nr e t r i e v es e r v i c e s s e c o n d l y ，t h i ss y s t e mi ss ow e l l d i s t r i b u t e da n di n t e r a c t e dt h a ti tb e a r se x c e l l e n tr o b u s t n e s sa n d m 四川大学计算机学院2 0 0 3 级硕士学位论文 e x p a n s i b i l i t y t h i r d l y 。a u t o n o m o u st h i n k i n gi si n c o r p o r a t e di n t ot h i s s y s t e ma sw e l la n dt h em a i n t e n a n c ec o s ti sg r e a t l ym i n i m i z e d a tl a s t 。 i n d i v i d u a t i o no ni n f o r m a t i o ns e r v i c ew a sm a t e r i a l i z e db e c a u s ei tn o t o n l yo f f e r sw e br e t r i e v a ls e r v i c e ，b u ta l s os u p p o r t sa c t i v ep u s h i n g m e t h o d i nt h i ss t u d y ，t h et h e o r i e so ns e a r c h i n ge n g i n e ，d i s t r i b u t e ds y s t e ma n d a u t o n o m o u ss y s t e mw e r ep r e s e n t e dr e s p e c t i v e l ya tt h ev e r yb e g i n n i n g t h e nt h es e r v i c es y s t e ma r c h i t e c t u r eo ni n f o r m a t i o nc o l l e c t i n ga n d r e t r i e v i n g w a si n t r o d u c e d w ee l a b o r a t e d d e e p l y i nt h e s y s t e m a r c h i t e c t u r e ，s y s t e ma n dm o d u l es t r a t e g y a tl a s t ，i th a sb e e ne v a l u a t e d o np e r f o r m a n c e se x h i b i t e db yt h i si n f o r m a t i o ns e r v i c ea r c h i t e c t u r e k e y w o r d s ：s e a r c h i n ge n g i n e ，d i s t r i b u t e ds y s t e m ，a u t o n o m o u ss y s t e m ， w e b 2 0 四川大学计算机学院2 0 0 3 级硕士学位论文 1 引言 1 1 互联网改变了人们的生活 互联网的出现，使得远隔千山万水的人们也能够方便地进行交流与沟通。 w e b ，e - m a i l ，f t p ，b b s 等等网络应用早已经渗透进了现代人的生活。网络自 从问世以来，就一直保持着高速的发展状态。就我国来说，据统计，截止到 2 0 0 5 年1 2 月3 1 日，我国的网民总人数为l l l 0 0 万人，网民普及率已经达到 8 5 。与上年同期调查结果相比，我国网民总人数在一年之内增加了1 7 0 0 万 人，增长率为1 8 1 ，而同1 9 9 7 年1 0 月第一次调查结果6 2 万网民人数相比， 现在的网民总人数已是当初的1 7 9 倍。截止到2 0 0 5 年1 2 月3 1 日，我国的上 网计算机总数已达4 9 5 0 万台，与上年同期相比，增加了7 9 0 万台，增长率为 1 9 0 9 6 ；是1 9 9 7 年l o 月第一次调查结果2 9 9 万台的1 6 5 6 倍。而目前全球网 民约9 7 亿。平均普及率为1 5 2 m4 网络规模的迅猛发展带来了互联网上资源的爆炸性增长，可以这样说，人 们都能够在网上找到自己需要的信息，事实上，人们也逐渐习惯了这样做。然 而，海量信息的出现也使得人们不可避免的逐渐迷失在了浩如烟海的信息中。 人们逐渐发现，虽然有大量的资源存在于互联网之上，但是若要方便的找到自 己需要的资源，总是缺乏一种行之有效的方法。于是，搜索引擎技术应运而生， 并越来越受到重视。越来越多的人已经习惯使用搜索引擎在互联网上查找信 息。目前，搜索引擎已经成为了一种重要的网络应用。 搜索引擎使用程序周期性遍历网络上的海量网页，从其中提取有效信息， 对这些信息进行索引，供人们查询。现代的搜索引擎网页覆盖面广，内容相关 性好，更新更加及时。据统计，浏览新闻、搜索引擎、收发邮件已经成为网民 最常使用的三大网络服务，其中，搜索引擎已经占整个网络服务功能的 6 5 7 1 】。可见，随着互联网的发展，人们越来越依赖于搜索引擎获取有用的 信息。 四川大学计算机学院2 0 0 3 级硕士学位论文 不过，现在的搜索引擎仍然存在一些不足；除了搜索结果的相关性之外， 最突出的一点就是搜索引擎还不够个性化。也就是说，不同用户，提交了相同 的关键字后，得到的都足相同的信息。但事实上，这些用户可能需要的是不同 的信息，他们需求的相同之处只有关键字。也就是说，搜索引擎在返回查询结 果时，还没有考虑用户所在地域、用户年龄、使用习惯等差异。随着互联网技 术的发展，个性化和互动性越来越被人们所重视与提倡。这也对搜索提出了更 高的要求。 1 2w e b 2 o 一互联网发展的新特性 同许多改变人们生活的新技术一样，互联网最初也是来源于军事需求。成 立于1 9 5 7 年冷战期间的美国高级计划署( a r p a ) 为了对抗苏联，启动了一个 计划，用于建立一个称为a r p a n e t 的网络。这就是现代互联网的雏形 互联网的本质就是各个网络连接起来，使得各个网络结点间的数据能够互 连互通。互联网的一般原则就是一组互相连接的网络，通过叫做“路由器”的 硬件按照“尽力传送原则”在互相独立的网络间实现通信。 在互联网慢慢转向民用之初，个人用户还只能利用为数不多的有限的资 源。随着互联网技术的发展，尤其是万维网的出现，使得个人和企业能够更加 方便地在互联网上创建属于自己的站点，在上面共享资源。而随着各式各样的 站点的增多，门户网站随后产生，它涵盖了绝大多数站点的功能。通过门户网 站，一般用户就能够完成上网的绝大部分需求。再后来，随着网络应用的逐渐 丰富，门户网站也不能够涵盖人们上网的需要了，而且，人们已经不再满足于 被动接收信息，他们开始追求个性化的空间。用户在互联网上的作用越来越大； 他们贡献内容，传播内容，而且提供了这些内容之间的链接关系和浏览路径。 时下，博客( b l o g ) ，p 2 p 应用，r s s ，w i k i ，s n s ，网摘等都是个性化应用的 例子同最初的网络应用相对，对于互联网的新特性，人们为之取名叫做 w e b 2 0 0 “1 。可以说，w e b 2 0 是以用户为核心的互联网。 人们对于w e b 2 0 的特性也进行了大量的讨论和研究，最终提炼出了 w e b 2 0 时代互联网应用应具有的3 个具体的特征，即及时性、个性化和互动 2 四川大学计算机学院2 0 0 3 级硕士学位论文 性。 在w e b 2 o 所提倡的个性化的思想下，搜索引擎提供的信息检索服务也应 当具备“因人而异”的特征，也就是说，搜索引擎返回的结果应该根据用户的 不同而不同。再进一步，搜索引擎应该能够尽可能的把用户潜在需要的信息在 第一时间主动送达用户面前。用户再无需关心这些信息是从何而来、如何而来， 因为，信息已经呈现在他面前了。 1 3 利用分布式系统带来高性能 搜索引擎可以使用多种架构来实现，但是，用分布式系统来实现搜索引擎 的功能，具有许多潜在的好处： 1 ) 分布式系统的多结点协作可以有效分布负载，减少工作负荷，从而减 少机器故障； 2 ) 利用多结点备份可以在某些结点失效时仍然能够维持系统的运转，提 供不问断检索服务，使系统具有高稳定性； 3 ) 利用分布式系统的特征，可以方便地向系统中添加结点，提高系统性 能，而无需进行复杂的二次开发，也不会影响现有正在运行的系统结点。 4 ) 分布式系统还是一种低成本的解决方案，利用多个低性能的结点来实 现高性能结点的效果。 1 4 引入自治思想，减少维护成本 系统在运行之后，应尽可能的实现自我管理。一般来说，再系统上线提供 服务之前，都会进行短期的测试，通过测试之后才被允许对外提供服务但是， 随着连续服务时间的增加，数据量的增大，一些在短期测试中无法发现的问题 会随之出现，可能引起程序的异常，造成服务中断。如果仅由维护人员主动监 视程序运行状态，无疑是对人力成本的浪费。所以，在系统设计时引入自治思 想，当程序出现异常时，系统能够自动重新启动，并给出错误提示，记录出错 时系统状态，供事后维护人员参考。这样，就能在不中断服务的情况下大大减 3 四川大学计算机学院2 0 0 3 级硕士学位论文 少维护成本。 为此，本文融合了上述思想，提出并实现了一种分布式的信息采集与检索 系统。本系统依托搜索引擎技术，采用分布式体系结构加以实现，在系统规划 时引入自治思想，并能够提供网页查询与信息主动推送这两种的服务模式，从 而提供了及时、稳定、互动的信息服务。 4 四川大学计算机学院2 0 0 3 级硕士学位论文 2 相关技术理论 2 1 搜索引擎技术 搜索引擎技术是一种提供信息检索的技术。搜索引擎使用程序从互联网上 的信息源获取信息，并进行归类处理，缩短人们查找信息的时间。通过对现有 搜索引擎技术的研究，我们能够从中提取出信息采集的方式与方法，将它们应 用与我们的系统，从而实现对指定信息源的监控和对特定信息的获取，为信息 采集系统的后续处理过程奠定坚实的基础。 2 1 1 搜索引擎技术的发展历史 搜索引擎是随着互联网服务器信息的迅速增长从九十年代开始逐渐发展 起来的技术嘲。早期的网络主要是文字界面，并不直观也不是很容易使用，这 时的网络用户主要是研究人员和专业的网络使用人员。因为网络资源相对较 少，所以对于搜索引擎并没有太多的应用要求。后来网络浏览器大规模普及， 极大地推动了互联网的普及。普通网络用户成为了网络用户的主体，网络用户 的大规模增加又促进了互联网规模的不断扩大。对于网络用户来说，可供使用 的网络资源非常多，不可能通过自己来维护这些资源的相关信息，更不可能实 时更新这些相关信息。所以，搜索引擎技术就越来越受到人们的重视。 搜索引擎( s e a r c he n g i n e s ) 利用网络自动搜索技术，对互联网各种资源 进行索引，并为检索者提供检索服务搜索引擎网站是互联网上专门提供查询 服务的一类网站，这些网站通过网络自动索引软件或网络登录等方式，将互 联网上大量网站的页面收集到本地，经过对这些信息进行分类、建立索引，然 后对索引的内容建立数据库，从而能够对用户提出的各种查询做出响应，提供 给用户所需的信息。搜索引擎技术，来源于人们对知识获取途径的探索。 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网 爆炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满 足大众信息检索需求的专业搜索网站便应运而生了 5 四川大学计算机学院2 0 0 3 级硕士学位论文 在1 9 9 0 年之前，没有人能够搜索互联网。现代意义上的搜索引擎的祖先， 是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明的a r c h i e 。虽然当时万维网 ( w o r l dw i d ew e b ) 还未出现，但网络中的文件传输还是相当频繁的，而且由 于大量的文件散布在各个分散的f t p 主机中，查询起来非常不便，因此a l a n e m t a g e 想到了开发一个可以通过文件名查找文件的系统，于是便有了a r c h i e 。 r r c h i e 工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜 索网上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由 于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 年开发了另一个与之非常相似的搜索工具g o p h e r ( g o p h e rf a o ) 搜索工具v e r o n i c a ( v e r o n i c af a q ) 。不过此时的搜索工具除了索引文件外， 已能检索网页。 当时，“机器人”一词在编程者中十分流行。电脑“机器人”( c o m p u t e r r o b o t ) 是指能以人类无法达到的速度不间断地执行某项任务的软件程序。由 于专门用于检索信息的“机器人”程序象蜘蛛一样在网络间爬来爬去，因此， 搜索引擎的“机器人”程序也被称为“蜘蛛”程序。 世界上第一个用于监测互联网发展规模的“机器人”程序是m 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 。刚开始它只用来统计互联网上的服务器数 量，后来则发展为能够检索网站域名。 与w a n d e r e r 相对应，m a r t i nk o s t e r 于1 9 9 3 年l o 月创建了a l i w e b ，它 是r 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 d w i d ew e bw o r m ( g o t o 的前身，也就是后来的o v e r t u r e ) ，和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 o r m 只是以搜索工具在数据库中找到匹配信息 6 四川大学计算机学院2 0 0 3 级硕士学位论文 的先后次序排列搜索结果，因此毫无信息关联度可言。而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 。同年4 月，斯坦福( s t a n f o r d ) 大学的两名博士生，d a v i df i l o 和美 籍华人杨致远( g b r r yy a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜 索引擎的概念深入人心，从此搜索引擎进入了高速发展时期。目前，互联网上 有名有姓的搜索引擎已达数百家，其检索的信息量也与从前不可同日而语。例 如最近风头正劲的g o o g l e ，其数据库中存放的网页已达8 0 亿之巨l 随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗已无法适应 目前的市场状况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的 搜索引擎技术和搜索数据库服务提供商。象国外的i n k t o m i ( 已被y a h o o 收购) ， 它本身并不是直接面向用户的搜索引擎，但向包括o v e r t u r e ( 原g o t o ，已被 y a h o o 收购) 、l o o k s m a r t 、m s n 、h o t b o t 等在内的其他搜索引擎提供全文网页 搜索服务因此从这个意义上说，它们是搜索引擎的搜索引擎。 现在，搜索引擎所收集的资源也已经从最初的网页扩展到f t p 文件、新 闻组、g o p h e r 、e - m a i l 以及多媒体信息等。依靠搜索技术的支持，搜索引擎 门户们也推出了各式各样的信息服务：地图搜索、图片搜索、硬盘搜索等。搜 索服务也从最初的网站页面，迁移到了浏览器工具条，最终来到桌面。 2 1 2 搜索引擎的工作方式 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索 引擎( m e t as e a r c he n g i n e ) 嘲。 2 1 2 1 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、 f a s t a l l t h e w e b 、a l t a y i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有 7 四川大学计算机学院2 0 0 3 级硕士学位论文 百度( b a i d u ) 。它们都是从互联网上提取的各个网站的信息( 以网页文字为主) ， 建立数据库，从中检索与用户查询条件匹配的相关记录，然后按一定的排列顺 序将结果返回给用户，因此他们是真正的搜索引擎。 从搜索结果来源的角度，全文搜索引擎又可细分为两种，一种是拥有自己 的检索程序( i n d e x e r ) ，俗称“蜘蛛”( s p i d e r ) 程序或“机器人”( r o b o t ) 程序，并自建网页数据库，搜索结果直接从自身的数据库中调用，如上面提到 的7 家引擎；另一种则是租用其他引擎的数据库，并按白定的格式排列搜索结 果，如l y c o s 引擎。 2 1 2 2 目录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅 仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词 ( 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 等。国内的h a 0 1 2 3 就属于这一类这类通过手 工维护得很好的系统的优点是提供的网页准确率高，可以有效地覆盖热门的主 题，但它们的缺点是过于主观，并需要高昂的代价来建立和维护目录，且限于 维护人员的知识面，并不能很好地覆盏所有的主题。后来虽然出现了用程序进 行登记的方法，但还是没有从根本上解决目录服务所面临的主要问题。 2 1 2 3 元搜索引擎 元搜索引擎其实不是真正意义上的搜索引擎，因为它并没有自己的索引数 据库，它是将用户的搜索请求分发到多个独立的搜索引擎，然后将各个独立的 搜索引擎返回的结果进行归并后返回给用户。 这种设计在一定程度上避免了独立搜索引擎因为商业因素或是设计上的 局限而对搜索结果产生的干扰，从而使得搜索结果更加公正，同时还可以很大 程序上避免独立搜索引擎因为索引数据库更新周期的原因而没有遍历到互联 网新增内容( 不同独立搜索引擎的更新时间不会碰巧总是重合) ，同时调用多 8 i l l 大学计算机学院2 0 0 3 级硕士学位论文 个搜索引擎也会大大提高信息的覆盖面。可以说元搜索引擎是对独立搜索引擎 的一种封装。元搜索弓i 擎在接受用户查询请求时，同时在其他多个引擎上进行 搜索，并将结果返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、 v i v i s i m o 等( 元搜索引擎列表) ，中文元搜索引擎中具代表性的有搜星搜索引 擎等。 在搜索结果排列方面，有的元搜索引擎直接按来源引擎排列搜索结果，如 d o g p i l e ，有的则按自定的规则将结果重新排列组合，如v i v i s i m o 。 除上述三大类引擎外，还有以下几种非主流形式： l 、集合式搜索引擎：如h o t b o t 在2 0 0 2 年底推出的引擎。该引擎类似元 搜索引擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的 4 个引擎当中选择，因此叫它“集合式”搜索引擎更确切些。 2 、门户搜索引擎：如a o ls e a r c h 、m s ns e a r c h 等虽然提供搜索服务，但 自身即没有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。在国 内，腾讯公司的搜索引擎( w w s o s o c o m ) 就是这种类型。 3 、免费链接列表( f r e ef o ra l ll i n k s ，简称f f a ) = 这类网站一般只简 单地滚动排列链接条目，少部分有简单的分类目录，不过规模比起y a h o o 等目 录索引来要小得多 由于上述网站都为用户提供搜索查询服务，为方便起见，我们通常将其统 称为搜索引擎。 2 1 3 搜索引擎的工作原理 2 1 3 1 全文搜索引擎 全文搜索引擎从网站提取信息，进行处理，建立网页数据库吣。搜索引 擎的自动信息搜集功能分两种。一种是定期搜索，即每隔一段时间( 比如 g o o g l e 一般是2 8 天) ，搜索引擎主动派出“蜘蛛”程序，对一定i p 地址范围 内的互联网站进行检索，一旦发现新的网站，它会自动提取网站的信息和网址 加入自己的数据库。 另一种是提交网站搜索，即网站拥有者主动向搜索引擎提交网址，它在一 9 四川大学计算机学院2 0 0 3 级硕七学位论文 定时间内( 2 天到数月不等) 定向派出“蜘蛛”程序到达这个的网站，扫描网 站并将有关信息存入数据库，以备用户查询。由于近年来搜索引擎索引规则发 生了很大变化，主动提交网址并不保证网站能进入搜索引擎数据库，因此目前 最好的办法是多获得一些外部链接，让搜索引擎有更多机会找到网站并自动将 网站收录。 当用户以关键词查找信息时，搜索引擎会在数据库中进行搜寻，如果找到 与用户要求内容相符的网站，便采用特殊的算法一通常根据网页中关键词的 匹配程度，出现的位置频次，链接质量等计算出各网页的相关度及排名 等级，然后根据关联度高低，按顺序将这些网页链接返回给用户。 以下就是全文搜索引擎的体系结构册： 图1 ：全文搜索引擎的体系结构 在全文搜索引擎中，网页获取称为网页爬行( c r a w i n g ，指网页下载过程) ， 是由若干个分布式的网络爬虫( c r a w l e r ) 软件实现的。u r ls e r v e r 将若干个 需求提交给若干个网络爬虫进行处理，每个网络爬虫可以同时打开大约3 0 0 个连接线程，以保持一个足够快的网页爬行速度。当网页数据被取回后，会被 送到s t o r es e r v e r 中，s t o r es e r v e r 对网页数据进行压缩，然后保存到 r e p o s i t o r y 数据库中。每一个网页都有一个惟一的i d 编号称为d o c i d 。 网页爬行有几个主要的问题要解决，一是面对众多不可控的服务器如何提 l o 四川大学计算机学院2 0 0 3 级硕士学位论文 高网页爬行的性能和可靠性；二是如何防止下载到垃圾页面；三是如何避免获 取网页所有者不希望被访问的页面。 索引器的任务是解析r e p o s i t o r y 中的文档以建立前序索引，文档被解析 成为一组命中( h i t ) 。命中是一种数据结构，其中记录了每个词在文档中的位 置，大小写、字体相对大小等信息。索引器利用这些命中来建立一个部分排序 的前序索引。前序索引的结构如下图所示： l d o c i i 个 w r 缸d 弋i r i 三 r 缸k l t - d 1 - r 图2前序索引结构图 前序索引分别存放在一组桶( 桶指一部分硬盘存储空间) 中，每个桶中包 含一定范围的w o r d i d ( 单词编号) 值，当文档中有词对应到某个桶中的w o r d i d ， 就将此d o c i d 记录到桶中，每个d o c i d 后跟一个属于它的w o r d i d 列表( 此 w o r d i d 列表中的所有w o r d i d 都属于这个桶) ，每个w o r d i d 后又跟着相应的命 中列表( 此w o r d l d 在此d o c l d 中的命中列表) 。可以看出无论是单个桶还是所 有桶，前序索引都会包含大量的重复的d o c l d ，造成一定程度的空间浪费，但 前序索引的结构便于进行文档解析，同时使得建立后序索引的时间和编程的复 杂度大大降低。 前序索引以文档编号d o c i d 为序，便于进行文档解析，但用户的搜索请求 是以关键字组合来表达的，因此还需要建立以w o r d l d 为序的索引以便于迸行 搜索，这就是后序索引。当前序索引建立完成后，排序器接管了它们。后序索 引结构如下图所示： 明川大学计算机学院2 0 0 3 缓硕士学位论文 l t r d i n 巾 d c i 升叫h t i - d c 工 h l t 4 0 c i | 1 t d e c 工 d o e 工 图3后序索引结构图 在后序索引建立以后，有一个叫d u m p l e x i c o n 的工具将后序索引中的 w o r d i d 与字典相结合产生一个新的字典，新字典、后序索引、p a g e r a n k 一起 为用户提供检索服务。 在使用搜索引擎服务的过程中，用户面对常常是数以十万计的返回结果， 所以用户一般只会去点击排在前一百位的搜索结果，因此，搜索引擎最关注的 并不是如何返回尽可能多的结果，而是尽可能地将最有可能与用户搜索请求相 关的结果链接排在返回结果的前面。搜索结果中对应页面的p a g e r a n k 值是全 文搜索引擎进行结果排序的一项重要依据。 p a g e r a n k 利用了互联网特有的互联特征，通过网页的被引用情况来计算网 页的级别( r a n k ) ，当一个网页a 被别的网页所引用后，就认为别的网页给a 投了票，a 所得的票数越多就说明a 越重要。 由于投票过程是在整个互联网范围内进行的，所以较大程度地排除了人为 因素的干扰。一个页面会因为别的页面对自己的引用而增加自己的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 值并不是每个页面都相同，各个搜索引擎都事先指定了一些网站级 别，级别越高的网站它所链接到的网页所获得的p a g e r a n k 值越高。这样对于 网页来说，很重要的一件事就是被重要网站所引用。 当用户查询请求到来时，搜索引擎先找到对应的结果集，按照结果的 p a g e r a n k 值等排序信息对结果进行排序，再显示给用户，完成一次查询过程。 四川大学计算机学院2 0 0 3 级硕士学位论文 2 1 3 2 目录索引 目录索引，顾名思义就是将网站分门别类地存放在相应的目录中，因此用 户在查询信息时，可选择关键词搜索，也可按分类目录逐层查找。如以关键词 搜索，返回的结果跟搜索引擎一样，也是根据信息关联程度排列网站，只不过 其中人为因素要多一些。如果按分层目录查找，某一目录中网站的排名则是由 标题字母的先后顺序决定( 也有例外) 。 与全文搜索引擎相比，目录索引有许多不同之处： 首先，搜索引擎属于自动网站检索，而目录索引则完全依赖手工操作。用 户提交网站后，目录编辑人员会亲自浏览你的网站，然后根据一套自定的评判 标准甚至编辑人员的主观印象，决定是否接纳你的网站。 其次，搜索引擎收录网站时，只要网站本身没有违反有关的规则，一般都 能登录成功。而目录索引对网站的要求则高得多，有时即使登录多次也不一定 成功。尤其象y a h o o 这样的超级索引，登录更是困难。此外，在登录搜索引擎 时，我们一般不用考虑网站的分类问题，而登录目录索引时则必须将网站放在 一个最合适的目录( d i r e c t o r y ) 。 最后，搜索引擎中各网站的有关信息都是从用户网页中自动提取的，所以 用户的角度看，我们拥有更多的自主权；而目录索引则要求必须手工另外填写 网站信息，而且还有各种各样的限制。更有甚者，如果工作人员认为你提交网 站的目录、网站信息不合适，他可以随时对其进行调整，当然事先是不会和你 商量的。 目前，搜索引擎与目录索引有相互融合渗透的趋势。原来一些纯粹的全文 搜索引擎现在也提供目录搜索，如g o o g l e 就借用o p e nd i r e c t o r y 目录提供分 类查询。而象y a h o o 这些老牌目录索引则通过与g o o g l e 等搜索引擎合作扩大 搜索范围。在默认搜索模式下，一些目录类搜索引擎首先返回的是自己目录中 匹配的网站，如国内搜狐、新浪、网易等；而另外一些则默认的是网页搜索， 如y a h o o 。 四川大学计算机学院2 0 0 3 级硕士学位论文 2 1 4 搜索引擎技术的发展方向 一个优秀的搜索引擎，应该能够以一种最简单的方式将用户最需要的信息 显示在用户面前。更高的网页覆盖率，更快的相应速度，更好的结果相关性排 序是所有搜索引擎发展的永恒目标。 应该看到，现有的搜索引擎都只是在一个较为低级的层次上为用户提供信 息检索服务，距离用户的要求还有一段距离。就目前的发展来看，搜索引擎还 有以下几个发展方向： 1 在搜索内容的细化：垂直搜索。 垂直搜索是针对某一个行业的专业搜索引擎，是搜索引擎的细分和延伸。 在对网页数据库中的某类专门信息进行一次整合，定向分字段抽取出需要的数 据进行处理后再以某种形式返回给用户。 垂直搜索引擎和普通网页搜索引擎的最大区别是对网页信息进行了结构 化信息抽取，也就是将网页的非结构化数据抽取成特定的结构化信息数据。网 页搜索是以网页为最小单位，基于视觉的网页块分析是以网页块为最小单位， 而垂直搜索是以结构化数据为最小单位。进行结构化处理的数据被存储到数据 库，进行进一步的加工处理，如：排重、分类等，最后分词、索引再以搜索的 方式满足用户的需求。 整个过程中，数据由非结构化数据抽取成结构化数据，经过深度加工处理 后以非结构化的方式和结构化的方式返回给用户。 垂直搜索引擎的应用方向很多，比如企业库搜索、供求信息搜索引擎、购 物搜索、房产搜索、人才搜索、地图搜索、叩3 搜索、视频搜索、图片搜索 几乎各行各业各类信息都可以进一步细化成各类的垂直搜索引擎。 2 对用户查询的深入理解：依据自然语言分析。 搜索引擎深入全面理解用户的查询意图，才能够返回更符合用户需求的信 息。但由于简单的关键词很难将用户的意愿表达清楚，而使用复杂的表达式规 则进行查询对于普通用户来说要求很高，所以，基于自然语言分析的搜索引擎 技术也正在逐渐受到人们的重视。在人工智能语言分析技术还没有取得突破之 前，一些搜索引擎已经采用了另外一种方式，来间接达到这样一种效果。这些 1 4 四川大学计算机学院2 0 0 3 级硕士学位论文 搜索引擎并不是依靠自身的数据库来直接提供搜索结果，而是提供一个场所， 由用户将需要了解的问题公布出来，再由其他用户来负责解答，解答者可以根 据自己对问题的理解并利用搜索工具得出，提交给问题发布者，并由问题发布 者选出最优的，作为问题的答案。如s i n a 的“爱问i a s k ”，b a i d u 的“知道”， 雅虎中国的“知识堂”等都是这一类型。 3 个性化搜索：基于用户使用习惯的分析。 个性化可由搜索的双方共同完成。用户能够主动选择自己感兴趣的内容分 类，来定制信息。搜索引擎可以利用c o o k i e s 等技术，记录用户的使用习惯， 在向用户返回搜索结果时，参考这些使用习惯，从而使得结果更符合用户的需 要。现在，号称个性化搜索引擎的产品已经问世，中搜( 俐z h o n g s o u t o m ) 已经在4 月推出了1 6 ( i n t e r n e tg a t e w a y ) 1 0 版本其中包含了丰富个人专 题定制和互动功能，力争提供最符合用户要求的信息。 2 2 分布式搜索技术 采用分布式系统架构来实现搜索引擎系统，需要在深入研究分布式系统 1 1 7 1 的基础上，结合分布式系统的特点进行相应的修改与调整。这样才能够使 得信息采集系统后台稳定、高效。 2 2 1 分布式系统技术 分布式系统成为二十世纪九十年代计算机领域里的研究热点。作为网络一 体化和并行处理分布化的产物分布式系统，解决了系统透明性及处理机动 态分配等问题，表现出比网络系统更强的生命力和更大的吸引力 概括地说，分布式系统是由多个相互连接的处理资源组成的计算系统，它 们在整个系统的控制下可合作执行一个共同任务，最少依赖于集中的程序、数 据或硬件。这些资源可以是物理上相邻的，也可以是地理上分散的。 分布式系统是在网络的基础上发展起来的，按照使用的计算机网络以及其 组成的计算机种类的不同可分成同构型分布式系统和异构型分布式系统。异构 型分布式系统是由若干不同的计算机和网络的硬件或软件系统互连而成；同构 四川大学计算机学院2 0 0 3 级硕士学位论文 型分布式系统则是由相同类型的计算机和网络的硬件和软件组成。与网络系统 相比，分布式系统具有很好的透明性。在分布式系统中，用户不必去区分本地 操作和远程操作；系统可将处理机动态地分配给最需要的地方；在某一个结点 上要运行的程序，系统可根据各结点负载多少等因素进行均衡，将程序移至负 载少的结点运行。 总之，在分布式系统环境下，尽管是多机系统，但由于分布式系统的透明 性，从而对用户而言，就象只有一个配置极佳、效率极高的单机系统在为他服 务。 相对于集中式