（计算机应用技术专业论文）一个基于web的搜索引擎的分析与设计.pdf

华中师范大学硕士学位论文 摘要 i n t e r n e t 的一个重要功能是信息的交流和共享，而查询检索又是获 取信息的主要方法。网络技术和w e b 的快速发展给设计开发有效的网络 资源检索工具提出了更高的需求。在纵观国内外的搜索引擎和信息检索 系统的基础上，本文首先对搜索引擎的结构和有关技术进行了分析，提 出了一个基于w e b 的全文检索搜索引擎的基本框架。在设计中，系统采 用了自己的信息收集机器人，并针对w e b 信息分布的特点对机器人的搜 索策略进行了初步的讨论，给出了一个改进的宽度优先搜索算法。 关键词 万维网、搜索引擎、网络机器人、信息检索、搜索算法 华中师范大学坝士学位论文 a b s t r a c t ： t h es h a r ea n dc o m m u n i c a t i o no fin f o r m a t i o ni sa a i m p o r t a n t f u n c t i o no fi n t e r n e t d u et ot h er a p i da d v a n c eo fi n t e r n e ta n d w e b ， t od e s i g naw e bs e a r c he n g i n es y s t e mi sac h a l l e n g i n gt a s k a f t e r m a k i n gac o m p r e h e n s i v ev i e wo ft h ew o r l dw i d ew e bs e a r c he n g i n e s ， t h i sd i s s e r t a t i o nf i r s ta n a l y z et h em a ins t r u c t u r ea n dt e c h n o l o g i e s o ft h es y s t e m t h e nw ed r e s e n taf r a m e w o r ko faf u l lt e x tr e t r i e v a l s e a r c he n g i n e t h is s y s t e mu s e sar o b o tt oc r a w lt h ew e bs p a c e i n t h es e c o n d p a r t ，w e d i s c u s st h ef e a t u r e s o ft h e h y p e r t e x t i n f o r m a t i o no nt h ew e ba n dg i v ea ni m p r o v e db r e a d t h f i r s ts e a r c h i n g a l g o r i t h m w e b 、s e a r c h e n g i n e 、w e br o b o t 、i n f o r m a t i o nr e t r i e v a l 、s e a r c h i n g a l g o r i t h m i v 华中师范大学硕士学位论文 1 1 引言 第一章搜索引擎的发展及现状 随着网络技术和信息技术的迅猛发展，作为全球范围内科研、教育、 商业和社会等信息传播和交流的主要渠道，i n t e r n e t 已经成为世界上最 大的信息宝库。这其中又以环球信息网w w w ( w o r l dw i d ew e b ) 的发展 最为迅速。w w w 的概念最初是在1 9 8 9 年提出的，其目的是开发一个全球 范围内的跨平台的分布式超媒体系统，它是i n t e r n e t 上信息组织和聚集 的一种方式。w w w 是一个由许多超媒体文档组成的集合，这些文档也叫w e b 主页都是用h t m l ( h y p e r t e x tm a r k u pl a n g u a g e ) 语言写成，页面包含 了文字、图像等各种多媒体对象以及指向其它文档的超链。现在，w w w 上有上百万的站点，各站点上的主页数目已累计达到上亿页，它们散布 在世界各地的w e b 服务器上，每个服务器自主的管理自己的资源，没有 统一的管理机制。浏览器使用h t t p 协议实现w e b 文档的浏览。 由于目前i n t e r n e t 上信息的积累的速度和规模达到空前的水平，与 此同时i n t e r n e t 用户的人数也在不断地增加。在这样一个信息时代里， 如果没有一个明确的目标，用户单纯靠浏览w e b 文档，沿页面中的超链 去查找所需要的信息是很困难的事情。所以如今i n t e r n e t 用户面临的最 根本的问题之一就是：如何在浩翰如海的信息空间里快速地获取到高质 量的信息。这就需要有一个导航系统，即搜索引擎( s e a r c he n g i n e ) 为 用户指引方向。搜索引擎的任务就是到i n t e r n e t 上发现和收集信息，进 行相应的加工，建立索引并为用户提供索引查询的服务。通过搜索引擎， 用户可以快速定位有用信息，找到感兴趣的站点。由于用户对信息的大 量需求，许多搜索引擎站点已经成为了用户进入i n t e r n e t 的第一步，搜 索引擎也成为i n t e r n e t 上的一个新兴产业。 1 2 国内外发展综述 从1 9 9 4 年第一个搜索引擎w w w w o r m 的出现到现在，i n t e r n e t 上已 经出现了各式各样的搜索工具。据统计，1 9 9 6 年在美国开发出来的各种 类型的搜索工具已达1 0 0 多种，噩洲、非洲、欧洲和大洋洲各国开发的 搜索工具也达到了7 0 余种。在亚洲，中国、日本、韩国、马来西亚、新 加坡、台湾和香港地区都有了母语的搜索工具 1 | 。这些搜索引擎有的用 华中师范人学硕士学位论文 于专业信息的查询，有的用于提供某地区的信息的查询，有的只用于 提供某一i n t r a n e t 内部的信息查询；另外还有许多搜索引擎致力于提供 无国界、多语种的综合信息查询服务。其中，综合式的搜索引擎是i n t e r n e t 上最受欢迎的搜索工具，象y a h o o 、a l t av i s t a 、l y c o s 、i n f o s e e k 、 w e b c r a w l e r 等都是用户经常访问的站点。 近几年来，我国的网络建设也正以前所未有的速度发展：中国教育 和科研网( c e r n e t ) 已经连接了国内3 0 0 多所高等院校，邮电部的中国 公用i n t e r n e t 网( c h i n a n e t ) 中国科技网( c s t n e t ) 以及金桥网 ( c h i n a g b n ) 等在国内也有了相当大的规模“1 。随着各网络的不断发展， 国内站点上中文信息资源的数量也急剧增长，如何快速、准确地获取w e b 上的中英文信息为我国的教育、经济、科研等行业服务已经成为一个迫 在眉睫的课题。为了解决中文信息查询困难的问题，国内许多计算机专 家和信息检索专家也积极地探索和开发出了一系列的中文搜索引擎，如 北大天网、华南木棉网、广州网易、指南针、北极星、搜狐、若比邻、c s e e k 以及香港的茉莉之窗，台湾的o p e n f i n d 等等。 1 3 搜索引擎的分类 随着技术的不断更新以及用户要求的不断提高，搜索引擎从诞生到 现在也经历了很多变化和改进。按其技术和功能的发展历程来看，我们 可以将搜索引擎分成以下几类： ( 1 ) 人工分类的搜索引擎 较早期的搜索引擎采用的是人工的方法对i n t e r n e t 上的信息进行收 集和分类的，例如y a h o o 。这一类搜索引擎首先将于搜集到的网站手工 划分到某个分类下，再记录一些摘要信息，对网站进行简单的介绍。它 们的优点是：具有目录式的分类结构，收录的网页经过系统的筛选和组 织，质量较高，条理性比较强，用户可以很方便地查到某一类别的信息。 而它们的缺点就是：采集信息的速度远远比不上网络资源的增长速度， 所建立的数据库的规模都比较小，检索到的文件数量有限。现在，对于 拥有如此庞杂的信息的i n t e r n e t ，人工分类索引的方式已逐渐不能适应 用户的要求。 ( 2 ) 基于机器人技术的搜索引擎 为了能更快、更广地收集到网上的资源，现在的搜索引擎一般都采 华中师范大学硕士学位论文 用了自动搜索索引机制，通过向i n t e r n e t 派出r o b o t ，信息的收集和索 引都是由程序自动完成，很少需要人工的参与。如a l t av i s t a 、l y c o s 、 e x c i t e 、天网、北极星等，它们都拥有自己的搜索机器人r o b o t ( 也叫 w a n d e r e r 、c r a w l e r s 或s p i d e r ) 。r o b o t 实际上是一个专门设计的程序， 它能递归地跟随w e b 文档中的超链( a n c h o r ) 去获取网上的信息。这一 类搜索引擎的优点在于收集的信息量大，信息的处理速度快，用户可以 通过关键词检索的方式来查询信息。 由于搜索策略的不同，不同搜索引擎具有不同规模的数据库，例如 e x c i t e 数据库中记录了5 0 0 0 万个网页，a 1 t a v i s t a 记录3 1 0 0 万个网页， l y c o s 有7 0 0 0 万个u r l 索引。相比之下y a h o o 只有1 0 0 多万索引，规模 要小许多j 。搜索引擎数据库规模的大小决定了查询的信息是否全面。 虽然自动索引搜索引擎的覆盖面很广，能给用户提供了较全面的搜索结 果，但由于其数据库包含的信息过于庞杂，有的查询会列出成百上千条 结果。这些结果一般精确性较差，用户仍然得花费大量的精力在其中寻 找自己真正需要的信息。现在有些搜索引擎也已经提供了相关性排序的 功能来提高查询的精确性，但因为大部分排序算法的主要依据还是通用 意义上的处理结果，如根据文档中查询关键字出现的个数来确定优先等 级，所以排序后的结果离用户的要求还有一定的差距。 分类目录导航和索引查询都各有优点：通过分类目录，用户可以很 方便的对某个范围内的信息进行查找；而关键词查询又可以提供较精确 的查找手段。为了充分发挥两者的优势，很多搜索弓1 擎都是将它们结合 起来，为用户提供服务。 ( 3 ) 元搜索引擎( m e t a s e a r c h ) 因为i n t e r n e t 上的资源非常丰富，而且信息散布在全球没有统一的 管理和组织机制，单个搜索引擎的数据库很难涵盖所有的资源，有时人 们不得不查询多个搜索引擎来扩大寻找的范围。为了满足这种需求，网 上又出现了独立于数据库的查询工具元搜索引擎。元搜索引擎是一 种建立在多个异地的搜索引擎基础之上的信息查询工具，它自己并没有 索引数据库面是选择现有的独立的搜索引擎中的优秀者，利用它们的检 索功能，以集成的界面向用户提供查询服务。现有的元搜索引擎通常以 两种不同的方式提供服务：一种只是提供多个搜索引擎的查询入口，用 户每次可选择其中一个执行查询操作，这并不是真正意义上的元搜索引 擎。另一种方式则构造了统一的查询界面，查询要求经转换后并行地传 给多个搜索引擎，各引擎返回的搜索结果被元搜索引擎综合、去除重复、 进行统一的相关性评估，最终才返回给用户那些优化排序的结果。 华中师范大学硕士学位论文 由于元搜索引擎不用考虑索引的建立和维护，开发者可以将精力集 中在查询功能和界面的设计上。m e t a c r a w l e r 和s a v v y 是这一类搜索引 擎的典型代表，它们的优点在于能够提供覆盖面广、命中率商、相关性 更好的搜索结果。但元搜索引擎在很大程度上依赖于其它引擎的索引数 据，所以它们还具有一定的局限性，查询的速度也较一般的搜索引擎要 慢一些。 ( 4 ) 分布式的搜索引擎 面对如今i n t e r n e t 上信息量呈指数增长的发展趋势，收集并索引网 上如此庞大的信息在今后已不是单个集中式的搜索引擎可以完成的。为 了解决这一问题，有关专家已经提出了分布式系统的设计。 下面的两个图分别表示了集中式和分布式搜索引擎的一般结构。 i 用户 i 山 用户代理层 0 中间层 0 服务提供代理层 ， 请求数据 图1 1集中式搜索引擎图1 2 分布式搜索引擎 在集中式的搜索引擎中，用户首先向查询服务器提交查询申请，查 询服务器再通过访问系统的索引数据库并将结果返回给用户。索引库中 韵信息是由r o b o t 从网上搜集并建：藏，信息的收集一般都集中在一个地 华中师范大学硕士学位论文 点。另外，r o b o t 还要周期性地上网检查，保证索引库中存放的是最新 的信息。 而分布式的搜索引擎是由用户代理层( u s e ra g e n t s ) ，中间层 ( b r o k e r s ) 和服务提供代理层( p r o v i d e ra g e n t s ) 组成的一种层次型 结构。其中用户代理层由多个用户代理组成，每个代理可以为系统提供 不同的用户界面；中间层则由多个b r o k e r s 组成，每个b r o k e r 负责接受 用户代理递来的查询请求，并将请求任务分配给一个或多个服务提供代 理来完成：每个服务提供代理负责从各低层信息库收集特定主题内容的 信息。低层信息库是由分布在不同地区的搜索器建立，各个库信息的搜 集一般是按照i n t e r n e t 域或地理范畴来划分的。 分布式的搜索引擎提供给用户的是一种透明的层次式的搜索模式， 用户并不需要知道自己查找的数据具体存放在哪个索引库中，对他们而 言整个系统仍然象一个集中式的搜索引擎。各地区、各个域的搜索系统 相互分工，协同合作，不仅避免了信息的重复搜集，也节约了网络带宽 等资源。因为分布式系统的特点和优势，它已成为世界各地网络研究的 重点之一。美国c o l o r a d o 大学开发的h a r v e s t 系统就是一个较好的分布 式的系统。 按索引内容来分，搜索引擎又可以分为全文检索和非全文检索两类： ( i ) 非全文检索类 既标引检索，它只对文档的u r l 、篇名、题名、文件的前几段文字、 关键词等比较重要的信息进行索引。这一类搜索引擎因为需要的索引空 间较小，通常可以搜集到更多的文档信息，而且查询速度快。但由于标 题和摘要等所含的信息片面且有偏差，它们不能反映整个文档的内容， 所以查询结果存在精确性差的问题。非全文检索类的搜索引擎有l y e o s 、 w w ww o r m 等。 ( 2 ) 全文检索类 全文检索技术在8 0 年代以前主要用于大型的联机信息查询系统，9 0 年代以来，随着i n t e r n e t i n t r a n e t 的迅猛发展和信息对正确决策的日 趋重要，全文检索技术愈来愈成为信息系统中不可缺少的关键功能和必 要手段。它是以整个文本数据为主要处理对象，提供根据资料内容而不 是外在特征来实现的先进查询手段。与标引检索相比较，全文检索提供 了全新的、强大的检索功能，它可以直接根据文档的内容进行检索，能 华中师范大学颅十学位论文 多角度、多侧面地综合利用信息资源。 全文检索类的搜索引擎是对所收集到的信息全文进行索引，以全文 检索为核心技术的搜索引擎已经成为网络时代的主流。象a l t av i s t a 、 e x c i t e 、o p e n t e x t 、w e b c r a w l e r 等都采用了全文索引的方式。这类的搜 索引擎的优点是查询全面充分，只要某个文档中含有查询条件中的关键 字，该文档就可能被返回给用户。但因为含有查询条件的文档并不一定 就是相关性好的文档，所以全文检索类搜索引擎的缺点就是查询结果的 数量太大，用户很难从中找到自己真正需要的信息。 1 4 现有搜索引擎存在的问题 我们可以从以下一些方面来评价一个搜索引擎性能的优劣： ( 1 ) 查询的回复性( r e c a 1 ) ：也就是信息的查全率，用户通过查询 应该能得到尽量全面信息，这要求搜索引擎建立具有一定规模 和范围的数据库； ( 2 ) 查询的精确性( p r e c i s i o n ) ：也就是信息的查准率，用户希望 通过查询得到相关性高的结果，这要求搜索引擎能够很好地进 行相关性计算； ( 3 ) 查询的速度：搜索引擎一般都拥有庞大的信息资源数据库，一 个好的搜索引擎应采用先进的索引技术和检索技术，为用户提 供快捷的服务； ( 4 ) 数据库的更新频度、时效性 的信息变化，及时更新数据 和重复链接的情况； 搜索引擎应该能够不断跟踪网上 查询结果尽量避免出现无效链接 ( 5 ) 能提供方便、全面的查询服务：简单查询服务并不能满足用户 的需求，一个好的系统还应能支持短语查询、范围查询、结构 查询、概念查询、自然语言查询等多种方式。 虽然国外象a l t av i s t a 、e x c i t e 、w e b c r a w l e r 这样的搜索引擎已经 具有了高效率的资源搜索器，能够处理海量数据的索引和查询，以及友 好的用户查询界面，但它们也仍有。些不足之处，如： 因为收集的信息庞杂，造成查询返回结果的数量太大，降低了 查询的精确性； 华中师范大学硕士学位沦文 大部分国外的搜索引擎提供都是英文的查询界面，只有少数站 点能够提供中文的查询，这给中国的用户造成很大的不便； 考虑到区域性的问题，有些本来是国内站点上的信息，若通过 国外的搜索引擎来查找会浪费大量的网络资源； 国内的中文搜索引擎虽然近两年的发展速度较快，但由于起步较晚， 再加上中文信息自身具有的特殊问题( 如中文字符的双字节编码机制， 中文句子具有连贯性，难以分词等) ，大部分的中文搜索引擎还不能满足 国内用户的要求。与国外的搜索引擎相比较，它们的性能还有待进一步 的完善和提高，国内现有的搜索引擎一般存在有以下一些问题： 查询结果杂乱无序，不能很好的进行相关性排序； 查询结果中经常出现重复和无效链接的情况； 查询功能比较单一； 国内搜索引擎大部分都局限于特定范围，造成信息的不全面； 有些搜索引擎的查询速度很慢，性能也较差； 鉴于以上搜索引擎中存在的问题，为了充分发挥中文信息资源的作 用，适应中国信息产业的迅猛发展的需要，开发自主、完善、高效的搜 索引擎已经成为当前网上的一个重要课题。本文就借鉴国内外搜索引擎 的开发经验，分析并提出了个对国内w e b 信息进行有效的收集、整理 和查询服务的系统椰w s e 。 1 5 本文的组织 本文的第一章介绍了国内外搜索引擎的发展现状，并对现有的系统 进行了分类讨论，提出了它f 1 的优缺点。第二章提出了w w w s e 设计的总 体目标及现阶段的目标。第三章简要地介绍了w e b 上数据传输的基本原 理。第四章先介绍了搜索引擎的各个模块和相关技术，然后提出了v l 1 】| w s e 的设计原型。最后，第五章中详细地探讨了系统中r o b o t 设计应注意的 问题以及r o b o t 的搜索算法。 华中师范火学坝上学位论文 第二章总体目标及设计思想 w w w s e 系统的设计开发目标是建立一套自动收集、识别并索引 i n t e r n e t 资源的网络信息管理和查嘲系统。它应结合i n t e r n e t 技术与 数据库检索技术，为用户提供技术先进、稳定可靠的开放式i n t e r n e t i n t r a n e t 信息检索服务。 具体来说，系统应具有以下的特点： ( 1 ) 采用机器人自动奄找、发现信息，搜索具有可配置性，沿着 超文本与超媒体链搜索时，采用改进过的宽度优先算法，能 优先访问特定知识领域或特定地域范围内的信息( 如 i n t r a n e t ) ，而不是盲目遍历； ( 2 ) 系统设计时把对相关协议和标准的支持作为一个重要的目 标，重要的标准有：h t m l ，h t t p ，w e br o b o t 协议等。 ( 3 ) 采用b r o s w e r s e r v e r 方式，支持主流浏览器，用户只要用普 通浏览器如n e t s c a p e 或l e 就可以方便地对系统进行检索。 ( 4 ) 支持全文检索； ( 5 ) 支持按词索引策略，能进行汉语的自动分词，这样可缩短系 统的响应时间，提高服务质量； ( 6 ) 采用数据和索引压缩技术，提高系统的查询效率，降低空间 膨胀率： ( 7 ) 提供交互式层次目录和全文检索两种导航方式； ( 8 ) 提供多种查询方式； ( 9 ) 能对检索结果按与检索表达式的相关性和重要性进行排序： ( 1 0 ) 充分利用w e b 文档中的锚链信息，为用户提供更满意的查询 结果； ( 1 1 ) 友好的用户界面，用户可以选择采用不同的方式输出结果( 如 返回结果的数目，是甭显示摘要等) ； 搜索引擎是是一个复杂而庞大的系统，设计一个搜索引擎具有很强 的挑战性。鉴于时间和人力的问题，w w w s e 现阶段的目标是：开发一个 针对w e b 上国内的各中文站点的h t m l 文档进行搜集、索引和查询的系统 原型。 华中师范大学硕士学位论文 3 1 引言 第三章基本技术概述 搜索引擎是一个对网络信息进行收集、索引和查询的工具，而w e b 上h t t p 协议和h t m l 标准又是信息资源交流和发布的基础，所以本文在 讨论搜索引擎的结构之前介绍一下h t t p 协议和h t m l 标准。 3 2t l t t p 协议 h 1 u r p 是一个属于应用层的面向对象的协议，由于其简捷、快速的特 点，它非常适合于分布式超媒体信息系统。它是w e b 上数据传输的标准 协议，通过h t t p 我们可以与w e b 服务器进行信息的交换。h t t p 协议于1 9 9 0 年提出，经过几年的使用与发展，得到了不断地完善和扩展。目前h t t p 1 1 的规范已经出台，而h t t p n g ( n e x tg e n e r a t i o no fh t t p ) 的建议也已经 提出。 h t t p 协议的主要特点可概括如下： ( 1 ) 支持客户服务器模式。 ( 2 ) 简单快速：客户向服务器请求服务时，只需传送请求方法和 路径。由于h t t p 协议简单，使得h t t p 服务器的程序具有规 模小的特点，因而通信速度很快。 ( 3 ) 灵活：h t t p 允许传输任意类型的数据对象。传输的类型由 c o n t e n t t y p e 加以标记。 ( 4 ) 无连接：其含义是限制每次连接只处理一个请求。服务器处 理完客户的请求，并收到客户的应答后，即断开连接。采用 这种方式可以节省传输时间。 ( 5 ) 无状态：h t t p 协议是无状态协议。无状态是指协议对于事务 处理没有记忆能力。缺少状态意味着如果后续处理需要前面 的信息时它必须重传，这样会导致每次连接传送的数据量增 大；但另一方面，当服务器不需要先前信息时它的应答就比 较快。 h t t p 协议是基于请求响应范式的。一个客户机与服务器建立连接 华中师范大学顾士学位论文 后，发送一个请求给服务器，请求格式中包含了统一资源标识符、协议 版本号等内容。服务器接到请求后，给予相应的响应信息，其中包括了 信息的协议版本号、状态码以及服务器信息等内容。请求和响应信息都 是由头和实体两个部分组成，其中头由一个或多个头信息域( 如c o n t e n t t y p e ，d a t e ，i f m o d i f i e d s i n c e 等) 组成，而实体部分则包含了客户 机( 浏览器) 或服务器要发送的信息。 在i n t e r n e t 上，h t t p 通讯通常发生在t c p i p 连接之上。缺省端口 是t c p8 0 ，但其它的端口也是可用的。但这著不预示着h t t p 协议在 i n t e r n e t 或其它网络的其它协议之上才能完成，h t t p 只预示着一个可靠 的传输。 基于h t t p 协议的客户n 务器模式的信息交换过程分四个步骤：建 立连接、发送请求信息、发送响应信息和关闭连接。 在w w w 中，“客户”与“服务器”是一个相对的概念，只存在于一个 特定的连接期间，即在某个连接中的客户在另一个连接中可能作为服务 器。w e b 服务器运行时，一直在t c p s o 端口( w e b 的缺省端口) 监听，等待 连接的出现。 1 建立连接： 连接的建立是通过申请套接字( s o c k e t ) 实现的。客户打开一个套接 字并把它约束在一个端口上，如果成功，就相当于建立了一个虚拟文件。 以后就可以在该虚拟文件上写数据并通过网络向外传送。 2 发送请求： 打开一个连接后，客户机把请求消息送到服务器的停留端口上，完 成提出请求动作。常用的请求方法有g e t 、l l e a d 和p o s t 。 不同的请求对象对应g e t 的结果是不同的：如果请求对象是文件则 返回的是文件的内容，若请求的是程序则返回的是该程序的执行结果， 若请求是数据库查询则返回为查询的结果。一个g e t 请求的例子为： g e th t t p ：w w w c c n u e d u c n i n d e x hl m lh t t p 1 0 与g e t 方式不同，h e a d 方式要求服务器查找某对象的元信息，而不 是对象本身，利用元信息可以实现有条件的请求或应答。p o s t 方式从 客户机向服务器传送数据，在要求服务器和c g i 做进一步处理时会用到 p o s t 方法。p o s t 主要用于发送h t m l 文本中f o r m 的内容，让c b i 程序处 理。 华中师范大学硕士学位论文 3 发送响应 服务器在处理完客户的请求之后，要向客户机发送响应消息。其响 应消息中包含了表示响应类型的状态码： l 保留 2 表示请求成功地接收 3 为完成请求客户需进一步细化请求 4 客户错误 5 服务器错误 状态码反映了请求是成功还是失败，通过这些状态码，客户机可以 了解到请求的执行情况并作出相应的处理。 4 关闭连接 客户和服务器双方都可以通过关闭套接字来结束t c p i p 对话。 3 3 超文本标记语言( 雎札) 和o r l w e b 是目前世界上规模最大的超文档系统，它是一个广泛分布的w e b 页面和页面间的超链构成的巨大的信息网络，w e b 页面的表现形式是用 h t m l 语言或j a v a 语言等编写而成，关键技术就是超文本标志语言。 h t m l 的发展最早应该追溯到1 9 8 6 年国际标准化组织( i s o ) 发布的 为生成标准文档而定义的标准通用标记语言s g m l 。s g m l 定义了许多不同 类型的文档，其中我们最感兴趣的部分是超文本文档( h y p e r t e x t d o c u m e n t ) 。h t m l 定义了超文本文档的s g m l 的子集。具体来说，h t m l 是 一种类似于排版语言的标记语言，是s g m l 的一个应用实例。随着w w w 的发展，h t m l 的重要性和广泛性很快地超过了s g m l 。 超文本标记语言h t m l 是一种简单但功能强大的语言，它是由标记 ( t a g ) 和代码( c o d e ) 所组成”。实际上，h t m l 文件是一种加了额外 标记的文本文件，文件中标记符一般都是成对使用的，每一个标记都是 用尖括号 括起来的a s c i i 字符或字符串。标记的作用是告诉浏览 器各种文字和图象等元素应放在哪罩以及该如何显示。 一份标准的t l t m l 文档有如下的结构： 华中师范大学顾。卜学位论文 ( h t m l ) 文档具体内容； h t m l 中采用了统一资源定位u r l ( u n i f o r mr e s o u r c el o c a t o r ) 来 标志文档的位置。现在几乎所有的i n t e r n e t 文档和服务器都可以用u r l 来表示。一个u r l 被双斜线分成两个部分，前一部分指出访问资源的 类型( f t p 、h t t p 、g o p h e r 等) ，后一部分指明文件或服务所在服务器 的地址及具体存放路径。u r l 通常按以下的方法表示： 资源类型：主机域 ：端l | 路径文件名 客户机和浏览器就是通过向服务器发送一个打开u r l 的请求来建立 与文档和服务器的连接。 华中师范大学硕士学位论文 4 1 引言 第四章系统分析与设计 搜索引擎是一个综合性非常强的系统，其开发涉及到网络、数据库、 信息检索等多种领域方面的技术，由于它的开发具有重大的理论意义和 实际应用价值，许多学校和公司等科研机构已经在各方面进行了广泛的 研究，提出了各种不同的解决方案。但因为大部分的搜索引擎都是出于 商业目的而开发的，现在国内外，特别是国内有关的资料都还不多。本 章就根据对各种网上检索工具进行的初步研究对搜索引擎的主体框架和 一些关键的技术进行了讨论。 由于w e b 上的信息具有分散性、动态性和多样性的特点j ，采用手 工的方式进行信息的搜集和分类已经不符合w e b 实际的发展；而基于机 器人的搜索引擎因为具有获取信息量大、耗费的人力资源小的优势已经 成为现在的主流，所以本文主要讨论的是采用机器人的搜索引擎的关键 技术。 4 2 总体结构 按功能来划分，一个基于机器人的搜索引擎主要由信息采集模块、 信息处理模块、信息检索模块、用户查询接口几部分组成( 如图4 1 ) 。 图4 1 搜索引擎的总体结构 j 华中师范大学顿士学位论文 其中信息采集模块是用来从w e b 上搜集信息：信息处理模块负责将 搜集的信息进行过滤分析、分词处理并建立索引数据库；信息检索模块 则按一定的检索模型为用户提供各种查淘检索 查询检索接口提供给用 户一个查询检索信息的界面。 搜索引擎要提供导航的服务，首先必须从网上搜集信息，建立自己的 索引信息库。所以信息的采集是整个搜索引擎实现的基础。 信息采集主要是由一个叫r o b o t 的机器人来完成的。r o b o t 也叫w e b w a n d e r e r s 、w e bc r a w l e r s 、s c o e t e r 或s p i d e r s ，它实际上是一些专 门设计的程序，程序能以一个或批给定的u r l 为起点，根据一定的策 略跟随着h t m l 文档中的超文本链( a n c h o r ) 递归地穿行于w w w 的信息空 间，获取各站点的网页内容。 4 3 i 数据的收集 r o b o t 的设计需要考虑到诸如搜索原理、搜索策略、搜索效率以及 很多社会性方面的问题。 我们知道w e b 中各站点的数据传输是遵循着h t t p ( h y p e r t e x t t r a n s f e rp r o t o c 0 1 ) 协议进行的，而r o b o t 则可以被看作是一个客户端 的浏览器程序，它按h t t p 协议向指定的服务器发出申请( g e t 、h e a d 等) ， 请求获取有关的数据。服务器在接到请求后根据请求的内容作出答复： 如果访问成功，则返回相应的文档数据，否则返回访问失败的原因。虽 然r o b o t 程序中从网上读取数据的原理比较简单，但一个好的r o b o t 并 不是盲目地穿行于网络空间，其运行的关键还在于采用怎样的策略去智 能地搜索。 w e b 是一个由大量分布广泛的网页和网页间超链构成的信息网络， 如果不考虑w e b 中的环路，我们可以将其看作是一个有向树。要遍历树 中的各站点，原则上r o b o t 可以有两种选择：一种是深度优先( d e p t h f i r s t ) 方式，也就是从某个u r l 开始，r o b o t 跟着网页上的链接逐层向 下，直至树的最底层，然后再回到起u r l ，找出新的链接，出发向下直 到另一个终点，如此不断往返，赢至走完该u r l 下的所有网页。另一种 华中师范大学硕士学位论文 是宽度优先( b r e a d t h f i r s t ) 方式，在这种方式中r o b o t 会先访问高层 所有网页，待这一层的网页都分析过以后，才逐层向下进发。 虽然理论上，两种方式到最后都会走完整个w e b 空间对所有的公共 网页进行索引：但实际上由于信息量的庞大以及网络的复杂结构，r o b o t 不可能对所有站点的信息进行收集。按w e b 文档存放的特点，一个服务 器上越上层的网页所载资料的内容会越为普遍，而越接近底层的网页， 内容越为具体。所以我们可以看到，按深度优先的方式，信息搜集的范 围比较集中深入，但短时间内大量地访问同一站点会给网路和服务器造 成很大的负担。而按宽度优先的方式，r o b o t 可以在一定的时间内访问 到分布范围较广的站点，同时也会减轻带给服务器的压力。通常大部分 的搜索引擎都会选择宽度优先方式以求获得更广泛的信息。由于两种方 式各有利弊，如果将它们结合起来，并采用启发性的知识来限定搜索的 内容和范围的( 如协议、服务器名、目录名、目录深度等) ，则可以实现 各种不同的搜索。 除了上面提到的几个方面，r o b o t 还需要考虑许多社会性的问题， 如遵守“机器人排斥协议”( r o b o te x c l u s i o np r o t o c 0 1 ) ，访问时尽可 能减少对其服务器造成干扰等等，有关的细节在以后的算法设计中再进 行讨论。 4 3 2 数据的更新 动态性是i n t e r n e t 上信息的一个重要特点，它表现在：一方面新的 信息不断的被加入，另一方面已有的信息也在不断地改变移动，甚至被 删除：据统计w e b 上一个文档平均生命周期只有7 5 天m j 。所以虽然现在 i n t e r n e t 上的信息是最容易获得的资源，而动态性又给网络增添了不少 的活力；但是这种特性同时也给使用者带来了很大的不便。例如，用户 在通过已知的u r l 地址查找信息时，由于信息的更改，经常会遇到“4 0 4 d o c u m e n tn o t f o u n d ”的之类的错误提示，这不仅给用户带来烦恼，也 造成了时间的浪费。为了保证获取信息的正确性和及时性，r o b o t 需要 定期地自动检查所有的站点，一旦发现文档已经被更新，就应当重新搜 集数据替换过时的信息；若站点被移动或删除，r o b o t 也要对数据库作 出相应的更改，尽量避免给用户提供错误或无效的地址链接。 数据库中的信息更新一般可采用两种的方法：全体更新和部分更新。 全体更新也就是利用r o b o t 重新上网去发现和收集网页文档的数据。但 因为w e b 上各页面的更新时间不同，全体更新对那些没有变动的页面也 华中师范火学硕士学位论文 重新进行了访问搜索，这样造成了资源的大量浪费。采用部分更新的方 法，我们需要用到h t t p 协泌中的i fm o d j f je d s i n c e 机制。首先，r o b o t 在收集数据的同时需要将已访问过的主页的u r l 和最后修改时间保留下 来。当数据库中的信息已经超过一定的时限，r o b o t 就启动其更新模块 依次取出保留的u r l 和时间信息向服务器发出g e t 请求。服务器根据对 请求消息头中的i f m o d i l i e d s jn c e 域进行检查，判断文档在指定的时 间后是否发生变动，如果文档被修改，服务器爿会将数据返回给r o b o t 。 因为服务器在文档数据被传递之前就对信息进行了检查，避免了大量无 谓的重复传输，所以部分更新的方法既提高了数据更新的速度也减轻了 网路的负担。 4 3 3 执行效率 r o b o t 设计中要重点考虑的另一个问题是程序的效率，高效搜索不 仅可以让搜索引擎在较短的时间内搜集到更多的主页，同时也能更快的 进行数据库的更新。信息收集的瓶颈主要在于等待服务器的响应和网络 的数据传输，为了提高数据收集的速度，很多r o b o t 都采用了多线程技 术，充分地利用网络的带宽并发地去不同的服务器获取；一些大型的搜 索引擎还采用了分布式的采集系统。分布式系统中通常包含了一个专门 的u r l 地址分配模块，它负责协调发放u r l 地址给多个并行的r o b o t ， 每个r o b o t 还可以同时运行多个线程，这种设计能够达到更高的效率， 但同时也给实现提出了更高的要求。 4 4 信息处理模块 对于r o b o t 取回的数据，如果，1 i 进行分析和处理用户是无法对它们 进行查询的。所以搜索引擎f 一步要考虑的问题是如何从文档( 本文只 对h t m l 格式的文档进行讨论) 中抽取文本信息，建立可查询的索引。文 本信息的索引可以有标弓l 索引和全文索引两种方式。因为全文索引能够 提供更确切的检索结果，所以下面我们只针对全文索引的方式进行讨论。 建立w e b 信息的索引数据库是一项困难的工作，它和建立一般的索 引数据库在原理基本上都是相同的，所以信息处理模块的设计和实现需 要涉及到很多信息检索( i n f o r m a t i o nr e t r i e v a l ) 领域的技术。这里将 处理的过程分成三个步骤： 华中师范大学硕上学位论文 4 4 1h t m l 文档的分析和过滤 h t m l 文档是w e b 服务器上最主要的文档格式。对于一般的搜索引擎 而言，它主要的搜索目标是文档中的文本信息，而其中许多标记( 如 、 、 、 、 ) 和代码( 如j a v a s c r i p t ) 对查询并没有多大的意义。所以系统必须对h t m l 文档进行解析，分析识 别其中的各种标记，提取出有用的信息。虽然分析的原理比较简单，但 它的实现却很复杂。首先，h t m l 规范是一个不断变化的标准，系统不仅 要能识别出各种不同含义的标记，进行相应的操作。其次，w e b 上的h t m l 文档一般都具有不规范的特点。据统计，几乎4 0 的w e b 文档都存在至 少一个以上的语法错误；所以为了正确地对文档进行分析，系统必须 能够处理各种可能出现的错误。另外，系统还要将文档中的内容分解成 各种不同领域的信息，如标题，正文等等，以便后面的模块能够提供精 确的查询服务。 4 4 2 分词处理 当原始文档经过的预处理之后，下一步需要建立文本的全文索引。 索引是为实现快速检索而设计的一种机制，它是用户进行查询检索入口。 对于中英文来说，虽然分词的方法和步骤不尽相同，但是它们的目的都 是为了获取最优的索引记录，使用户能够很容易地获取查询信息。 要提取索引词，首先必须从文本的段落和句子中分离出单个的词语。 对于英文信息，由于英文本身词间存在间隔，所以它们的关键词或索引 词的提取都比较明了，不存在分词的问题。 与英文不同，中文信息有着自身的特点：中文的语句是连贯的，词 与词之间没有可以识别的间隔；中文句子中的人名地名也没有明显的标 记，不象英文有大写字母可以区分等等。所以中文索引的提取比较复杂， 现在常用的有按字索引与按词索引两种不同的方式： 所谓按字索引，是将每个汉字当作一个词来处理并建立索引。按字 处理技术的优点在于避开了汉字词义分析和切分的困难，它的查全率较 高，实现相对简单，但其主要缺陷是索引量大，检索需要的时间较长。 按词索引则是以汉字的词而不是字为基本的索引单位，系统必须利 用词典对文本进行自动分词和辨别。词典可以有多种不同的类型如：主 题词典、分词词典、用户自定义词典、禁用词典、同义词典、反义词典、 范围词典等。分词过程中最重要的是分词词典和禁用词典两种。 华中师范大学倾十学位论文 一般来说，因为词索引量比字索引最要少，所以相比之下按词索引 比按字索引占有一定的优势，如： 减少索引需要的空间； 提高了检索的效率； 提高检索的精度，能获得更良好的检索效果； 另外因为语词是信息表达的晟小单位，所以对于中文信息，搜索引 擎一般采用按词索引的方案。 要建立按词的索引，首先要建立分词、禁用词等词典，词典的优劣 会直接影响分词的质量和效率。分词词典由汉语阋条及其属性组成，它 是用于汉语的自动分词。而禁用词词典是由一些没有检索意义的高频词 组成。不论是中文还是英文，信息中都存在有一些没有意义的高频词， 如中文的“关于”、“如果”、“的”，茛文的“a ”、“a n ”、“t h e ”等等。因 为这些词语存在的广泛性，为它们建立索引没有太大的意义，所以系统 需要将它们排除。使用禁用词典不仅可以大大减少数据库的空间膨胀率 还可以提高索引建立和查询检索的速度。 分词过程首先利用禁用词词典匹配出所有的高频词，将段旬划分成 多个短语词段。对剩下的短语词段，系统再利用分词词典进行自动切分。 由于汉语语词切分中存在切分歧异，如句子“中华人民共和国”的正确 切分是“中华人民共和国”，但它f 虹可能被错误地切分为“中华人民 共和国”，因而系统通常需要利用各种上下文知识来解决语词切分歧异。 常用的词语切分方法有诋向最大匹配法( m m ) ，逆向最大匹配法，最佳匹 配法，联想一回朔法，全自动词典切词法等“o 。这些方法还可以结合使 用，以取得更好的切分结果。 汉语自动分词是目i j l 中文信息处理中的难点，如何进行正确的语意 切分还有很多技术方面的问题需要解决，我们在此就不做详细的讨论了。 4 4 3 建立检索项索日 信息的索引就是创建文档信息的特征记录，它使用户能很容易地检 索到所需信息。一般的检索系统都采用到排文件的方式建立索引。倒排 索引( i n v e r t e di n d e x ) 是对文本型字段实现快速检索的一种有效索引方 法。文本中任何有意义的词和字都可以建立索引。 华中师范大学硕上学位论文 4 5 信息查询检索模块 4 5 1 查询检索模型 查询检索主要研究信息的表示、存储、组织和访问，即根据用户的 查询要求，从信息数据库中检索出与之相关的信息资料。根据搜索引擎 查找相关信息方式的不同，可将信息检索分为：布尔逻辑模型、模糊逻 辑模型、向量空间模型等。 布尔型信息检索模型，是最简单的信息检索模型，用户可以根据检 索项在文档中的布尔逻辑关系提交查询，搜索引擎根