（计算机软件与理论专业论文）基于xml+schema的模式匹配研究与应用.pdf

中山大学硕士学位论文基于x m ls c h 锄a 的模式匹配研究与应用 基于x m ls c h e m a 的模式匹配研究与应用 专业：计算机软件与理论 硕士生：王永宾 指导教师：高集荣副教授 摘要 随着网络技术和信息技术的飞速发展，网上数据交换也越来越频繁。l 因具有可扩展性、跨平台性、自描述性等优点，逐步成为网上信息表达和数据交 换的事实标准。但是在享受蹦l 带来便捷的同时，由于删l 的标签可以自由 定制，数据交换面临模式不统一的问题，如何匹配不同模式文档中的信息，已成 为数据交换领域亟待解决的问题。 本文从研究模式匹配入手，分析现有模式匹配方法的优缺点，重点研究了基 于模式的匹配方法。在综合已有模式匹配方法的基础上，结合x m l 文档数据和 s c h e m a 的特点，本文提出了一种基于x m ls c h e m a 的模式匹配方法。首先，结 合l 的最新变化，在计算元素的语义相似时，采用提取元素的特征信息来计 算其相似度，而非单纯的字符串匹配。其次，本文重点研究了ls c h 锄a 的数 据类型，鉴于ls c h e m a 数据类型的特殊性，打破传统匹配方法把数据类型当 作约束信息对待的思想，着重研究了复合数据类型之间的相似，并提出一种计算 复合数据类型问相似的算法。c d t s ( c o n l p o u _ i l dd a t a t y p es i i 词撕劬。最后，在 研究元素结构相似性时，本文不仅考虑了孩子节点、祖先节点、兄弟节点的影响， 同时还考虑了这种特性的传播特点。本文借鉴s i m i l 撕够f 1 0 0 d i n g 算法思想，提 出一种新的结构相似算法一s s f ( s 咖c t u r a ls i n l i l 撕够f 1 0 0 d i n g ) 计算元素的结构 相似度。 最后，本文从实践角度出发，通过实验和对比分析，验证了算法的高效性。 并且通过一个实际的例子，应用本文算法介绍了转换l 文档的整个流程。 关键字：模式匹配；ls c h e m a ；相似度；自动匹配 中山大学硕士学位论文基于x m ls c h 咖a 的模式匹配研究与应用 t h er e s e a r c ha n da p p l i c a t i o no fs c h e m am a t c h i n g b a s e do nx m ls c h e m a m 旬o r ：c o m p u t c rs o 胁a r ea l l dt h e 0 d r n a m e ：w a n gy o n 曲i n s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rg a oj i l o n g a b s t r a c t a l o n gw i t ht l l er a p i dd e v e l o p i n e n to fn e t w o f ka 1 1 di n f o m a t i o nt e c l l l l o l o g y m o r e a n dm o r ed a t ae x c h a n g e so nn e 咐o r k w i mt h ec h a r a c t 耐s t i c so fe x t e l l s i b i l i 劬 c r o s s - p l a t f o m l ，s e l f d e s c r i p t i o no t h e rm e r i t s ，x m lh a sb e c o m em ef a c m a ls t a i l d a r do f t h ed a t ar 印r e s e n t a t i o na n de x c h a l l g ei i lt 1 1 ew 曲w h e i le n j o ) ，i n gm ec o n v e m e l l c e b r o u 曲tb y l ，w ea l s of a c et l l ep r o b l e mo fd i s u i l i t yo fs c h e m 勰t h e r e f o r e ，h o wt o m a tc _ hd i 筇巳i l ts c h e m ad o c u m e l l t si n f 0 肌a t i o nb e c 0 m 懿t l l eu r g e n tp r o b l 锄i i l 1 e d a t a - c x c h 距g ed o m 血 h lm i sm e s i s ，w es t u d ym em e t h o d so fs c h e n l am a t c l l i n g a n a l y z i i l gn l em 酬d s o fs c h e m am a t i c l 痂吕a n dc o n l b i i l i n gw i t ht 1 1 ed a t a 臼面to f ) a ld o c u m 朗t sa i l d ) a l s c h e m ad l a m c t e 打s t i c s ，w ep r o p o s ean e wm e t l l o do fm a t c l l i n gs c h e m ab a s e do nm e 删ls c h 锄a 趾d0 u r 咖d y f i r s t l y i 1 1v i e wo f 捌ll a t e s tc h a i l g e s ，w h e i lc o m p u l ：i i l g e l e m e n ts e m 枷c ss i i i l i l 撕坝w ee x t r a c te l e m e n t sl 锄m a ss e tt 0c a l 砌a t ei t s s i m i l 撕够s e c 0 n d l mw es 昀s so nt l l es t i j d yo f x m ls c h e m ad a t at y p ep 枷c u l 撕坝w r e b r e a km ef 0 肌e ri d e at t l a tr e g a r d sd a t at y p ea sr e s t r i c d v ei n f o m a t i o 玛a l l dp r o p o s ea n a l g o r i t l 吼( c d t s ) t 0c 0 1 1 1 p u t et l l ec o m p o u i l dd a t at ) ，p l es i i l l i l 砸吼f i 砌l mw h e i l s t u d ) ，i n ge l e m e n ts 仇】c t u r es i n ：l i l a r i 坝w e1 1 0 t0 1 1 1 yc o l l s i d e rm e i i l n u e n c eo fe i l i l d r e i l i l o d e s ，锄c e s t o rn o d e sa n ds i b l i i l g1 1 0 d 鹤，b u ta l s oc o n s i d e f 吐l ep r o p a g a t i o no fm i s e 腩c t h lv i e wo fn l ef 1 0 0 d i n ga l g 耐t l 蚰i d w ep r i ) p o s e 锄a l g 硎t l 瑚o fs s f ( s t n l 咖a ls i m i l 撕t ) rf l o o d i n 曲t 0c a l 饥1 a t em ee l e i i l 饥ts 舡u c t u r a ls i m i l a r i 够 h lm ee i l d ，w ep r 0 v em a t 恤m e m o dp r o p o s e di nn l i st l l e s i si sh i 削ye 虢以v e m r o u g l le x p 酬m e i l t a la i l a l y s i s a n dw ei i l 昀d u c e l cw h o l ep r o c e s so fs w i tc ! l l i n g x m ld o c u m e n tb yar e a lw o d de x 锄p l e k e y w o r d s ：s c h 锄am a t 出略删ls c h 锄s i l i l i l 撕嗷a u t 0 - m a t 出n g l 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 王款凄 日期：砌脾妇莎日 使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名： 王宓0 胃 日期：加o x 年留月寥日 中山大学硕士学位论文基于x m ls c h a n a 的模式匹配研究与应用 1 1 研究背景 第1 章绪论 随着网络和信息技术的发展，企业内部与外部联系越来越紧密，甚至融为一 体，这种变化深刻地影响着企业的组织结构，这不仅反映在企业内部的业务流程 中，而且影响着企业如何与客户、合作伙伴、供应商、分销商等进行的商务活动。 面对快速变化的市场条件，当今的商务活动必须以快度、高效与灵活的策略去应 对，这就需要各个企业的业务系统相互协作，交换数据，实现业务流程的协同和 业务信息的共享。 数据交换是企业应用集成解决方案中最简单和最直接的途径，目前已在企 业、政府和教育部门得到了广泛的应用。数据交换的目的是屏蔽企业之间或部门 之间的业务系统在硬件平台、操作系统、网络协议和数据源等方面的差异，实现 不同实体之间的信息共享与交换。目前数据交换技术正在发生着变化，以前的数 据传输多采用传统传输协议，如f t p 、e m a i l 等，或专用的传输接口、分布式组 件方式，如d c o m e j b 、r m i 、c o r b a 方式实现数据的共享和交换，现在，随 着网络技术的发展，特别是以煳l 为信息载体的数据交换体系的构建，很多领 域的数据交换格式都采用了x m l 数据格式。由于l 可以实现数据内容和数 据样式的分离，并且允许在其文档中内嵌数据的逻辑结构信息，提供结构化的数 据，同时加之l 的其它特点( 如可扩展性、自描述性、跨平台性等) 都使得订l 在数据交换中得到广泛的应用。l 标准一经制定，就得到了使用者的认可， 现在，诅l 已经成为网络上信息表达和数据交换的事实标准。 x m l 给数据交换带来了便捷，但是随着应用的深入也遇到很多问题。如果 信息交换双方都遵循相同的模式规范，那么实现它们之间的数据交换比较容易。 但事实上，由于x m l 对其数据的格式要求很低，加之) a l 的开放性，不同的 开发人员在使用煳l 开发应用时制定的文档模式不尽相同，大量煳l 模式的 制定和应用，使得数据交换变得比较困难，目前，如何理解、识别和匹配这些定 义的模式成为数据交换领域的一个难点。x m l 数据转换就是给出两个讧l 文 档数据( 相关的数据) ，发现它们元素之间的对应关系，通过这个对应关系表把一 中山大学硕士学位论文基于x m ls c h 锄a 的模式匹配研究与应用 个模式中的信息转换为另一个模式中的信息，而寻找元素对应的过程就是匹配文 档元素的过程，也是模式匹配的一种应用。 目前，l 模式元素的匹配和转换通常是人工手动完成的，一方在接受到 对方发来的数据后，通过人工发现元素之间的对应关系，然后手动编写x s l t 转 换文件，完成数据交换的目的。或者，事先双方把自己的数据模式告诉对方，把 元素对应关系写进代码，由程序自动完成，但是一旦一方要改动数据的结构，双 方都要去更改应用程序，可见，这种方法在未来应用的范围是很狭窄的。所以如 何能够实现x m l 文档之间的自动匹配，是一个亟待解决的问题。 1 2 国内外研究现状 由上面的分析可以知道l 文档之间的转换，最为关键的是找出x l l 文 档模式中元素之间的匹配关系，有关模式匹配的研究早在上个世纪8 0 年代就已 经开始，不过早期的模式匹配工作多集中在数据集成领埘啦 3 】。进入九十年代， 随着模式集成问题的发展和变化，模式匹配开始应用于数据仓库中【4 】。最近二十 年，特别是由于电子商务和网络技术的快速发展，进一步推动了模式匹配的研究。 有关模式匹配的研究多集中在国外，研究也主要集中针对某一具体应用的研究 【5 ，6 ，文献【8 9 ，1 0 ，1 1 1 中给出了几种通用的模式匹配的方案。随着x m l 数据库的提 出，有关关系数据模式与l 数据模式的转换【1 2 1 3 ，1 4 ，1 5 】也成为一个热点。 本文重点研究x m l 文档之间的转换，目前针对x m l 数据模式之间的转换 的研究还不是很多。虽然以前的比较成功的模式匹配系统经过改进可以处理 x m l 文档之间的转换，例如，d i k e 【4 】，c u p i d 9 】，t r 趾s c m 【1 6 1 ，s e m i n t 【1 7 1 系统 等，但是它们在处理分层的订l 数据时，效果比较差，其主要原因有： 1 模式信息挖掘不足 元素模式信息是模式匹配中发现元素之间的对应关系的重要信息，其主要包 括元素的名称、元素数据类型，约束类型和邻居项等。由于应用领域或设计者理 解的不同，模式中的名称即使是表示相同的意思也会有很大的差别。在比较元素 名称时，有些系统仅判断两个名称的相等关系，而没有考虑到同义词、缩写，以 及对同形异义词的处理，例如，l s d 【1 8 1 仅使用了相等和同义词关系，d i k e 【4 】中 也没有对缩写和首字母大写词进行处理。对于结构相似的比较各系统的粒度也不 2 中山大学硕士学位论文基于x m ls c h 啪a 的模式匹配研究与应用 同，多数系统没有充分考虑周围元素信息的影响。 2 缺乏对复杂匹配的研究 不论是对关系数据模式还是l 模式以及其它形式的独立文档来说，目前 的很多系统只是能处理简单匹配，即l ：l 匹配，缺乏对复杂匹配的研究，如1 ：，l 匹配、刀：l 匹配、玎：研匹配，更难自动实现复杂匹配表达式的寻求，如n 锄e = c o n t a c t ( 伍s 饿锄e ，l 弱烈锄e ) ，这也是目前研究的一个难点所在。 3 难以应付大数据处理 随着模式匹配应用范围的扩大，以及应用规模的不断提高，现有的模式匹配 算法及模型很难适应大规模数据量的处理，尽管模式匹配对性能的要求不是很 高，但是随着数据量的增大，如何提高模式匹配的效率也是最近研究的一个热点， 特别是随着大规模x m ls c h e m a 的出现。 4 缺乏对已处理的映射重用，用户信息反馈利用不高 在已有的匹配系统中主要的辅助信息和重用支持的形式有数据字典、术语表 以及一些专用的匹配知识说明。而对于已经产生的匹配结果的重用支持还没有提 供。例如，“r e p o n s t 0 = m a i l a g 盯这样的匹配在之前的匹配操作中已经出现过， 或这样的匹配通过人工调整产生过，则在同类匹配过程中可以直接使用，而不需 要再次经过复杂的匹配计算。 针对订l 模式匹配的研究，国内外研究者也提出了很多解决方法。t 捌a l ， c 1 a y p 0 0 l 等提出一种q m a t c h 【1 9 1 算法，该算法重点研究了如何计算语义相似和结 构相似。h o n g 1 l a id o ，e r h a r dr a l l m 的c o m a 【2 川方法提供一种动态组合各类匹 配算法结果。s h a n 吐y i ，b oh u 锄g 在文献【2 1 】中提出一种松弛标签法( r e l a x a t i o n l a b e l 蛐匹配思想。文献【冽中提出一种m 旧l s - b a s e ds i i i l i l 撕t ) ，算法，该算法应 用人工智能技术，在半监视策略下训练数据，针对大规模的模式匹配。在研究规 模比较大的模式间的匹配时，文献【2 3 刀，2 5 2 6 】中提出模式可以先对模式进行聚类， 并就如何聚类做了详细的介绍。h o n 分h a id o ，e r h a r dr a l l m 还在文献【2 7 】中介绍了 如何匹配l a r g ex m ls c h 锄鹊，提出片段匹配的概念( f r a 舯e n tm a t c h i l l 曲。文献 【2 8 2 9 1 中提出基于本体( o n 幻l og ) i b 鹤e d ) 操作的思想解决复杂匹配的方法。在研究 l 结构相似时u c o l 【3 0 】提出要考虑元素的孩子节点、兄弟节点和孩子节 3 中山大学硕士学位论文基于x m ls c h 锄a 的模式匹配研究与应用 点。乔健，陈彤兵在文献【3 i 】中提出一种基于结构索引的匹配方法。在重用已匹 配信息时，文献【3 2 】中提出利用复制节点，文献【3 3 】中提出c o r p u s - b 嬲e d 方法。文 献【3 4 】中研究了d t d 和x m l 实例文档之间的转换。c a n l l e ld o m s h l a l ( ，a v i 酣o rg a l 等在文献【3 5 】中给出几种聚集不同模式匹配结果的算法：t aa 1 9 0 r i t l l i n ，m d a 1 9 0 r i m m ，m d ba 1 9 0 r i t h m 。以上成果对研究如何自动转换不同模式的x m l 文 档都有很大的参考和借鉴意义。 1 3 论文的主要工作 本文重点研究x m l 数据文档之间的转换技术，首先分析现有模式匹配方法 的优缺点，重点研究了基于模式的匹配方法。在综合已有模式匹配方法的基础上， 结合订l 文档数据和s c h e m a 的特点，特别是针对x m l 文档特殊的数据类型 定义和分层的文档结构，本文提出了一种基于x m ls c h e i i l a 的模式匹配方法。 本文的主要工作包括以下几个方面： 1 ) 研究数据交换技术的发展现状，重点研究基于x m l 的数据交换技术和 x m l 自身的特点，分析已有的模式匹配技术和方法，总结各自实现方法、 应用范围及它们的优缺点。 2 ) 在计算模式元素语义相似性时，结合删l 的最新变化，提出采用提取 元素的特征信息的方法计算元素的语义相似，而非单纯的字符串匹配。 3 ) 提出一种计算复合数据类型相似的算法。订ls c h e m a 的数据类型不同 于其它数据格式的数据类型，s c h 锄a 支持用户自定义数据类型，数据类 型派生机制也比较复杂，所以以往简单利用静态赋值判断数据类型相似 的方法是不可取。 4 ) 提出一种新的计算元素结构相似的算法s s f ( s 仃u 删s i m i l a r i 够 f l o o d i n g ) 。在以往的结构相似算法中只是简单的考虑了元素邻居项的影 响，本文借鉴s 碱l 耐够f l o o d i n g 算法思想，不仅考虑了邻居项的影响， 还考虑了这种特性的传播特点，提高了元素结构相似的区分度。 5 ) 结合以上研究成果，提出了一种转换x m l 文档的方法，并通过实验验 证了这种方法的高效性。最后通过一个实际应用的例子说明了整个转换 l 文档的过程。 4 中山大学硕士学位论文基于x m ls c h 锄a 的模式匹配研究与应用 1 4 论文的结构组织 本文共六章，其内容安排如下： 第一章绪论，介绍问题的研究背景和目前数据交换领域的发展情况，并重 点分析了l 模式匹配的研究现状，最后给出本文主要工作和结构安排。 第二章煳l 与模式匹配，简单介绍了x m l 语言的特性以及其相关技术， 例如，x p a t l l 、d o m 、s a x 等。接着介绍了模式匹配的相关概念及其分类方法， 并给出模式匹配的形式化定义，为进一步的研究奠定基础。 第三章x m ls c h 锄a 匹配研究，这是本文的重点，首先介绍了几种研究基 于) ( 1 ls c h e m a 的模式匹配方法，接着结合ls c h e m a 的特点，分别研究了 删l 元素的语义相似和约束相似，在研究x m ls c h 锄a 数据类型的相似时，提 出区分看待内置类型与用户自定义的复杂数据类型，并给出计算复合类型的相似 度的一种算法。最后借鉴s i l i l i l a l l yf 1 0 0 d i n g 算法，提出一种新的结构相似性算法 s s f ( s 仃u c t u r a ls i m i l 撕够f 1 0 0 d i n g ) 。 第四章模式匹配设计与实现，在这一章中，基于前面的分析，形成一个完 整的实现自动模式匹配的算法模型，并对算法中的重点模块做了详细说明，重点 算法还给出了其伪码表示。 第五章实验与结果分析，在这章中，对本文提出的模式匹配算法做了实验 验证，从对比分析的结果上，可以看出本文算法的优越性。最后，简要说明了如 何应用匹配算法实现l 文档的自动化转换。 第六章结束语，总结全文，并就如何更进一步研究做了展望。 1 5 本章小结 本章主要介绍了数据交换的发展现状，阐述了订l 在未来数据交换领域的 地位，指出v i l 文档之间的匹配是未来数据交换中的一个难点，接着重点介绍 了国内外模式匹配的研究现状，并分析了现有模式匹配方法解决l 文档匹配 存在的问题及不足，最后介绍了本文的主要研究内容和论文的组织结构。 5 中山大学硕：f ：学位论文基于x m ls c h 锄a 的模式匹配研究与应用 第2 章x m l 与模式匹配 2 1x m l 技术 2 1 1x m l 语言 x m l ( e x t e n s i b l em a 曲pl a l l g u a g e ，可扩展标记语言) 是w 3 c 于1 9 9 8 年推 出的一种用于数据描述的元标记语言的国际标准。l 是一套定义语义标记的 规则，这些标记将文档分成许多部件，并对这些部件加以标识。它是 s g m l ( s t a l l ( 1 a r dg e n e r a l i z e dm a r k u pl a i l g u a g e ，标准通用标记语言) 的一个简化子 集。但由于s g m l 文档过于冗余，仅语法说明就5 0 0 多页，应用实施不方便。 x m l 继承了s g m l 的许多优秀特性，也形成自己的一些特色，具有如下【3 6 】。 1 可扩展性 l 是设计标记语言的元语言，而不是像h t m l 那样，只有一些固定标记 集的特定的标记语言。而是如使用面向对象语言编写程序一样，使用者声明他们 自己的类，l 也允许使用者创造和使用自己的标记，而不是使用有限词汇表。 可扩展性是至关重要的，企业可以用删l 为电子商务和供应链集成等应用定义 自己的标记语言，甚至可以在特定的领域定义该领域特殊的标记语言，为创建在 该领域内的信息共享与交换打下基础，例如，数学界的m a t l l m l 。 2 灵活性 h t m l 发展很慢，主要因为它的格式、数据、超文本和图形用户界面语义标 签是混合在一起的，随着数据量的增加和显示多样化的发展，要同时提高这些混 合在一起的功能是非常困难的。而剐l 提供了一种结构化的数据表示方式，使 得用户界面的显示信息与结构化数据信息分离，在x m l 中，可以使用样式表 x s l ( e x t e i l s i b l es t y l es h e e tl a l l g u a g e ，可扩展样式表语言) 和c s s ( c a s c a d i n gs t y l e s h e e t s ，层叠样式表) ，将数据呈现到浏览器中。 3 自描述性 6 中山大学硕士学位论文基于x m ls c h 锄a 的模式匹配研究与应用 订l 文档通常包含一个文档类型声明，从而使得x m l 文档是自描述的， 不仅人能读懂x m l 文档，计算机也能处理。x m l 文档中的数据可以被任何能 够对l 数据格式进行解析的应用程序所提取、分析、处理，并以所需格式显 示。v i l 表示数据的方式真正做到了独立于应用系统，并且使得数据能重用。 所以l 适合开放的信息管理。 4 开放性和跨平台性 x m l 是w 3 c 正式批准的，x m l 的相关标准也是完全开放的，可以免费获 得，并且x m l 自身也是开放的，任何程序都可以对一个良构的x m l 文档进行 解析，从而获取其中的数据信息，并且l 还提供数据模式的验证。同时x m l 由于是s g m l 的子集，有与生俱来的跨平台特性，可以在各种平台上使用，并 且支持多种字符编码。近来不同平台相互交换信息的要求不断高涨，为x 1 l 的 发展带来契机。 除上述特征外，l 还具有简明性。它只有s g m l 的约2 0 的复杂性，但 具有s g m l 提供的约8 0 的功能3 6 1 ，同完整的s g m l 相比，) 洲l 简单得多， 易学、易用、易实现。同时，煳l 的诞生吸收了人们多年来在w 曲上使用h t m l 的经验。所以，正如h t m l 开辟了一种计算机用户能浏览文档的途径，l 也 将会成为未来网络读、写信息的世界语，为未来的数据交换带来新的机遇。 2 1 2 舭数据模式 由于x m l 具有可扩展性的特点，) a l 文档的创建者可以自由定义文档的 数据结构以及元素其它信息，虽然这给文档的制作提供了很大的灵活性，但也使 得不同应用的数据交换变得困难起来。) a l 模式就是为了确保l 文档的有 效性而提出的，并可以为数据交换建立一个标准。l 的有效性是指v i l 文 档中的数据要符合特定的规则，比如哪些元素是必需的，哪些是可选的，等等。 目前应用最广的两种x m l 数据模式语言是文档类型定义( d o 咖e n t 聊e d e 觚t i o n ，d t d ) 和x m ls c h e m a ( x m l 模式大纲) 。 d t d ：它是随着x m l l o 标准提出的一种l 模式语言，它可以准确地定 义x m l 文档实例的词汇表，可以精确地定义x m l 文档实例的结构、确定文档 的元素、元素的数目、元素的排列次序、元素的属性等，由此形成一种有效的验 7 中山大学硕士学位论文基于x m ls c h 锄a 的模式匹配研究与应用 证机制，保证x m l 文档实例符合一定的模式。d t d 文档可以是x m l 的一部分， 但通常是一份单独的文档或一系列文档。 x m l s c h 锄a 【3 7 】x m l s c h e m a 在2 0 0 1 年5 月正式成为w 3 c 的推荐标准， 它提供了创建删l 文档的必要的框架，详细说明了一个l 文档的不同元素 和属性的有效结构、出现次数限制和数据类型等。x m ls c h e m a 不像d t d 使用 特殊的语法，它本身就是用x m l 来写的。并且x m ls c h 锄a 提供了更丰富的数 据类型，功能更强大，而且使用灵活，以下是两者的对比。 1 ) 在语法方面：d t d 的语法是用巴斯科范式( e x t e n d e db a c k u s n u a rf o m ， e b n f ) 定义的，较难理解，而x m ls c h e m a 本身就是用x m l 写的，使 用者不需要学习新的语法和相关规则来创建模式，因而x m ls c h e m a 本 身可以用处理x m l 工具进行操作处理。 2 ) 在数据类型的支持方面：d t d 对数据类型的支持不够，所定义的数据类 型有限，无法满足未来应用所需要的数据类型，而s c h e m a 比d t d 的能 力强得多，它不仅提供丰富的内置数据类型。例如，s t r i n g ，b o o l e a n ， d a t e l h e ，n u m b e r ，n o a t 等，还支持用户定义自己的数据类型。 3 ) 在对内容模型的支持方面：d t d 只允许限制文档元素的次序及哪些元素 可选择，不能验证混合内容模型( 既包含字符数据又包含其它标记的元 素) ，文档元素不能规定数字或范围限制。而x m ls c h e m a 考虑到了更 复杂和灵活的内容模型，以上d t d 不支持的特性x m ls c h e i i l a 都支持。 例如，可以制定某一元素出现的次数范围。 4 ) 可扩展性方面：d t d 本身不是可扩展的，而x m ls c h e m a 则不然。例 如，ls c h 锄a 支持在另一个订ls c h e m a 中使用这个x m ls c h e m a 部分功能的能力，支持从己有的数据类型出发定制自己的新数据类型的 能力，以及在一个文档实例中引用多个模式的能力等。 2 1 3x m l 解析 在处理v i l 文档数据时，应用程序并不是直接对其进行操作的，而是首先 利用解析器对l 文档进行解析，然后，应用程序通过解析器所提供的接口， 通过访问接口实现对煳l 文档的访问。如何解析x m l 文档，w 3 c 给出了解析 8 中山大学硕士学位论文基于x m ls c h 啪a 的模式匹配研究与应用 规范，即对文档操作时要遵循的应用编程接口a p i ( a p p l i c a t i o np r 0 伊a i i 吼i n g 蛐c e ) ，可以使用不同的技术实现这些接口。目前比较流行四种实现的煳l 应用编程接口如下【3 6 】。 1 d o m o c u m e n to b j e c tm o d e l ) ：文档对象模型( d o c u m e n to b j e c tm o d e l ) 是公认的w 3 c 标准，它提供了一套应用程序接口( a p d ，为创建、处理和操作 l 文档内容、结构和样式提供了灵活而有效的方法。d o m 是一个基于树型的 解析技术，它在内存中构建起一棵完整的解析树。它可以实现对整个垤l 文档 的全面、动态访问。使用d o m 解析模型的优点是编程容易，开发人员只需要调 用建树的指令，然后利用i l a v i g a t i o na p i s 访问所需的树节点来完成任务。然而由 于使用d o m 解析时需要处理整个l 文档，所以对性能和内存的要求比较高， 尤其是遇到很大的v i l 文件的时候。 2 s a x ( s i l i l p i ea p i f o rx m l ) ：s a x 解析x m l 数据是基于事件的框架，即 扫描整个文档，将数据拆解成几个有用部分的一种处理方式。与d o m 相比，s a x 解析技术提供更佳的性能优势。它提供了对l 文档内容有效的低级访问。s a x 模型最大的优点是内存消耗小，另外，因为整个文档无需一次加载到内存中，这 使得s a x 可以解析大于系统内存的文档。当然，s a x 也有缺点，即在使用时用 户必须实现处理所有到来事件的事件处理程序，必须在其应用程序代码中维护这 个事件的状态。 3 m o m ：j d o m 是基于j a v a 技术的开放源码项目，它试图遵循8 0 2 0 规则， 用d o m 和s a x2 0 的功能来满足8 0 的用户需求。其目的是要成为j a v a 特定 的解析l 文档的模型。j d o m 与d o m 主要有两方面不同。首先，j d o m 仅 使用具体类而不使用接口，这在某些方面简化了a p i ，但是也限制了灵活性。其 次，a p i 大量使用了c o l l e c t i o n s 类，简化了那些已经熟悉这些类的j a v a 开发者 的使用。 4 d o m 4 j ：d o m 4 j 是j d o m 的一种智能分支，它合并了许多超出基本订l 文档表示的功能，包括集成的a t l l 支持、ls c h e l i l a 支持以及用于大文档或 流化文档的基于事件的处理。它还提供了构建文档表示的选项，通过d o m 4 ja p i 和标准d o m 接口具有并行访问功能。d o m 4 j 是一个非常优秀的j a v a 讧l a p i ， 具有性能优异、功能强大和极端易用使用的特点，同时它也是一个开放源代码的 软件。表2 1 给出它们之间区别。 9 中山人学硕士学位论文基于x m ls c h e t i l a 的模式匹配研究与应用 表2 1d o m 、s a x 与j d o m d o m 4 j 的比较 d o m s a xj d o m d o m 4 j 处理方式基于树 基于事件 基于树 读入文档方 整个文档，并在内存 流式，不在内存中建 整个文档，并在内存中 式 中建文档树文档树建文档树 访问方式随机顺序随机 速度慢快较快 内存需求大小中 处理功能 强大简单强大 接口级别高级 低级高级 支持语言 各种编程与脚本语言 j a v a 、c + + 、p y t l l o n只能j a v a 等编程语言 适用文档的结构化随机处 ( 大型) 文档的简单顺文档的结构化随机处理 理序处理 2 1 4 其它相关技术 x s l t 技术 x s l t 【3 7 】是由x s l ( e x t e l l s i b l es t y l e s h e e tl a n g u a g e ) 发展而来的，x s u 是一种 基于l 的语言，它提供了一种转换和操作l 数据的机制。x s l t 是基于 w 3 c 标准的，它同x p a m 标准紧密结合，致力于网络数据库的开发工作。x p a t h 用于指定需要进行转换的内容，而x s l t 则提供了描述如何实现转换的相应的互 补语言。x s l t 样式表描述了将源x m l 文档转换为结果x m l 文档的一系列的规 则，通过x s l 处理器即可完成基于这些规则的转换过程。x s l t 可以获得l 文档的内容，并且可从字面上将它转换成其它的内容，也可以选择要显示的内容， 添加内容，或者重新排列内容等。同时x s l t 文档本身是格式良好的x m l 文档， 可以应用处理x m l 文档的工具来处理x s l t 文档。 x p a t h x p a m 是第四代声明式语言【3 刀，它是w 3 c 由创建，并于1 9 9 9 年1 1 月1 6 日 和x s l t 一起成为正式标准的。它的主要作用是如何对一个瑚l 文档中的节点 进行定位，为了支持这个主要目的，它也为操纵字符串、u r i 和删l 属性里的 数值和布尔值提供了一些基本的功能。x p a m 使用一种紧凑的、非x m l 的语法， 以方便在u r i 和删l 属性值中使用，它是基于l 文档的抽象和逻辑结构进 l o 中山大学硕士学位论文基于x m ls c h e l l l a 的模式匹配研究与应用 行操作，而不是在它的表面语法上。x p a t l l 把一个l 文档作为一个节点树， 树中每个节点都可以通过详细的描述该节点在树中的位置进行存取操作。x p a m 使用类似于的路径表示法，例如，r o o t b o o k 【1 】表示选择以r o o t 为根节点的其第 一个b o o k 子元素的x p a n l 表达式。 x q u e r y x q l l e r y 最初称为州l t 。q u i l t 【3 8 1 最初作为用户级语法的测试工具，是由 j o n a t l l 妣i 沁b i e 、d o nc h 舡n b 甜i i l 和d a l l i e l af l o r e s c u 创建的。目前，x q u e r y 是 w 3 c 所制定的一套标准，用于从类x m l 文档中提取信息，类煳l 文档可以理 解成一切符合x m l 数据模型和接口的实体，它们可能是文件或r d b m s 。x q u e 巧 对x 】l 数据源的查询，具有精确、强大和易用的特点。对x q u e r y 语言标准的 定义工作已经于2 0 0 7 年初完成，版本为1 o 。 2 2 模式匹配 2 2 1问题研究 所谓模式s 中的元素j 与模式t 中的元素f 匹配( 对应) ，是指相对于某一应 用p 来说，当j 和f 分别作为这个应用的输入时，其运行结果p ( s ) 和p ( t ) 在某种 意义下是等价的或相似的。表2 2 给出了两个模式的信息，要查找c l i e n t 模式中 的某个元素与c 缸t o m e r 模式中的某一个元素在语义上是对应的，其实就是要找 到一个映射，这个映射可以用一个表达式来说明它们之间的关系，如映射元素m 把c l i 饥t 模式中的i d n 曲e r 元素映射到c u s t o m e r 模式中的d 元素，可以用表 达式m ( 傩绷f 肭6 盯) 兰c 妇f d m 仃j d ，而对于整个模式s 与t 来说的匹配就 是要找出它们之间所有元素的对应关系，使得模式s 和t 中的每个元素在逻辑 上存在着对应关系。 表2 _ 2 不同的客户信息表示 c 1 i 锄tc u s t o m e r 埘m 妇d f r i s l n 锄en 锄e l 鹤t n a m e t e l 印h o n e c t e l e m a i l c e m a i l 中山大学硕士学位论文 基于x m ls c h 锄a 的模式匹配研究与应用 从上面的分析可以看出模式匹配的目标：给定两个模式s 和t ，对s 中的每 个元素s ，利用所有可用信息( 包括模式信息、数据实例以及用户反馈信息等) 在t 中找到与s 在语义上最匹配的元素f 。考虑到模式匹配是具有个人的主观性的， 从模式中可能并不能完全得到它们所描述数据的含义，在两个模式间的匹配可能 有多种理解。鉴于这种主观性，使得用户干预是有必要的，用户可以通过输入来 指导匹配以及最终决定匹配结果的有效性。这种指导可能通过初始化匹配，数据 字典或是信息积累，已知匹配库，等等。因此，模式匹配目标可进一步概括为： 给定两个任何数据模型的输入模式、辅助信息和输入的映射，在两个模式的元素 之间计算出一个映射关系，并能通过用户的有效性验证。 造成数据模式之间差异的原因多种多样，分析与找出其中的原因可以在模式 匹配研究中应用适当的方法发现语义上匹配的元素。本文按照造成数据模式差异 的原因不同，将其总结为如下几种情况： 1 ) 不同的数据模式中采用不同的数据模型描述问题。例如，源数据模式用 面向对象数据库描述，而目标模式采用关系数据库或x m l 数据库描述。 2 ) 不同的数据模式中可能使用相同或相近的术语描述不同的概念，或者用 两个不同的术语来描述相同的概念，或者用不同的语言种类描述同一概 念，例如，y b s ”，n o ”与“是”，“否”。 3 ) 在不同的数据模式中，由于描述信息的粒度不同，存在着语义冲突。例 如，某个局部数据源数据模式中描述了“m a l e ”和“f e i i l a l e ”信息，而在同 一集成系统中的另一个局部数据源的数据模式中却只简单地描述为 “p e o p l e ，不区分它们的性别信息。 4 ) 不同的数据模式用不同的方式描述相同的信息。例如，某一事物在一个 数据模式中用属性来描述，而另一个则用实体或称为元素来描述。 5 ) 不同的数据模式模式创建者使用的标签的数量不同或位置不一致，例 如，在一个数据模式中存在的实体或属性，在另一个数据模式中不存在 或者所在的位置不同。 2 2 2 形式化定义 上以小节只是从语言层面上讨论的最简单匹配问题，也是最基本的一种匹 配，即1 ：1 匹配。在模式匹配问题中还有几种匹配，也称为复杂匹配，即：1 ：，l ， 1 2 中山大学硕士学位论文基于x m ls c h 锄a 的模式匹配研究与应用 刀：1 ，以：聊等，例如，在表2 1 中c o n c a t e i l a t e ( c 1 i e n t 蹦s t n 锄e c l i e n t l 嬲t n 锄e ) 兰 c 抛t ( ) m e r n a m e 。 在这一节中，为了研究的需要，给出匹配的形式化定义，在给出形式化定义 之前，首先介绍下面几个概念： 1 ) 用户解释 用户解释是指用户对数据模式中的元素在其应用的问题领 域的一种解释，或一种表示。例如，元素a d d r e s s 根据用户在不同的问 题域就会有不同的解释，在公司交易时，a d d r e s s 很可能表示公司的地 址；在户籍管理问题上，a d d r e s s 元素则可能表示户主的家庭住址。 2 ) 问题域q ：问题域是指当前元素应用的这个领域内的所有的词汇元素的 含义的集合。 3 ) 映射矽：是指在模式s 中元素p l 通过影射矽，使得p i 在用户的解释， 下矽( p 。) 兰吃，具体的相似程度有相似函数给出。 4 ) 相似函数跏伍力：相似函数是用来计算不同模式中两元素的相似程度 的，有关如何计算两者的相似在下一章将重点讨论，其值域是 o ，1 】。 【定义2 1 】1 ：1 匹配：设给定模式s 和t ，给定问题域q 和阀值万，对于模 式s 中的任意s 元素和模式t 中某个元素f 满足： 协s ，了f r ，p 罗，尹j = 熨聊( 矽( s ) ，f ) 万 也就是说元素s 通过映射痧，使得元素s 与f ，在给定问题域和用户解