（计算机科学与技术专业论文）webcm一种基于搜索引擎的网络内容监控系统的研究.pdf

浙江人学顺f + 学位论文 摘要 一1 在最近的十年里，互联网得到了惊人的发展，它成为一个海量的、异质的、 非结构化的信息中心，成为人们生活中不可或缺的一部分。 在网络蓬勃发展的同时，网络安全也成为网络发展的一个中心议题。各种类 型的网络安全系统应运而生，诸如入侵监测系统、软件防火墙、电子邮件监控系 统得到了广泛的应用。然而，作为人们最关心的个问题一对网络内容的监控发 展滞后。 导致这一结果的原因是是多方面的，其中最重要的原因是t c p i p 协议带来 的平台的分布性、开放性以及h t m l 语言造成的内容的多样性，同时h t m l 语 言也无法为计算机提供足够的语义支持。 在缺乏成熟的网络内容监控系统支持的情况下，对网络内容的检查都是通过 人来完成的，其效率低下，无法适应网络发展的需要，人类迫切需要计算机提供 辅助来进行网络内容的监控。 本文以网络“电子警察”研究为背景，围绕网络内容监控的三个关键问题进 行了探索性研究。 第一个是内容监控中监控模式的识别、表达、匹配问题。本文用机器学习的 方式来识别监控模式。我们提出了基于关键字的概念模型，来表达领域无关情况 下的监控模式。为了提高模型表达的精度，我们提出了基于o n t o l o g y ( 本体论) 的概念模型以充分利用领域相关的信息。通过计算监控模式与被监控的文档之间 的概念匹配度，解决了模式匹配的问题。 第二个是网络内容的获取、组织、表达问题。本文描述了一个高性能的网络 信息采集器，在有限的时间里获得所要监控的网络上的信息。这些信息经过压缩 处理后分布在仓库中。最后，我们定义了一个h t m l 标记集，通过“属性一值” 对的形式表达了网页的内容。 第三个是内容监控系统的总体架构问题。本文描述了w e b c m ( w e bc o n t e n t m o n i t o r ) 的原型系统的框架，通过可配置的学习模块、信息采集模块、内容分 析与匹配模块、结果显示与反馈模块，在实现基于文本的内容监控的同时，为以 后的基于图象、语音的监控提供了合理的框架。 关键字：网络内容监控，搜索引擎，网页分析，机器学习，模式识别，本1 娅 浙江人学坝i ：学位论义 a b s t r a c t t h ew o r l d w i d ew e b ( w w w ) i sg r o w i n gr a p i d l yi nr e c e n tt e ny e a r sa n db e c o m e sa i n f o r m a t i o nc e n t e rw h i c hi sav a s tc o l l e c t i o no fl a r g ev o l u m e ，h e t e r o g e n e o u sa n d u n s t r u c t u r e di n f o r m a t i o n i th a sb e e na ni n d i s p e n s a b l ep a r ti np e o p l e sl i f e a tt h es a m et i m e ，t h en e t w o r ks e c u r i t yh a sb e e nac e n t r a lt o p i co ft h ed e v e l o p m e n to f t h en e t w o r kt o o v a r i o u sk i n d so ft h en e t w o r ks e c u r i t ys y s t e m sc o m ef o r t ha n dt h e y a r eu s e dp o p u l i a r l y , s u c ha si n t r u s i o nd e t e c t i o ns y s t e m s s o f t w a r ef i r e w a l la n dm o n i t o r s y s t e mo ft h ee m a i l h o w e v e r ，t h ed e v e l o p m e n t o fm o n i t o rs y s t e mo ft h ec o n t e n to f w e bi n f o r m a t i o n ，w h i c hi sp a i dt h em o s ta t t e n t i o nt o ，l a g sb e h i n d m a n yr e a s o n sa r e a d d r e s s e da n dt h em o s ti m p o r t a n to n ei sd i s t r i b u t i o na n do p e n i n go ft h ep l a t f o r m a c c o r d i nt ot h en e t w o r kp r o t o c o lo ft c p i pa n dt h ev a r i e t i e so ft h ec o n t e n ta c c o r d i n g t oh t m l f u r t h e r m o r e h t m lc o u l d t p r o v i d ee n o u g hs u p p o r t f o rm a c h i n e st o u n d e r s t a n dt h es e m a t i cc u eo ft h ew e bp a g e s w i t ht h e u n d e r s t a n d i n g o fl a c k i n ga d v a n c e dm o n i t o rs y s t e m sf o rw e bd o c u m e n t ， p e o p l eh a v e t oc h e c kt h ec o n t e n to ft h ew e bc o n t e n tb yt h e m s e l v e s b u tt h ee f f i c i e n c y i ss ol o wt h a ti tc o u l d n tm e e tt h en e e d so ft h ed e v e l o p m e n to ft h en e t w o r k w en e e da c o m p u t e r - a i d e dm o n i t o rs y s t e m f o rt h ew e bc o n t e n t t h i sp a p e rc o n s i d e r st h er e s e a r c ho ft h e e l e c t r o n i cp o l i c e m a n o ft h en e t w o r ka st h e b a c k g r o u n d a n df o c u s e so nt h et h r e ek e y p r o b l e m s t h ef i r s to n ei sh o wt oi d e n t i f y r e p r e s e n ta n dm a t c ht h em o n i t o rp a t t e m i no u r r e s e a r c h ，m a c h i n el e a m i n gi su s e dt of i n dt h ep a t t e r n t w ok i n d so fm o d e l sa r eu s e dt o r e p r e s e n tt h em o d e l ：k e y w o r d - b a s e dc o n c e p t u a lm o d e l a n d o n t o l o g y b a s e dc o n c e p t u a l m o d e l t h ef o r r n e rp r o v i d e saf i e l d i n d e p e n d e n tm o n i t o rm o d e la n dt h el a t t e rp r o v i d e s af i e l d s p e c i f i co n e w ec o m p u t et h ec o n c e p t u a ld e g r e eb e t w e e nt h ep a t t e r na n dt h e m o n i t o r e dd o c u m e n tt og i v et h er e s u l t t h es e c o n do n ei sh o wt of e t c h ，o r g a n i z e ，r e p r e s e n ta l l r e q u i r e dw e b d o c u m e n t s t h i s p a p e rd e s c r i b e s ah i g h p e r f o r m c ec o l l e c t o ro ft h ei n f o r m a t i o n a l ld o c u m e n t sa r e c o m p r e s s e da n ds a v e di n t h er e p o s i t o r y w ed e f i n eas e to fh t m l t a g w h e nt h e d o c o u m e n t sa r ei nt u r nt op r o e s s ，t h ec o n t e n to ft h ed o c u m e n t si ss a v e da c c o r d i n gt o t h e p a i ro f t h ea t t r i b u t e - v a l u e t h et h i r do n ei sh o wt om a k ea ne x c e l l e n ta r c h i t e c t u r ef o rt h em o n i t o r s y s t e mf o rw e b c o n t e n t t h i sp a p e rd e s c r i b e saf r a m e w o r ko fp r o t o t y p es y s t e mn a m e dw e bc o n t e n t m o n i t o r , s h o r ta sw e b c m ，w h i c hp r o v i d e sa na p p r o p r i a t ef r a m e w o r kt h ei m a g e b a s e d a n dv o i c e b a s e dm o n i t o r s y s t e mi nt h ef u t u r e k e y w o l d s ：w e bc o n t e n tm o n i t o l ，s e a r c he n g i n e ，w e bd o c u m e n ta n a l y s i s ，m a c h i n e l e a r n i n g p a t t e r nr e c o n g n i t i o n ，o n t o l o g y 浙i 工人学坝j 学位论文 1 引言 互联网( 尤其是w w w 技术) 的发展已经大大改变了这个世界，这种发展在 很大程度上得益于t c p ，i p 协议以及h t m l 格式语言的流行，从此，人们能够通 过浏览器方便的发布、获取信息。在十年左右的时间内，互联网已经成为一个海 量的、异质的、非结构化的信息中一t ： e i k v i l ，成为人们生活中不可或缺的一部 分。 1 1 滞后的网络内容监控 在网络蓬勃发展的同时，网络安全也成为网络发展的一个中心议题 d o w d & m c h e n r y 。各种类型的网络安全系统应运而生，诸如入侵监测系统、软件防火墙、 电子邮件监控系统得到了广泛的应用 r a n u m s c h o n l a u & d u m o u c h e le t 】。然而，作为 人们最关心的一个问题一对网络内容的监控发展滞后。 导致这一结果的原因是是多方面的，其中最重要的原因是t c p i p 协议带来 的平台的分布性、开放性以及h t m l 语言造成的内容的多样性。结果，与传统 的媒体( 报纸、电视) 相比，网络具有了自身鲜明的特点：首先，从内容的构成 上看，网络的信息更加丰富。网页的内容通常是由文字、图像、语音等综合而成 的。其次，从信息的载体看，其特点是分布、异质异构、海量的。大量的信息分 布在世界各地的网站上，网页可以是静态的、也可以是动态的。随着时间的推移， 网站积累的信息越来越多，技术的进步导致存储器性价比的提高，为存储这些信 息提供了可能。第三，从信息供求关系看，已经打破了传统的发布者和获取者这 种简单的单向关系。每个人既可以是信息的发布者，也可以是信息的获取者。 面对海量、异质、非结构的信息，h t m l 语言的简单性暴露了出来，这构成 了另一个重要原因。由于计算机难以理解信息的语义 f e n s e l & m u s e n 】，阻碍了搜 索、采集、维护、信息生成等技术的发展，同时自然语言理解和机器学习技术进 展缓慢，无法为机器自动理解网络内容提供更多的支持。 由于缺乏成熟的网络内容监控系统的支持，对网络内容的检查都是通过人来 完成的。人类具有高度的智能，对于能够理解的语言( 文字) 会从语法、语义上 进行分析和评价，因而这种监控是精确的，但是其效率是低下的，无法适应网络 发展的需要。人们迫切需要计算机提供辅助来进行网络内容的监控。 1 2 相关领域的进展 为了能够。完成埘网络信息内容的舱控t h t - ：到f 1 动的转变，究人员作i 叫络 浙江人学顺i 。学位论义 内容j 融腔相关的研究领域取得了进展，这些进展对于研制计算机辅助的网络内容 监控系统具有重要的意义。如： 针对信息的海量性和分斫i 性，现有的主要解决办法基于信息搜索引擎技术 【l a m 】。搜索引擎能够从从万维网上搜集各种信息，近几年，搜索引擎的相关技 术有了很大的发展。譬如，对w w w 结构的深入研究，对超文本结构的充分理 解及其中超链信息的充分利用，人们发明了p a g e r a n k 算法 p a g e & b r i n 、h i t 算 法 k l e i n b e r g ，提高了搜索的精度。搜索引擎技术的发展为研究基于r o b o t 的网 络内容监控系统奠定了基础。 针对信息的异构性，利用x m l 及其相关技术，可以使非结构化的数据半结 构化或结构化，并且在此基础上，完成异构的数据互相转化的工作。利用元数据 技术和相关工具结合o n t o l o g y 技术，对网络数据、资源进行语义上的刻画和描 述，从而使异构信息在语义上可互相理解 b e m e r s l e e ，【f e n s e l ， f e n s e le t ，克 服了h t m l 语义的缺乏性。真正的内容监控必然是基于语义的监控，这样监控 的结果才能最准确的反映网络的真实情况。 针对信息的非结构化，诸多技术中，比较多的是利用w r a p p e r 技术 e i k v i l 结合数据库技术f 1 0 r e s c u & l e v y l ，w r a p p e r 从本质上来看能够提供对网站背后的 数据库结构的部分还原，因而这类技术较多的运用在网站的管理、建设和重构上。 对于网络内容监控来说，这意味着监控的对象由静态的页面向动态页面( 数据库 内容) 的进步，然后目前自动生成w r a p p e r 的技术尚不成熟，为了生成页面的 w r a p p e r ，都需要人的交互，这就限制了w r a p p e r 技术在内容监控领域的应用。 1 3 研究内容 本文所研究的网络内容监控系统以公安部门网络“电子警察”的研究为背景， 满足了自动进行网络内容监控的需求。 通过对人类进行的内容分析过程以及内容监控的需求的抽象，必须解决如下 问题： 内容监控中监控模式的识别、表达、匹配问题： 网络内容的获取、组织、存储、表达问题； 监控结果的评价、展现问题。 此外，在实现基于文本的内容监控的同时，为以后的基于图象、语音的监控 提供了合理的框架。 本文通过对这些问题的解决，提供了一个可扩展的网络内容骼控系统的框 架，以此为基础实现了一个基于搜索引擎的内容监控的原型系统w e b c m ( w e b c o i l l e n tm o n i t o l ) 。 浙江人学坝i 学位论义 1 4 本文组织结构 本文的下面章节如下组织，为了了解搜索引擎的发展状况，第二章讨论了信 息检索的一些基本概念以及目前主要的搜索引擎技术；第三章从词法、语法和语 义角度描述了与内容监控相关的网页内容分析、识别、理解技术的发展，第四章 开始介绍原型系统的设计的思路、体系结构和各模块工作机制；第直章在第二、 三、四张的基础上介绍了系统用到的关键技术以及主要算法；第六章基于本体论 对w e b c m 系统的监控能力做了增强；第七章对系统做了总结并展望了下一阶段 的工作。 浙江人学倒f 岸位论义 2 搜索引擎技术发展趋势 2 1 从信息检索到搜索引擎 在理解搜索引擎的核心技术和结构之间，首先需要先来了解一下信息检索本 身，因为网络内容监控需要在很多方面需要借鉴信息检索的技术。 2 1 1 信息检索概念模型 信息检索，狭义地讲，就是在各种信息资源中找到满足信息需求的信息资源 的动作、方法和过程。 信息检索系统在具体实现上千差万别，但从基本组成单位的角度上分析，一 个典型的信息检索系统可以用黑盒子的方法来刻画 f a l o u t s o s 】。即从概念上，它 可分解为以下几个组成单元：输入、处理器和输出，如图2 一l 。 图2 1信息检索概念模型 1 输入 输入的内容可分为两部分：第一部分是查询请求，它代表了一个信息需求； 第二部分是原始信息，它是一个某个信息需求的希望集合，即可能满足该信息需 求的所有信息的集合，信息检索的值域空间。 2 信息处理机 信息处理机是整个信息检索的核心部分。信息处理机涉及以下几方面内容： i ) 有信息的表示和存储； 2 ) 某种近似的方式将信息结构化； 3 ) 实际的检索功能，即执行响应输入的查询请求的检索策略。检索策略的 优劣直接影响最终的检索输出。它是检索效率的一个重要因素。 3 输出 信息处删机的处删结泶，。股是纰信息的0 i 用表示。同rr , j _ j h ，、可以对输 浙江人学顺i 学位论义 的评价反馈到输入和信息处理机，以取得更能满足信息需求的输出。 采用数学语言，网络信息检索系统可以定义为一个三元组： s = ( d ，a ，盯) 其中d 表示原始文档，q 表示查询请求，a 表示匹配函数： 仃：d a _ r 此处，面是经过索引的文档集合，百是经过索引的查询集合，r 是函数值集 合。f f tc r ( 一d ，石) r ( 一d d ，石西) 表示文档d 关于查询q 的相关程度。设k 为检索 状态值，则关于查询q 的输出文档集为： f 一一 1 v ( g ) = p ic r ( d ，q ) 2k ，d d 在i n t e r n e t 诞生以前，信息的检索仅仅是索引的搜索，比如搜索作者，标题， 主体等。今天的信息检索要复杂的多了，信息检索包括建模、文档分类、体系结 构、用户接口、数据的可视化、过滤和语言，信息检索系统必须考虑数据的表示、 存储、组织和访问在内的一系列问题 b a e z a y a t e s 。 为了满足用户的信息需要，信息检索系统必须找到方法来解释信息条目的内 容，并根据与用户查询的相关度来对它们进行分级，这种解释涉及如何在语法和 语义上采集信息。信息检索系统的目标是检索所有与查询相关的文档，尽可能少 的检索到不相关的文档。为了达到这一目的，信息检索系统需要用户提供一组能 够覆盖所需信息语义的关键字，文档也需要按照关键字或者索引术语进行表示， 这些关键字或者索引术语可以来自信息专家，也可以来自计算机( 通过消除冠词 和连接词、将独特的词归纳到常用语法根下、识别名字) 。 2 1 2 经典的检索方法 传统的文本检索方法包括全文检索、签名文件、倒置方法 f a l o u t s o s 。 全文检索 全文检索是一种最直接的方式，只要将需检索的词组在所有文档中定位。全 文检索是最早使用的一种信息检索模型。全文检索虽有其固有的一些缺点，如不 能对结果进行排序，不能进行分类等，但由于全文检索能清晰地表达用户查询， 所以它在如今的信息检索中仍然有着不可替代的作用，现在使用的网络信息检索 系统大部分是布尔检索或是陔模型的推广。 有一些简单的算法求完成全文搜索这一工作，k n u t h 、m o r r i s 和 p n a t t k n u t h & m o r t i s & p r a t t l 挺f l i f i , j 算法需要0 ( m + n ) 次比较，但很显然这砦算 浙江人学顺i 学位论立 法的效率比较低。最快的是b o y e r 和m o o r b o y e r & m o r r e e 的算法。另外还有 s u n d a y s u n d a y j da h o h 和c o r a s i c k 【a h o & c o r a s i c k 】的算法。 从总体上来说，全文搜索的优点是它不需要额外的空间，插入和修改比较方 便。但响应时间较慢，如果是对于大型数据库来说。因此，全文检索通常都由特 殊的硬件来支持，或者和其他的检索方式同时使用来限制搜索的范围。数据库的 全文搜索和检索系统，一般是科学、医学和技术期刊杂志的电子版，或文献信息 检索系统。 为了克服上述的缺陷，人们企图能够建立新型的信息检索理论改进全文检索 理论，下面一节将对这些理论分别进行论述。 签名文件( s i g n a t u r e f i l e s ) 对文档的词进行h a s h 编码和其他编码，产生一个签名( s i g n a t u r e ) 。产生的 结果文档签名在存储在另外一个文件中，这个文件比原始文件小的多，查找比原 来迅速许多。f i l e s 和h u s k e y f i l e s & h u s k e y 将这个方式应用到某个数据库中，他 们使用一个停用词表( s t o pl i s t ) 来减少常用词，而且将每个不常用词归入它的 词根中。他们也利用了一个过程作为h a s h 函数来替代查询( 1 0 0 k u p ) 表。h a r r i s o n 用这个签名文件来加速查找子字符串。其他有很多科学家来研究这个方式，都表 明这种方式对于基于文本的检索很有效。 这种方式的主要优点是：实现比较简单，插入方便，有能力解决单词的部分 查询，有能力支持增长的文件，能容忍输入错误。另外这个方法还很容易实现并 行化。 这种方法的缺点也是非常显著的，当一个文件比较大时，响应比较慢。 倒置方法( i n v e r s i o n ) 每个文档都能表示成一串关键字，这些词描述了文档的内容。这些关键词 存储在一个“索引文件中”；对每个关键词保持连串指针指向相应的文档，这 存放在某文件中中，这种方式主要结构是d o c - - w o r d s = w o r d s d o c 。大多 数现有商业系统都采用这样的模式。 很多方式和结构都用来提高组织索引文件的效率，如利用b 树，t r i e s ，h a s h 或是这几种方式的组合。倒置方法的优缺点： 优点：实现相对简单，查找效率比较高，其中一大特点是查找近义词方便有 效。 缺点：存储空间较大，一般一个i n d e x 文件通常是源文件3 倍。 在这方面的研究也在不断进行，最近的这个理论的发展包括几个方面： l 、插入列表分布不平衡。其中一些词经常出现，而主要的词仅仅出现一次 或两次，为了补救这个事实而产i ，4 些方法。 2 、索引非常大人约兆字1 ，甚至是g 的数最级。仡这样的人数据库- h 浙江人学颁f ：学位论文 要求插入快速。所以相应的插入算法很多。 向量模型和聚类： 向量空间模型是一个以向量表示文档和查询的检索模型【s a l t o n & m c g i l l r i j s b e r g e n d u d a & h a r t 。向量空间模型将所有的文档集合定义为一个n 一 维的向量空间，向量空间中的每一维表示一个项或一个概念。文档集合中的每个 文档用空间中的一个向量表示。当给定一个用户查询后，这个查询将被转换为此 向量空间中的一个向量，通过计算查询向量与所有的文档向量之间的某种相似度 来判定文档与查询的相关性。聚类文档也可以通过计算其中所有文档的“质心” 得到其向量表示。 向量空间模型特点：向量空间模型易于理解；用向量空间的信息检索系统可 无需修改地应用于一个新的文档集合，这一点对信息内容日新月异的网络信息资 源而言显得更加重要；而且该模型的检索质量非常高。 最基础的思想是相同的文档可以组成一些聚类，基础假设是：相似的文档一 般相对于相同的请求。聚类在信息获取和图书馆学中有广泛的重视。尽管模式 识另0 的重点不是文档聚类，但它的思想通常非常适合现在的环境。词一般应用 到词上，而不是文档。因此，词可以分成一些类别，一个类别中的词同时出现， 相关或同义。当通常自动产生词的聚类似乎有困难。 文档聚类包含的步骤： 1 、产生类别；2 、聚类搜索；其中第1 步较复杂。 文档聚类模型是重要的模型，l s i 的方法就是在它基础上产生的改进。 2 1 3 利用语义( s e m a n t i c ) 提高信息检索的效率 通常，信息获取技术其实只是使用了文档的一小部分信息。尽管这样的做 法存在许多固有的限制，但这些技术在一般状况下还是能得到非常好的结果， 这是因为一个文档中通常包含了许多冗余信息。所以，利用语义的方法获取信 息通常能更有效。这些方法包括如下： 自然语言处理技术 自然语言处理技术通常寻求语义上的匹配。自然语言技术在一些应用上比 较成功。尽管在信息抽取之前通常需要做许多深层次语义上的分析但是自动 的语义分析技术( 浅层) 已经得到证实。自然语言的信息获取方法并不和浅层 次的方法有非常大的区别。通常利用一些技术，例如，冗余词表用来来去掉些 不包含语义的词。利用词组来作为索引词是一种结合传统技术的方法。另外还有 其他许多的自然语言处理技术。臼然语义结构的分析在近两年有许多研究，并在 不断取得进展。 浙江人学坝i 学位论史 神经网络 神经网络的主要特征是：大规模的并行处理和分布式的信息存储，良好的自 适应、自组织性，以及很强的学习功能、联想功能和容错功能，更加接近人脑的 信息处理模式。主要表现如下： 1 神经网络能够处理连续的模拟信号。 2 能够处理混沌的、不完全的、模糊的信息。 3 传统的计算机能给出精确的解答，神经网络给出的是次最优的逼近解答。 4 神经网络并行分布工作，各组成部分同时参与运算，单个神经元的动作 速度不高，但总体的处理速度极快。 5 神经网络信息存储分布于全网络各个权重变换之中，某些单元障碍并不 影响信息的完整，具有鲁棒性。 6 传统计算机要求有准确的输入条件，才能给出精确解。神经网络只要求 部分条件，甚至对于包含有部分错误的输入，也能得出较好的解答，具有容错性。 7 神经网络在处理自然语言理解、图象模式识别、景物理解、不完整信息 的处理、智能机器人控制等方面有优势。 这个方法的主要是利用传递激活算法 l e e ( s p r e a d i n ga c t i v a t i o nm e t h o d ) 。通 常的技术是建立一个词典，对于每个概念建立一个相应节点。 从传统的信息抽取各种方法和语义信息的方法进行比较，在语义信息方法中 对词汇建立索引大致能得到大约2 0 的性能提高，但这是以大量的前期工作为代 价的。 对上述方法作一小结，得到的结论如下： 全文检索适合小型的数据库： 倒置方法适合工业上的大型数据库： 聚类方法有两大优势1 ) 相关反馈；2 ) 能产生得分高低； 语义的方法在性能上确实有改进，但效果究竟如何，还有待深入研究。 2 1 4 搜索引擎的出现与发展 搜索引擎( s e a r c he n g i n e ) 是随着w e b 信息的迅速增加，从1 9 9 5 年开始逐 渐发展起来的技术。出于信息的膨胀速度实在快的令人难以置信，用户要在浩瀚 的信息海洋里寻找信息，必然会”大海捞针”无功而返。搜索引擎_ f 是为了解决这 个”迷航”问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现信息， 对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导 航的目的。搜索引擎提供的导航暇务已经成为互联ht - _ t h 常重要的网络服务，搜 索引擎站点也被美誉为”网络，o ”。搜索0j 擎技术蚓而成为汁算机一n k 界和学术 浙江人学倾f ? 学位论义 界争相研究、开发的对象。 目前，按照信息搜集方法和服务提供方式的不同，搜索引擎系统可以分为三 大类： 1 目录式搜索引擎：以人工方式或半自动方式搜集信息，由编辑员查看信 息之后，人工形成信息摘要，并将信息置于事先确定的分类框架中。信息大多面 向网站，提供目录浏览服务和直接检索服务。该类搜索引擎因为加入了人的智能， 所以信息准确、导航质量高，缺点是需要人工介入、维护量大、信息量少、信息 更新不及时。这类搜索引擎的代表是：y a h o o 、l o o k s m a r t 、o p e nd i r e c t o r y 、g o g u i d e 等。 2 机器人搜索引擎：由一个称为蜘蛛( s p i d e r ) 的机器人程序以某种策略 自动地在互联网中搜集和发现信息，由索引器为搜集到的信息建立索引，由检索 器根据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式是面向 网页的全文检索服务。该类搜索引擎的优点是信息量大、更新及时、毋需人工干 预，缺点是返回信息过多，有很多无关信息，用户必须从结果中进行筛选。这类 搜索引擎的代表是：a l t a v i s t a 、n o r t h e r nl i g h t 、e x c i t e 、i n f o s e e k 、i n k t o m i 、f a s t 、 l y c o s 、g o o g l e ；国内代表为：”天网”、悠游、o p e n f i n d 等。 3 元搜索引擎：这类搜索引擎没有自己的数据，而是将用户的查询请求同 时向多个搜索引擎递交，将返回的结果进行重复排除、重新排序等处理后，作为 自己的结果返回给用户。服务方式为面向网页的全文检索。这类搜索引擎的优点 是返回结果的信息量更大、更全，缺点是不能够充分使用所使用搜索引擎的功能， 用户需要做更多的筛选。这类搜索引擎的代表是w e b c r a w l e r 、i n f o m a r k e t 等。 下面，我们将首先介绍搜索引擎的主要体系结构，然后重点分析几个由代表 性的搜索引擎。 2 2 搜索引擎的主要体系结构 绝大多数搜索引擎使用集中式的抓取器一索引器体系结构，下面我们分析一下 三个具有代表性的搜索引擎 l a m 】，来看看它们各自的特点，以决定我们构建的 搜索引擎支撑平台应该具有怎样的架构和功能特点。 2 2 1 集中式体系结构 集中式体系结构的代表是a l t a v i s t a ，在a l t a v i s t a 中，抓取器运行存本地机器 上，其主要任务足向远程主机发送请求。以集中的方式使用索引柬州符用户的查 询。图2 - 2 是a l t a v i s t a 的体系结构降i 可以看到a l t a v i s t a 分成肌个部分，第一 个部分是f j 户接和奄询引_ 1 5 1 l ，第一个部分包括抓取擀和索引器。 浙江人学顺l 洋位论立 图2 - 2a l t a v i s t a 的体系结构 在1 9 9 8 年的时候，a l t a v i s t a 就运行在2 0 个处理器上 l a m 】，每个处理器带 有1 3 0 g 的内存和超过5 0 0 g 的硬盘空间。仅仅查询引擎就消耗了这些资源中的 7 5 。这一体系结构存在两个问题，第一个是在动态网络环境下的数据采集问题， 它导致网络线路的饱和以及加大了服务器的负载。第二个是数据容量的问题，这 种抓取器，索引器的体系结构无法适应未来网络发展的变化。 2 2 2 分布式体系结构 分布式体系结构的一个典型代表是h a r v e s t ，h a r v e s t 采用了个变形过的抓 取器，索引器体系结构，其最大的变化在于使用分布式体系结构来收集和存放信 息，如下面的体系结构图2 - 3 b o w m a n ： 幽2 - 3h a r v e s t 的体系结构 h a r v e s t 介绍了四个主要的冗袭：采集器( g a t h e r e r ) 、代理( b 1 1 0 k e r ) 、复：剐器 浙江人学硕j ：学位论文 ( r e p l i c a t o r ) 和对象c a c h e ( o b j e c t c a c h e ) 。 采集器采集索引信息，而代理对采集到的信息提供增量式的索引查询接口。 采集器和代理能够以多种方式组合以灵活和高效的使用网络和服务器： 采集器被设计运行在提供者端( p r o v i d e r ) ，降低服务器负载和网络流量。 采集器也可以使用f t p 、h t t p 协议通过网络访问信息提供者，这安 排主要用来与不运行h a r v e s t 软件的系统进行互操作，当然会导致服务 器和网络效率的低下，尽管这样的安排仍然存在采集的信息可以在多个 代理之间共享的优点。 代理可以收集来自多个采集器的信息。 采集器可以将信息送给多个代理，减少了重复收集的代价。 代理可以向其它代理检索信息，高效的级联( c a s c a d i n g ) 彼此的索引视 图，使用索引查询接口来从一个代理到另一个代理过滤，重定义信息。 采集器和代理使用称为概要对象交换格式( s u m m a r yo b j e c ti n t e r c h a n g e f o r m a t ，s o i f ) 通信，s o w 描述了对象概要流。 h a r v e s t 提供了称为服务器注册表( h a r v e s ts e r v e rr e g i s t r y ，h s r ) 的顶层代 理，通过它可以知道公开且可用的采集器、代理、c a c h e ，复制管理器。当构建 新的采集器和代理时，避免了重复劳动，此外对搜索时查找合适的代理以及定位 c a c h e 和复制管理器也是有用的。 h a r v e s t 提供了一种称为m i r r o r - d 的弱一致的、复制范围广文件系统，代理在 该文件系统之上进行复制。m i r r o r - d 本身又分布在一种称为f l o o d d 的分层的、 基于泛洪更新( f l o o d i n gu p d a t e b a s e d ) 的组通讯的子系统之上。复制组中的每个 实例偶偶会向它的邻接者发送完成状态信息，以探测可能因为长期的网络断开、 站点失败或者f l o o d d 处理失败引起的f l o o d d 投递失败而引起的更新问题。 m i r r o r - d 实现了最终的一致性。 f l o o d d 逻辑上将按照由自己管理的图在组的成员间传递对象，每个f l o o d d 实例测量可获取的在自己与其它组成员的主机上运行的f l o o d d a e m o n s 之间的网 络带宽，由每个组的主站点建立并可靠的分配组成员问两连结( t w o c o n n e c t e d ) 或三连结( t h r e e c o n n e c t e d ) 的低直径( 1 0 wd i a m e t e r ) 的逻辑拓扑结构。由于一 个f l o o d d a e m o n s 可能属于多个组，这使得构造组的层次结构以及通过共享两个 或三个共同的成员将不相关的组连接在起成为可能。 为了满足越来越多的网络链接和信息服务器的需要，h a r v e s t 包含了一个分 层的对象c a c h e 。c a c h e 给它的每个邻节点和父节点发送个“查询”报文，加 上一个给对象h o m e 站点i c m p 回复，选择响应最快的服务器来检索数据。它缓 存了h t t p 、f t p 对象，加上最近的名字一地址映射。 浙江人学倾i ：学位论义 2 2 3g o o g l e 体系结构 作为目连为止互联网上最成功的搜索引擎，g 0 0 9 l e b n n p a g e 】两个重要特 点：第一，充分利用网络的链接结构计算每一页面的质量等级，这种分级技术叫 做页面等级( p a g e r a n k ) 【p a g e & b r i n ；第二，g o o g l e 使用链接来改善搜索结果。 页面等级实质上是为网络排序，b r i n 和p a g e 认为网络引用( 链接) 图作为 重要的资源，在现有的搜索引擎中被大大的忽视了。通过创建包含多达5 亿多个 超链接的图( 作为所有超链接的样本) ，允许快速的计算出网页的页面等级( 与 用户对重要性的主观看法相一致的引用重要性的客观评价) 。由于这种一致性， 与关键字搜索引擎相比，页面等级提供了更优的方法。对大多数流行主题，页面 等级对接过排序后，受到网页主题限制的简单文字匹配搜索很好的工作。对于 g o o g l e 主系统中的全文检索类型，页面等级也起到很好的作用。 页面等级被认为是用户行为的一个模型。假定”随意冲浪者”( r a n d o ms u r f e r ) 从随意给定的页面开始，始终跟着链接浏览，从来不点后退，最后厌倦了该页并 从另一个随机页面开始。随意冲浪者的访问一个页面的概率是该页的页面等级， 控制因子d 是每个页面上”随意冲浪者”厌倦该页并请求另个随机页的概率。一 个重要的变动是：仅仅给单个页面或者一组页面增加控制因子d ，这考虑到了个 性化以及使得为了获得更高的等级而故意误导系统的可能性几乎不存在。另一 个直观的理由是如果一个页有很多页指向它，或者指向它的页中有一些有较高的 页面等级，这样这个页就有一个较高的页面等级。直觉上讲，网络上被许多页引 用的页应该值得看一看，也有一种情况，尽管只被一个网页引用，但却是被像 y a h o o 这样的网页引用，一般它也值得看一看。网页等级处理这两种情况及其中 的一切，通过网络的链接结构，递归传递权重。 在g o o g l e 搜索引擎中，锚的文字以特殊的方式对待。大多数搜索引擎将链 接的文字与链接所在的页联系起来，g o o g l e 将锚的文字和它指向的页联系起来。 这有几个有点，首先，与页面本身相比，锚通常提供了更精确的网页描述，第二， 无法出基于文字的搜索引擎索引的文档，如图片、程序和数据库中也可能存在锚， 这使得返回从未抓取过网页成为可能，注意，从来没有抓取过的页面可能引起问 题，因为他们在返回给用户以前从来没有进行验证。在这科- - 隋况下，搜索引擎甚 至可能返回尽管有超链接链接着的、实际上并不存在的页面，然而因为对结果排 序是可能的，这种特殊的问题几乎不会发生。 将锚的文字传递到它指向得页面的思想，在w w w 在得到实现，特别是因为 它有助于搜索非文字信息，将搜索的覆盖面扩展到很少下载的文档。因为锚的文 字有助r 提供更好质量的搜索结果。因为必须处理大量的数据，高效的使用锚的 文亨存技术i ：有点旧难。祀jg o o g l e l 9 9 8 年 b r i n & p a g e 2 4 0 0 j ! i 丽的统计数掘 浙江人学烦i ：学位论史 中，有2 亿5 千9 百万索引过的锚。 为了效率及能够在s o l a r i s 或l i n u x 下运行，g o o g l e 大部分使用c 和c + + 实 现的。其体系结构如图2 - 4 b r i n p a g e 】。 图2 4 g o o g l e 高层体系结构 在g o o g l e 中，网络抓取由几个分布式的抓取器完成，一个u r l 服务器发送 u r l 列表给抓取器，获得的网页然后发往存储服务器，存储服务器然后压缩并 将网页存入仓库。每个网页有个相关d 号，称d o c l d ，一旦一个u r l 分析出一个 网页就赋予这个值。由索引器和排序器完成索引功能，索引器完成大量的功能， 它从仓库中读，解压文档并且分析它们。每个文档被转化为组称为命中( h i t ) 的词的出现，命中记录了词、文档中的位置、字体大小的近似值、大小写，索引 器通过创建了一个部分有序的前向索引( c r e a t i n ga p a r t i a l l ys o r t e d f o r w a r d i n d e x ) ， 将这些命中分配到一组“桶”( b a r r e l s ) 中。索引器还执行另一个重要的功能， 它分析出一个网页内所有的链接，并将关于它们的重要信息存入锚文件中，这个 文件包含了足够多的信息，可以确定每个链接来自何处、指向何处以及链接的文 字。 u r l 解析器从锚文件罩读。将相对u r l 转化为绝对u r l ，然后再转化成 d o c i d ，它将锚文字放入d w i j 索引f i ，与锚指向0 j , j d o c l d 天暇，世水。它电牛成d o c i d 浙