（计算机应用技术专业论文）deep+web模式匹配技术研究.pdf

d e e pw e b 模式匹配技术研究 摘要 摘要 w 曲上的大量信息只能通过查询接口获得，这些资源被认为是d e e pw 曲资源。 对于不同兴趣领域，不同的查询接口有着各自迥异的查询能力和内容覆盖率。因此， 用户需要频繁的访问不同的资源接口以获得想要的信息，这是非常耗时的。为了处理 这个问题，一种有效的解决方法是在这些查询接口之上建立一个集成的全局接口，提 供给用户一个统一的访问途径。 模式匹配是集成的前提条件。本文首先对d e e pw e b 模式匹配技术进行深入地分 析和研究，借鉴已有技术提出了一种新的模式匹配方法，然后依据匹配结果实现d e e p w e b 接口集成。最后提出了一个面向d e e p w e b 对象的查询接口集成原型系统的设计。 本文主要研究的工作包括： ( 1 ) 首先介绍d e e pw e b 相关知识和国内外研究状况，然后阐述模式匹配的概 念和原理，对传统模式匹配技术和当前主要的模式匹配技术进行比较分析。 。 ( 2 ) 进行d e e pw e b 模式匹配的研究，本文提出了一种基于数据挖掘技术的整 体性模式匹配方法( c o r r e l a t e d c l u s t e r i n g ) ，该方法主要利用正相关关联挖掘发现潜在 属性组，并利用聚类思想对同义属性进行挖掘。 ( 3 ) 利用模式匹配的结果，同时结合数据域类型和值域范围，构造并生成d e e p w e b 主题领域全局模式，提供给用户集成统一的查询接口。 ( 4 ) 根据上述研究，最后设计了一个面向d e e pw e b 对象的查询接口集成系统。 本文还对文中提出的方法和技术进行了实验验证，通过对实验结果的分析进一步 说明了本文提出的技术方法是行之有效的。 关键词：d e e pw e b ，模式匹配，全局模式，数据集成 作者：钟昕 指导教师：伏玉琛 a b s t r a c t r e s e a r c ho i lt e c h n o l o g yo f d e e pw e bs c h e m am a t c h i n g a bs t r a c t a l a r g en u m b e ro fd a t as o u e c c so nt h ew e ba r eo n l ya c c e s s i b l et h r o u g ht h e i rq u e r y i n t e r f a c e s t h e s es o u r c e sa r ec o m m o n l yk n o w na sd e e pw e bs o u r c e s f o ra n yd o m a i no f i n t e r e s t ，t h e r em a yb em a n ys u c hs o u r c e sw i t hv a r i e dq u e r yc a p a b i l i t i e sa n dc o n t e n t c o v e r a g e a sar e s u l t ，u s e r sf r e q u e n t l yn e e dt oa c c e s sm u l t i p l es o u r c e si no r d e rt of i n dt h e d e s i r e di n f o r m a t i o n ，w h i c hc a nb eav e r yt i m e - c o n s u m i n ga n dl a b o r - e x p e n s i v ep r o c e s s t o a d d r e s st h i sp r o b l e m ，a ne f f e c t i v es o l u t i o ni st ob u i l da l li n t e g r a t i o ns y s t e mo v e rt h e s o u r c e s s u c has y s t e mp r o v i d e su n i f o r ma c c e s s e sf o ru s e r s s c h e m am a t c h i n gi sp r e r e q u i s i t et od a t ai n t e g r a t i o n t h i sp a p e rf i r s t l yf o c u s e so n t e c h n o l o g yo fd e e pw e bs c h e m am a t c h i n g ，a n dp r o p o s e san e wm e t h o da c c o r d i n gt o e x i s t e dm e t h o d s ，t h e ni n t e g r a t e sq u e r yi n t e r f a c e su s i n gm a t c h i n gr e s u l t s f i n a l l yd e e pw e b o b j e c t l e v e lq u e r yi n t e r f a c e si n t e g r a t i o na r c h e t y p a ls y s t e mi sp r e s e n t e d t h em a i nw o r ki s s u m m 撕z e da sf o l l o w s ： ( 1 ) f i r s t l y , i n t r o d u c er e l e v a n tk n o w l e d g eo fd e e pw e b a n di t sr e l a t e dr e s e a r c hw o r k , a n dt h e ne x p a t i a t et h ec o n c e p ta n dp r i n c i p l eo fs c h e m am a t c h i n g ，a n dc o m p a r et r a d i t i o n a l m e t h o d sa n dc u r r e n tp o p u l a rm e t h o d s ( 2 ) s t u d yo nd e e pw e bs c h e m am a t c h i n g ，t h e np r o p o s ean e wh o l i s t i cs c h e m a m a t c h i n gm e t h o db a s e do i ld a t am i n i n g ，n a m e da sc o r r e l a t e d c l u s t e r i n g ，w h i c hm i n e s p o s i t i v e l yc o r r e l a t e da t t r i b u t e st of o r mp o t e n t i a la t t r i b u t eg r o u p s ，a n df m d ss y n o n y m a t t r i b u t e sb yc l u s t e r i n g ( 3 ) t h ed o m a i n s p e c i f i cg l o b a ls c h e m ai sc o n s t r u c t e da c c o r d i n gt om a t c h i n gr e s u l t s ， d a t at y p e sa n dv a l u ed o m a i n , w h i c hp r o v i d e su n i f o r mq u e r yi n t e r f a c e sf o ru s e r s ( 4 ) d e s i g nad e e pw e bo b j e c t - l e v e lq u e r yi n t e r f a c e si n t e g r a t i o ns y s t e ma c c o r d i n gt o a b o v et e c h n o l o g y f i n a l l yw ed e s i g ne x p e r i m e n t st oi m p l e m e n tm e n t i o n e da l g o r i t h m sa n dt e c h n o l o g y e x p e r i m e n t a lr e s u l t sd e m o n s t r a t eo u r s o l u t i o ny i e l d sa h i g h e ra c c u r a c ya n de f f i c i e n c y k e y w o r d s ：d e e pw e b ，s c h e m am a t c h i n g ，g l o b a ls c h e m a , d a t ai n t e g r a t i o n l i w r i t t e nb y ：z h o n gx i n s u r p e r v i s e db y ：f uy u c h e n 图表目录 图1 1 搜索引擎获取d e e pw e b 和s u r f a c ew e b 信息l 图2 1d e e pw 曲数据集成框架9 图2 2 查询处理过程涉及到的四种模式匹配1 0 图2 3 模式匹配方法分类13 图2 4m g s 方法在书籍查找领域研究案例18 图3 1 网页查询界面示例2 5 图3 2c o r r e l a t e d c l u s t e 血g 方法研究框架2 7 图3 3 类型的兼容性2 7 图3 4 书籍领域属性分布频度3 4 图3 5w o r d n e t 上下位关系分类层次示例。3 9 图4 1 领域属性词汇的发展趋势4 5 图4 2 合并字符型数据域示例。4 7 图4 - 3d e e pw e b 查询接口集成模式层次树4 7 图4 4 不同范围表示格式示例4 8 图4 5 全局范围构建示例4 8 图4 6 集成界面示例_ 。4 9 图5 1 系统框架- 5 2 图5 2 成组发现运行结果图5 9 图5 3 匹配发现运行结果图。6 0 图5 4 书籍领域全局集成模式。6 l 图6 1 平均查准率、查全率、f m e a s u r e 值的比较6 4 表3 1 正相关挖掘( a p r i o d c o r r m i n i n g ) 算法。3 0 表3 2 普通凝聚层次聚类( h a c ) 算法3 2 表3 3 两个属性在模式实例中可能的组合方式3 4 表4 1 八个领域4 9 4 个数据源属性统计4 5 表4 2 范围修饰符表示字典( 表示需要配对使用) 4 9 表4 3 范围元素语义表4 9 表6 1 三个领域3 组权值的设置6 4 表6 2 领域模式匹配实验数据。6 5 表6 3 在b a m m 数据集上4 种领域内3 种方法的实验结果比较6 5 表6 4m m e a s u r e 和j a c c a r d 的比较6 6 表6 5 全局模式构建的准确性和完整性6 7 v 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：蟑日期：逊谬 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名 导师签名 期：迦墨：尘：! 墨 期：礁塑：垡 d e e pw e b 模式匹配技术研究 第l 章引言 + 1 1 问题的提出 第1 章引言 随着w e b 的飞速发展，其蕴涵的信息量也在急剧增长。人们急需一种能对w e b 上 信息进行自动搜索的工具。然而自动获取w e b 中的有价值信息很有挑战性，原因在于： w e b 中的信息主要通过网页的形式对外发布，而由文本和超链接构成的网页数量惊 人，信息丰富；由不同的个人或群体开发的网页，形式与内容有很大差异，且分布在 地球上i n t e m e t 连接的每一个角落，这就造成了w e b 数据的异质性和缺乏结构性。如果 把整个i n t e m e t 上的信息比喻为一个信息海洋，那么为了在这片海洋中撒网捕鱼，我们 需要一种“捕捞工具”搜索引擎( s e a r c he n g i n e ，s e ) 应运而生。 近年来，网络朝着深度方向发展，大批的高价值、高质量的信息隐藏于网络海洋 的深处。这些信息没有静态链接，需要用户向表单接口提交查询，由站点的后台数据 库动态产生链接返回的页面。这类页面被称为d e e pw e b i i 】( 如图1 1 所示) 。传统的搜 索引擎通过爬虫程序或爬行整个w e b 表面页面来创建页面索引，可以发现这些页面通 常是静态链接产生的。这类页面被称为表面可索引的信息一s l u l f a c ew e b 。d e e pw e b 与s u r f a c ew e b 的本质区别在于，s u r f a c ew e b 包括的内容基本都是非结构化的h t m l 信息，对搜索引擎而言是相对可见的，因此又被称为v i s i b l ew e b ；而d e e pw | e b 的内容 存储在w e b 中可访问的在线数据库中，是相对不可见的，于是又被称为i n v i s i b l ew e b 。 图卜1 搜索引擎获取d e e pw e b 和s u r f a c ew e b 信息 第1 章引言 d e e pw e b 模式匹配技术研究 与s u r f a c ew 曲相比，d e e pw e b 蕴藏了更加丰富、更加专业的信息。近年来的调 查研究表明：p 1 1 2 1 3 1 ( 1 ) d e e pw ，e b 页面信息大约是s u r f a c ew e b 页面的4 0 0 5 0 0 倍，大约有3 0 7 ，0 0 0 个站点，4 5 0 ，0 0 0 个后台数据库和1 ，2 5 8 ，0 0 0 个查询接口，并且仍在迅 速增长。从2 0 0 0 年至1 j 2 0 0 4 年，增长了3 7 倍。 ( 2 ) 整个d e e pw e b 覆盖了世界的各个领域，例如商业、教育、政府等等。但 就单个d e e pw e b 而言，有超过5 0 l 拘d e e pw e b l 为容是特定于某个领域的， 即领域专一化的。 ( 3 ) d e e pw r e b 中的后台数据库大多是结构化的，其中结构化的数据库是非结 构化的3 4 倍之多； ( 4 ) w e b 数据库查询接口往往位于站点浅层，9 4 之多的大量w e b 数据库查询 接口可以在站点前3 层发现。 ( 5 ) 对d e e pw e b 的数据访问量比s u r f a c ew e b 要高出1 5 ，其信息质量远远高 于s u r f a c ew e b 。 ( 6 ) d e e pw e b 上9 5 的信息是可以公开访问的，即可以免费获取。目前一些 d e e pw e b 目录服务已经开始索引w r e b 数据库，但是它们的覆盖率比较小， 仅为0 2 , - 1 5 6 。 综上所述，d e e pw e b 具有信息量大、价值高、质量优、结构化好等特点，然而 由于目前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 p w ，e b 模式匹配技术研究在d e e pw e b 研究领域中有着重要的地位。 本文着重对d e e pw e b 模式匹配技术进行研究，并在此基础上提出查询接口全局 模式的建立，希望为人们获取和利用d e e pw e b 资源提供一些方法。 2 d e e pw e b 模式匹配技术研究 第l 章引言 1 2 国内外研究现状 d e e pw e b 信息获取与集成至今仍是一个新兴的研究领域，虽然在该领域已经开 展了大量的研究工作，但其中仍有很多急待解决的问题。 ，互联网从上个世纪末才传入我国，发展时间太短，人们对网络的研究并不深入。 而d e e pw e b 是随着网络的快速发展出现的，因此绝大多数网络用户对d e e pw r e b 的概 念还很陌生，学者们也并不太重视这个问题，相关论述较少，其中有关的论述都是综 述性的介绍m 夕l d e e p w 曲研究状况，具体的深入研究尚处于空白阶段。 目前国内对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 l 4 ，i n v i s i b l e w e b 5 1 ，b r i g h t p l a n e t 1 1 三家公司生产相关产品。 经过对比分析得出：这几家公司的产品采用半自动方式，人工干预较多。他们在产品 i 、中加入d e e pw e b 信息挖掘功能，但目前还没有中文d e e pw e b 信息服务。 ： 伊利诺斯大学m e t a q u e r i e r l 6 研究小组：该小组建立一个m e t a q u e r y 系统，目标是 有效获取w e b 上结构化的信息。首先，m e t a e x p l o r e r 项目聚焦于发现、模型化和重 构w e b 数据库来建立一个可搜索的数据源知识库。特别是，项目开发了一个w e b 数 据库搜索引擎，它可以有效发现w e b 上含有数据库的站点，设计模型来描述这些数 据库，设计包装器自动抽取这些模型中的参数，重组和索引可搜索的w e b 数据库。 其次，m e t a e x p l o r e r 项目聚焦于集成在线数据库。在研究大规模信息集成的过程中将 依赖于前面所建立的数据源知识库，其重点研究了动态信息集成技术。与传统的信息 检索不同，所设计的m e t a q u e r y 系统是动态的，即可以将实时发现的新数据源加入系 统中，同时动态选择数据源将用户查询进行相应转换，从而获取用户查询结果。 华盛顿大学的s h o p b o t 7 】研究小组：s h o p b o t 是一个针对消费产品的比较代理， 它利用特定领域的启发式方法来填写表单以比较其领域内的商业产品。其聚焦于处理 卖主站点的表单提交页面所返回的产品列表。s h o p b o t 操作分为两个阶段：离线学习 阶段和在线产品比较阶段。在学习阶段，确定如何对填写站点表单，以及对产品站点 3 第1 章引言d e e pw e b 模式匹配技术研究 结果页面进行分析获取其站点模式信息。在比较阶段，利用得到的站点模式结构来抽 取结果信息，寻找满足用户要求价格最优的产品。最终将这些产品信息格式化输出。 可以看出其研究领域非常狭窄，不适用于大规模的信息集成。 斯坦福大学的h i w e i s ：h i d d d e nw e be x p o s e r ( h i w e ) 是s t a n d f o r d 大学的一个研 究项目。r a g h a v a na n dg a r c i a - m o l i n a 设计了一种可以抽取d e e pw e b 信息的爬虫。在 此系统中爬虫管理器负责管理搜集过程。它对下载的w e b 页面进行分析，包含表单 的页面被送到表单处理器中处理。表单处理器首先从页面中抽取表单结构再从预先准 备好的数据集中选择数据自动地完成表单的填写，然后将合成的u r l 提交爬虫管理 器去下载响应的结果页面。由于需要系统自动完成表单填写，所以要求用户预先准备 相应的表单数据集。h i w e 只能面向特定的领域使用，而且必须在人工帮助下完成。 因此存在很大的局限性。 w e b b a s e 9 1 研究小组d a v u l c 等人提出了设计w e b b a s e 的框架，它可以通过工具 帮助用户实现特定领域复杂搜索服务。 、 哥伦比亚大学的q p r o b e r o o j 研究小组：哥伦比亚大学的p a n a g i o t i sg i p e i r o t i s 等人 研究了自动地将w e b 页面所连接的后台数据库进行分类的方法。它首先使用机器学 习技术生成一套基于规则的分类器( c l a s s i f i e r ) 。然后将分类器转变成查询u r l ，对后 台数据库进行查询，计算查询结果数。他们的算法最后根据查询结果对数据库进行分 类。但他们的研究只集中在怎样针对文档数据库的分类上面，而大量的h i d d e nw e b 数据库提供的内容是结构化的数据。 微软亚洲研究院第三代搜索引擎：第三代搜索要对整个网页做一种分析和数据挖 掘，更加智能化、人性化，更加精确，能够理解用户需要什么结果，然后进行聚合和 整理。比如说买一台联想笔记本电脑，如果现在的搜索引擎搜索联想笔记本，会在页 面左边列很多网页，介绍一些联想笔记本的情况，然后右边是一些广告。但对你更有 价值的是哪一家最便宜，哪一家离你最近等信息。而利用第三代搜索引擎搜索联想 笔记本，除了有用的网页和几家广告以外，它还可以生成一个表，这个表会告诉你哪 几家在卖，价位是怎么样的，多长时间能够提货，地图和交通路线是什么，哪家在网 上的评价最好等内容一目了然。其实现在比较购物搜索也有类似的东西。实际上， ， 这二者理念是非常像的，不同的地方就在于，比较购物搜索是在一个很窄的垂直行业 做这样的东西，而第三代搜索引擎不管用户搜索哪一个行业都将达到这样的效果。 4 d e e pw e b 模式匹配技术研究 第1 章引言 1 3 论文主要研究内容 上述国内外研究现状表明，d e e pw 曲正受到越来越多的关注。对d e e pw e b 研究 的根本目的是为了能够自动地获取和利用自由分布在整个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 模式匹配技术进行深入的研究，主要研究内容如下： ( 1 ) 对传统模式匹配技术和当前主要模式匹配技术进行比较和分析，总结它 们各自的优缺点，从中探求新的方法； ( 2 ) 提出一种基于数据挖掘技术的整体性模式匹配方法，利用正相关关联挖 掘和聚类思想，着重处理复杂匹配，力求匹配结果更准确、效率更高； ( 3 ) 设计一种d e e pw e b 全局模式的生成方法，主要利用匹配结果，同时结合 数据类型和值域的判断，构建查询效率高、界面结构化程度好的全局接 口： ( 4 ) 设计一个d e 面w 曲特定领域查询接口集成的初步方案，在基于数据挖掘 技术的模式匹配方法基础上，面向d e e pw e b 某一领域，集成局部查询接 口，建立统一界面，方便用户查询。 1 4 结构安排 本文共分为7 章，结构如下： 第l 章 提出d e e pw e b 的特点及研究意义，同时介绍国内外研究现状，最后给 出本文主要研究内容及结构安排。 第2 章 首先对d e e pw e b 概念进行简要介绍，对其特点进行分析。其次概述d e e p w e b 数据集成及模式匹配概念，主要分析和比较传统模式匹配技术和当 前主要模式匹配技术的优缺点。最后给出本文的研究难点。 第3 章分析利用数据挖掘主要技术进行模式匹配的可行性，重点阐述本文提 出的这种整体性模式匹配方法的原理和具体实现步骤。 第4 章利用本文提出的模式匹配方法得到的匹配结果，提出通过匹配技术来 构造领域d e e pw e b 全局模式的方法。主要给出全局模式的形式化定义 5 第1 章引言 d e e pw e b 模式匹配技术研究 第5 章 第6 章 第7 章 及生成的具体策略。 简单介绍d e e pw e b 查询接1 3 集成方法。并在总结前几章的方法和技术 基础上，提出一个d e e pw e b 特定领域查询接口集成的初步设计。 对本文提出的方法和技术进行实验设计，并通过实验数据的分析验证， 评价本文提出的方法或算法。 对本文工作进行总结和展望。 6 d e e pw e b 模式匹配技术研究 第2 章d c 印w e b 与模式匹配 第2 章d e e pw e b 与模式匹配 2 1 d e e pw e b 简介 1 9 9 4 年，d r j i l le l l s w o r t h 在互联网领域首次提到了不可见网络( i n v i s i b l ew e b ) 一词。但是真正的d e e pw e b 研究起始于1 9 9 8 年，当时两位美国信息管理专家l a w r e n c e 和g i l e s 提出网络信息利用率问题，意识到通用搜索引擎的覆盖率较低，鉴于网络信息 资源没有得到充分的开发和利用，他们提出了开发深层网络信息资源的想法。2 0 0 1 年，不可见网络：挖掘搜索引擎不能看见的资源的作者c h r i ss h e r m a n 和g a r yp r i c e 把不可见网络定义为：通过万维网可以获得的文本网页、文件或其它高质量、权威性 的信息资源，但是由于技术限制或者特定选择的原因，使得通用搜索引擎不能或不愿 把这些信息加入网页索引数据库中。 作为互联网资源的一个重要组成部分，d e e pw e b 的规模十分庞大。u i u c 大学在 2 0 0 4 年4 月对整个d e e pw 曲做了一次估算【3 】，推测整个w e b 上大约有3 0 7 ，0 0 0 个 站点，4 5 0 ，0 0 0 个后台数据库，比b r i g h t p l a n e t 在2 0 0 0 年估计的5 0 0 ，0 0 0 个数据库 网站的数目增长了6 倍多。2 0 0 4 年1 2 月，b d g h t p l a n e t 公司最新调查表明，位于d e e p w e b 上的公用信息大约是s u r f a c ew e b 的4 0 0 到5 0 0 倍。其它研究者使用不同的假设 和估计方法，认为d e e pw e b 是s u r f a c ew e b 的5 8 到2 0 倍。2 0 0 8 年1 月c n n i c ( 中 国互联网络信息中心) 发布了第二十一次中国互联网络发展状况统计报告j ，报告显 示：截至2 0 0 7 年1 2 月，我国网民人数达到了2 1 亿，网站数量达1 5 0 万个，比去年 同期增长了6 6 万个，增长率达到7 8 4 。中国网页总数有8 4 7 亿个。年增长率达到 8 9 4 。这些网页中，动静态的比例为0 9 2 ：1 ，动态网页的比重在逐年增高。 另外，b r i g h t p l a n e t 公司的研究发现，d e e pw ，e b 整体质量至少l g s u r f a c ew e b 高 1 0 0 0 到2 0 0 0 倍，而且所包含的内容与每个信息需求市场和领域高度相关。据调查，9 5 的d e e pw r e b 信息是公开可获取的，不需要交费或订阅。由于d e e pw 曲资源内容与特 定专业领域具有高度相关性，因此对于大多数专业研究人员来讲，d e e pw e b 资源具 有s u r f a c ew e b 资源不可比拟的优越性。 d e e pw 曲包括的内容大多数为结构化的数据库信息，其内容更丰富，更专业。 7 第2 章d e e pw e b - 与模式匹配 d e e pw e b 模式匹配技术研究 在d e e p w e b 中，无数在线异构数据库通过各自的查询接口提供了基于动态查询的数 据访问，不同于静态的u r l 链接。比如：a m a z o n c o r n 网站，其后台服务器中存储着 图书信息的结构化数据库，它根据查询页面中用户输入的a u t h o r 、t i t l e 、s u b j e c t 等信 息查找用户所需的书，反馈给用户包含a u t h o r 、t i t l e 、s u b j e c t 等格式整齐的结构化的 信息页面。这些有价值的查询页面及结果页面就是由a u t h o r 、t i t l e 、s u b j e c t 等这些模 式构成的。因此在对d e e pw e b 的研究中，模式研究占有极其重要的地位。 2 2d e e pw e b 数据集成概述 面对纷繁复杂的w e b 数据库，用户为了获得所需信息，会遇到一系列的问题， 往往不知所措。比如，一个用户刚来到一个新的城市工作，他可能需要通过网络寻找 一些租房、找工作、买车等信息，那么他如何找到w e b 上的数据库，如何挑选出关 于房屋、工作和车的那些数据库，如何从某个领域( 比如，工作) 的成千上万的数据 库中找到一系列相对比较相关的w e b 数据库? 而且即使是在一类w e b 数据库中，每 个查询接口的设计也是不尽相同的，因此为了能正确地提交查询，他必须了解每个数 据库查询接口的填写细节；由于各数据库的内容存在一定的重叠，所以返回的查询结 果中必然有很多重复的数据，需要进一步的处理：然而各结果页面的设计存在很大差 异，没有明确的模式，合并和去重的过程也十分困难；经过上述这些步骤之后，才能 得到用户需要的结果。可见，整个过程非常复杂，仅仅依靠用户手工处理是非常烦琐 耗时的，因此迫切需要一种自动的方法帮助用户高效地完成这些复杂的工作，这也就 是d e e p w e b 数据集成的目标。 d e e pw 曲数据集成主要分为两个步骤【1 2 1 ，图2 1 给出y d e e pw 曲数据集成系统框 架。d e e pw e b 数据集成框架共分为两大模块：集成查询接口的生成和对集成查询接 口上查询的处理。集成查询接口生成模块：该模块整体的功能是在w e b 中发现w e b 数 据库并对其按领域进行分类，在每个分类上对所有查询接口集成，为用户提供一个统 一的查询接口，使之可以同时向多个实际的查询接口提交查询，即达到同时访问属于 同一领域的多个w e b 数据库的目的。该部分共有四个主要的子模块：w e b 数据库的发 现、查询接口模式的抽取、基于领域w e b 数据库的分类和查询接口集成。查询处理模 块：当用户在集成的查询接口上填写并提交查询，需要将该查询转化到对各个本地查 8 d e e pw e b 模式匹配技术研究第2 章d p w e b 与模式匹配 询接口的查询，提交后各个w e b 数据库会返回符合查询的结果页面，从这些结果页面 - 中将查询结果抽取出来并添加语义注释，由于各个w e b 数据库之间具有自主性和异质 性，因此所产生的结果数据格式也是各不相同，需要将这些格式各异的数据形成统一 的格式，最终得到可被自动处理的数据格式。该部分包括领域的映射、w e b 数据库的 选择、查询分派、结果抽取、结果注释、实体识别和结果合并7 个子模块。 l 期c q p 岫di n t o a c eg e n e r a t l o nm o d h i 址挪a z r o c e s s m 8 m o 出1 t 图2 - 1d e e pw e b 数据集成框架 在d e e pw e b 数据集成的查询处理中，将有以下四个方面涉及到模式匹配问题： 查询接口集成、集成的查询接口与各w e b 数据库查询接口查询转换中的属性匹配， 以及最后的结果标注和结果合并。 2 3 模式匹配问题 2 3 1 数据集成中的模式匹配 模式匹配一直是异构数据库集成领域的一个基础而又比较困难的问题。传统的模 式匹配的方法已经有一套比较完整的方法论和分类，而w e b 数据库的模式在特征上 与传统数据库的模式有很大的不同。w e b 数据库集成中的模式匹配有其自己的特点。 首先，传统数据库提供一套规范的模式定义语言，用来对数据库即将要存储的数 据逻辑结构和特征进行描述，不同的数据库只要了解它的模式就能够了解数据的数据 9 第2 章d e e pw 曲与模式匹配 d e e pw e b 模式匹配技术研究 类型、数据的结构、数据之间的关系。但是w e b 数据库无法提供对底层数据库模式 的直接定义，只能通过网页对底层数据库的描述进行推断，这些网页上的模式都只是 底层数据库的特定视图。 其次，传统数据库的数据是按一定的数据模型组织、描述和存储的，具有较小的 冗余度、较高的数据独立性和易扩展性，并可为各种用户所共享。但w e b 数据库却 不具备这些特点，它的数据一般由h t m l 语言定义，数据类型都反应了h t m l 网页 信息的特征，它来源于各种组织或个人，因而其没有固定的数据模型。 此外，w e b 数据库的数据内容和表现方式又处在动态变化中。 因此，w e b 数据库集成中的模式匹配比传统数据库的模式匹配难度更大，而且在 w e b 数据库集成的查询处理中有多个环节涉及模式匹配问题，其重要性可见一斑。如 图2 2 是w e b 数据库集成中查询处理所涉及到的模式匹配的示意图( 其中，各缩略 词含义为：i s ：i n t e r f a c es c h e m a ；r s ：r e s u l ts c h e m a ；g i s ：g l o b a li n t e r f a c es c h e m a ) 。 s c h e m am a t c h i n g o i n t e r f a c es c h e m av s i n t e r f a c es c h e m a g i o b a li n t e r f a c es c h e m av s i n t e r f a c es c h e m a r e s u l ts c h e m av s r e s u l ts c h e m a t m e r f a c es c h e m av s r e s u l ts c h e m a 图2 - 2 查询处理过程涉及到的四种模式匹配 查询接口之间的模式匹配( i sv s i s ) ：可以建立一个统一的集成查询接口； 集成查询接口与各w e b 数据库查询接口之间的模式匹配( g i sv s i s ) ：可以用于 将统一接口的查询条件匹配到相应w r e b 数据库的查询接口上； 查询结果之间的模式匹配( r sv s i 峪) ：可以对同一领域的不同w e b 数据库的返 回结果进行去重和合并，有效地集成结果信息支持用户的需求： 同一个网站的查询接口和查询结果之间的模式匹配( i sv s r s ) ：可以相互解释 1 0 d e e pw e b 模式匹配技术研究第2 章d e e p w e b 与模式匹配 彼此模式的语义信息，即为查询结果进行语义标注，进而有助于解决查询结果的合并 问题。 目前，在w e b 数据库集成中研究的主要是为生成集成查询接1 ：3 进行的查询接口 之间的模式匹配。本文也将就这方面的问题展开深入研究。 2 3 2 模式匹配原理 ， 随着计算机网络和数据库系统的迅速发展，信息资源的异构性在信息系统中无处 不在，越来越多的应用需要访问各种异构数据源。而为了达到异构数据源的共享，必 须首先解决数据集成问题。异构数据集成为异构数据源提供一个完整的数据源模式和 一致的访问接口，使用户不必考虑数据模型的异构性、数据抽取、数据合成等问题， 用户只需指定他们想要的数据，而不必描述怎样得到数据。模式匹配就是寻找两个或 多个模式的元素之间语义上的对应关系，由于在不同的模式中可能用相同的术语描述 不同的概念，或用两个不同的术语描述相同的概念，就会造成命名冲突：在不同的模 式中，用不同的抽象层去模型化相同的实体就会造成语义冲突；不同的模式中用不同 的方法描述相同的信息就会造成结构冲突。因此，模式匹配在异构信息源集成中是一 个困难而又关键的问题，已经受到普遍的关注。模式匹配是一个涉及机器学习、信息 检索等多个领域的复杂问题，现有的大部分模式匹配还是以人工方式为主，不仅费时， 而且要花相当大的代价。随着信息量的日益增多，人工方式的模式匹配的弊端日益明 显，迫切需要一些模式匹配的新思路。 模式匹配的过程通常结合一定的启发式规则，般没有严格的数学理论支持。 模式匹配的形式化描述如下【1 3 】： 模式匹配( s c h e m am a t c h i n g ) 定义为形如m a t c h i n g ( 1 1 ，1 2 ，a ) 的函数，其输 入、输出满足以下条件： ( 1 ) i l ( s l ，d 1 ) is l 为模式信息，d l 为满足模式s l 的数据实例) ； ( 2 ) 1 2 e s 2 ，d 2 ) is 2 为模式信息，d 2 为满足模式s 2 的数据实例) ； ( 3 ) a 为匹配过程需要利用的辅助信息( 包括词典、本体、人的判断信息等) ， 广义上可认为a 指所有可利用的能帮助更好理解模式语义并协助完成匹配任务的所 有辅助信息。 ( 4 ) 匹配函数执行过程中先产生模式元素间的候选对应关系集c c ( c a n d i d a t e l l 第2 章d e 印w 曲与模式匹配 d e 印w e b 模式匹配技术研究 c o r r e s p o n d e n c es e t ) ，经人工判断最终生成模式元素间确定的对应关系集d c ( d e c i d e d c o r r e s p o n d e n c es e t ) 并输出。c c 的形式化描述如式c c = 7 入，入r o ，1 ) 其中，s i l 指由模式s l 中i 个元素按简单语义规则书写的表达式， is li 为模式s l 的元素个数，若is li = m ，则i 1 - 1 ，m ，最简单的情形为i - 1 。 跏同s i l ，若is 2i = n ，则j 1 ，n 。s i m 为相似度，且s i m e o ，1 。入为相似 度阈值，是由用户指定的系统参数。只有s i m 一 入时， ( s i l ，s i 2 ，s i n 才并入集合 c c 。 2 3 3 模式匹配方法分类 匹配是一个模式操纵，它将两个模式作为输入然后返回在这两个模式中相应元素 的一个映射。模式匹配在许多应用程序中是一个重要的步骤：在电子商务里，帮助在 不同的 o d l 模式之间映射信息；在数据仓库里，将数据源映射成仓库模式：在中介 器里，辨别异构数据库之间的集成点。 一个模式由一组元素组成，元素可以是表、列、类、属性等。模式匹配问题是： 对于一个模式s l ( 比如全局模式) 和一个模式s 2 ( 比如数据源模式) ，在这两个模式的相 应元素之间找出某些语义上相同或相似的关系，由此产生s l 与s 2 的匹配关系。当前， 解决这些异构性问题的模式匹配一般是手工执行的。这个手工过程是冗长的、费时的， 容易出错，因而代价很高。这就需要一种劳动强度相对较小的方法。这样一种方法应 该对辨别关系提供自动支持，并且能够在源模式和全局模式之间生成映射。现存方法 的分类总结在图2 3 中。 模式匹配时可能会用到多种匹配方法( 匹配器) 。可以根据具体的应用要求灵活的 选用不同的方法及其组合。可以在