（计算机应用技术专业论文）基于多agent协作的智能搜索引擎的研究.pdf

摘要 在互联网获得巨大发展的今天，搜索引擎提供的互联网信息导航服务已经 成为非常重要的网络服务，搜索引擎也已成为互联网用户在较短的时问内从在 信息量浩如烟海的互联网上搜索、获取信息资源必不可少的网络工具，有许多 商业搜索引擎已成为“网络门户”。但随着用户对信息检索的要求不断提高和网 络信息资源的不断丰富，当前广泛使用的按照传统的设计模式设计的搜索引擎 虽然在一定程度上解决了对互联网中的信息资源的定位问题，但也表现出不能 照顾用户的兴趣、资源迷向、信息丢失等缺陷，已不能完全满足用户日益增长 的对信息检索服务智能化、个性化的使用需求。 对传统搜索引擎的缺陷进行分析后认为：传统搜索引擎缺乏智能化，缺少 知识处理和理解知识的能力，对要检索的信息只是采用某类检索模型到预先建 好的索引文件中去检索，而不能学习用户的兴趣需求、区分不同领域的词义差 别、对同一概念的词语进行关联扩展，将已在许多领域得到广泛应用的人工智 能技术与搜索引擎技术结合起来使搜索引擎具有智能化将是解决搜索引擎存在 的缺陷的关键。因此提出了以多个智能a g e n t 组成的多a g e n t 系统( m a s ) 协 作实现智能化的搜索引擎的思想，并在此思想基础上设计了一个基于多a g e n t 协作的智能辅助翻译搜索引擎( i a t s e s m a ) ，以其为模型描述m a s 在完成搜 索引擎智能化方面的应用。 i a t s e s m a 是一个既突出用户的个性化特色又能自动学习、理解、扩展、 处理知识，又集主动搜索和元搜索于一体的智能搜索引擎系统，它将智能a g e n t 技术、搜索技术和翻译技术有机结合，将互联网上的中英文双语网页信息汇集 起来提供给用户进行翻译检索。它采用多个智能a g e n t 组成的m a s 协同工作的 方式实现搜索引擎的智能化，用索引检索，主动搜索和元搜索相互补充的方法 来提高整个系统的查全率和查准率；采用“用户个性化数据库”描述搜索引擎 的用户个性化，结合m a s 中的学习a g e n t 、用户a g e n t 针对用户的个性化特征 对信息分析学习，帮助用户细化搜索请求、区分特定领域词语的含义、扩展关 联词语、以兴趣为依据归并信息。 关键字：搜索引擎，智能，a g e n t ，m a s ，用户个性化数据库 a b s t r a c t n o w a d a y s , w i t ht h eg r e a td e v e l o p m e n to fi n t e r n e t ，n a v i g a t i o ns e r v i c et o i n f o r m a t i o no ni n t e m e to f f e r e db ys e a r c he n g i n eh a sb e c o m eav e r yi m p o r t a n tn e t s e r v i c e s e a r c he n g i n eh a sb e e nan e c e s s a r yn e t w o r kt o o lf o ri n t e m e tu s e r s u s e r sc a n s e a r c ha n dg e ti n f o r m a t i o nf c s o u r c eq u i c k l yf r o mi n t e m e to nw h i c ht h e r ei sag r e a t d e a lo fi n f o r m a t i o n s om a n yc o m m e r c i a ls e a r c he n g i n e sh a v eb e c o m e “d o o r so ft h e n e t w o r k h o w e v e r ，t h eu s e r s r e q u i r e m e n tt oi n f o r m a t i o ns e a r c ha n dt h ei n f o r m a t i o n r e g o u r c 4 皓o ni n t e r a c ta r eb o t hm o r ea n dm o r e a l t h o u g ht h es e a r c he n g i n e sw h i c ha r e d e s i g n e di nt r a d i t i o n a lm o d e la n du s e db ym a n yp e o p l ec a np a r t l yr e s o l v et h e p r o b l e mh o wu s e r s 啪l o c a t et h ei n f o r m a t i o nr e s o u r c e so nt h ei n t e m e t ，n o wt h e ya l s o s h o ws o m el i m i t a t i o n s ，s u c ha si g n o r i n gu s e r s i n t e r e s t s ，p u z z l i n gu s e r sf o rm a n y i n f o r m a t i o nr e s o u r c e s ，d i s c a r d i n gi n f o r m a t i o n ，a n dt h e yc a n ta c c o r dw i t ht h e i n c r e a s i n gu s e r s d e m a n d st ot h ei n t e l l i g e n ta n di n d i v i d u a li n f o r m a t i o ns e a r c hs e r v i c e c o m p l e t e l y a f t e ra n a l y z i n gt h el i m i t a t i o n so ft r a d i t i o n a ls e a r c he n g i n e s ，ig e tar e s u l tt h a tt h e t r a d i t i o n a ls e a r c he n g i n e sh a v en oi n t e l l i g e n c ea n dt h ea b i f i t yt oa n a l y z ea n d u n d e r s t a n dk n o w l e d g e w h e nt r a d i t i o n a ls e a r c he n g i n e ss e a r c ht h ei n f o r m a t i o n ，t h e y o n l ys e a r c ht h ei n d e x e sc r e a t e db ys o m es e a r c hm o d e l ，a n dt h e yc a n tl e a r nu s e r s i n t e r e s t sa n dn e e d s ，d i s t i n g u i s ht h em e a n i n g so fw o r d si nd i f f e r e n tf i e l d s , a s s o c i a t e a n de x t e n dd i f f e r e n tw o r d st h a th a v et h es a m em e a n i n g s t h ek e yt or e s o l v et h e s e l i m i t a t i o n si st oc o m b i n et h ea r t i f i c i a li n t e l l i g e n c et e c h n i q u et h a th a sb e e nw i d e l y u s e di nm a n yf i e l d sw i t ht h es e a r c he n g i n et e c h n i q u et om a k et h es e a r c he n g i n e i n t e l l i g e n t s oip r o p o s et h a tt h ei n t e l l i g e n ts e a r c he n g i n ec a nb er e a l i z e db yt h e c o o p e r a t i o n o f m u l t i - a g e n t s y s t e m ( m a s ) c o m p o s e d b y m a n y i n t e l l i g e n t a g e n t s ， a n db a s e do ni t ，a l li n t e l l i g e n ta s s i s t e dt r a n s l a t i o ns e a r c he n g i n e s y s t e mb a s e do n m u l t i - a g e n tc o o p e r a t i o n ( i a t s e s m a ) i sd e s i g n e d t h e nld e s c r i b et h ea p p l i c a t i o n t h a tm a sc o m p l e t e st h ei n t e l l i g e n ts e a r c he n g i n eb a s e do ni a t s e s m at h a ti sl o o k e d a s m o d e l i a t s e s m ai sa l li n t e l l i g e n ts e a r c he n g i n ew h i c hm a ys t a n do u tu s e r s i n d i v i d u a l p e c u l i a r i t y ，c a nl e a r n ，u n d e r s t a n d ，e x t e n da n dd e a lw i t hk n o w l e d g e ，a n di n c l u d e st h e i n i t i a t i v es e a r c ha n dm e t as e a r c h i tc o m b i n e si n t e l l i g e n ta g e n tt e c h n i q u e , s e a r c h t e c h n i q u ea n dt r a n s l a t i o nt e c h n i q u ev e r yw e l l a n di tp r o v i d e st h ec h i n e s ea n d e n g l i s hb i l i n g u a lw e bp a g e sc o l l e c t e df r o mi n t e m e tf o ru s c r st os e a r c ht r a n s l a t e d t e x t s t h ei n t e l l i g e n c eo fs e a r c he n g i n ei ni a t s e s m ai sr e a l i z e db yt h ec o o p e r a t i o n o fm a st h a ti sc o m p o s e db ym a n yi n t e l l i g e n ta g e n t s r e c a l lr a t ea n da c c u r a c yr a t eo f t h ew h o l es y s t e ma r ei m p r o v e db ym a k i n gi n d e xs e a r c h , i n i t i a t i v es e a r c ha n dm e t a s e a r c hc o m p l e m e n te a c ho t h e r a tt h e , f a i l l et i m e iu s e “u s e r si n d i v i d u a ld a t a b a s e t od e s c r i b et h eu s e r s i n d i v i d u a lp e c u l i a r i t yo fs e a r c he n g i n e a f t e rl e a r n i n ga g e n t a n du s e ra g e n ti nm a sa n a l y z ea n dl e a r nt h ei n f o r m a t i o na b o u tt h eu s e r s i n d i v i d u a l p e c u l i a r i t y ，t h es e a r c he n g i n es y s t e mh e l p su s e r st o d e t a i lt h es e a r c hr e q u i r e s , d i s t i n g u i s hw o r d s m e a n i n g si nd i f f e r e n tf i e l d s ，a s s o c i a t ea n de x t e n dd i f f e r e n tw o r d s ， m e r g ei n f o r m a t i o nb a s e do nn s c r s i n t e r e s t s k e yw o r d s ： s e a r c he n g i n e ，i n t e l l i g e n c e ，a g e n t ，m a s ，u s e r si n d i v i d u a ld a t a b a s e i l l 此页若属实请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料与我一同工作的同志对本研究所傲的任何贡献均已 在论文中作了明确的说明并表示了谢意 研究生签名：耸篮叠日期绝z 生夕 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文 ( 保密的论文在解密后应遵守此规定) 研究生签名：j i j 翅卫导师签名： 注：请将此声明装订在学位论文的目录前 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究的背景及现状 2 0 世纪末是互联网获得巨大发展的时期，其速度十分惊人。如今互联网已 连通了世界上几乎所有的国家，发展成为由数百亿个静态页面组成的超大型信 息库i l 】，而与此同时，涉及w e b 后端数据库的动态网页估计为整个静态页面空 间的5 0 0 剧2 l 。互联网已成为世界上最大的信息源和全球范围内科研、教育、商 业、社会、新闻、专业机构、图书及娱乐等信息的集大成者。搜索引擎是一类 在互联网中主动搜索信息并能自动索引且为互联网用户提供查询服务的软件系 统，它的出现使互联网用户能在较短的时间内从互联网上获取信息，然后根据 一定的规则建立索引、组织数据库，最后通过友好的界面呈列在用户的面前。 目前对于搜索引擎的理论研究与商业应用都已取得了很大的进步，国外的 g o o g l e ，国内的b a i d u 等典型的搜索引擎已成为互联网用户必不可少的网络工 具。但随着互联网用户对信息检索的要求不断提高和网络信息资源的不断丰富， 当前使用的传统搜索引擎已不能完全满足用户的使用要求，仍有几方面问题需 要有进一步的研究： ( 1 ) 尽管搜索引擎的索引覆盖范围已经很广，但实际上绝大部分互联网信 息资源不能被用户检索到。就目前世界上最大的搜索引擎g o o g l e 来说，其获取 的页面数已达3 0 亿，但这也仅仅是整个互联网上信息资源总量的很小的一部分， 且互联网上信息资源的增长速度远远超过g o o g l e 获取的页面数的增长速度。导 致这一问题的主要原因是互联网的发展及信息资源的增长是日新月异的。从搜 索引擎投入商业运营起，这一问题就存在，且必将在以后相当长的一段时间内 一直存在，已有大量研究的分布式计算理论对此问题的解决将起很大的作用1 3 j 。 目前国际上在搜索引擎中采用分布式方法的研究比较典型的是h a r v e s t 系统1 4 j 。 ( 2 ) 现有搜索引擎无法根据互联网用户的使用特点及兴趣返回用户最想要 的信息检索结果，主要体现在排序上一般来说搜索引擎更关心速度而使用相 对简单的索引排序方法。但它面向的千千万万用户因年龄、学历、行业背景、 兴趣爱好各不相同，这就决定了他们向搜索引擎提交同一个要求查询的关键字， 武汉理工大学硕士学位论文 期望返回的检索排序结果却要千差万别。他们总希望符合自己使用特点、自己 感兴趣的结果排列靠前，而其它结果靠后。但实际上一个搜索引擎对不同用户 提交的同一查询关键字得到的都是同一排序结果，并不能根据用户的特点来返 回用户真正想要的信息。 ( 3 ) 用户使用搜索引擎检索信息时常常有大量冗余信息的传输，从而降低 了查询的准确度和相关度。搜索引擎一般是基于关键字查询的，但互联网用户 使用其检索信息资源时往往不能准确地描述自己所要查询的内容，因而提交的 关键字常常过多过少或无关，从而使得陈列出来的检索结果中经常有许多冗余 的无关信息存在，用户再从中选出相关的内容。有研究表明，一般查询结果中 高达7 5 的信息是不相关的i s ，且任何一个搜索引擎的搜索结果的相关度不超过 4 5 1 + i 。 众多搜索引擎由于其自身的局限性，再加上w e b 信息的大容量、异构性、 分布性和动态性，普通用户在搜索信息资源时往往陷入“资源迷向”及“信息 过载”的境地。大量可用信息与用户对信息的驾驭能力形成强烈的反差，造成 这种困境的实质在于目前的信息检索技术缺乏智能，不能理解用户的真正需求 和打算，缺少知识处理能力，因此将人工智能技术结合到这一领域是解决问题 的关键。 1 2 课题研究的目标和内容 人工智能( a r t i f i c i a li n t e l l i g e n c e , a i ) 是用人工方法在机器上实现智能，其 研究目标是认识与模拟人类智能的行为。但传统a i 的研究方法往往无法恰当地 分割或模拟人类智能行为，对智能问题求解的研究逐步使分布式人工智能 ( d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n c e 。d a d 成为研究的重点。d a i 主要研究的是在 人工智能计算中，分散的智能系统如何并行的、相互协作的进行问题求解，因 此具有广泛的应用前景，也适合应用于搜索引擎中实现智能搜索。智能搜索引 擎中的d a i 系统由多个智能a g e n t 组成，每个a g e n t 是一个自治的计算实体， 彼此之间需要进行通信。 针对传统搜索引擎存在不能顾及用户的兴趣、资源迷向、信息丢失等缺陷， 要将多a g e n t 技术与搜索引擎技术结合起来形成一种新的搜索引擎设计模式，实 现搜索引擎的智能化。本文要在此思想基础上设计一个基于多a g e n t 协作的智能 2 武汉理工大学硕士学位论文 辅助翻译搜索引擎，作为智能搜索引擎的模型进行研究，并采用“用户个性化 数据库”塑造方法形成用户兴趣模型以提高系统检索结果与用户兴趣的贴近度， 完成智能搜索引擎的用户个性化。 1 3 论文的组织 围绕课题研究的目标和内容，本文主体部分的具体组织如下； 第2 章对现在得到广泛使用的传统搜索进行概述，介绍它的概念、分类、 工作原理，并指出目前主要的使用对象和研究对象为基于查询串方式的搜索引 擎，在此基础上介绍其组成结构、工作过程，最后介绍搜索引擎的两个性能指 标的含义及计算方式。 第3 章对现在日益得到广泛研究与应用的智能a g e n t 技术进行介绍。先从 多a g e n t 理论的产生和发展开始介绍，详细分析其定义及特性，指出多a g e n t 系统( m a s ) 是研究和应用的重点，最后分析a g e n t 技术在搜索引擎中应用的 可能性、特点，现状及前景。 第4 章是本文的重点内容。针对传统搜索引擎的缺陷，提出将多a g e n t 技术与搜索引擎技术结合起来实现搜索引擎的智能化的思想，并设计一个基于 多a g e n t 协作的智能辅助翻译搜索引擎( i a t s e s m a ) ，作为智能搜索引擎的模 型进行研究。详细描述其设计思想、基本结构和工作流程，详细分析m a s 中各 个a g e n t 的结构和功能，并探讨多a g e n t 之间是如何完成相互间的协作和交互的。 第5 章论述采用“用户个性化数据库”完成智能搜索引擎的用户个性化 的思想，描述提取用户兴趣、塑造用户兴趣模型、构造用户个性化数据库以提 高系统检索结果与用户兴趣的贴近度的方法。 最后，对本文所做的研究工作做了总结，并提出了一些有待进一步探讨、 研究和改进的问题。 3 武汉理工大学硕士学位论文 第2 章搜索引擎的综合研究 2 1 搜索引擎概述 搜索引擎( s e a r c he n g i n e ) 技术是近十年来随着w e b 应用的迅猛发展、网 络信息资源的迅速增加而发展起来并得到广泛应用的技术。通常说来，搜索引 擎是指在互联网中专门提供查询服务、方便用户能够快速地在w e b 信息空问中 查找到其所需要的信息内容的一类网站，它以一定的策略在互联网中搜集，发 现信息，对信息进行理解，提取，组织和处理，并为用户提供检索服务，从而 达到信息导航的目的。用户的查询途径主要包括自由词、全文检索、主题词检 索、分类检索以及其他特殊信息的检索。 目前搜索引擎提供的互联网信息导航服务已经成为互联网上非常重要的网 络服务，它成为人们搜索，获取信息资源时必不可少的工具。现在许多搜索引 擎的功能越来越强大，提供的服务也越来越全面，它们不仅为用户提供信息查 询检索功能，而且把自己发展成为用户首选的互联网入口站点，因而被美誉为 “网络门户”用。搜索引擎技术因而成为计算机工业界和学术界争相研究、开发、 使用的对象。 2 2 搜索引擎的分类 目前，按照信息搜集方法和服务提供方式的不同，可以将搜索引擎分为三 大类：基于查询串方式的搜索引擎、基于目录的搜索引擎以及元搜索引掣8 】。 2 2 1 基于查询串方式的搜索引擎 基于查询串方式的搜索引擎通常是由一个称为网络机器人( r o b o t ) ，也称为 网络蜘蛛( s p i d e r ) 、网络爬虫( w e b c r a w l e r ) 的程序以某种策略自动地在互联 网中搜集和发现信息，并将搜集到的信息建立索引，形成索引库。由检索器根 据用户的查询输入检索索引库，并将查询结果返回给用户。服务方式是面向网 页的全文检索服务。此类搜索引擎一般由三个主要部分组成：s p i d e r 、索引库、 4 武汉理工大学硕士学位论文 搜索程序。 s p i d e r 是一个用c 、p e d 、j a v a 等语言编写，能运行在u n i x 、s o l a r i s 、w i n d o w s 等操作系统平台上的程序，它从一个初始u r l 列表出发访问w e b 站点，提取站 点上的网页，并根据网页中的链接进一步提取其它网页，或转移到其它站点上。 如此递归地访问w e b 站点并提取页面信息。s p i d e r 的设计是否合理直接影响到 它访问w e b 站点的效率，并影响整个搜索引擎的搜索质量。另外，设计s p i d e r 时必须考虑它对网络和被访问w e b 站点的影响，且应遵守一些协议，以便被访 问站点的管理员能够确定哪些内容可以被其所访问。 索引库是一个庞大的数据库，被s p i d e r 提取的网页内容被放入其中以便建 立索引。建立索引的方式有多种：对整个h t m l 文档中的所有单词建立索引； 只分析h t m l 文档的标题或前几段内容，即对单词建立索引。建立索引时， 一般给网页中的每个关键词设一个等级值，表示网页内容与关键词之间的关联 程度。当用户输入某关键词进行查询时，搜索程序将从索引库中找出所有与关 键词相关联的网页，以等级值作为排序依据，按从高到低的顺序把搜索结果通 过用户接口返回给用户。 基于查询串方式的搜索引擎一般要定期访问大多数以前搜集过信息的网 页，更新索引库，刷新网页更新情况，去除死链接。此类搜索引擎因为依靠程 序搜索信息资源，所以其信息资源数据库非常庞大，内容非常丰富，搜索结果 的查全率较高，但查准率较低。典型的有：a l t av i s t a 、i n f o s c c k 、g o o s e 、b a i d u 等。 2 2 2 基于目录的搜索引擎 基于目录的搜索引擎也称为目录型检索工具，或分类目录式搜索引擎，是 互联网上最早提供w e b 信息资源查询的工具，它由人工方式或半自动方式发现、 抓取、辨别网络中的信息资源，再由编辑目录的人员按某种分类法，建立主题 树分层目录，将采集、筛选后的信息分门别类地放入各大类或子类下面。目录 的数据库是依靠专职编辑或志愿人员建立起来的，这些编辑人员在访问了某个 w e b 站点后撰写一段对该站点的描述，并根据站点的内容和性质将其归为一个 预先分好的类别，把站点的u r l 和描述放在这个类别中。当用户通过某个关键 词进行查询时，搜索程序通过逐级层层浏览这些类目中的描述信息，寻找对应 的站点信息。很多目录同时也接受用户提交的网络站点描述，得到目录的编辑 5 武汉理工大学硕士学位论文 人员认可后，就会将之添加到合适的类别中。 目录的结构为树形结构，首页提供了最基本的几个大类的入口，用户可以 一级一级地向下访问，直至找到自己需要的类别。另外，用户也可以利用目录 提供的搜索功能直接查找某个关键词。但由于目录只在保存的对站点的描述中 进行搜索，因此站点本身的动态变化不会反映到搜索结果中来。 基于目录的搜索引擎所收录的网络信息资源是经过专业人员鉴别、选择和 组织了的，因为加入了人的智能，所以信息准确、导航质量高，但因采用了人 工方式，则有了成本高、维护量大、信息量少的缺点。现在很多搜索引擎站点 都同时提供有基于目录的和基于查询串方式的搜索服务，以便尽可能地为用户 提供全面的查询结果。具有代表性的目录搜索引擎有：y a h o o ! 、o p e nd i r e c t o r y 等。 2 2 3 元搜索引擎 元搜索引擎( m e t a - s e a r c he n g i n e ) 是在搜索引擎基础上建立的可以同时查 询多个搜索引擎的w w w 站点。这类搜索引擎的特点是本身并没有存放网页信 息的数据库，没有自己的数据，通过设立一个w e b 服务器接收用户所提交的查 询关键词等信息。当用户查询一个关键词时，它把用户的查询请求转换成其它 搜索引擎能够接受的命令格式分发给其他的搜索引擎或其他数据库，并行地访 问数个搜索引擎来查询这个关键词，然后将从目标搜索引擎所返回的结果进行 相关处理，以整体统一的格式发送给查询用户，完成用户信息的查找过程。 严格意义上来讲，元搜索引擎只能算是一种用户代理，而不是真正的搜索 引擎1 9 1 ，它依赖其他独立搜索引擎而存在它集成了不同性能和不同风格的搜索 引擎并发展了一些新的查询功能，用一个元搜索引擎进行查询信息就相当于在 多个独立搜索引擎上进行查询，可以收到事半功倍的效果。同时元搜索引擎不 必参与原始信息的搜集过程，简化了系统设计过程。并且多数元搜索引擎在处 理其它的搜索引擎返回结果时，只提取出每个搜索引擎的结果中前面1 0 - 5 0 条， 并将这些结果合并在一起返回给用户，因此最后结果的数量可能会远少于直接 在一个搜索引擎上进行查找所得到的数量。 元搜索引擎实现起来比较简单，但是它也有一定的局限性，例如多数元搜 索引擎都只能访问少数几个搜索引擎，并且通常不支持这些搜索引擎的高级搜 索功能，在处理逻辑查询时也常常会出现错误。具有代表性的元搜索引擎有： 6 武汉理工大学硕士学位论文 a s l d c e v e s 、d i g i s e a r c h 、m e t a c r a w l e r 等。元搜索引擎的操作流程如图2 - 1 所示。 元搜索引擎 彳 蕊 硝黛 图2 - 1 元搜索引擎的操作流程示意图 分析处理关键字 按相关度捧序 查找索引库得到文档列表 追历文档列表 f 找到包芎 芝竺! 岁 计算罔页相关度 组织n 个结果返回给用户 2 3 搜索引擎的原理 图2 - 2 搜索的处理流程图 搜索引擎通常指的是收集了互联网上几千万到几十亿个网页并对网页中的 每一个文字( 即关键词) 进行索引，建立索引数据库的全文搜索引擎。当用户 使用搜索引擎进行信息查询时，它并不在整个互联网上搜索，它搜索的实际上 是预先整理好的网页索引数据库。搜索引擎也不能真正理解网页上的内容，它 7 武汉理工大学硕士学位论文 只能机械地匹配网页上的文字。当用户查找某个关键词的时候，所有能与该关 键字相匹配的页面内容都将被搜出。通过排序算法排序后，这些结果将按照与 搜索关键词的相关度高低，依次排列。 搜索的过程实际上是对关键字进行匹配的过程，首先对用户输入的搜索关 键字进行分析、处理，然后在索引库中得到文档列表并对文档列表进行扫描， 与处理后的关键字进行匹配，包含了此关键词的网页都将作为搜索结果被提取 出来。依据排序算法计算网页和关键词的相关度，若每次页面显示n 个结果， 根据相关度的数值将前n 个结果返回给用户查看。如果用户查看下一页结果， 则重新进行搜索，把排序结果中在第n + 1 到2 * n 的网页形成列表返回给用户， 如此类推。其处理流程如图2 2 所示。 图2 - 3 搜索引擎的组成结构图 8 武汉理工大学硕士学位论文 2 4 搜索引擎的组成及工作过程 目前，基于查询串方式的搜索引擎成为主流搜索引擎，也有很多搜索引擎 站点都同时提供有基于目录的和基于查询串方式的搜索服务，以更好地为用户 提供服务。因此基于查询串方式的搜索引擎是本文的研究重点，另两类搜索引 擎在文中不作研究。 一个搜索引擎程序主要由搜索器( c r a w l e r ) 、分析器( a n a l y z e r ) 、索引器 ( i n d e x ) 、检索器( s e a r c h e r ) 和用户接口( u s e ri n t e r f a c e ，u i ) 等五个部分组成， 主要存储设备由页面存储库和索引数据库两部分组成【8 】。其组成结构图如图2 3 所示。 2 4 1 搜索器 搜索器( c r a w l e r ) 通常是一个被称为网络蜘蛛( s p i d e r ) 的计算机网络爬虫 程序。它日夜不停地运行，在互联网中漫游，从一个预先定好的初始u r l 列表 出发，按照一定的u r l 爬行和信息搜集策略发现并搜集互联网中的w e b 页面信 息。它爬行到某个网页时，就将该网页信息抓取下来，供分析器分析处理；同 时沿着网页中的所有u r l ，以宽度优先、深度优先或启发式方式迭代地爬行到 其它页面【1 0 】。其工作过程如图2 4 所示。 韧始u r l 列表 分析链接 待处理的 u r l 主! 结束 正在赴理的 u r l 已赴理的 u 卫l 分析器 图2 - 4s p i d e r 的工作过程示意图 9 粼一 处合 番 看一 武汉理工大学硕士学位论文 搜索器要尽可能多、尽可能快地搜索互联网中的各种类型的新信息，但因 互联网上的信息更新很快，所以一般要定期访问大多数以前搜集过信息的网页， 刷新网页更新情况，以避免死连接和无效连接。 搜索器通常采用分布式并行计算的技术来实现，以提高抓取和更新网页信 息的速度【1 1 】。 2 4 2 分析器 分析器( a n a l y z e r ) 的功能是对搜索器抓取的网页信息进行文档分析处理， 再保存到本地页面存储库中，以供索引器处理。 因为搜索器抓取到的页面是不同组织形式的数据信息，如各种数据库、不 同文件系统以及互联网静态w e b 页面等，所以必须对它们进行分析处理。文档 分析处理技术一般包括中英文分词、网页过滤和净化、网页内容转换等，这些 技术往往与网页信息用到的具体语言、系统的预期功能、系统的索引模型等密 切相关，因而不同的搜索引擎中分析器的设计也各不相同。通过分析处理后， 不同格式的文档( 如m i c r o s o f tw o r d 、w p s 、t e x t 、h t m l 等) 都被转换为统一 的标准格式文本文档。 2 4 3 索引器 索引器( i n d e x ) 的功能是理解被搜索器抓取下来、经过分析器分析处理并存 入页面存储库后的文档，从中抽取出索引项，将文档表示成一种便于检索的方 式，生成文档库的索引表并存储在索引数据库中。它定期从页面存储库中取出 经过文档分析处理过的文档，以单词为主关键字建立索引，即为每个关键字设 一个等级值，表示文档内容与关键词之间的关联程度，并初步进行排序处理， 结果保存到索引数据库中。 索引器读入被分析处理的文档后，首先进行分词处理生成索引项，并作归 并排序，生成i n v 和i n d e x 文州1 1 】，合称为索引表。索引项有两种：客观索引项 和内容索引项。客观索引项与文档的语意内容无关，如作者姓名，文档的原始 u r l ，更新时间，编码方式，长度等等。内容索引项是用来反映文档内容的， 如关键词及其等级值，短语，单字等等。内容索引项可以分为单索引项和多索 引项( 或称短语索引项) 两种。单索引项对于英文来讲即是一个个英语单词， 1 0 武汉理工大学硕士学位论文 因为单词之间有空格作为天然的分隔符，所以比较容易提取；而对于中文则必 须进行词语的切分。 i n v 文件为某种形式的倒排表( i n v e r s i o nl i s t ) ，即由索引项查找相应的文档， 它是索引项专文章编号( 或u r l ) 的映射关系，如图2 - 5 所示。相关信息主要 包括索引项、索引项在所在文档中的位置、索引项的等级值。i n d e x 文件存储索 引项与倒排表的对应关系，内容为索引项在倒排表中相应的文档块中出现的位 置，含有该索引项的文档数量等信息，这样以便检索器计算索引项在文档中出 现的位置，以便检索器计算索引项之间的相邻或者相近的关系。索引器可使用 集中式索引算法或分布式索引算法来建立索引。 由 当页面存储库中的数据量很大且更新速度很快时必须实现即时索引，否则 跟不上信息量急剧增加的速度。索引算法对索引器的性能( 如大规模峰值查询 时的响应速度) 有很大的影响。一个搜索引擎的有效性在很大程度上取决于索 引的质量【1 1 1 。 2 4 4 检索器 检索器( s e a r c h e r ) 的功能是根据用户的查询在索引数据库中快速检索出文 档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种 用户相关性反馈机制。首先采用与分析、索引文档相似的方法来处理用户查询 请求；然后按照某种方法来计算用户查询与索引数据库中每个文档之间的相关 度；最后，将相关度大于阙值的所有文档按照相关度递减的顺序排列，返回给 用户。 检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合 1 1 武汉理工大学硕士学位论文 模型四种。它一般要支持多种语法规则，如逻辑运算操作符a n d 、o r 、n o t 、 “+ 、一”、连接号和通配符，逗号、括号或引号等。对于每个索引项，匹配i n d e x 文件，查询倒排表中包含该索引项的文档，并对所有找出的文档进行集合运算， 将结果集按照基于内容和基于链接分析的方法进行相关度评价并排序，最大限 度保证检索结果与用户查询串的高相关性，将最终形成的有序文档结果集合返 回给用户接口。 2 4 5 用户接口 用户接口( u s e ri n t e r f a c e , u i ) 的作用是根据用户输入进行查询，并显示查 询结果，提供用户相关性反馈机制。主要的目的是方便用户使用搜索引擎，高 效率，多方式地从搜索引擎中得到有效的，及时的信息。用户接口的设计和实 现使用人机交互的理论和方法，以充分适应人类的思维习惯。 用户输入接口可分为简单接口和复杂接口两种。简单接口只提供用户输入 查询关键字的文本框；复杂接口可以让用户对查询进行限制，如可以限制进行 逻辑运算( a n d 、o r 、n o t 、+ 、) 、相近关系( n e a r ) 、域名范围( 如e d u 、c o r n ) 、 出现的位置( 如标题、摘要、内容) 、信息更新时间、长度等。 当互联网用户通过用户接口u i 提交查询时，检索器( s e a r c h e r ) 程序根据 用户输入的查询关键词，在已由索引器( i n d e x e r ) 完成索引和初步排序的存储 桶( b a r r e l ) 中进行查找，并采用特定的页面优先度算法对其结果进行最终排序， 使之尽可能符合用户查询需求。最后，用户接口u i 将最终查询结果呈现在互联 网用户面前。 2 5 搜索引擎的性能指标 对w e b 页面信息的搜索从本质上说是一个信息检索问题，所以信息检索的 两个性能参数：召回率( r e c a l lr a t e ) 和精度( p r e c i s i o n ) 就可以用来衡量搜索 引擎的性能i l z j 。因此一个性能优秀的搜索引擎除具有查询速度快，较好的可维 护性外，召回率、精度也是衡量搜索引擎性能的两个重要指标【”l 。 召回率是检索出的相关文档数和文档库中所有的相关文档数的比率，衡量 的是搜索引擎的查全率；精度是检索出的相关文档数与检索出的文档总数的比 率，衡量的是搜索引擎的查准率( a c c u r a c yr a t e ) 。其具体计算公式如下： 武汉理工大学硕士学位论文 召回率= 检索出的相关文档数集合中相关文档数= ( a a + b ) * 1 0 0 公式 ( 2 1 ) 精度= 检索出的相关文档数检索出的文档总数= ( a a - ) c ) * 1 0 0 公式 ( 2 2 ) 上述两公式中的a 代表检索出的相关文献数，公式( 2 1 ) 中的b 代表文档 库中其它不相关的文档数，公式( 2 2 ) 中的c 代表被检索出的，但内容与关键 字不相关的文档数。 对于一个搜索引擎系统来说，查全率和查准率是有相互关联关系的，召回 率和精度不可能做到两全其美，若查准率高但查全率低，查到的信息的绝对数 量就少；反之，查到有用信息时所付出的代价就高。对于目前的搜索引擎系统 来讲，很难搜集到所有的w e b 页面信息，所以召回率很难计算。各个搜索引擎 系统都非常关心精度，以c - o o g l e 为例，它通过不断优化自己的文档和查询的表 示方法、关键字相关性的匹配策略和查询结果的排序方法等一系列相关措施， 使g o o g l e 具有了非常高的查准率，从而也得到了广大用户的认可【1 4 1 。 武汉理工大学硕士学位论文 第3 章智能a g e n t 技术研究 3 1a g e n t 理论的产生与发展 a g e n t 起源于2 0 世纪7 0 年代的人工智能( a r t i f i c i a li n t e l l i g e n c e , a i ) 领域 【1 5 l q 。哲学家d c n n e t t 于1 9 7 1 年提出了“意图系统( i n t e n t i o n a ls y s t e m ) ”的概 念，用于描述这样一类实体，它们的行为可用信念、愿望等理性智慧来预测。 后来他又创造了“意图姿态( i n t e n t i o n a ls t a n c e ) ”的概念，这一概念启发了人工 智能研究者们将通常应用于人类自身的一些认知思想和概念( 如信念、愿望、 承诺等) 应用于a g e n t 。8 0 年代中后期，人工智能技术与分布式计算技术相结合， 出现了分布式人工智能( d i s t r i b u t 酣a r t i 缸c i a li n t e l l i g e n c e ，d 越) 这个研究方向。 作为分布式人工智能的构成因素，a g e n t 一词越来越多地被人们所提到，由于它 突破了长期以来人工智能研究进展不大的局面，因此受到人们的重视。1 9 9 3 年 首次召开了a g e n t 形式化模型的国际会议，同年ys h o h a m 提出了面向a g e n t 编程( a g e n t o r i e n t e d p r o g r a m m i n g 。a o p ) 的概念。1 9 9 4 年1 月，美国g e n e r a l m a g i c 公司演示了他们开发并初次公开的a g e n t 软件。1 9 9 4 年3 月，美国人工智能协 会( a m e r i c a na s s o c i a t i o nf o ra r t i f i c i a li n t e l l i g e n c e ，a a a i ) 春季年会的主要议题 即为软件a g e n t ，参加者包括了如下领域的研究者：软件工程、机器人、知识表 达、知识库系统、数据库、机器学习、认知科学、心理学、计算机图形学、人 机交互等，这意味着a g e n t 的研究集成了来自多种研究领域的重要成剁1 。”。 从此，a g e n t 融入了主流计算机的各个领域，产生了一系列新的思路、方法 和技术，各种类型的软件a g e n t 大量用于信息处理、办公自动化、交通管理、