（计算机应用技术专业论文）deep+web网络蜘蛛研究与初步设计.pdf

摘要 目前随着i n t e r n e t 信息的爆炸增长，w e b 服务器上数据信息已经被大量可搜索的在 线数据库极大的“深化”，传统搜索引擎已经不能有效检索到隐藏在w e b 服务器后台在 线数据库中的d e e pw e b 信息。如何快速有效获取d e e pw e b 信息正成为搜索引擎研究的 热点和和发展趋势。 本文重点对网络蜘蛛( s p i d e ro rc r a w l e r ) 的研究和改进，以及d e e pw 曲信息提取涉及 到的相关技术和算法问题，设计和实现了一个d e e pw e b 网络蜘蛛。论文的主要工作包 括以下几个方面： 1 分析了传统搜索引擎的设计思想、工作原理和体系结构，从而发现传统搜索引 擎在技术上存在的缺陷、不足之处和可改进的地方。 2 分析了d e e pw e b 信息集成系统的工作原理和体系结构，并简要说明d e e pw e b 信息集成系统工作流程，系统组成模块中各个模块的功能。 3 在以上相关理论和研究结果的基础上，提出了本文中设计d e e pw e b 网络蜘蛛的 思想、体系结构和工作流程。 4 针对网页采集问题，提出有选择的采集网页类型策略和控制重复网页采集策略， 有效地过滤了噪音信息和重复网页抓取问题。 5 针对从静态网页中提取d e e pw e b 数据库查询接口问题，提出通过分析网页构建 网页标记树模型，通过遍历网页标记树来寻找查询接口。提出用对象模型表示( d w i ) 查 询接口和存储表单数据，为后续查询接口合并与分类提供有效的数据表示模型和良好的 存储结构，并给出具体实现算法。 6 针对d e e pw e b 查询接口合并与分类问题，提出通过聚类方法实现对其合并与分 类，并设计和实现了l m a x 算法，使得查询接口分类与合并的准确性有很大的提高。 7 总结了d e e pw e b 网络蜘蛛研究与开发经验，并指出了不足之处以及下一步研究 的重点。 关键词：搜索引擎，d e e pw e b 网络蜘蛛，u r l ，查询接口，表单谓词，l m a x 算法 a b s t r a c t a tp r e s e n t ，w i t ht h eb l u s e l yi n c r e a s i n go ft h ei n t e m e ti n f o r m e n t i o n ，t h ed a t a i n f o r m e n t i o na tt h ew e bs e r v e rh a sb e e ng r e a t l yd e e p e n e db yag r e a td e a lo fs e a r c h a b l eo n - l i n e d a t a b a s e ，m o r e o v e r , t h et r a n d i t i o n a ls e a r c h i n ge n g i n ec a l ln o ts e a r c h e so n - l i n ed e e pw e b i n f o r m e n t i o nh i d e db e h i n dt h ew e bs e r v e re f f i c i e n t l y h o wc a l lw eo b t a i nt h ed e e pw e b i n f o r m e t i o nh a sb e e nah o t s p o ta n dt r e n do ft h es e a r c h i n ge n g i n er e s e a r c h b a s e do nt h er e s e a r c ha n di m p r o v eo ft h ei n t e r n e ts p i d e ro rc r a w l e r , a n dt h et e c h n i q u e a n da r i t h m e t i cr e l a t e dt op i c ku pt h ed e e pw e bi n f o r m e n t i o m ，t h i sp a p e rd e s i g na n dc a r r yo u ta d e e pw e bi n t e r n e ts p i d e ro rc r a w l e r t h ec o n t e n to ft h ep a p e rm a i n l yi n v o l v e st h ef o l l o w i n g s e v e r a la s p e c t s ： 1 v i aa n a l y s et h ed e s i g nt h o u g h ，w o r kp r i n c i p l ea n ds t r u c t u r es y s t e mo ft h et r a n d i t i o n a l s e a r c h i n ge n g i n e ，t h ea u t h o rf o u n dt h el i m i t a t i o no ft h et r a n d i t i o n a ls e a r c h i n ge n g i n e ，a n d a l s o t h ea u 山o rf o u n dt h es o l u t i o n 2 v i aa n a l y s et h ew o r kp r i n c i p l ea n dt h es t r u c t u r es y s t e mo ft h ed e e pw e bi n f o r m e n t i o n i n t e g r a t i o ns y s t e m ，t h ea u t h o re x p l a i nt h ew o k l i n eo ft h ed e e pw e bi n f o r m e n t i o ni n t e g r a t i o n s y s t e m ，a n dt h ef u n c t i o no fe a c hs e c t i o no f t h ew h o l e 3 b a s e do nt h ea b o v et h e o r ya n ds t u d y , t h ea u t h o rp u tf o r w a r dt h et h o u g h t ，s t r u c t u r e s y s t e ma n d w o r kl i n eo ft h ed e e pw e bi n t e r n e ts p i d e ro rc r a w l e r 4 f o rt h ep a g ec o l l e c t i o n ，t h ea u t h o rp u tf o r w a r dt h ep a g ec o l l e c t i o ns e l e c t i v e l ys t r a t e g y a n dt h es t r a t e g yo fc o n t r a lt h er e p e t i t i o n a lp a g ec o l l e c t i o n ，s ot h a tw ec a nf i l t r a t et h en o i s e i n f o r m e n t i o na n dr e p e a t e dp a g ec o l l e c t i o ne f f e c t i v e l y 5 a sr e s p e c tt ot h ep r o b l e mt h a te x t r a c t i v i n gd e e pw e bd a t a b a s eq u r yi n t e r f a c ef r o mt h e s t a t i cp a g e ，t h ea u t h o rp u tf o r w a r dt h es o l u t i o nt h a ts t r u c t u r i n gt a g t r e e - b a s e dm o d e lv i a a n a l y s et h ep a g es t r u c t u r e ，s e a r c h i n gq u e r yi n t e r f a c ev i at r e v a l st a g t r e e - b a s e dm o d e l ， e x p r e s s i n gt h eq u e r yi n t e r f a c ea n ds t o r a g et a b l ed a t av i ad w i ，s ot h a to f f e rv a l i dd a t a s h e e t a n dp e r f e c ts t o r a g es t r u c t u r ef o rc o m b i n a t i o na n dc l a s s i f i c a t i o no ft h eq e u r yi n t e r f a c e a f t e r w o r d s ，a n da l s og i v et h ep r a c t i c a la r i t h m e t i c 6 f o rt h ec o m b i t i o na n dc l a s s i f i c a t i o no fd e e pw e bq e u r yi n t e r f a c ei s s u r e ，t h ea u t h o ro u t f o r w a r dt h ew a yt h a tc o m b i n a t ea n dc l a s s i f yi tv i at h em e t h o do fc l u s t e r i n g ，m o r e o v e rt h e a u t h o ra l s od e s i g na n dc a l t yo u tl m a xa r i t h m e t i c ，s ot h a tv e r a c i t yo ft h ec o m b i t i o na n d c l a s s i f i c a t i o nc a nb ei m p r o v e dg r e a t l y 7 v i ac o n c l u d et h er e s e a r c ha n dt h e e x p l o i t u r ee x p e r i e n c eo fd e e pw e bi n t e r n e ts p i d e ro r c r a w l e r , t h ea u t h o rg i v eo u tt h el i m i t i t i o na n d m a i np o i n tf o rf u r t h e rr e s e a r c h k e yw o r d s ：s e a r c h i n ge n g i n e ；d e e p w e bi n t e m e t s p i d e r ；u r l ；q e u r yi n t e r f a c e ；f o r m p r e d i c a t i o n ；l m a xa r i t h m e t i c 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究工 作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何 未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 敝作者虢协卜限 易年月日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 协卜胂 导师签名：鲥 2 。咯年6 月日 i 2 。u 妒年月3 日 长安人学硕士学位论文 第一章绪论 1 1 问题的提出 1 1 1i n t e r n e t 信息组织结构 今天，我们处在信息时代，获取信息大部分的途径是通过访问互联网络而实现。随 着互联网络技术的不断发展和互联网不断的普及应用，i n t e r n e t 上信息量不仅成指数级 的增长，同时信息的组织方式也发生了根本性的变化。最初i n t e r n e t 上w e b 服务器信 息大部分是由静态网页组成，随着网络技术的发展，w e b 服务器上出现了动态网页，而 且现在逐步成为网站信息重要组成部分。静态网页是指网页文件中没有程序代码，网页 内容使用h t m l 语言，不需要在服务器端执行的网页，且网页文件一般以h t m l 或h t m 为后缀存放。其特点是： ( 1 ) 静态网页中每个网页都有一个固定的u r l 指向其在w e b 服务器上的访问路径， 且网页u r l 以h t m 、h t m l 、s h t m l 等常见形式为后缀。 ( 2 ) 网页内容一经发布到网站服务器上，无论是否有用户访问，每个静态网页的内 容都是保存在网站服务器上的。 ( 3 ) 静态网页的内容相对稳定，制作完成后内容不会改变，因此容易被搜索引擎检 索。 ( 4 ) 静态网页的内容一般直接嵌在h t m l 语言中，没有形成数据和表现形式的分离， 如果要改变网页显示内容，就必须修改源代码，然后重新上传到服务器，在网站制作和 维护方面工作量较大，因此当网站信息量很大时完全依靠静态网页制作方式比较困难。 ( 5 ) 静态网页的交互性交叉，在功能方面有较大的限制。 ( 6 ) 用户浏览静态网页时，网站服务器不会执行任何程序就直接将静态网页内容传 输给客户端的浏览器解读。 对于静态网页，由于其都有固定的u r l ，传统的搜索引擎用其网络爬虫( c r a w l e r ) 按照某种控制策略，沿着w e b 页面的超链接能够下载其w e b 页面集合，因此，这类网页 可以被搜索引擎搜索像百度、g o o g l e 等检索到，我们称之为表层网络( s u r f a c ew e b ) 。 动态网页是相对静态网页而言的，它是指网页文件中不仅包含有h t m l 标记，而且 含有程序代码，需要被服务器端执行的网页，其特点是： ( 1 ) 动态网页以数据库技术为基础，实现了数据和表现形式的分离，可以大大降低 网站维护的工作量。 第一章绪论 ( 2 ) 采用动态网页技术的网站可以实现更多的功能，如用户注册、用户登录、在线 调查、用户管理、订单管理等等。 ( 3 ) 动态网页实际上并不是独立存在于服务器上的网页文件，只有当用户请求时， 先由服务器执行相关程序后，然后将不同的执行程序结果实时动态地返回给客户端浏览 器。 ( 4 ) 动态网页中的“? ”对搜索引擎检索存在一定的问题，搜索引擎一般不可能从一 个网站的数据库中访问全部网页，或者出于技术方面的考虑，搜索蜘蛛不去抓取网址中 “? 后面的内容，因此采用动态网页的网站在进行搜索引擎推广时需要做一定的技术 处理才能适应搜索引擎的要求。 动态网页中许多内容是存贮在后台数据库中，只有用户实时的通过填写前台表单页 面信息后提交给后台数据库才动态的产生页面信息，其没有固定的u r l 与其对应，所以 传统的搜索引擎是无法发现和检索到此类网页信息，我们称这类网络信息为深层网络 ( d e e pw e b ) 。 1 1 2d e e pw e b 概念 整个w e b 看似杂乱无章，但如果按其所蕴涵信息的“深度 可以划分为s u r f a c ew e b 和d e e pw e b 两大部分。s u r f a c ew e b 是指通过超链接可以被传统搜索引擎索引到的页面 的集合，在现实中，有大约2 1 3 的页面由于缺乏被指向的超链接而没有被搜索引擎索引 到，我们把这一部分页面也看作是s u r f a c ew e b 的范畴，其信息量只占到整个w e b 服务器 上很小的一部分，好多信息是重复或无用的，在信息时代称其为“噪音信息”。而对于 用户来说，d e e pw e b 蕴藏了大量高质量和有用的信息，此概念最初由d r j i l le l l s w o r t h 于1 9 9 4 年提出，指那些由普通搜索引擎难以发现其信息内容的w e b 页面。2 0 0 1 年c h r i s t s h e r m a n 署o g a r yp r i c e 对d e e pw e b 定义为：虽然通过互联网可以获取，但普通搜索引擎由 于受技术限制而不能或不作索引的那些文本页、文件或其他通常是高质量、权威的信息 乜引。举个最简单的例子：用户想知道长安大学图书馆是否收藏了j a v a 编程思想这本 书，这时候如果通过传统搜索引擎检索，一般来说无法直接找到答案。而利用长安大学 图书馆的联机公共目录查询系统则可快速获得所需信息。联机公共目录查询系统就是 d e e pw e b 信息检索的一种。d e e pw e b 是由许多w e b 数据库组成，其内容隐藏在w e b 后台数 据库中，用户只有通过数据库各自的查询接口来访问其内容。d e e pw e b 信息主要包括： ( 1 ) 不透明网络( t h eo p a q u ew e b ) 或灰色网络( t h eg r e yw e b ) 不透明网络是指搜索引擎可以索引但没有索引的网页，主要是由于经济因素制约和 2 长安大学硕士学位论文 搜索频率的限制。 ( 2 ) 私人网络( t h ep r i v a t ew e b ) 私人网络就是指含有个人的非公开信息、限制访问的网页，主要是指需要输入网站 用户名和密码才能登录访问的网页或通过使用“r o b o t s t x t ”协议来阻止s p i d e r 爬行 的网页。 ( 3 ) 专有网络( t h ep r o p r ie t a r yw e b ) 专有网络是指只对注册用户( 免费注册用户和收费注册用户) 开放的网页，这部分网 页都需要用户输入用户名和密码，其资源才可被利用。 ( 4 ) 真正的深层网络( c o m p l e t e l yd e e pw e b ) 真正的隐蔽网络主要包括习f h t m l 格式的文档、动态网页、实时数据及网络数据库。 1 1 3d e e pw e b 研究目的与意义 迅速增长的网络信息资源成为一个巨大的信息宝藏。面对这些海量信息，人们一开 始感到惊喜万分，以为可以随心所欲地获取自己想要的一切信息，然而在网络信息资源 的利用过程中，人们发现对如此庞大的信息库进行存取和利用并非易事，在某些情况下 甚至步履维艰。当人们满怀信心地利用一些通用搜索工具在网上搜索资料时，所得到的 往往是大量风马牛不相及的无关信息。尽管不断地变换检索关键词，但检索结果却没有 太大的改善，有时根本就找不到所需资料。出现这种情况的原因是检索者没有意识到通 用搜索引擎的局限性，以为几个通用搜索引擎就可以解决检索中的一切问题。实际上， 通用搜索引擎搜索到的只是整个网络资源中的一小部分，大部分更有价值的，专业性强 的数据资源潜藏在d e e pw e b 中，必须采取特殊的策略和工具才能找到它们。u i u c 大学 h 1 在2 0 0 4 年4 月对整个d e e pw e b 做了一次较为准确的估算一，推测整个w e b 上有3 0 7 0 0 0 个提供w e b 数据库的网站、4 5 0 0 0 0 个w e b 数据库，比b r i g h t p l a n e t 晦1 在2 0 0 0 年估计的 5 0 0 0 0 0 个数据库网站的数目增长了6 倍多。根据近年来研究调查n 6 l ： ( 1 ) d e e pw e b 页面信息大约是表面页面信息的5 0 0 倍，其大约有3 0 7 ，0 0 0 个站点， 4 5 0 ，0 0 0 个后台数据库和1 ，2 5 8 ，o o o 个查询接口。它仍在迅速增长，从2 0 0 0 年到 2 0 0 4 年，它增长了3 7 倍。 ( 2 ) d e e pw e b 内容分布于多种不同的主题领域，尽管电子商务是其主要的驱动力量， w e b 数据库的发展趋势不仅在此领域，而在非商业领域相对占更大比重。 ( 3 ) 大约一半d e e pw e b 资源存在于各种主体明确的网络数据库中，其中结构化的是 非结构化的3 4 倍之多。 第一章绪论 ( 4 ) d e e pw e b 中的后台数据库大多是结构化的，其中结构化的是非结构化的3 4 倍之多。 ( 5 ) w e b 数据库查询接口往往位于站点浅层，9 4 之多的大量w e b 数据库查询接口 可以在站点前3 层发现。 ( 6 ) 对d e e pw e b 数据的访问量比s u r f a c ew e b 要高出5 0 。 ( 7 ) 超过5 0 的d e e pw e b 的内容是特定于某个领域的，即面向某个领域，内容更精确。 ( 8 ) d e e pw e b 上9 5 的信息是可以公开访问的，即免费获取。 d e e pw e b 信息量要比静态页面信息量多的多，同时由于d e e pw e b 页面信息是由 后台数据库动态产生的，数据库多是结构化的关系数据库，因此d e e pw e b 页面信息的 质量要比非结构化的页面要高，主题更专一，内容更丰富。如何有效快捷地从d e e pw e b 中找到用户查询的信息，传统的搜索引擎是无能为力，通过用d e e pw e b 网络蜘蛛对d e e p w e b 信息资源进行搜集整理，最后为用户提供某一领域的统一查询接口，使用户能够更 快更准确地从w e b 服务器上找的所需信息。同时对d e e pw e b 信息的搜索研究将是各大 搜索引擎公司将来研究的重点，有利于提高搜寻引擎的查找速度和精确度，提高用户使 用满意度。 1 2 d e e pw e b 国内外研究与发展现状 1 国外d e e pw e b 信息资源研究现状 1 9 9 4 年，d r j i l le 1 i s w o r t h 在互联网领域首次提到了不可见网络一词。但是真 正的d e e pw e b 研究起始于1 9 9 8 年，当时两位美国信息管理专家l a w r e n c e 和g i l e s 提出网络信息利用率问题，意识到通用搜索引擎的低覆盖率，鉴于网络信息资源没有 得到充分的开发和利用，他们提出了开发d e e pw e b 信息资源的想法。在国外，从d e e pw e b 的提出到现在已经有几年的研究历史，出版了大量专著和学术论文。a r t i c l e f i r s t 、e c o 、 w i i s o n s e l e c t p l u s 三大外文数据库中查到1 1 5 篇有关论文，可见国外这方面的研究已 经非常深入。目前，国外d e e pw e b 的研究已经成为信息检索领域的一个研究热点，出 现了大量关于d e e pw e b 资源搜索的网站，像c o m p l e t e p l a n e t c o m 和i n v i s i b l e w e b n e t 网站，对一些专业的w e b 数据库都已按领域作了分类。同时对d e e pw e b 信息集成系统 中的数据库发现，数据库查询接口抽取、聚类、表单自动填充及数据源自动选择等都有 深入的理论研究，但是完全意义上的d e e pw e b 信息集成系统产品还在实验阶段，还没 有真正的投入市场应用。 2 国内d e e pw e b 信息资源研究现状 4 长安大学硕士学位论文 互联网从上个世纪末才传入我国，虽然在短短的时间之内获得了飞速发展，但是毕 竟发展时间太短，人们对网络的研究并不深入。而d e e pw e b 是随着网络的快速发展出 现的，因此绝大多数网络用户对d e e pw e b 的概念还很陌生，相关论述较少，其中有关 的论述都是综述性的介绍国外d e e pw e b 研究状况。随着w e b 上信息资源的不断被“深 化”，国内的学者也开展关注和研究d e e p w e b 信息。国内中国人民大学的孟小峰教授走 在d e e pw e b 信息研究前端，对d e e pw e b 信息集成有比较深入的研究，同时国内的软 件学报在2 0 0 8 年开始开设了d e e pw e b 信息集成论文专刊，收录了国内9 篇具有代表 性的有关d e e pw e b 信息集成的论文。同时为数不多的大学对d e e pw e b 的研究也是在消 化国外相关技术和理论的基础上，开始关注并着手d e e pw e b 的研究。随着w e b 服务器 上的信息每年以指数级递增，越来越多的信息要求用户处理，如何从信息资源大海中找 到准确有用的信息，将是我们每个人要面对的问题，d e e pw e b 信息集成将是各大搜索引 擎公司今后研究的重点，这也是今后一段时间信息检索研究的重点和热点。 1 3 论文研究内容 本论文研究重点是通过对传统的网络蜘蛛( s p i d e ro rc r a w l e r ) 的研究和改进，以 及d e e pw e b 信息提取涉及到的相关技术和算法问题，是其尽可能抓取d e e pw e b 中的信 息。本文研究的具体重点为： ( 1 ) 研究网络蜘蛛的工作原理和体系结构，完成d e e pw e b 网络蜘蛛的设计与实现，用 其抓取网页为课题提供实验数据。 ( 2 ) 研究如何对静态网页中查询接口( 表单) 抽取、表单过滤、表单元素抽取以 及对查询接口元素数学建模表示与存贮。 ( 3 ) 对抽取的d e e pw e b 数据库查询接口d w i 对象根据其属性特征实现查询 接口进行聚类，通过聚类思想设计和实现l m a x 算法，实现查询接口的分类与合并。 ( 4 ) 分析在实际设计和编程实现d e e pw e b 网络蜘蛛过程中遇到的问题，并 探讨解决问题的方法。 1 4 论文结构 第l 章引出要研究的问题，介绍本文的研究背景和意义，包括本文研究的基础以 及要研究的主要内容。 第2 章首先概述了传统搜索引擎的发展历史、工作原理、体系结构以及其面临的 挑战，继而引出了d e e pw e b 信息集成系统，并对d e e pw e b 不可见的原因进行分析，然 第一章绪论 后分析了d e e pw e b 信息集成系统的工作原理和其体系结构，最后分析了d e e pw e b 信 息集成系统和传统搜索引擎的区别。 第3 章首先分析了d e e pw e b 网络蜘蛛要完成的任务，接着提出本文设计d e e pw e b 网络蜘蛛的工作流程、具体实现体系结构和d e e pw e b 运行控制界面设计，最后说明了 系统开发的软硬件环境。 第4 章介绍了w e b 服务器扫描模块设计实现。它首先详细阐述w e b 服务器扫描模 块的体系结构、具体工作流程和本模块中数据存储结构设计，接着提出w e b 服务器扫描 模块设计中考虑到的各种具体问题和针对各个问题的具体解决策略与具体实现过程，最 后给出用w e b 服务器扫描模块抓取网页实验数据来验证设计其是否达到预期目标要求。 第5 章介绍d e e pw e b 查询接口抽取与预处理，它首先阐述查询接口抽取的作用与 困难、目前研究现状，接着分析静态网页中表单结构和元素，在此基础上给出查询接口 的表示模型d w i 对象，并通过实例表单接口说明接口表示模型；同时提出用网页标记树 模型表示网页结构，通过对网页标记树分析来提取表单信息，给出表单接口抽取思想与 具体实现算法，最后详细说明d e e pw e b 查询接口抽取与预处理模块的具体设计与实现， 同时通过对实例表单抽取来验证设计的有效性。 第6 章分析了d e e pw e b 查询接口分类与合并，对d e ew e b 查询接口分类与合并实 质上是对w e b 后台数据库的分类，w e b 数据库分类从形式上分为两种类型一指导方式和 非指导方式。本文通过聚类思想设计和实现l m a x 算法来对d e e p w e b 数据库分类，依据 d e e pw e b 查询接口的分类，阐述了基于查询接口特征的数据源聚类算法，属于指导方 式分类方法中的一种。最后给出实验数据验证l m a x 算法对查询接口分类效果。 第7 章对论文所做的工作进行了总结，并对还需要进一步解决的问题进行了讨论 和展望。 6 长安人学硕：l 学位论文 第二章传统搜索引擎与d e e pw e b 信息集成系统概述 2 1 搜索引擎简介 在互联网发展的最初阶段，w w w 服务器上的网页数量相对比较小，信息查找比较容 易。随着互联网的迅猛发展，网络信息的膨胀速度呈指数急速增长，用户很难找到所需 的资料，即使能够找到所需的信息，也要浪费用户好多的时间。i n t e r n e t 上拥有极其丰 富的信息资源，如何方便、准确而且快速地从i n t e r n e t 上找到并获取所需的信息，是 一件非常困难的工作。针对这种情况，研究人员不断提出各种解决方法。最早在上世纪 八十年代，出现了目录服务x 5 0 0 、f t p 文档地址检索系统a r c h i v e 、菜单式信息检索系 统g o p h e r 、广域信息服务系统w a i s ( w i d ea r e ai n f o r m a t i o ns e r v i c e s ) 等工具：到了上 世纪九十年代中期，随着w w w 的兴起产生了w e b 的搜索问题，于是又出现了基于w w w 的 搜索引擎。经过十几年的发展，现在许多大的搜索引擎站点已经成为用户进入i n t e r n e t 的第一步，成为人们检索w e b 信息最常用的一种手段口刚，短短的十多年年时间，搜索引 擎已经经历了萌芽、产生、发展和繁荣几个阶段，在这期间，同时也产生了像百度、g o o g l e 等著名的搜索引擎。同时，随着w w w 服务器上信息组织结构的变化，其构成不单纯是静 态网页，好多信息是隐藏在后台结构化数据库中，这部分信息对传统的搜索引擎来说是 无能为力的，这就产生了对隐藏在后台数据库中d e e pw e b 信息搜索的d e e pw e b 信息集 成。 搜索引擎是为解决网络信息获取难得的问题而发展起来的一种信息检索工具阳1 。它 是一种在w e b 上应用的软件系统，它以一定的策略在w e b 上搜集和发现信息，在对信息 进行处理和组织后，为用户提供w e b 信息查询服务。从使用者的角度看，这种软件系统 提供一个网页界面，让他通过浏览器提交一个词语或短语，然后很快返回一个可能和用 户输入内容相关的信息列表，这个列表的每一条目代表一篇网页，每个条码至少包括三 个元素：( 1 ) 标题：以某种方式得到的网页内容的标题。( 2 ) u r l = 该网页对应的“访问 地址 。( 3 ) 摘要：以某种方式得到的网页内容的摘要n 0 1 。 作为对搜索引擎的基本了解，这里有两个问题需要首先澄清。第一，当用户提交查 询的时候，搜索引擎并不是即刻在w e b 上“搜索 一通，发现那些相关的网页，形成列 表呈现给用户；而是事先已“搜索“了一批网页，以某种方式存放在系统中，此时的搜 索只是在系统内部进行而已。第二，当用户感到返回结果列表中的某一项很可能是他需 要的，从而点击u r l ，获得网页全文的时候，他此时访问的则是网页的原始出处。于是， 7 第二章传统搜索引擎jd c c pw e b 信息集成系统概述 从理论上讲搜索引擎并不能保证用户在返回结果列表上看到的标题和摘要内容与他点 击u r l 所看到的内容一致，甚至不能保证那个网页还是否存在。这也是搜索引擎和传统 信息检索系统的个重要区别。这种区别源于w e b 信息的基本特征。为了弥补这个差别， 现代搜索引擎都保存网页搜集过程中得到的网页全文，并在返回结果列表中提供”网页 快照”或”历史网页 链接，保证让用户能看到和摘要信息一致的内容。 2 2 搜索引擎的发展历史与现状 2 2 1 传统搜索引擎的发展历史与现状 现代意义上的搜索引擎的祖先，是1 9 9 0 年由蒙特利尔大学学生a l a ne m t a g e 发明 的h 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 。 h 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 年开发了另一 个与之非常相似的搜索工具，不过此时的搜索工具除了索引文件外，已能检索网页。 当时，“机器人 一词在编程者中十分流行。电脑“机器人”( c o m p u t e rr 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 年1 0 月创建了a l i w e b ，它是a 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 p s t a t i o n 、t h ew o r l dw i d ew e b w o r m ( g o t o 的前身，也就是今天o v e r t u r e ) ，和r e p o s it o r y b a s e ds o f t w a r ee n g i n e e r i n g 8 长安大学硕上学位论文 ( r b s e ) s p i d e r 最负盛名。然而j u m p s t a t i o n 和w w ww o r m 只是以搜索工具在数据库中找 到匹配信息的先后次序排列搜索结果，因此毫无信息关联度可言。而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 n l 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 i o 和美籍华人杨致远( g e r r yy a n g ) 共同创办了超级日录索引y a h o o ，并成功地使搜索引擎的概念深入人心。从此搜索引擎 进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已达数百家，其检索的信息 量也与从前不可同日而语。比如最近风头正劲的g o o g l e ，其数据库中存放的网页已达 3 0 亿之巨! 随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗已无法适应目前的市 场状况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的搜索引擎技术和搜 索数据库服务提供商。象国外的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 等在内的其他搜索引擎提供全文网页搜索服务。国内的百度也属于这一类，百度已于 2 0 0 1 年9 月开始提供公共搜索服务，搜狐和新浪用的就是它的技术，搜狐二级网页搜索 现己改为中搜的引擎，而新浪则已转用g o o g l e 的搜索结果。因此从这个意义上说，它 们是搜索引擎的搜索引擎。 2 2 2 d e e pw e b 信息集成系统发展历史和现状 目前国内外对d e e pw e b 信息集成技术的研究主要集中在对后台数据库的访问，通 过对静态网页进行分析提取表单信息，自动填充提取的表单并提交表单来实现对对动态 网页中存贮数据的后台数据库的访问。 就国外而言，最著名有h i d d e nw e be x p o s e r ( h i w e ) n 1 1 这是斯坦福大学研究的一个 项目，设计了一种可以抽取d e e pw e b 内容的c r a w l e r 。在此系统中c r a w l e r 管理器负责 管理静态网页和d e e pw e b 信息的搜集过程。它首先下载w e b 静态网页，然后对下载的 w e b 静态页面进行分析，把包含表单的页面被送到表单处理器中专门处理。表单处理器 先从页面中抽取出表单，再从预先准备好的数据集中选择数据自动地完成表单的填写， 然后将合成的u r l 提交c r a w l e r 管理器去下载相应的结果页面。由于需要系统自动完成 表单填写，所以要求用户事先准备相应的表单数据集。h i w e 只能面向特定的领域使用， 而且必须在人工帮助下完成。另外，哥伦比亚大学的p a n a g i o t i sg i p e i r o t i s 等人在 9 第二章传统搜索引擎与d e e pw e b 信息集成系统概述 文章中n 2 1 讨论了自动地将w e b 网页所连接的后台数据库进行分类的方法。它首先使用机 器学习技术生成一套基于规则的分类器( c l a s s i f i e r ) 。然后将分类器转变成查询u r l ， 对后台数据库进行查询，计算查询结果。他们的算法最后根据查询结果对数据库进行分 类，但只针对文本数据库的分类上面。现在d e e pw e b 信息集成的研究是在理论和实验 阶段，真正像传统搜索引擎g o o g l e ，百度投入市场运作的成熟产品还没有。 就国内而言，目前国内对d e e pw e b 方面的研究尚处于学习、跟踪和探索阶段。国 内研究单位及相关文献非常少，也是在消化国外相关技术和理论的基础上进行初步的研 究。上海交通大学宋晖等n 3 3 人提出基于标记树的对象抽取( t a g t r e e b a s e do b j e c t e x t r a c t i o n ) 方法自动地从w e b 页面中抽取d e e pw e b 信息，然后在此基础上给出了结构 化的d e e pw e b 信息查询算法。另外苏州大学的郑冬冬，赵朋朋等人也对d e e pw e b 的访 问进行了相关的研究，在“爬虫研究与设计b 1 一文中提出使用启发式规则集和领域本 体知识库来自动发现相关表单，填写表单，同时识别和收集相关结果页面。中国人民大 学的孟小峰教授走在d e e pw e b 信息研究前端，对d e e pw e b 信息集成有比较深入的研究， 同时国内的软件学报在2 0 0 8 年开始开设了d e e p w e b 信息集成专刊，收录了国内9 篇具有代表性的有关d e e pw e b 信息集成的论文。 2 3 传统搜索引擎的工作原理与体系结构 2 3 1 传统搜索引擎的工作原理 搜索引擎一般的工作过程是：首先对互联网上的网页进行搜集，然后对搜集来的网 页进行预处理，建立网页索引库，实时响应用户的查询请求，并对查找到的结果按某种 规则进行排序后返回给用户。搜索引擎是一个网络应用软件系统，在处理用户请求时， 并不实时地在搜索互联网，它实际上搜索预先整理好的网页索引数据库。搜索引擎同时 也不能真正理解网页上的内容，它只是机械的通过文字配匹规则来配匹网页上的文字。 现在大规模高质量的搜索引擎，通常是收集了互联网上几千万到上百亿个网页并对网页 中的每一个文字进行索引，建立索引数据库来满足大量用户查询需求。当用户查找某个 关键词的时候，所有在页面中包含了该关键词的网页作为索引结果被搜出，经过复杂的 算法排序后，这些结果将按照与搜索关键词的相关度高低，依次排列显示给用户。搜索 引擎一般采用如图2 1 所示的称之为三段式的工作流程，即：网页搜集、预处理和查询 服务。 1 0 长安大学硕1 ：学位论文 图2 1 搜索引擎三段式工作流程 搜索引擎服务的基础应该是有一批预先搜集好的网页，因此它首要的任务是首先从 w e b 上抓取原始网页。网页搜集就是负责从w w w 服务器上自动发现、抓取网页存贮到本 地机器上。在网页搜集过程中，因为面对的w e b 服务器上海量网页信息，并且网页信息 是在变化的，不是永远不变的，因此存在如何有效维护网页数据库信息，通常采用两种 方式：定期搜索和