（计算机科学与技术专业论文）分布式搜索引擎缓存设计及优化.pdf

北京邮电大学硕士学位论文分布式搜索引擎援存设计及优化 分布式搜索引擎缓存设计及优化 摘要 互联网是个巨大的信息资源库，从这个资源库中提取和检索出有用信 息是个很重要的课题。搜索引擎是通用的信息检索服务。 搜索引擎一般由c r 椰l e r 、索引库、检索器和用户接口组成。c r a w l e r 从w e b 上下载页面：分析器对下载页面的内容进行分析以用于建立索引：索 引器将文档表示为一种便于检索的方式并存储在索引数据库中：检索器实 现用户查询关键词和目标文档匹配度的计算：用户接口为用户提供一个输 入查询请求，定制查询结果的w e b 页面并将查询结果格式化后返回给浏览 器。 由于搜索引擎处理的对象是十分庞大的数据量，同时互联网的结构是 分布式的，搜索引擎设计成分布式并行处理的系统同时用若干机器协同计 算处理，分布式并行的方法可以取得更好的性价比。本文论述构建一种基 于分布式并行计算技术的w e b 搜索引擎模型架构。采用分布式并行编程模 式，选用了任务分发模式。在并行编程中线程是流行的模型，在并行计算 上采用c + + t h r e a dp 0 0 l 的编程模型。消息传递对分布式的并行编程是有 效的，在分布式计算的消息传递上采用c + + 的s o c k e t 通信方式。 在w e b 搜索引擎的设计上，主要论述了缓存优化的相关技术。缓存设计 的好坏直接影响搜索引擎的相应速度，本文论述了一种搜索引擎缓存的设 计方法。 关键词：搜索引擎、分布式、优化、性能 北京邮电大学硪士学位论文 分布式搜寮引擎缓存设计及优化 t h ed e s i g na n do p t i m i z a t i o no fd i s t r i b u t e d s e a r c he n g i n e sc a c h e n ei m 蛐e th 船h u g ei n 硒瓶a t i o n s o u r c e s 她di t sab i gt a s kt os e a r c ha n d p i c ku pu “i 越m n a ：t i o n s e a 托he l 画n ej u s tp r 0 v i d e s m es e r v i c eo f u | i i v e 培a li n 仍姗a t i 疵h j n g as e a r c he n g i l l ei su s u a l l yc m i l p o s e do f o 暇w l e r ，i n d e x e r ，s e 甜c h e ra i l du s e r i n t e r f _ a c e s c 暇w l c ri su s e dt od i 删dw e bp a g 船盘o m 廿l e 如t e m 科，p a r s e r s t o p a r s e 吐1 e m i n o 坩e r t o m a k e i n d e ) 【h l d 雠钉t o m a ：k e m 锄a b 淞w a y f b r s e a r c h m ga n d s a v et l l e mi i l1 1 1 m 赫玎；gd a 毛i b a s e ，s r c h e rt om a t c ht l l eq i l c l y k e ”阳柑a n dd e s t i n a t i o nd o c n t ，u s e ri l l t e r f h c e st o 删d ea 、e bp a g e 1 o r u s e r t o 眦q u e f y 觚d 嫦t l l m 也e a r c h f e s u l 乜 a s 岫d a t a s e 玳he l 咖p l d 删i ss o h u g e 龃d i 士l t e m e t i s d i s t r i b u t e d ， i t sb d = c e rt od i a k es e a r c he n 窖尊n ead i 蹦b i l t e ds y s t 咖、) i ，i t h 舢l t i p l e c o m p u t e 璐p r o c e 蹦m gt o 黟晒e f 、】l ：h i c hw i l lp f o v i d e sb e n e r 搿刑f o 】嘲觚c e n 嵋p a p e rg i v e su sad i s c s i o no faw e bs 髓托he n 西n e 曲m b 8 d o n d i s t r i b u t e dp 删l e lc o 毋p u 恤gt 酣h n o l o g 弘i ta l s ou s e dd i s t r i b m 耐p a m l l e l p r 0 鲫珊i n i n gm o d e ，t a s _ kd 融i v e r i n gm o d e a n dr e l e v 锄td e c o m p o s i n g t e c h n o l o g y i np a r a l l e lp r o 罟阴m n 血【舀曲r e a di sap o p u l a rm o d 岛w i l i l ec + + 1 1 删p 0 0 1i sag o o do n ei n 删k dc o m p 砸n 吕f o rd i 蹦b 嘶e dp a r a j l e l p r o 铲a m m i n g ，m e s s a g ed e l i v e r i n gi s e 保蛾i v ea n dw e 郴e d 也es o c k e t c o m m 岫i c a t j o ni l lc + + i l lt h ed e s i 萨o fw e bs 黜h 翩西n e ，w em a i l l l ys h o wy o uab u 脓 0 p t i 戚z a t i o n 删蝴w k c h i s t h ek e y t o 廿1 es p c e d o f s e a r c he l l g i n e a n d i t s p 盱f o m a n c e k e y w o r d s s e a r c he n g i n e ，d i s 虹i b m e d ，b u 妊醯。埘i l l i z a t i o n ，p e m 嘞a n c e 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 1 1 什么是搜索引擎 第1 章引言 w e b 搜索引擎( s e a r c he n g i n e ) 是随着w e b 信息的迅速增加，从1 9 9 4 年开始逐 渐发展起来的技术。实际上，搜索引擎是指因特网上专门提供查询服务的一类网站， 它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理， 并为用户提供检索服务，从而起到信息导航的目的。用户的查询途径主要包括自由 词、全文检索、主题词检索、分类检索及其它特殊信息的检索( 企业、人名、电话黄 页等) 。 目前搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务，搜索引 擎站点也被美誉为“网络门户”。搜索引擎技术因而成为计算机工业界和学术界争相 研究、开发的对象。 1 2 搜索引擎产生的背景和发展历史 随着信息技术的不断发展，特别是互联网应用的迅速普及，电子信息爆炸似的 丰富起来。目前仅g o 0 9 1 e 收录的网页就超过8 0 亿，并且每天全球互联网网页数目 以千万级的数量增加。要在如此浩瀚的信息海洋里寻找信息，就像“大海捞针”一 样困难。工欲善其事，必先利其器。要在浩瀚的网络信息海洋中自如冲浪，搜索引 擎己成为必不可少的利器。 白1 9 94 年起至今，伴随着因特网的日益发展壮大以及w e b 信息量的迅速膨胀， w e b 搜索引擎技术为了不断满足人们对w e b 信息检索的需求，已经经历了三代 发展阶段： 第一代搜索引擎出现于1 9 9 4 年，以集中式检索为主要特征。这类搜索引擎一般 都索引少于1 百万个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常 慢，一般都要等待1 0 秒甚至更长的时间。在实现技术上也基本沿用较为成熟的l r ( i n f o r i i l a t i o nr e t r i e v a l ) 、网络、数据库等技术，相当于利用一些己有技术实现的 一个w w w 上的应用。在1 9 9 4 年3 月到4 月，网络爬虫w o r l dw e bw o r m ( w w w w ) 平均 每天承受大约1 5 0 0 次查询。第二代搜索引擎系统大约出现在1 9 9 6 年，大多采用分 布式检索方案，即多个微型计算机协同工作来提高数据规模、响应速度和用户数量。 它们一般都保持一个大约5 千万网页的索引数据库，每天能够响应1 千万次用户检 索请求。1 9 9 7 年1 1 月，当时最先进的几个搜索引擎号称能建立从2 百万到1 亿的 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 网页索引。a 1 t a v i s t a 搜索引擎声称他们每天大概要承受2 千万次查询。 第三代搜索引擎系统出现在1 9 9 8 年到2 0 0 0 年期间，这一时期是搜索引擎空前 繁荣的时期。第三代搜索引擎的发展有如下几个特点： 1 索引数据库的规模继续增大，一般的商业搜索引擎都保持在几千万甚至上亿 个网页 2 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂 直门户站点开始使用该技术。 3 由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的研 究又可以分为两类：一类是对超文本链的分析，在这方面始于s t a n f o r d 大学的 g o 0 9 1 e 系统作出了很大的贡献：另一类是用户信息的反馈，d i r e c t f l i t 系统采用的 就是这种方法。 4 开始使用自动分类技术。n o r t h e r nl i g h t 和i n k t o m i 的d i r e c t o r ye n g i n e 都在一定程度上使用了该技术。 进入2 1 新世纪以后，随着信息多元化的增长，千篇一律的给所有用户同一个 入口显然己经不能满足特定用户更深入的查询需求。同时，这样的通用搜索引擎在 目前的硬件条件下，要及时更新以得到互联网上较全面的信息是不太可能的。针对 这种情况，我们需要一个分类细致精确、数据全面深入、更新及时的面向主题的搜 索引擎。由于主题搜索运用了人工分类以及特征提取等智能化策略，因此它比上面 提到的前三代的搜索引擎将更加有效和准确，我们将这类完善的主题搜索引擎称为 第四代搜索引擎。 1 3 搜索引擎的分类 搜索引擎有各种不同的分类方法，大体上可有如下三种形式： ( 1 )按照组织信息方式来分类 ( 2 )按照信息的内容来分类 ( 3 ) 按照搜索根据的数量 现分述如下： 1 3 i 按照信息的组织方分类 厚最茜分类搜索烈雾( c a t a l o go rd n c t o r ys e a r c he n 百n e ) ，或称按主题查询型 搜索引擎，是将信息分门别类，按照传统的分类方式分为各级目录。用户一般采取 逐层浏览目录，逐步细化来寻找合适的类别赢至具体信息，著名的y 亦o o ! 就是其 代表，检索系统将搜索到的h l t e m e t 中的所有资源按其主题分为若干大类，在大类 的下面分设若干二级，三级类目，甚至十几级类目。优秀的网站目录经常设有“交 2 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 叉显示”即同一子类目可以同时出现在不同的类目下。而它们的目录体系则因各自 采用不同的分类方法而不同，在这里传统的图书馆的分类方法有可能被采用，例如： 杜威分类法，有p a 仃i c ss u 巧e c tc a 伽o g ， h t t p ：、v w w s l a c s t a i 曲r d c d 吒l a n c e y 坩e w ey 【1 1 1 美国国会图书馆分类法，有c v b c r s t a c k s ， h 却：，w h m p u b l i c i 船t a t e e d “七y b e r s i a c k s m o m 印a g e - h 州 目录式分类搜索引擎由系统将搜索到的网络信息分别归类。这一工作有的系统 由机器自动完成，大部分系统则由人工操作完成，用户只要遵循该系统的分类体系 按图索骥、层层深入即可，这与图书馆中传统的分类标引功能十分相似。特点是质 量和匹配精度较高，能够有效涵盖目前普遍的主题，用户操作也十分方便。不足之 处是搜索范围较小，查全率较低，对偏僻主题、新兴学科、交叉学科不能很好的涵 盖；类目间的交叉又导致重复和资源浪费；各个搜索引擎没有统一的分类方式，检 索结果直接依赖于用户的主观判断；且因为需要人工维护，周期长，代价昂贵。 垒磁紧罗饽奸u 1 1 t e x ts e 删le n g i i l e ) 或称按关键字查询型搜索引擎，是指能够 对各网站的每个页面中的每个词进行搜索的搜索引擎。通过用户直接输入检索词、 查找索引数据库用检索词标引的的索引记录来寻找用户所需信息资源，检索结果， 通常是一个个网页的u r l m i f o n nr e s o u r c el o c a 6 d r 统一资源定位，在i m e m e t 的 w w w 服务程序上用于指定信息位置的表示方法) 和一段段的文字摘要，并且依照匹 配率排序返回给用户。在检索中可以使用布尔逻辑检索、短语或邻近检索、模糊检 索、自然语言检索等高级检索方式，可以限制检索对象的地区、网络范围、数据类 型、时间等，可对满足特定条件的资源准确定位。a 蛔s t a 、e x i t e 、h o t b o t 、h l 矗琊e e k 、 l y c o s 、0 p e n t e x t 、w 曲蹦耕l e r 等就是著名的检索型工具。 全文搜索引擎的特点是信息量很大，在理论上用户可以对i n t e m e t 所有网站的每 一页文档进行检索。因此它的查全率较高；而且此类搜索引擎依赖于软件自动定期 维护，周期短，发展快，代价相对便宜。不足之处是它提供的信息虽然多而全，但 是可供选择的信息太多反而降低了查准率，由于没有分类式搜索引擎那样清晰的层 次结构，只能利用关键字来检索，精度依赖于系统的标引、分词技术，经常返回低 效信息；对系统软件的健壮性和网络质量要求很高。 耀台望馊! 嘉烈掌是针对全文和分类搜索引擎的缺点而设计的。有的的搜索引擎 是分别提供两种检索方式供用户选择；有的是在分类的基础上在进一步进行全文检 索。后者既可以使用户在分类目录中浏览，保证了一定的查准率，又可以使用户进 行全文检索，查找特定资源。现在多数的搜索引擎都朝这个方向发展。 1 3 2 按照信息内容分类 缘管壹馊紧彭葬又称为通用型搜索引擎，内容包罗万象，涵盖各个领域和专 业，适用面广，用户利用它可以检索几乎任何方面的资源，y 曲o o ! 、a l t av i s t a 。e x i t e 北京邮电大学硕士学位论文 分布式搜索引擎堙存设计及优化 等许多流行的大型搜索引擎均属这一类。这种搜索引擎获得信息量大，每次检索返 回结果很多，但是由于涉猎领域太多，在需要得到某一特定领域的专业信息，会使 用户很难从成千上万的检索结果中快速过滤出真正需要的信息，反而导致各个领域 的信息搜索都不完整、不全面。 专逝型攫霜彰警是指就某一特定专业的信息资源进行检索的搜索引辈。专业型 搜索引擎采用详尽和专业的分类、标引方法对信息资源重新标引描述，在相应的检 索机制中设计利用于该专业领域密切相关的技术方法和检索语言，从而使关于该专 业的查询精度大大高于综合型搜索引擎。专业型搜索引擎是搜索引擎技术发展的一 个新方向，但是目前数量较少，涉及专业范围有限，尚不能满足社会需要。下面是 几个典型的专业型搜索引擎的例子： m c g r a e h i l lr y c r s o n 公司建立的r r s s ，社会科学研究资源( r e s e a r c hr e s o u r c e s 南r l es o c i a ls c j c n c e s ) ，u u ：h 亡l p ：w 聃w s o c s c i s e a r c h c o m 美国化学学会( a m c r i c 弛c h e n i s 竹s o c i e t y ，a c s ) 建立的专业资源站点： c h e m c e n c e r ，u r l ：h t l p ：，吼啊w c h c n c e l l t e r o r s e a r c h h n n l 劳璇型搜索影雾是指那些用来检索某一类型信息的或数据的检索工具，通常所 说的黄页( y e l l o wp a g e s ) 、白页( w h i t cp a g e s ) 、指南与名录( d i 咒c t 耐e s g 试d e s ) 就是其中不同的类型。特殊型搜索引擎典型的例子有：检索电话号码的5 5 5 1 2 1 2 ( h t t p ：，唧_ r5 5 5 1 2 1 2 c o m )和 s 谢t c h b a r s、 查询地图的m 印b l 髂t ( h t t p ：怕n m m a p b l a s t c o m ) 、t a 咖的图像检索、检索新闻组的d e j a n e 粥等。 1 3 3 按照搜检索工具的数量分类 捌立镬紧烈搴有自己的数据库，利用自身的r o b o t 程序或是使用人工方式搜集 信息，并依据自己的的处理规则对这些信息进行组织和分类，最终为用户反馈出相 应的查询结果或是u 1 地。独立搜索引擎一般都会有多种搜索策略，如：全文检索， 简单检索，高级检索等。目前大型搜索引擎多为独立型。象y a l l o o ! 、a l 扭v i s 诅，国 内的有搜狐、悠游等。这种最基本的搜索引擎存在一定的局限性： ( 1 ) 数据库容易过时。由于采用自己的数据库，更新时间是固定的，用户无法从 返回的结果中看出那些信息是最新的，哪些是过时的。 ( 2 ) 覆盖面有限。各个独立搜索引擎系统的覆盖区域各不相同，且均具有一定的 局限性。 ( 3 ) 利用性有限。文档相关性评估采用的技术主要依赖于各选关键字的匹配情况。 因此查询不可能是精确的。目前各个搜索引擎处理文档信息的方法不同，对 文档相关度的评估结果存在很大的差异。 ( 4 ) 用户接口有限。不同搜索引擎具有不同的检索策略和用户界面，有的存在界 面不友好，通用性差，对用户的使用有技术要求，即需要用户提供良好的表 达要求。 4 北京邮电大学礤士学位论文 分布式搜索引擎缓存设计及优化 元拦席彰擎( m e 诅s e a r c h e n g 讧l e ) 由于每个独立搜索引擎收集站点的专业不同、 专业分类方法不同、搜索引擎速度、信息收集量也不同，有时仅使用一两个搜索引 擎还是难以准确查询到最有用的信息。研究人员在对著名的6 个网站进行搜索时发 现，使用6 个网站搜索所得结果是使用单个网站搜索所得结果的3 5 倍。而分别使 用多个搜索引擎逐一进行查询，会消耗许多不必要的时间，元搜索引擎就是为解决 这样的问题而产生的。 这种搜索引擎要利用其它搜索引擎。自身仅是作为用户和其它搜索引擎的中介， 用户看见的是简单统一的集成查询界面，它将检索词在若干个搜索引擎中同时进行 查询，将查询结果进行相关度排序、去重后，返回给用户。 元搜索引擎不通过机器人程序为w w w 建立索引，因此不需维护庞大的搜索引 擎数据库，也不需要构造复杂的搜索引擎，查询结果能更好的满足用户要求；但是 网络负载大，时延较大。 元搜索引擎又可以分为两类：一类是基于客户端的元搜索引擎，它是利用客户 端计算机进行合并处理、相关度排序等运算，这样的搜索引擎对客户端计算机要求 较高。另一类是基于服务器端的元搜索引擎，它是利用搜索引擎服务器进行这些运 算。从外观上看，这类搜索引擎看起来和独立搜索引擎一样，但比任何一个单一的 搜索引擎查询结果要全面。 目前，比较有影响的元搜索引擎有： m e t a c r a w e r ，u r l ：h t t p ：f 一 w m e 协c 柏_ w l e r c o m ； m e t a s e a r c h ，u r l ：h t 职f 帕ww 呦s e a 出1 c o m ； s a w y s e a r c h ，u r l ：h t 啦f 几 几s a v 、r ys e _ 酣c h c o m 。 集獗 i 肇紧张擎( 越1 i n - 0 哩l e ) 是指用户只要通过一个网站，即可选择多个搜索引 擎依次进行检索。这与元搜索引擎的工作方式有些相似，只是元搜索引擎只要一次 性输入检索要求，就可以同时让多个搜索引擎一起或分别进行检索，并对检索结果 进行分析整理：而a 1 1 n o n e 通常是逐一输入检索要求，然后从搜索引擎列表中每 次选择一个进行检索，一般不对检索结果进行处理。 a 1 1 i n - o n e 搜索公司的a n “o s e a r c hp a g c 可以看做是集成搜索引擎的代表。 该网站汇集了h n e m e t 中4 0 0 多个大型的搜索引擎、数据库、索引和分类目录，其 数据库容量、系统相应速度和用户界面等多项指标在同类产品中均居领先地位。 1 4 主要搜索引擎简介 现在在网上的搜索引擎也已经有很多，比较著名的有g o 0 9 1 e ，a l t “i s t a ，y a h o o i n f o s e e k ，m e t a c r 删1 e r ，s a v v y s e a r c h 等等。国内也建立了很多的搜索引擎，比如： 搜狐、新浪、百度等等。其中在信息搜索的取全率和取准率上做得做好的还数 g o o g l e 。当然搜索引擎的准确度和用户查询相关度还有待于改进和提高。 北京邮电大学硕士学位论文 分布式搜索b i 擎缓存设计及优化 a i t a v i s t a 是一个速度很快的搜索引擎，由于它强大的硬件配置，使它拥有复 杂的查询。它主要是基于关键字进行查询，它漫游的领域有w e b 和u s e n e t 。支持布 尔查询的”a n d ”，”o r ”和n c r r ”，同时还加上最相近定位“n e a 旷，允许通配符和“向 后搜索( 比如：你可以查找链接到某一页的所有w e b 站点) 。你可以决定是否对搜索 的短语加上权值，在文档的什么部位去查找它们。能够进行短语查询而不是简单的 单词查询的优点是很明显的，比如，我们想要查找一个短语”t ob eo rn o tt ob e ， 如果只是把它们分解成单词的话，这些单词都是属于s t o pw o r d ，这样这个查询就不 会有任何结果，但是把它当作一个整体来查询，就很容易返回一些结果，比如关于 哈姆雷特或者是莎士比亚等等的信息。系统对查询结果所得到的网页的打分是根据 在网页中所包含的你的搜索短语的多少，它们在文档的什么位置以及搜索短语在文 档内部之间的距离来决定的。同时可以把得到的搜索结果翻译成其他的语言。 e x i t e 是称为具有”智能“的搜索引擎，因为它建立了一个基于概念的索引。 当然，它所谓的“智能“是基于对概率统计的灵活应用。它能够同时进行基于概念 和关键字的索引。它能够索引w e b ，u s e n e t 和分类的广告。支持”a n d ”，”o 旷，”n o t ” 等布尔操作，同时也可以使用符号”，和”一。缺点是在返回的查询结果中没有指定 网页的尺寸和格式。 1 5 本文的主要工作 本文主要阐述了w e b 搜索引擎的基本原理、核心技术和处理流程及优化。对于 搜索引擎的内部软件组织和数据结构、数据存储方法进行了深入的研究和分析。同 时，对如何提高搜索引擎的精度和性能等，进行了深入细致的研究，对其中的核心 算法进行了讨论和评估。对于搜索引擎的相关优化做了详细的分析，并提出自己的 算法，使得信息检索系统的搜索性能得到进一步的提高。 1 6 论文的结构 本文第一章介绍了搜索引擎当前现状、搜索引擎仍然需要完善之处，同时提出 了项目的研究背景和意义。 第二章对搜索引擎的基本框架傲了概述。 第三章深入分析了搜索引擎中一些关键技术。 第四章对搜索引擎的设计及优化需求进行了详细的分析。 第五章描述了搜索引擎缓存的设计及置换策略，同时对于影响搜索引擎缓存结 果的因素进行了分析。 第六章对工作的结果进行了总结并探讨了下一步的研究方向。 6 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 第2 章搜索引擎概述 2 1 总体模型 搜索引擎的基本架构如图所示： 图2 - l 搜索引擎架构图 2 1 1 网络爬虫( s p i d e lw 曲c r 唧k r ) 架构 网络爬虫也称为“搜索器”，在i m e m e t 上沿网页链接访问并保存页面信息，作为 检索信息的来源。这一部分由爬虫程序自动完成，一般都日夜不停地运行。爬虫搜集 地信息类型可以是文本文档( 例如， r i m l 文本、l 文本、正文文本等) 、字处 理型文档( 例如，、v o r d 文档、p p t 文档、p d f 文档等) 、多媒体信息( 例如，地图、图 形、图像、音频和视频等) 。w e b 网页作为结点，网页之间的链接作为边，可以把 w e b 网页的关系表示为图。网络爬虫的工作，本质上是图的搜索。 2 1 2 索引器 索引器对爬虫收集来的网页信息，构造出便于快速访问和检索的索引数据结构。 为了支持高效率检索。索引器是一般采用倒排索引( i n v e r t e di n d e x ) ，其核心数据结 构是倒排表( i n v e n e dt 曲l e ) ，其每一表项记录某一单词所出现的文档编号序列【6 】。 同时，为了快速定位待查询的单词，索引器还提供了高效的单词索引结构。由于对文 档建立索引的过程一般在后台完成，因此对于建立索引这个过程的时间效率要求不太 高。不过，检索索引的相应速度要求很高，一个搜索引擎的有效性在很大成都上取决 于索引的质量。 北京雌电大学硕士学位论文分布式搜索引擎缓存设计及优化 2 1 3 查询处理 查询处理也称为“检索器”，分为前台和后台两部分。前台提供用户检索的界面 并接收用户查询输入( 通常是关键词组合) ；后台主要包括数据库管理程序和结果检 索程序。检索接口有直接用户接口和a p i 接口两种。其中，直接面对用户的接口能支 持用户查询输入、查询结果显示，有些搜索引擎还提供用户反馈机制。另外，绝大部 分使用搜索引擎都加入了结果排级( 【l l l ，血g ) 的功能模块以改进搜索结果。g o 0 9 1 e 的成功就在于它所发明的p a g e r a n k 算法有效的解决了文档相关性问题。当然，它还 成功地使用了地理信息，也就是说，它把与查询词的相对位置最吻合的文档排在前面。 2 2 系统结构 搜索引辈主要有两个部分，数据库建立过程和查询过程。具体系统结构如图所示： 图2 - 2 搜索引擎系统结构图 网络爬虫： 负责从i n t e m e t 上收集网页并转存到本地硬盘。 8 北京邮电大学硕士学位论文 分布式搜索引擎缓存设计及优化 索引器 对存储在本地的网页进行索引并保存为索引数据结构以供查询。 检索器： 接受并分析用户查询请求，检索并返回查询结果。 9 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 3 1 什么是网络机器人 第3 章网络机器人 网络机器人又称为s p i d e r 程序，是一种专业的b o t 程序。用于查找大量的、b 页面。它从一个简单的w e b 页面上开始执行，然后通过其超链接在访问其他页面， 如此反复理论上可以扫描互联网上的所有页面。 基于因特网的搜索引擎是s p i d e r 的最早应用。例如搜索巨头g o o g l e 公司，就 利用网络机器人程序来遍历w e b 站点，以创建并维护这些大型数据库。 网络机器人还可以通过扫描w 曲站点的主页来得到这个站点的文件清单和层 次机构。还可以扫描出中断的超链接和拼写错误等。 3 2 网络机器人的结构分析 i n t e m e t 是建立在很多相关协议基础上的，而更复杂的协议又建立在系统层协议 之上。w 曲就是建立在h t t p ( h y p e r t e ) ( tt r 蛆s f c rp r o t o c 0 1 ) 协议基础上，而 r r r p 又是建立在t c p ，m ( t r 锄s m i s s i o nc o “仃o lp r 砷o l h l t e m e tp m t o c 0 1 ) 协议之上，它 同时也是一种s o c k e t 协议。所以网络机器人本质上是一种基于s o c k e t 的网络程序。 3 2 1 如何解析h t m l 因为w 曲中的信息都是建立在 r n 协议之上的，所以网络机器人在检索网 页时的第一个问题就是如何解析r m l 。在解决如何解析之前，先来介绍下h t m l 中的几种数据。 我们在进行解析的时候不用关心所有的标签，只需要对其中几种重要的进行解 析即可。 1 0 北京雕电大学硕士学位论文 分布式搜索引擎缓存设计及优化 3 2 1 1 超连接标签 超连接定义了w w w 通过i n t 锄c t 链接文档的功能。他们的主要目的是使用户 能够任意迁移到新的页面，这正是网络机器人最关心的标签。 3 2 1 2 图像映射标签 图像映射是另一种非常重要的标签。它可以让用户通过点击图片来迁移到新的 页面中。 3 2 1 3 表单标签 表单是w e b 页面中可以输入数据的单元。许多站点让用户填写数据然后通过点 击按钮来提交内容，这就是表单的典型应用。 3 2 1 4 表格标签 表格是h 眦的构成部分，通常用来格式化存放、显示数据。 下面给出该类几种重要的方法。 3 2 2s p i d e r 程序结构 网络机器人必须从一个网页迁移到另一个网页，所以必须找到该页面上的超连 接。程序首先解析网页的h r m l 代码，查找该页面内的超连接然后通过递归和非递 北京邮电太学硬士学位论文 分布式搜索引擎缓存设计及优化 归两种结构来实现s p i d e r 程序。 3 2 2 1 递归结构 递归是在一个方法中调用自己本身的程序设计技术。虽然比较容易实现但耗费 内存且不能使用多线程技术，故不适合大型项目。 3 2 2 2 非递归结构 这种方法使用队列的数据结构，当s p i d e r 程序发现超连接后并不调用自己本身 而是把超连接加入到等待队列中。当s p i d e r 程序扫描完当前页面后会根据制定的策 略访问队列中的下一个超连接地址。 虽然这里只描述了一个队列，但在实际编程中用到了四个队列，他们每个队列 都保存着同一处理状态的u i 也。 等待队列在这个队列中，u r l 等特被s p i d e r 程序处理。新发现的u r l 也被加入到这个队列中 处理队列当s p i d e r 程序开始处理时他们被送到这个队列中 错误队列如果在解析网页时出错，u r l 将被送到这里。该队列中的u r l 不能被移入其他队列中 完成队列如果解析网页没有出错，u r l 将被送到这里。该队列中的u r l 不能被移入其它队列中 在同一时间u r l 只能在一个队列中，我们把它称为u r l 的状态。 图3 1 u r l 状态图 以上的图表示了队列的变化过程，在这个过程中，当一个u r l 被加入到等待队 列中时s p i d e r 程序就会开始运行。只要等待队列中有一个网页或s p i d e r 程序正在处 理一个网页，程序就会继续他的工作。当等待队列为空并且当前没有任何网页时， s p i d e r 程序就会停止它的工作。 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 3 2 3 如何构造s p i d e r 程序 在构造s p i d e r 程序之前我们先了解下程序的各个部分是如何共同工作的。以及 如何对这个程序进行扩展。 流程图如下所示： 北京邮电大学硕士学位论文 分布式搜索引擎缓存设计及优化 图3 - 2s p i d e r 流程图 1 4 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 3 2 4 如何提高程序性能 i m e m c t 中拥有海量的w 曲页面，如果开发出高效的s p i d e r 程序是非常重要的。 下面就来介绍下几种提高性能的技术： 3 2 4 1 多线程技术 线程是通过程序的一条执行路线。多线程是一个程序同时运行多个任务的能力。 它是在一个程序的内部进行分工合作。 优化程序的通常方法是确定瓶颈并改进他。瓶颈是一个程序中最慢的部分，他 限制了其他任务的运行。据个例子说明：一个s p i d e r 程序需要下载十个页面，要完 成这一任务，程序必须向服务器发出请求然后接受这些网页。当程序等待响应的时 候其他任务不能执行，这就影响了程序的效率。如果用多线程技术可以让这些网页 的等待时间合在一起，不用互相影响，这就可以极大的改进程序性能。 3 2 4 2 数据库技术 当s p i d e r 程序访问一个大型w 曲站点时，必须使用一种有效的方法来存储站点 队列。这些队列管理s p i d e r 程序必须维护大型网页的列表。如果把他们放在内存中 将会是性能下降，所以我们可以把他们放在数据库中减少系统资源的消耗。 北京邮电大学硕士学位论文 分布式搜索引擎缓存设计及优化 第4 章分布式搜索引擎的设计分析 4 1 搜索引擎设计 4 1 1w e b 信息采集 目前i n t c m e t 上的w 曲文档包括t e x t ，h 衄l ，x m l ，r s s 等类型的文本文档，和 i m a 萨，a u d i o ，v i d e o 类型的多媒体文档。其中s g m l 格式的h n n l ，x m l 文档占绝大部分。 s g m l ( s t 趴d a r dg e n e r a l i z e dm a d ( u pl a l l g 叽g e ) 它是一种通用的文档结构描述置标语 言，主要用来定义文献模型的逻辑和物理类结构。s g m l 是i s o 组织于1 9 8 6 年发 布的i s o8 8 7 9 国际标准【2 0 ，2 1 1 。 w 曲信息采集一般利用s p i d e r ，c r a w l e r 等类型网络搜索器在互联网中漫游，发现 和搜集信息。搜索器通常是一个计算机应用程序，不停地运行。它要尽可能多、尽 可能快地搜集各种类型的网上信息资源，同时因为互联网上的信息更新很快，所以 还要定期更新已经搜集过的旧信息，去除死连接和无效连接。 目前有两种搜集信息的策略：从一个起始u 融集合开始，下载这些u r l 文档； 同时从这些文档提取出新的i 瓜i 按照这些u r l 中的超链接，以广度优先或者深度 优先浏览整个互联网。这些起始u r j 可以是任意的u l u ，但常常是一些影响较大的、 包含很多链接的站点如h t l p ：价哪w y a h o o c o m 将w 曲空间划分成不同的子空间，按照域类型如( c o m ，o 唱) ，i p 递增、国家、地域 名( u k ，e n ，叫等方式划分，一个或者若干个搜索器负责一个子空间的搜索。 4 1 - 1 1 信息采集器 信息采集器即c r a w l e r 是通过网页的链接地址u m 来查找网页，从一个页面集 开始，读取网页的内容，提取出该网页中包含的u r j 链接地址，然后通过这些链接 地址寻找网页，这样一直循环下去，直到把互联网所有的网页都抓取完为止。 1 6 北京邮电大学硕士学位论文分布式搜索引擎缓存设计及优化 对于c r a w l e r 来说，要抓取互联网上所有的网页几乎是不可能的，从目前公布的 数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。 这其中的原因一方面是抓取技术的瓶颈) ，无法遍历所有的网页，有许多网页无法从 其它网页的链接中找到，另外抓取网页要遵循该网站的r o b o t 协议；再者是存储技术 和处理技术的问题，即使能够存储，下载也存在问题。 同时，由于数据量太大，在提供搜索时也会有效率方面的影响。因此，搜索引 擎的采集器只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据是某 个网页的链接深度。 c r a w l e r 的算法如下： i i l i t i a l i z e ： u r l s d o n e = n u l l ： u r l s d o = 、h t i p ：， 棚m y a h o o c o m ，h 却：， 九 州i b m c o m ，) ； r e p e a t ： l l r l = u r l s d o n e x t 0 ； h t n l l = d o 汕a d ( 眦1 ) ； u d s d o n e i n s e r t ( 1 ) ； n e w u r l = e 】( t 髓c t ij n l ( s o 衄1 1 ) ； f o r e a c h n e 、州r l i fn o tu r l s d e c 伽t a 缸( n e w u r l ) ； t h e nu d s d o i i l s e r t ( n e w u r l ) ； 4 1 1 2 抓取策略 互联网可以看成一个有向图，抓取网页，可以看成是图的遍历，c m w l e r 抓取网 页一般有以下几种策略：深度优先、广度优先、区分优先级。 深度优先是指c r a w l c r 会从互联网的一个起始页开始，提取出该页所有的u i u ， 北京邮电大学硕士学位论文 分布式搜索引擎缓存设计及优化 再从一个未被访问的u r j 出发，深度优先遍历u r i ，直到该起始页相连的页面都被 访问，处理完这条线路之后再转入下一个起始页，继续遍历链接。直至所有的u r j 被访问。在实现深度优先遍历时，采用s t a c k 的f i l o 数据结构，将从文档中提取出 的u 耻入栈。要遍历的u 砌由出栈取得。 广度优先是指c m w l e r 会先抓取起始网页中链接的所有网页，然后再选择其中的 一个链接网页，继续抓取在此网页中链接的所有网页，依次类推。实现时采用q u e u e 的f i f o 数据结构，将从文档中提取出的u r j 从q u c u e 尾插入。要遍历的u i u 由 q u e u e 头取得。 优先级策略是按照高优先级先遍历的思想，优先级的标准是： 一 网页文档的更新频率，经常更新的网页优先抓取； 网页文档的重要性，重要性根据页面的影响确定，重要的网页优先抓取。 4 1 1 3r o b o t 协议 c mw le r 在访问网站网页的时候，网站可能有一些资源不愿意被搜索引擎抓取， 网站的所有者可以通过协议规定哪些文件c r a w l e r 不能抓取。一般网站都有一个 m l 斌s 戗t 文件如h 郇：协m r d o m 如c o m r o b o 招戗t 在网站根目录下，通常c r a w l e r 都会遵守该协议。该协议定义了不能抓取的文件路径或列表。r o b o 乜t x t 文件的格式 是由u s e r _ a g e m 和d i s a l l o w ：组成。u s e r - a g e i l t 是访问的c m w l e r 名字的列表例 如：u s e r - a g e n t ：g o o 出e b o t ； 也可以用+ 设置对所有的c 删l e r ：us c r - a g e n t ：+ d i s a l l o w 规定了不能下载的路径或文件： d i s a l l o w ：c 百- b i n ，a p p d i s a l l o w ：e m a i l t l 仃n 完整的r o b o l l ) ( t 文件实例如下： u s e r a g e n t ：+ 北京邮电大学硕士学位论文 分布式搜索引摹缓存设计及优化 d i s a l l o w ：c g i - 髓州b p p ， d i s a l l o w ：c g i - b i n h p p ， 它规定了对于所有的搜索引擎c 百- b i i 砌b p p ，和c 西- b 劬却p 下的所有文件都不 能遍历。该协议只是作为一种保护规范，在技术上来说搜索引擎可以强行抓取而不 遵守该协议，绝大部分搜索引擎都会遵守该协议。 4 1 1 4 数据下载 数据下载是将网络资源下载到本地机器。下面介绍典型的h t t p 协议的数据下 载，在搜索网页过程中，可以有两种方式s o c k e t 和u i 也方式。s o c k e t 方式是用来 i p 和端口( p o n ) 建立s o c k e t 连接，然后发出g e t h 勘m p o s t 等类型请求。 p o s t 请求：大量的数据提交到服务器，允许w 曲服务器将数据返回。下面是 向h o s t 站点的p a t h 资源p o s t 数据d a t a ，同时设置会话c o o 比 4 1 1 5u i 乩提取 下载的每个页面，都要求提取出该页面链接的u 融，以便继续访问其他资源，对 于 r r m l 的资源来说我们可以利用正则表达式处理，首先定义匹配锚字符的表达式： c o n s ts t d ：如n ge 印r c s s i o n _ ” n 4 1 1 6 数据存储 通过磁盘阵列存储下载的w e b 文档，如果按照每个页面的平均大小为2 0 k 计算( 包 含图片) ，l 亿网页的容量是l 】( 2 t 字节，另外还有索引的存储，数据字典的存储。 4 1 ，2 w 曲挖掘 w e b 挖掘按照挖掘对象可以分为基于w 曲内容挖掘和基于w 曲结构的挖掘。前者是 指从w 曲文档的内容中提取有用信息，比如用于相关文档的分类，当用户检索时，只 需在与用户检索相关的一类文档中检索即可，这样