（管理科学与工程专业论文）deep+web搜索引擎的关键技术.pdf

d e e pw e b 搜索引擎的关键技术 摘要 d e e pw e b 中包含着数量巨大、质量很高的信息，却不能被通用搜索引擎搜 索。研究d e e p w e b 搜索引擎及其关键技术将有助于实现对d e e p w 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 pw e b ：数据库发现；数据库选择：w e b 信息拙取；结果聚合 t h e k e yt e c h n i q u e so fd e e pw e b s e a r c h e n g i n e a b s t r a c t t h e r ea r eg r e a ta m o u n t so fv a l u a b l ei n f o r m a t i o ni nt h ed e e pw e b ，w h i c hc a n tb e s e a r c h e db yg e n e r a ls e a r c he n g i n e s r e s e a r c ho nd e e pw e bs e a r c he n g i n ea n di t s k e yt e c h n i q u e sw i l lb eu s e f u lt or e a l i z es e a r c h i n gd e e pw e ba u t o m a t i c a l l y f i r s t l y ，i n t r o d u c et h eg e n e r a lp r i n c i p l eo fg e n e r a ls e a r c he n g i n e t h e ng i v et h e s u m m a r yo fd e e pw e b d i s c u s st h ed e f i n i t i o na n dt y p e so fd e e pw e b ，a n da n a l y z e t h es u r v e yo fd e e pw e bq u a n t i f i c a t i o n a l l y a f t e rt h a t ，d e s i g nt h em o d e lo fd e e p w e bs e a r c he n g i n ea n dg i v ei t sd e f i n i t i o n ，a n dp o i n to u ti t s4 k e yt e c h n i q u e sa s a u t o m a t i c a l l y d a t a b a s e s d i s c o v e r i n g ，a u t o m a t i c a l l y d a t a b a s e s s e l e c t i n g ， a u t o m a t i c a l l ys e a r c hr e s u l t se x t r a c t i n g ，a n dr e s u l t sa g g r e g a t i o n t h e nd i s c u s st h e s e4k e yt e c h n i q u e si nd e t a i l p r e s e n tan e wm e t h o df o rd i s c o v e r i n g d a t a b a s ei nt h en e tb a s e do nw e bs p i d e r ，a n de x p e r i m e n t ss h o wt h a tt h i sm e t h o di s e f f e c t i v e s u m m a r i z ed i f f e r e n tm e t h o d sf o rd a t a b a s es e l e c t i n g ，a n db a s e do nt h e s e ， d e s i g nan e wm e t h o dt os e l e c td a t a b a s e sa u t o m a t i c a l l y p r e s e n tan e wm e t h o df o r a u t o m a t i c a l l ye x t r a c t i n gs e a r c hr e s u l tr e c o r d s ，a n de x p e r i m e n t ss h o wt h a tt h i s m e t h o di ss i m p l ea n de f f i c i e n t a n a l y z et h eq u e s t i o no fr e s u l t sa g g r e g a t i o ni n t o3 c h i l dq u e s t i o n s ，t h e nd i s c u s st h e m ，a n dg i v et h es u m m a r yo ft h e m k e y w o r d s ：d e e pw e b ；d a t a b a s e sd i s c o v e r i n g ；d a t a b a s e ss e l e c t i n g ； w e bi n f o r m a t i o ne x t r a c t i o n ；r e s u l t sa g g r e g a t i o n i i 图2 - 1 图3 - 1 倒4 - 1 表4 - l 图6 一l 图6 - 2 图6 - 3 图 圈 搜索引擎结构图 图表清单 d e e p w e b 搜索引擎框架图 s d b 搜索界面 实验数据 s r 鼬。 s r p l s 标签张 s r r s 抽取试验结果图 s r p l s 抽取试验结果图。 v i 4 l l 1 4 1 7 ” 2 7 3 0 3 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 姐除了文中特* n 加以标泣那致谢的地方外，论文中不包古其他人已经发表或撰写过的研究成果， 也1 i 包含为获得 金目b 工些太堂 或其他教育机构的学位或证书而使用过的村料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学一一蕊导期：哆阳多日 学位论文版权使用授权书 本学位论文作者完全r 解盒胆些盍堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复日 件和磁盘，允许论文被查阅和借阅。本人授权金月b 工些盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者鉴名 蔼争 签字日期：沙夕年月i ；日 学位论文作者毕业后古向： 工作单位：二伙。乡 通讯地址： 导师签名： ( 蜩己 签字日期：c 弘夕年月吗日 电话 邮编 致谢 值此论文完成之际心中既有研究成果面世的快乐，更有满满的感激之情， 感激那么多在论文研究和写作过程中给予我诸多帮助的人们。 首先要感谢的是任明仑导师。任老师学识渊博，治学严谨。每每解答我们 提出的问题时，都旁征博引、循循善诱。任老师不仅在学术方向上给我以启发， 更在论文的研究、写作过程中给予了许多具体的指导和指正。 感谢合肥工业大学计算机网络所的杨善林老师，杨老师强烈的事业心、严 谨的治学精神和开放的胸怀都给我们深深的影响。感谢网络所的马溪骏老师、 左春荣老师，在日常的学习研究过程以及论文的修改、完善等方面，她们都给 予了我许多帮助。感谢管理学院4 0 1 室各位老师给予的帮忙和言行激励，感谢 张述初老师提出的宝贵的修改意见。 感谢网络所的同学，感谢管理学院4 0 3 室朝夕相处的学友，他们的研究热 情和活跃的思维在不断启发和激励着我。 感谢二炮驻校选培办的主任、参谋、干事，他们提供了一个宽松的环境， 鼓励我安心摘科研，并多次询问、关心研究的进展情况。 感澍论文评审专家在白忙之中抽出宝贵时间对本文进行评审、指正。感谢 答辩委员会的老师们在白忙之中抽出宝贵时间参加论文答辩、提出宝贵意见。 还要感谢本文所引文献的所有作者，他们杰出的研究工作和成果为我们后 来的研究提供了极大的便利。 最后要感谢我的父母和女友李夏，他们长久以来对我的默默支持、鼓励和 帮助，使我能够全心地投入到学习、研究中去，以自信和乐观的心态去为这个 世界做出尽可能多的贡献。 作者：藕军 2 0 0 7 年5 月 1 1 研究背景 第一章绪论 2 0 世纪9 0 年代万维网( w w w ，简称w e b ) 的出现使得人们在w e b 上发布 和浏览信息变得十分便利，并且随着w e b 技术的发展，各种各样基于w e b 的 应用层出不穷。这些因素导致存储在w e b 上的信息数量迅速膨胀起来，并且与 日俱增。以中文w e b 为衍，截至2 0 0 6 年底【i l ，中国已经有8 4 3 万个网站，中 文网页数达到4 4 7 亿个。一方面w e b 上信息数量的急剧膨胀，一方面由于互联 网的分布式体系结构使得网络导航变得越来越困难，人们急需一种能对w e b 上 信息进行自动搜索的工具这就是搜索引擎( s e a r c he n g i n e ，s e ) 。搜索引擎提供 了对w e b 网页的一种快速便捷的搜索方式，然而w e b 中还有非常巨大的一部 分信息是搜索引擎所不能搜索到的，比如保存在w e b 数据库中的信息、动态网 页等等。这些信息数量巨大、价值很高，但因为技术或商业等原因，目前搜索 引擎还不提供对它们的搜索。鉴于搜索引擎在检索w e b 信息方面的重要地位， 可以以搜索引擎为观察角度将w e b 分为“浅层网络”和“深层网络”：那些能 被搜索引擎搜索到的w e b 称为“浅层网络”( s u r f a c ew e b ) ，而那些还不能被搜 索引擎搜索的w e b 称为“深层网络”( d e e pw e b ) 。据调查研究的结果1 2 4 j 可知 d e e p w e b 中蕴含着大量有价值的信息，可是它们却不能被当前主流搜索引擎搜 索到；因此，寻找能够对d e e pw e b 进行搜索的技术和工具就显得很有必要很 有价值。 可以通过两种方式来搜索d e e p w 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 搜索引擎( d e e pw e bs e a r c he n g i n e ) 。 1 2 研究现状 关于d e e pw e b 的两种搜索工具在国外都有所发展。目录搜索方面，已经出 现了不少d e e pw e b 资源目录可供按主题查询，比如图书馆员互联网索引1 4 1 、 d i r e c ts e a r c h l 5 1 等。自动搜索方面的研究还刚刚开始，成熟的系统很少，可以举 出的只有b r i g h t p l a n e t 公司的c o m p l e t e p l a n e t 产品【6 1 。c o m p l e t e p l a n e t 一开始也 是一个d e e pw e b 资源目录，后来开发出l e x i b o t 检索工具，能根据用户的查 询请求选择6 0 0 个相关的d e e pw e b 资源进行搜索并返回结果。l e x i b o t 后来又 升级到d e e pq u e r y m a n a g e r ( d q m ) 检索平台。d q m 不是一个搜索引擎，而 是一个自动搜索平台，它能够同时检索多个搜索引擎、网站目录和深层网络数 据库，而且其搜索对象既包括深层网络，也包括表层网络。 c o m p l e t e p l a n e t 在d e e pw e b 搜索引擎方面的研究是走在前列的，不过由于 是一个商业系统，没有公布相关研究成果；并且其检索的效率和准确率都有待 大大提高。 元搜索引擎能调用多个搜索引擎同时进行搜索，它所涉及的数据库选择、 结果聚合等技术和d e e pw e b 搜索引擎有相通之处，因此可以借鉴其研究成果。 元搜索引擎的研究成果颇多，比如s a v v y s e a r c h ”、p r o f u s i o n 8 1 。元搜索引擎也 有成功的商用系统，比如d o p p i l e l 9 1 。然而传统的元搜索引擎因为集成的成员搜 索引擎数量有限，所以它在提高查全率和查准率方面的作用也是有限的。这就 导致了大规模元搜索引擎的出现。e f f e c t i v ea n ds c a l a b l em e t a s e a r c h e n g i n e 1 0 1 项目就研究如何构建一个大规模且高效的元搜索引擎及相关技术，比 如如何发现和分类搜索引擎，如何为搜索引擎构建w r a p p e r ，如何根据查询请 求自动选择搜索引擎，以及如何聚合多个搜索引擎返回的结果。这些相关技术 的研究和成果为构建d e e pw e b 搜索引擎提供了有益的启发。 国内在d e e pw e b 搜索方面的研究还是相对滞后的，既没有出现专门的d e e p w e b 资源目录，也没有d e e pw e b 搜索引擎方面的研究。而在元搜索引擎方面则 有一些研究成果，比如文献【1 1 - 1 3 】。为了解决元搜索引擎悖论的问题i l ”，也有 人研究了扩展元搜索引擎e m s e ”】，能提供对搜索引擎、o p a c 、网上数据库及新 闻网站的集成搜索。不足之处是它能搜索的数据库种类及规模有限，并且缺少 对数据库进行自动选择、对多个数据库返回结果进行聚合的功能。 1 3 目的和意义 本文的研究目的： ( 1 ) 对d e e pw e b 的定义和概况进行分析，得出发展d e e pw e b 搜索引擎的必 要性和可行性。 ( 2 ) 给出完整的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 搜索引擎的各个关键技术进行分析研究，在总结已有成果 的基础上试图给出实用高效的实现方法，并通过实验验证。 本文的研究意义： ( 1 ) 使得人们对d e e pw e b 及如何对d e e pw e b 进行有效搜索有比较全面的认 识。 2 ( 2 ) 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 中的巨量高价值的信息 能为大众所搜索，极大地提高了资源的利用率，提高了搜索的查全率和 查准率，意义重大。 1 4 论文内容和结构 本文的研究内容包括： ( 1 ) d e e pw e b 的定义及概况。 ( 2 ) 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 进行概述，讨论了d e e pw e b 出现的原因，定义及类型， d e e pw e b 概况，以及发展d e e pw 曲搜索引擎的必要性和可行性，最后给出d e e p w e b 搜索引擎的框架图及定义。 从第四章到第七章分别对数据库自动发现、数据库自动选择、返回结果自 动抽取、结果聚合这四个关键技术进行详细介绍。 最后在第八章中进行总结并指出不足之处及未来研究方向。 3 第二章搜索引擎概述 关于搜索引擎f 1 6 l 的定义，说法很多，还没有一个统一的定义，一般可以从 广义和狭义两个方面来理解。从广义上讲，搜索引擎是一类提供w e b 信息搜索 服务的网站。从狭义上来讲，搜索引擎是一种对w e b 网页进行搜集、索引并提 供搜索服务的信息检索机制。它对已下载网页的内容进行全文索引，并从网页 中提取新链接保存到链接库中；从链接库中提取链接，下载链接指向的网页， 索引网页内容，提取新链接，如此反复，不断搜集和索引w e b 信息。通过检索 接1 3 接受用户的查询，从索引中选择匹配的结果以合适的顺序返回给用户。本 文从狭义角度来理解搜索引擎，首先介绍一般原理，然后介绍性能评价指标， 最后介绍几种常见的搜索引擎类别。 2 1 一般原理 如图2 - 1 所示，一个完整的搜索引擎一般包括四个模块：信息采集模块，分 析索引模块，信息检索模块，用户接口模块。用户接口模块主要提供h t m l 交 互页面，先通过搜索表单( f o r m ) 获得用户的查询需求，再把返回的信息以 h t m l 页面的形式返回给用户。其它几个模块的工作原理介绍如下。 2 1 1 信息采集模块 图2 - 1 搜索引擎结构图 信息采集一般由一个称为网络蜘蛛【1 7 - 1 8 ( s p i d e r ，也称r o b o t ，c r a w l e r ) 的 软件完成。蜘蛛一般要维护一个u r l 列表( 链接库) ，一方面从这个列表中选 择种子u r l ，根据h t t p 协议下载u r l 指向的网页，这些下载的网页就可以 进入分析索引模块进行索引；另一方面，从下载的网页中提取新的u r l 加入 u r l 列表，实现后续更多的网页采集。通过这种不断提取添加新u r l 的方式， s p i d e r 就可以实现对w e b 的大规模自动采集，生成网页数据库。为了加快采集 速度，s p i d e r 一般使用多线程技术并发工作。当然，基于技术的、经济的或法 4 律的考虑，s p i d e r 并不是采集所有可以采集的网页，比如不采集网站采集限制 协议r o b o t t x t 规定的网页。有限地采集动态网页，对大型站点的采集深度和采 集网页总数做出限制等。 可以把w e b 看成一个图结构【1 9 l ，节点( n o d e ) 是网页，边由网页与网页之 间的链接组成。从这个角度看，信息采集实际上是对图的遍历的过程。蜘蛛遍 历的顺序有宽度优先和深度优先两种。所谓宽度优先就是先采集完同一层的网 页，再采集下一层网页；而深度优先则是先沿一条路径采集到叶节点，再从同 层其他路径进行采集。有研究表明，宽度优先的方法得到的网页集合的重要性 更好，所以一般通用搜索引擎都使用宽度优先原则。 2 1 2 分析索引模块 该模块要做的工作就是将网页数据库中的原始网页进行标签过滤、提取正 文、自动分词等分析处理后生成正向全文索引，然后建立倒排结构的反向索引， 得到索引数据库，用以最终检索。 网页是包含h t m l 标签的半结构化文档，从网页中提取正文需要过滤标签。 同时，由于标签蕴涵了一定的意义，比如字体的大小和颜色一定程度上反映了 文字的重要性，因此过滤标签的同时根据这些标签信息给相关文本赋以权值， 有利于计算查询相似度。提取网页上的u r l ，分析网页间的链接关系，可以用 来计算网页的重要性，用以搜索排序。 从网页上提取出正文后，需要对正文进行分词处理拉“，便于后续的索引和 最终的检索。分词效果的好坏，将直接影响到索引的效果和查询的效果，特别 是在以中文为代表的东方语系中，分词问题尤显重要。 搜索引擎可能同一时间面临大量的用户检索需求( 几十几千点击，秒) ，这 就要求搜索引擎在检索程序的设计上要高效，尽可能的将大运算量的工作在索 引阶段完成，使检索时的运算尽量的少。一般的数据库系统不能快速响应如此 大量的用户请求，在搜索引擎中通常采用倒排索引技术【2 1 1 。建立倒排索引包括 建立正向索引和反向索引。从网页上提取正文后，就可以建立正向索引，即从 网页到索引词的对应关系表。根据正向索引建立反向索引，即从索引词到网页 的对应关系表。 2 1 3 检索模块 检索模块需要对用户输入的查询词进行分析，转换为系统识别的格式，然 后从倒排索引表中选择匹配的网页，并且计算网页与查询词的相似度，根据相 似度的高低排列结果网页，同时根据查询词在网页中的位置自动生成网页摘要 显示给用户。 网页与查询词的相似度计算是信息检索模块中的核心，它决定了检索结果 5 的质量。相似度的计算有多种不同的方法，可以分为基于内容的、基于网页结 构的、基于链接结构的相似度计算法。 基于内容的相似度计算法主要是根据传统信息检索模型【“l ，包括布尔模型、 向量空间模型、概率模型、统计语言建模等。 基于网页结构的相似度计算法主要是利用网页上不同标签蕴涵的意义，比 如加大部分数据的权重f 如网页中的t i t l e 、 、 等重要标签中的内 容】。 基于链接结构的相似度计算方法采用链接分析的方法，根据网页问的链接 关系计算得出其重要性。比较典型的有g o o g l e 的p a g e r a n k 算法【2 刀和i b m 的 h i t s 算法 2 4 1 。 以上三种相似度计算方法各有优劣，一般不单独使用，而是结合使用。 最终显示的每条结果记录一般包括标题及网页摘要信息，并且标题带有链 接指向结果源网页。其中摘要信息是最重要的部分，一般有静态摘要和动态摘 要两种。静态摘要指一个网页事先生成其摘要，而动态摘要指基于查询的摘要， 不同的查询会生成不同的摘要。静态摘要比较简单，但是由于多主题问题的存 在，效果往往不好。现代搜索引擎往往采用动态摘要，用户也认可这种方式。 2 2 性能评价指标 搜索引擎的性能评价指标主要有查全率( r e c a l l ) 、查准率( p r e c i s i o n ) 1 2 5 1 响应时间。查全率是搜索引擎命中的相关网页数与该搜索引擎包含的所有相关 网页总数的比率，衡量的是搜索引擎的召回率；查准率是搜索引擎命中的相关 网页数与搜索引擎返回的网页总数的比率，衡量的是搜索引擎的准确率；响应 时间是搜索引擎从接受用户查询到返回查询结果的时间，衡量搜索引擎的检索 效率。搜索引擎的评价指标中，人们最关心的是查准率，其次是响应时间和查 全率。由于不同的查询关键词其查准率是不一样的，实际上以平均查准率来确 定搜索引擎的查准率；响应时间方面，我们实际以同一查询机器来区分不同搜 索引肇的搜索时间；至于查全率，由于我们一般无法确定所有相关文档的数量， 故其在计算方面比较困难。因此，一般把查准率和响应时间作为衡量搜索引擎 的评价指标。 2 3 几种常见类别 关于搜索引起的分类，目前还没有一个统一的方法。按照不同的分类标准， 搜索引擎有不同的分类方法，比如按照网页是否被全文索引可以分为目录式搜 索引擎和全文索引式搜索引擎；按照索引信息的范围可分为通用搜索引擎、专 业( 垂直) 搜索引擎和局域网内搜索引擎：按照工作方式可以分为独立搜索引 擎和元搜索引擎。 6 下面介绍几种常见的搜索引擎。 通用搜索引擎是目前主流的网页搜索引擎，比如g o o g l e 2 6 1 、百度【2 7 1 。它对 网页信息的类别不作区分，大量地对w e b 网页进行采集和索引，从而提供对一 般网页的信息搜索。 专业搜索引擎，也称垂直搜索引擎，它专门搜集某个专业或领域内信息并 提供搜索服务。专业搜索引擎除了要遵循通用搜索引擎的一般原理外，特别之 处在于其信息采集机制：它使用定向蜘蛛或主题蜘蛛【28 】采集信息。定向蜘蛛无 须对整个w 曲进行遍历，只需选择与主题页面相关的页面进行访问。 元搜索引擎和通用搜索引擎不一样，它本身不采集信息也没有自己的信息 索引库，而是将搜索请求发送给多个搜索引擎，获得多个搜索引擎的搜索结果 并进行聚合处理，以统一格式显示给用户。元搜索引擎不需要搜集和索引信息， 其主要精力放在提高搜索速度、智能化处理搜索结果、个性搜索功能的设置和 用户搜索界面的友好性等方面，其查全率和查准率相对较高。 2 4 本章小结 安排本章的原因有二：其一，d e e pw e b 搜索引擎遵循搜索引擎的一般原理 和技术；其二，d e e pw e b 的出现是因为搜索引擎的局限性导致的。因此有必要 对搜索引擎的一般原理和技术进行概述。 本章首先介绍了搜索引擎的一股原理，包括信息采集模块、分析索引模块， 检索模块。 其次，介绍了对搜索引擎性能进行评价的指标，包括查准率、查全率及响 应时间。 最后介绍了搜索引擎的几种分类方法，并具体介绍了目前常见的三种搜索 引擎：通用搜索引擎、专业搜索引擎及元搜索引擎。 7 第三章d e e p w 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 pw e b 搜索引 擎的整体框架以及关键技术。 3 1d e e pw e b 出现原因 d e e pw e b 的出现和搜索引擎的历史有密切关系。w e b 的简捷、标准和异构 特性，使得任何人都可以轻松地发布信息。这些信息一般以h t m l 网页形式保 存在w e b 服务器中，通过u r l 互相连接，称之为静态网页。w e b 上静态网页 规模的急剧膨胀，使得人们需要一种工具能对这些网页进行检索，这就是搜索 引擎。也就是说从一开始，搜索引擎就为搜索静态网页而开发的。但是，随着 w e b 技术的发展，特别是w 曲数据库技术的出现和发展，w e b 上保存的信息种 类越来越多，除静态网页外，还有诸如声音视频等多媒体文件、可执行程序、 查询w e b 数据库返回的动态网页等等。对于这些新出现的各种信息，搜索引擎 因为技术的( 比如担心陷入一个网站里过多的动态网页) 或商业的( 比如h t m l 网页以外的其他格式文件的需求量有限但耗用的资源却非常多) 原因，无法提 供对这些信息的搜索服务。这样，d e e pw e b 就出现了。而且w e b 技术在加速 发展，而搜索引擎技术的发展速度有限，d e e pw e b 规模也在增大，如何解决 d e e pw e b 搜索的问题也越来越显得迫切。 3 。2 定义及类型 深层网络这个概念最早是由d r j i l le l l s w o r t h 于1 9 9 4 年提出的【2 9 1 ，当时称 为“不可见网络”( i n v i s i b l ew e b ) 。但真正的深层网络研究起始于1 9 9 8 年，当 时两位美国信息管理专家l a w r e n c e 和g i l e s 提出开发深层网络信息资源的想 法【3 0 1 。此后出现了多个对“不可见网络”的定义，比如有定义为：可以通过万 维网获得的文本网页、各种文件或其它高质量的信息资源，但是由于技术限制 或者其它原因，使得通用搜索引擎不能或不愿把这些信息加入网页索引数据库 中，从而无法对这些资源进行搜索【3 1 】。也有定义为：通用搜索引擎不能或不愿 索引的信息1 3 2 l 。在d e e pw e b 领域颇有作为的b r i g h t p l a n e t 公司于2 0 0 1 年公布 的一份白皮书【2 】中首次用“深层网络( d e e pw e b ) ”代替“不可见网络”一词， 且把深层网络定义为：保存在可搜索数据库中，只能通过直接查询数据库才能 获取的资源。他们认为d e e pw e b 的提法比以前提出的不可见网络一词更科学、 合理。事实上，很多学者认为不可见网络和深层网络所指的是同一种网络资源， 并没有严格区分它们的不同。 根据d e e p w e b 产生的原因可以将其分为以下几类p 习： ( 1 ) 未被链接的网页，也叫孤立网页，即没有被其它任何网页链接。 ( 2 ) 非h t m l 网页，除h t m l 网页以外的各种形式的文件，比如p d f 文档， 可执行程序、声音视频等多媒体文件。 ( 3 ) 载有实时或者流动信息的网页，比如载有股票报价、天气预报等变化很 快、数据量很大的网页； ( 4 ) 可搜索数据库( s e a r c h a b l ed a t ab a s e ，s d b ) ，即可进行搜索的网络数据库 3 4 - 3 5 l 。s d b 一般由客户端一服务器端一数据库端三层结构组成：数据库 端保存信息内容，返回满足查询的结果；客户端提供一个搜索页面，供 用户输入查询请求，并显示最终搜索结果；服务器端将用户的查询请求 递交给数据库，并将数据库返回记录生成动态网页返回给用户。 ( 5 ) 动态网页。它们不是以静态网页保存在服务器中，而是保存在类似于 s d b 的三层结构中，由数据库返回内容，服务器生成动态网页。与s d b 不同的是，这些动态网页一般不是通过搜索产生的，而是由指向动态网 页的动态链接互相连接产生，比如b b s 上发布的动态网页。 从以上分类可以看出，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 3 d e e p w e b 概况 d e e p w e b 的规模巨大且包含着大量高质量的信息，关于这点已经有了初步 概念。但是，d e e p w e b 现状到底如何呢? 其规模大小、内容质量及分布情况究 竟如何呢? 这需要一些定量的方法进行研究。 b r i g h t p l a n e t 公司对2 0 0 0 年左右的以英文内容为主的d e e p w e b 概况进行了 研究分析，得出如下结论【2 j ： ( 1 ) d e e pw e b 里包含的可访问公共信息容量是我们熟知的s u r f a c ew e b 的 4 0 0 5 0 0 倍。 ( 2 ) d e e pw e b 包含7 5 0 0 t b 的信息，而s u r f a c ew e b 包含的信息容量只有 1 9 t b 。 ( 3 ) d e e pw e b 包含5 5 0 0 亿独立文档，相对应的s u r f a c ew e b 只包含1 0 亿个。 ( 4 ) 现有的d e e pw e b 站点估计超过1 0 0 ，0 0 0 个。 ( 5 ) 6 0 个最大的d e e pw e b 站点就已经包含7 5 0 t b 信息，超过s u r f a c ew e b 所包含信息的4 0 倍。 9 ( 6 ) 平均地看，d e e pw e b 站点的月访问量比s u r f a c ew e b 站点商出5 0 ，并 且与s u r f a c ew e b 站点相比有更多的链接。可是那些典型的大型d e e p w 曲站点在互联网搜索领域却不知名。 ( 7 ) d e e pw e b 是互联网新信息增长的最大来源。 ( 8 ) d e e p w e b 站点在信息内容范围上比一般s u r f a c e w e b 站点更专更深。 ( 9 ) d e e pw e b 包含的有效高质内容总量至少是s u r f a c ew e b 的1 0 0 0 到2 0 0 0 倍。 ( 1o )超过一半的d e e pw e b 内容都保存在专业领域的数据库中。 ( 1 1 )9 5 的d e e pw e b 信息都是面向公共访问的，面不是需要付费或者订 阅的。 由这个结果可以看出，d e e pw e b 中确实包含着丰富的高质量内容。同时， w e b 的发展一日千里，时隔几年后，今天d e e pw e b 状况又是如何呢? 另外，中 文内容在整个w e b 中所占的比重很大，而且这个比重和它的内容质量还在不断 提高，那么中文d e e pw e b 的现状又是如何呢? 于是以2 0 0 6 年1 0 月间的中文 d e e pw e b 为样本，对中文d e e pw e b 的大小、内容质量及分布情况进行了研究， 运用定性和定量的方法进行计算得出如下结论口j ： ( 1 ) s d b s 数量超过3 万个。 ( 2 ) d e e pw e b 中文件的总数量和总存储量分别约为5 0 7 亿、1 1 7 0 0 t b ，而中 文s u r f a c ew 曲中文件的总数量和总存储量分别约为1 0 亿、2 7 t b 。 ( 3 ) d e e pw e b 大小是s u r f a c ew e b 的2 4 0 倍以上。 ( 4 1d e e pw e b 的内容质量比s u r f a c ew e b 高。 ( 5 ) d e e pw e b 中文本内容占9 0 ，多媒体内容偏少：站内数据库占绝大多 数，专业数据库和专业搜索引擎偏少；绝大多数内容都是可以直接访问 的；行业与企业、政法军事及教育与培训等主题比重较大，其它主题分 布比较均匀。 与2 0 0 0 年英文d e e pw e b 的结果相比，相似的是d e e pw e b 的大小都远远大 于s u r f a c ew e b ，且s d b s 数量巨大，d e e pw 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 。不同的 是，英文s d b s 数比中文s d b s 多出3 倍以上，再考虑6 年来w e b 的发展，说 明中文d e e pw 曲相对较小；英文d e e pw e b 专业数据库的比例超过一半，而中 文d e e pw e b 中专业数据库只有5 ，说明中文数据库产业规模小，仍需大力发 展。 3 4 发展d e e pw e b 搜索引擎的必要性和可行性 从上一节的分析我们知道，d e e pw e b 包含着数量巨大的信息，而且其内容质量 也非常高。这些信息的数量和质量都比s u r f a c ew e b 高，因此至少需要像s u r f a c e w 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 pw e b 搜索引擎是可行的，因为通用搜索引擎技术已经发展得非常 成熟，而且元搜索技术也有大量的研究成果。这些研究成果为d e e pw e b 搜索 引擎的出现准备了技术基础。同时，s d b 的三层结构特征使得可以通过查询反 馈的方式获得s d b 包含的内容，从而为实现对d e e pw e b 搜索提供了一条途径。 这些都说明了d e e p w e b 搜索引擎研究的可行性。 3 5d e e pw e b 搜索引擎的框架及关键技术 目前的通用搜索引擎不能提供对d e e pw e b 中丰富高质量的信息资源的搜 索，必须使用全新的搜索引擎技术。如果仅从实现功能上看，可以粗略地认为 s d b s 也是搜索引擎。而元搜索引擎就是通过调用多个成员搜索引擎来进行搜 索的，可以在改进元搜索方式的基础上实现对多个s d b s 的搜索。由于s d b s 数量巨大而且情况复杂多变，所以需要一种全新的元搜索技术实现从众多s d b s 中搜索信息，这就是大规模元搜索引擎技术i l 。文献 3 6 1 把大规模元搜索引擎 分为三个模块，即搜索引擎自动发现模块、搜索引擎自动连接查询模块、搜索 结果自动抽取模块。文献f 3 9 提出一种大规模元搜索引擎的构成，包括数据库 选择、文件选择、查询分派及结果聚合等四个部分。综合以上研究成果，结合 d e e pw e b 的特点，本文提出一个d e e pw e b 搜索引擎的整体框架，见图3 一l 。 图3 - 1d e e pw e b 搜索引擎框架图 该框架主要由以下几个模块组成： ( 1 ) 数据库自动发现( a u t o m a t i c a l l yd a t a b a s e sd i s c o v e r i n g ) 模块。该模块利用特制 的网络蜘蛛在w e b 上定向爬行，发现可搜索数据库并提取它的有关元信 息，生成s d b s 库。 ( 2 ) 用户接i = 1 。该接口主要用来与用户进行交互，接受用户的查询请求，并 显示最终的搜索结果。 ( 3 ) 数据库自动选择( a u t o m a t i c a l l yd a t a b a s e ss e l e c t i n g ) 模块。该模块接受查询 词，然后利用一定的选择算法从s d b s 库里自动选择与查询词最相关的 若干数据库进行搜索。 ( 4 ) 数据库自动查询( a u t o m a t i c a l l yd a t a b a s e sq u e r y i n g ) 模块。该模块根据数据库 自动选择模块选择的s d b s ，调用这些s d b s 元信息中对应的查询表达 式，自动连接服务器进行查询并获得数据库反馈的页面。 ( 5 ) 返回结果自动抽取( a u t o m a t i c a l l ys e a r c h r e s u l t se x t r a c t i n g ) 模块。该模块接受 各s d b s 查询反馈的页面，利用抽取算法从页面中自动抽取出结果记录。 ( 6 ) 结果聚合( r e s u l t sa g g r e g a t i o n ) 模块。该模块利用返回结果自动抽取模块从 各个s d b s 抽取合适数量的结果记录，将这些结果记录通过去重、全局 排序后以统一的形式提交给用户接口进行显示。 根据这个框架，结合搜索引擎的定义，定义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 上的可搜索数据库( s d b s ) ，生成s d b s 库；用户接口接受到用户查询后， 调用数据库自动选择模块从s d b s 库里选择最相关的若干数据库；每个被选中 的数据库通过数据库自动查询模块链接数据库服务器查询；数据库查询返回的 页面经过返回结果自动抽取模块抽取出结果记录，并通过结果聚合模块进行聚 合；结果聚合模块将所有选中数据库的返回结果汇聚成一个统一、有序的结果 提交给用户接口，并最终显示给用户。 以上各模块中，除了数据库自动查询模块可以直接实现外，其它模块都需 要专门研究，它们对应的就是d e e pw e b 搜索引擎的几个关键技术：可搜索数 据库的自动发现、数据库自动选择、返回结果自动抽取、搜索结果聚合。 数据库的自动发现技术主要解决如何从w e b 中自动识别s d b s ，并提取出对 数据库自动选择、数据库自动查询等模块有用的元信息。 数据库自动选择技术主要解决如何计算数据库对于一个特定查询的相似度 得分，从而根据得分高低选择最相关的若干数据库进行查询。 返回结果自动抽取技术主要解决如何从数据库查询返回页面上识别出每个 结果记录以及结果多页显示时的后续页面链接，并为识别出来的结果记录和后 续页面链接构造w r a p p e r ，在实际抽取过程中根据这个w r a p p e r 就可以直接提 取出结果记录。 结果聚合技术主要解决如何从一个数据库所有返回结果中选择合适数量的 结果、如何对选择的结果进行全局排序、如何对多个数据库返回结果中的重复 结果进行识别和消重。 以下各章节将分别对这四个关键技术展开详细的讨论。 3 6 本章小结 本章对d e e pw e b 进行了全面的概述，包括其出现的原因、定义及类型、概 括；并在此基础上指出发展d e e p w e b 搜索引擎的必要性和可行性，最后提出了 d e e pw e b 搜索引擎的完整框架和定义。 第四章数据库自动发现 我们已经知道d e e pw e b 中包含了成千上万的可