（模式识别与智能系统专业论文）模式匹配的泛代数描述及算法研究.pdf

上海交通大学博士学位论文 模式匹配的泛代数描述及算法研究 摘要 模式是数据库应用中的一类特定的元数据模型，是实现异构数据和应用 系统互操作中不可缺少的基本元素。对于模式，最基本的操作就是匹配，其 目的在于获得模式元素之间的对应。模式匹配在许多数据库应用中起到关键 性的作用，例如电子商务、数据仓库、科学数据共享、元模型数据管理、x m l 消息交换等。 对于模式匹配问题，建立相应的形式化匹配框架是非常重要的，它有助 于分析模式匹配问题的结构，建立模式匹配的算法模型和评价模式匹配算法。 然而，目前对于模式匹配研究的工作主要集中在基于特定应用领域的匹配算 法研究，而没有对模式匹配问题的代数学基础进行过深入研究。因此，论文 研究工作首先着重丁- 建立一个模式匹配的泛代数描述框架： 1 基于泛代数的观点，本文将模式定义为一类特定的有限结构( 代数) ， 称之为多标记模式，其最显著的特点就是可以形式化地描述任何类型的模式， 并将这些模式转换为基于特定基调的有限结构，基调中包含各种可以用于匹 配操作的信息。基于多标记模式，运用泛代数学研究方法，可以对模式这类 有限结构的映射操作进行深入分析和研究。 2 为了刻画多对多的匹配，基于多标记模式，提出了个体匹配和多价匹 配的概念。利用多价匹配，可以形式化地描述多对多的模式匹配。 3 基于多标记模式，提出了模式同态的概念，它可以用数学的方法来描 述模式的多价匹配。 4 基于多价匹配和模式同态，证明了模式匹配问题与模式同态的等价 性：模式匹配问题等价于寻找两个模式之间最强的模式同态。这样，就建立 了模式匹配问题的泛代数描述框架：模式同态。 由于同态是一个典型的组合优化问题，基于模式同态，论文首次将模式 匹配问题形式化为一个组合优化问题，得到模式匹配的算法模型。基于模式 匹配的算法模型，论文进行了模式匹配算法的研究： 1 将多标记模式实例化为一种描述异构模式的元模型，称之为多标记图 模型，它可以很好地描述模式中元素的语义性质，以及元素之间的各种关系。 上海交通大学博士学位论文 多标记图模型实质上是种基于图模型的语义数据模型。 2 由于使用多标记图模型来表示各种异构的模式，因此，自然而然地将 模式匹配问题归约为多标记图同态，即多标记图匹配的问题，它是经典的组 合优化问题。 3 基于对比模型，研究了多标记图相似性计算方法，建立了基于对比模 型的多标记图匹配的优化目标函数。由此，综合已有的模式相似性度量方法， 可以设计各种优化搜索算法来求解模式匹配问题。 4 多空间搜索是解决n p 难解问题的有效的算法设计思想，论文采用贪 婪策略和局部搜索技术，设计了基于多空间搜索的多空间匹配算法。使用若 干模式样本对多空间匹配算法进行测试，实验结果证明了多空间匹配算法的 有效性，以及模式同态算法模型的正确性。 5 ，由于图匹配足一个经典的n p 难解问题，论文研究了模式匹配问题及 其子问题的计算复杂性问题。 关键词：模式，模式匹配，同态，模式同态，多标记模式，多标记图，图匹 配，多空间匹配，计算复杂性，组合优化 上海交通大学博士学位论文 u n i v e r s a la l g e b r af r a m e w o r ka n dm a t c h i n g a l g o r i t h mf o rs c h e m am a t c h i n g a b s t r a c t s c h e m a sa r es p e c i f i cm e t a d a t am o d e l si nd a t a b a s ea p p l i c a t i o n s ，w h i c ha r e i n d i s p e n s a b l eb u i l d i n gb l o c k sf o rr e a l i z i n gi n t e r o p e r a b i l i t yo fh e t e r o g e n e o u sd a t a a n da p p l i c a t i o n s f o rs c h e m a s ，t h eb a s i co p e r a t i o ni sm a t c h i n g ，a n dt h eg o a li st o f i n dt h es e m a n t i c c o r r e s p o n d e n c e sb e t w e e ne l e m e n t s o ft w os c h e m a s t h e s c h e m am a t c h i n gp r o b l e m ( s m p ) p l a y sa k e yr o l e i nv a r i o u sd a t a b a s e a p p l i c a t i o n s ，s u c ha sd a t ai n t e g r a t i o n ，e b u s i n e s s ，d a t aw a r e h o u s i n g ，s c i e n t i f i c d a t as h a r i n g ，m e t a d a t a m o d e lm a n a g e m e n t ，x m lm e s s a g em a p p i n g ，e t e af o r m a lf r a m e w o r kf o rs m pi s v e r yi m p o r t a n tb e c a u s ei tf a c i l i t a t e st h e b u i l d i n go fa l g o r i t h mm o d e la n dt h ee v a l u a t i o no fa l g o r i t h m s h o w e v e r , p r e v i o u s w o r kh a sm o s t l yb e e nd o n ei nt h ec o n t e x to fap a r t i c u l a ra p p l i c a t i o nd o m a i n ，a n d f o c u s e do np r a c t i c a lm a t c h i n gm e t h o d s t h e s em a t c h i n ga p p r o a c h e sh a v en o t u t i l i z e dt h et h e o r e t i c a lf o u n d a t i o na n dm o s to ft h e mh a v er e l i e do na d h o c a p p r o a c h e s ，t h e r e f o r e ，t h em a i np o i n to ft h i sd i s s e r t a t i o n i st od e v e l o pa n a l g e b r a i cf r a m e w o r kf o rg e n e r i cs c h e m am a t c h i n ga tf i r s t ， 1 ，a c c o r d i n gt ou n i v e r s a la l g e b r a ，s c h e m a sa r ef i n i t es t r u c t u r e s ( a l g e b r a s ) o v e rs p e c i f i cs i g n a t u r e s w ep r o p o s eaf o r m a l l ym a t c h i n g - o r i e n t e dd e f i n i t i o no f s c h e m a ，w h i c hi sam e t a m e t am o d e lf o rs c h e m aa n dc a l l e dm u l t i 1 a b e l e ds c h e m a t h em o s td i s t i n c t i v ef e a t u r eo ft h i si st h a ti tc a nf o r m a l l yd e s c r i b ea n yp a r t i c u l a r s t y l eo fs c h e m a sa n dt r a n s f o r mt h e mi n t ot h ef i n i t es t r u c t u r e so v e rs p e c i f i c s i g n a t u r e s t h es i g n a t u r e si n c l u d es o m eu s e f u li n f o r m a t i o nf o rm a t c h i n g 2 b ym u l t i l a b e l e ds c h e m a ，w ep r o p o s ei n d i v i d u a lm a t c h i n ga n dd e f i n e s c h e m am a t c h i n ga sm u l t i v a l e n tc o 盯e s p o n d e n c e s ，a l s oc a l l e da sm u l t i v a l e n t m a t c h i n g ，w h i c hm e a n st h a to n eo b j e c to fas c h e m am a yb em a t c h e dw i t has e to f o b j e c t s o fa n o t h e r s c h e m a ，i e ，t h i sd e f i n i t i o no fs c h e m am a t c h i n gc a n c h a r a c t e r i z em a n y - t o - m a n ym a t c h i n g 3 b ym u l t i - l a b e l e ds c h e m a ，w ep r o p o s es c h e m ah o m o m o r p h i s m ( s h o m ) ， 上海交通大学博士学位论文 w h i c hc a nd e s c r i b em u l t i v a l e n tm a t c h i n gb yu n i v e r s a la l g e b r a ， 4 b a s e do nm u l t i v a l e n tm a t c h i n ga n ds h o m ，w ed e m o n s t r a t et h a ts m pi s e q u i v a l e n tt of i n d i n gas e m a n t i ch o m o m o r p h i s mf r o mo n es c h e m at oa n o t h e r ， w h i c hp r e s e r v e st h es e m a n t i c sb e t w e e nt w os c h e m a s u pt on o w ，w eb u i l dt h e a l g e b r a i cf r a m e w o r kf o rs c h e m am a t c h i n g ：s c h e m ah o m o m o r p h i s m b e c a u s eh o m o m o r p h i s mi sac l a s s i cc o m b i n a t i o n a l p r o b l e m ，b a s e do n s h o m ，w ef o r m u l i z es m pi n t oac o m b i n a t i o n a lp r o b l e m t h e n ，w eo b t a i nt h e a l g o r i t h m i cm o d e lo fs c h e m am a t c h i n g ，b a s e do nt h ea l g o r i t h m i cm o d e l ，w e s t u d yt h es c h e m am a t c h i n ga l g o r i t h m 1 f i r s t ，w ep r o p o s ea ni n s t a n t i a t i o no fm u l t i - l a b e l e ds c h e m a ：m u l t i l a b e l e d g r a p hm o d e l t h em u l t i l a b e l e dg r a p hm o d e lc a nr e p r e s e n tt h ev a r i o u sp r o p e r t i e s o fs c h e m aa n dt h er e l a t i o n sb e t w e e ne l e m e n t so fs c h e m a ，w h i c hi sas e m a n t i c d a t am o d e lb a s e do ng r a p hi nn a t u r e 2 b e c a u s ew eu s et h em u l t i l a b e l e dg r a p hm o d e la si n t e r n a ls c h e m am o d e l t or e p r e s e n ta l lk i n d so fs c h e m a s ，t h e r e f o r e ，s m pi sr e c a s ti n t oam u l t i 1 a b e l e d g r a p hm a t c h i n gp r o b l e m ，w h i c hi s o n eo fc l a s s i cc o m b i n a t i o n a lo p t i m i z a t i o n p r o b l e m s 3 b a s e do nc o n t r a s tm o d e l ，w ep r o p o s e a s i m i l a r i t y m e a s u r eo f m u l t i l a b e l e dg r a p h ，a n dd e v e l o pt h eo p t i m i z a t i o nf u n c t i o no fm u l t i - l a b e l e d m a t c h i n g ，t h e nw ec a nu s eo p t i m i z a t i o ns e a r c hm e t h o d sa n dv a r i o u sm a t c h i n g m e a s u r e st o g e t h e rt os o l v es m p 4 s i n c em u l t i s p a c es e a r c hi san e wm e t h o dt os o l v en p h a r dp r o b l e m s ，b y u s i n gg r e e d ys t r a t e g ya n dl o c a ls e a r c h ，w ed e s i g nam u l t i s p a c em a t c h i n gm e t h o d t of i n dt h ed e s i r e dm a t c h i n gr e s u l t sb e t w e e nt w os c h e m a s f i n a l l y ，w ee m p l o y s o m es a m p l es c h e m a st ot e s to u ra l g o r i t h m t h em a t c h i n gr e s u l t sa r g u et h a tt h e m u l t i s p a c em a t c h i n ga l g o r i t h mb a s e do nm u l t i l a b e l e dg r a p hs i m i l a r i t yi sv e r y e f f e c t i v e ，a n dt h e np r o v et h ec o r r e c t n e s so fs h o m a l g o r i t h m i cm o d e l 5 f o r g r a p hm a t c h i n gi sac l a s s i c a ln p h a r dp r o b l e m ，w es t u d yt h e c o m p u t a t i o n a lc o m p l e x i t yo fs m pa n dv a r i a n t so fs m e k e y w o r d s ：s c h e m a ，s c h e m am a t c h i n g ，h o m o m o r p h i s m ，s c h e m ah o m o m o r p h i s m ， m u l t i l a b e l e d s c h e m a ，m u l t i - l a b e l e dg r a p h ，g r a p hm a t c h i n g ，m u l t i s p a c e m a t c h i n g ，c o m p u t a t i o n a lc o m p l e x i t y ，c o m b i n a t i o n a lo p t i m i z a t i o n 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：多长素哆 e l 期：w 形年占月，1 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“4 ”) 学位论文作者签名：办夕红指导教师签名：彳场t 歹 日期：了名年莎月，2 日 男e 每j t _ - - 甚- 上海交通大学博士学位论文 第一章绪论 论文主要研究模式( 模型、元数据) 的匹配问题：在两个异构的模式之间，建 立模式中元素之间的语义关联。在本章中，首先探讨模式匹配问题研究的起因、综 述模式匹配的发展及其应用，然后指出本文研究的背景和进行深入研究的实际意义， 最后介绍了论文的主要研究工作。 1 1 研究问题的起源 对于模式匹配问题，来源于目前对分布式应用的广泛要求，如语义网、网格计 算、p 2 p 计算、以及w e b 服务等等。这些研究的主要目的是意图实现不同应用系统 之间的资源共享和互操作，而实现共享和互操作的主要任务之一就是整合、集成不 同应用系统的异构资源。 1 1 1 共享和互操作 知识经济社会更加强调分工和协作，信息的传播和共享成为社会发展的需求， 各行各业之间进行广泛的合作与交流，越来越强烈地要求能够实现各种资源的共享 和复杂应用系统的互操作，如科学数据共享、大型数据仓库、电子商务、海量信息 中的查询和搜索等等【l 】。但是由于各个领域在历史发展过程中的自发性，使得异构 性的存在，资源共享和应用互操作的要求很难实现，这就驱使各个领域的专家致力 于研究各种可行的方法来实现资源共享和应用之问的互操作。 互操作成为万维网联盟( w 3 c ) 所提出的七点目标和宗旨中的第四点，如今成 为w e b 技术和基于w e b 的各种应用研究的基本问题1 2 。 互操作：多个使用不同硬件和软件平台，数据结构、接口的系统之问，以最小 的内容和功能损失为代价，进行数据交换的能力。使用定义的元数据模式、共享传 输协议，可以方便地、无缝地实现异构应用系统的连接并访问网络上的资源【3 1 这里，元数据模式是实现应用系统的互操作的关键元素，例如w e b 服务、语 义网中使用的x m ls c h e m a ，以及基于x m l 的其它元描述语言( d t d 、w s d l 、 r d f ，o w l 等等) ，在整合异构应用系统中起着至关重要的作用。 ， ：哟， 上海交通大学博士学位论文 1 1 2 异构性 异构性是计算机应用领域发展过程中自然存在的现象，各种数据源和应用系统 都是自发地发展生成的，不可避免地导致各种异质性的发生。 概括来说主要存在三种类型的异构性：首先是平台和系统的异构性，包括操作 系统和硬件系统的异构性、数据库管理系统的异构性以及并发控制和恢复能力的差 异，这种类型的异构性是针对硬件和基础设施而言的，比较容易解决；后面两种异 构性是针对计算机处理的数据而言的：一是句法和结构的异构性，包括数据模型的 异构、属性类型、格式或精确度等的差异、命名和本体的差异等，这些差异相对比 较好解决【4 j ；二是语义的异构性，是指数据表示含义的差异，在不同的数据源之间 分享数据、企图实现机器自动化处理以及理解数据时，这样的异构性必须重点考虑， 而且这种类型的异构性是机器最难处理的。 语义的异构性是指本地数据意义的差异和相似性h ，5 6 , 7 , 8 , 9 1 。例如两个本地数据 源的模式元素包含有相同的意义，仅名称不同。在集成的时候，这两个元素实际指 称的是相同的概念。另外，两个模式元素可能名称相同，但它们包含的内容是不相 容的，故在进行集成时，这些元素应被看作不同的两个对象。 为了解决数据源和应用系统的异构性，出现了元数据、模型、模式等众多的元 描述语言来实现对异构系统的整合，最终的目的就是为了消除异构性的影响，使得 各种各样的计算资源整合在一起，实现不同系统、不同数据源之间的互操作。这样， 模式( 元数据模型) 成为实现缝合异构性的桥梁，例如x m , s c h e m a 成为描述异构 资源的基础元语言。 对于论文研究的模式匹配来说，主要考虑后面提到的两种类型的异构性：句法 和结构的异构性以及语义的异构性。 1 2 模式匹配综述 1 2 1 模式( s c h e m a ) 数据，是信息存在的一种形式，只有通过解释和处理才能成为有用的信息，因 此，需要对数据进行描述，数据模型是用来描述数据的一组概念和定义，例如关系 模型、面向对象模型、e r 模型等等。 基于不同的数据模型，可以对一个单位的各种事物的结构、属性、联系、约束 和操作等进行描述，更加方便用户进行数据的操作和管理，方便进行数据的共享和 互操作，这就是数据模式。因此，由于数据模型的不同和使用的数据模式的描述方 法不同，存在有众多的数据模式分类，与数据模型相对应，就包含有关系模式、面 向对象模式、e r 模式等。 2 朔 鬟 ： 硼 荔 纷 翳 上海交通大学博士学位论文 由于早期的数据库研究注意集中于数据库的物理结构，绝大多数的研究关注数 据的物珲存储和信息结构的需求，以使得数据库的存储和检索更加的有效，很少考 虑到如何向用户提供数据的理解”。然而，为了实现的数据独立，以及为了得到在 数据建模过程中的附加语义信息，研究者试图提供建模的结构来简化数据库的设计 和使用，为用户提供数据的视图。其中有3 篇文章文献【l l ，1 2 ，1 3 】研究了这两个 重要的思想：数据建模和语义数据模型，并且这3 篇文章标志了语义数据模型的诞 生。 由于数据库设计以及数据共享的需求，各种各样的数据模型出现了，包括关系 模型、面向对象的模型、还有注重语义操作的e r 模型、t a x i s 模型，s d m 模型、 概念图、以及基于逻辑的模式等等【l o l 。到目前，随着互联网等分布式应用的发展， 人们提出了语义网、w e b 服务等新的网络应用架构，对于数据语义互操作的愿望越 来越强烈，x m l 模式成为主要的数据及数据语义建模语言，出现了基于描述逻辑 和x m l 模式的描述语言：o w l 、研但q 等等。 通常来说，模式是数据库应用中的一类特定的元数据模型，它是由相关的元素 组成的有限结构，例如视图、表、类，或x m l 元素和属性等组成的集合，是数据 蠕 库中全部数据的逻辑结构、概念结构和特征的形式化描述。在本论文的研究中，模 式是一个更加广义的概念，不仅仅局限与数据库研究中使用和研究的模式。 模式，在这里定义为一个复杂的离散结构，可以表示人工制品的设计，例如x m l s c h e m a 、d t d ，网站模式、接口定义关系模式，数据库转换脚本。工作流定义、 语义网络，软件规范或者复杂的文档等等【1 4 1 1 2 2 模式匹配( s c h e m am a t c h i n g ) 如今，模式是实现异构数据和应用系统互操作中不可缺少的基本元素。许多的 模式应用需要将一个模式以及其中的数据映射到另外一个模式，因此我们需要对模 式的操作进行深入的研究。对模式来说，最基本的操作就是匹配1 1 ”。 模式匹配是意图获得两个模式中待匹配的个体对象之间的语义匹配和映射，其 结果表示源模式的个体对象与目标模式的个体对象之间存在特定的语义关联，即得 到两个模式之间的语义映射1 1 5 1 ，如图1 1 所示。模式匹配最早是在数据库设计和分 布式多数据库研究过程中出现的1 1 6 ，模式匹配的研究跟数据库管理系统的研究一样 久远，它在许多数据库应用中具有关键性的作用，是诸多基于数据库应用的基础， 例如模式集成、电子商务、数据仓库、x i v i l 消息交换等，特别地，模式匹配成为 当前元数据管理的基本问题【l ”。模式匹配问题已经成为制约异构数据共享和应用系 统互操作的瓶颈之一。 3 上海交通大学博士学位论文 图1 1 关系模式和x m l 模式之问的匹配 f i g ，1 1 a m a p p = g k 呻e ar e l a t i o n a la n d x i v l ls c h e m a 目前，模式匹配是由领域专家手工进行的，有时使用图形工具【1 7 1 。由于各种异 构应用互操作的需求不断增长，不能总是依靠领域专家费时费力高成本地手工实现 匹配，因此，希望能有一些工具能够自动化地实现准确的模式匹配f 1 5 18 1 9 1 。 1 2 3 模式匹配的方法 关于模式匹配方法的分类，有众多的分类方法，基于匹配基数的分类方法，基 于句法或语义的分类方法，基于模式级或实例级的分类方法，基于元素级和结构级 的匹配分类方法等等。下面，我们简单介绍这些分类方法的依据和原因。 1 匹配基数( m a t c h i n gc a r d i n a l i t y ) 匹配基数包含4 种类型：一对一( o n e - t o - o n e ，1 ：1 ) ，一对多( o n e - t o - m a n y ，l ：疗) ， 多对一( m a n y - t o - o n e ，n ：1 ) 以及多对多( m a n y - t o - m a m y ，栉：脚) 。它是指两个待匹配 模式的元素相互对应的关系中，是否允许出现源模式中的一个元素对应目标模式中 的多个元素，如表1 1 所示。 表1 i 匹配基数的实例关系模式和x m l 模式之间的匹配 t a b l e1 1 a n e x a m p l e o f m a t c h i n g c a r d i n a l i t i e s 塑! 咝型些! ! 堕鱼!丛坐! 咝塑墅! 塑 ll ：ii t e mi t e mi t e m = i t e m d e l i v e r t o p o s h i p t o d e f i v e r t o2p o s h i p t o 2l ：月 3 ：l n a m e p r i 1 l n a m e2 ( f i r s t n a m e + la s i _ n 曲 c o s t = p r i c e + ( 1 + t a x 1 0 0 ) 由于需要使用复杂的匹配准则才能得到n ：l 和b t ：r a 的匹配，因此大多数的匹配 方法都是基于l ：l 和l 狮的匹配方法，具体的分类参阅模式匹配的综述 t s l 。 4 a 蛐 上海交通大学博士学位论文 2 基于句法或语义的分类方法 异构性包括：一是句法和结构的异构性，包括机器可读的数据表示、命名和本 体的差异、数据模型和模式的异构；二是语义的异榭眭，是指数据表示含义的差异。 因此，在进行模式匹配算法实施的时候，基于不同的异构性，解决的方法也就会有 差异，模式匹配可以分为句法匹配和语义匹配，如图1 2 所示。 m a t c h t n g 。 s y n t a c t i cm a t c hc n g s e m a n t i cm a t c h i n g r 商c o m p 呻耐b d w c m- r c a l 聊1 6 耐b c t w 矗n t h i i o f e l c m a a l t i c o n c q o f e l e m e n t s r i # e ( o 1 ) 1- r z = ，。王t 上门 图1 2 模式匹配方法分类 f i g 1 2t h ec l a s s i f i c a t i o no f s c h e m am a t c h i n g 句法匹配( s y n t a c t i cm a t c h i n g )使用基于句法的技术和句法相似性方法来比 较模式元素的相似程度。元素匹配的相似度值由【o ，1 】区间的实数来表示，如果相似 度值超过给定的阈值，则两个元素相匹配。句法匹配方法将在第6 章中更加详细地 阐述。 语义匹配( & r m m i cm a t c h i n g )主要处理元素的概念之间的关系，匹配结果 是得到元素之间的语义关系，一般的关系有：e q u i v a l e n c e ( _ ) ，m o r eg e n e r a lq ) ，l e s s g e n e r a l ( e ) ，m i s m a t c h ( 上) ，a n do v e r l a p p i n g ( 几) 。如果采用信息检索中的语义距离度量 方法，可以得到两个元素概念的语义距离，同样也可以用【o ，1 1 区间的实数值来表示 其相似的程度。本文提出的模式匹配算法采用了基于语义距离的匹配方法，将在第 6 章中详细讨论。 3 基于模式级或实例级的分类方法 实例级或模式级的匹配方法是根据该方法是否能够考虑实例数据( 即，数据内 容) 来进行分类的。 模式级匹配( s c h e m a d e v e lm a t c h i n g )模式级匹配方法仅仅使用模式信息，而 不考虑实例数据，可使用的匹配信息包括模式元素的属性，例如：名称、描述、数 据类型，关系类型( p a r t - o f , i s - a 等) ，约束以及模式结构等等。 实例级匹配( i n s t a n c e - l e v e lm a t c h i n g )实例级匹配方法能够给出重要的模式 元素的内容和意义，可以极大地帮助匹配算法获得更多的有用信息，使得匹配结果 更加准确。对于一些半结构化数据( s e m i - s t r u c t u r e dd a t a ) ，仅仅使用模式信息是很 有局限性的，在极端的青况下，没有给定模式，但是，利用人工或者自动的方法， 模式可以从实例数据中得到( 例如，x m l 模式可以从x m l 文档中构造得到) 。 对于目前的匹配方法，大多都集中在模式级的匹配，少数的匹配方法可以考虑 5 ，n ， 上海交通大学博士学位论文 到基于实例的匹配( l s d 2 0 1 、s i m i l a r i t yf l o o d i n g 2 1 j ) 。 4 基于元素级和结构级的分类方法 根据匹配粒度( m a t c h g r a n u l a r i t y ) 的不同，可以得到元素级匹配( e l e m e n t - l e v e l ) 和结构级的匹配( s t r u c t u r e - l e v e l ) 。 元素级匹配对于第一个模式中的每一个元素来说，元素级的匹配决定于第二 个模式的匹配元素，如果只使用最低级别的元素进行匹配，例如x m l 模式的属性 或者关系模式的列进行匹配，则该匹配方法称为元素纫原子级( a t o m i cl e v e l ) 的匹 配。例如，图1 1 中：p i dp r o d u c t i d 。 结构级匹配同时也会涉及到模式中组合元素的匹配方法。例如考虑x m l 模 式中c o m p l e x t y p e 类型的属性的匹配，以及关系模式中t a b l e 的匹配，例如图1 1 中： p r o d u c t s + p r o d u c t 。 5 单一匹配和组合匹配方法 如果仅使用以上提及的一种匹配方法，则该方法是单一匹配( i n d i v i d u a l m a t c h i n g ) ，若使用多个单一匹配方法的组合，则称为组合匹配( 6 加垤撇砌以g ) 。 模式匹配方法的分类如图1 3 所示。 州黜：窒慧时 c o m b i n l n gm a t c h e m 甜器彳嘶 。咖“锹掣8 晦 晰b 几dm 8 c h 啪c 鼬。n m l n a g i 咖m d e 晤p e n d 8 m l ，、 三哆掣 6 。9 f - 删 n o d e - l e v e l m 裂? 罄盅景妒a u t o m a t m a l l y - m a t c h e , - s e l e c t i o n f 一，s t r o c t u r a us t r 。u c t u r a l 。s t r u c t ”触妇咄 m u n b m m n ural b n 如蛳 嘣憎巾n n 憎吣u n 蛳鲫柚钏 1 郫俐“4 蚓 一 | ili | il， ，屏磊磊 ：豁搿器，。t y p e s , r a a a t y 咖g r a p h 品粼嚣挈：竺型竺竺2 嚣g t o t e t n a ”t a o 一”一一黼“”= 二磊一5 制 一w 4 4 可卅o 图1 3 模式匹配方法分类 f i g 1 3t h ec l a s s i f i c a t i o no f s c h e m am a t c h j n g 1 2 4 工具与原型系统 基于不同的应用领域，目前存在有众多的模式匹配的原型系统。由于针对的应 用问题有所不同，这些系统使用的匹配方法也有所差异，下面简单介绍几种现有的 模式匹配的工具。 1 a u t o p l e x & a u t o m a t c h = a u t o p l c x 及其增强型a u t o m a t c h 使用基于机器学习的单策略模式匹配方法。该 6 j 月 “ 彬 饬 上海交通大学博士学位论文 系统中，使用实例特征，n a i v eb a y e s i a n 学习器可以匹配源模式和先前构造的全局 模式的属性，这里的源模式使用的是关系模犁。对十每个源属性，可以得到关于每 个全局属性的匹配和不匹配的概率，这些概率的总和为1 ，系统将计算得到的吐配 概率作为源属性和全局属性的相似度。这两个系统可以得到l ：l 的局部和全局基数 属性对，构成最后的匹配结果。 2 c o m a ( c o m b i n a t i o no fm a t c h i n ga l g o r i t h m s ) c o m a 系统中，使用有根的有向无环图( r o o t e d d i r e c t e d a c y c l i c g r a p h ) 作为内 部模式模型，使用一种组合的模式匹配方法，可以灵活地将多种匹配器和不同的匹 配方法组合在一起。并且提出重用的( r e u s e ) 匹配方法，使用过去匹配的结果来得 到新的匹配结果，提高了匹配的精度。c o m a 可以得到元素级的l ：l 局部匹配和 m ：h 全局匹配。 3 c u p i d 1 9 l c u p i d 使用较为复杂的混和匹配方法，将名称匹配器和结构匹配算法组合在一 起，可以得到较为精确的匹配结果。其使用的结构匹配算法使用树结构作为内部模 式，因此设计了一种树匹配算法来得到模式之间的结构相似度。c u p i d 可以得到元 素级的l ：1 局部匹配和n ：l 的全局匹配基数。c u p i d 比较早的两个原型系统d i k e 嗍 和m o m i s 瞄1 更加通用，更加有效。 4 l s d 2 0 , 2 6 & g l u e 2 6 l s d 及其扩展g l u e 将不同的匹配器组合起来，使用组合的匹配方法来获得模 式元素之间的匹配。l s d 将新的源模式同预先确定的全局模式相匹配，g l u e 则直 接将两个模式进行匹配。这两个系统的单一匹配器都采用机器学习技术，然后将这 若干个匹配器组合起来自动地得到匹配的结果。单一匹配器除了名称匹配器外，还 包括若干个实例级的匹配器，用来发现学习阶段的不同实例模式特征以目标模式的 单个元素的匹配规则单一匹配器的预测组合起来称为元学习器，根据训练的阶段 得到的精度来权衡单一匹配器的预测结果。匹配结果由元素级的l ：l 局部匹配和以：1 的全局匹配构成。 5 s m a t c h p 1 & c t x m a t c h p s i s - m a t c h 是c t x m a t c h 的扩展系统，这两个模式匹配方法都是基于命题逻辑可 满足性的语义匹配方法。c t x m a t c h 将每个语义的模式看作一个上下文环境，是一 个基于s a t 的模式匹配算法；在c t x m a t c h 的基础上，s - m a t c h 添加了一些附加的 功能。这两个方法也都使用图结构作为内部的模式，算法得到的结果的表示同其它 方法有所不同，其它的方法得到的匹配元素相似度都是【o ，1 】区间的一个数值，而 s - m a t c h 算法由于考虑模式元素的概念匹配，基于元素概念的可满足性，得到元素 7 上海交通大学博士学位论文 之间的5 种语义关系( s e m a n t i cr e l a t i o n s ) ：e q u i v a l e n c e ( 一) ，m o r eg e n e r a l 口) ，l e s s g e n e r a l ( e ) m i s m a t c h ( 上) ，a n do v e r l a p p i n g ( 几) 。s - m a t c h 可以实现元素级的1 ：l 匹配 结果。 6 s i m i l a r i t yf l o o d i n g & r o n d o l 2 9 】 r o n d o 是一个通用模型管理工具，用于实现复杂模型( 模式) 的各种操作：包 括匹配( m a t c h ) 、删除( d e l e t e ) 、抽取( e x t r a c t ) 、反转( i n v e r t ) 、融合( m e r g e ) 等 等。其中基本的操作就是匹配，模型的匹配是其它操作的基础。在r o n d o 系统中， m e l n i k 等提出了( s i m i l a r i t yf l o o d i n g ，s f ) 算法，该算法是基于有向标记图模型的 一种迭代的图匹配算法。该算法使用相似度传播的思想来获得模式元素之间的相似 度，通过相似度向量的迭代来得到一个固定点( j 缸- p o m t ) ，然后由用户来规定相似 度的阈值，超过该阈值的关联节点则为匹配节点。该算法可以实现n ：m 基数的匹配 结果。 其它工具： 文献【1 8 】分析了六种模式匹配器： s e m i n t ( n o r t h w e s t e r nu n i v ) 文献 3 0 ，3 1 ，提出使用神经网络进行模式匹 配 s k a t ( s e m a n t i ck n o w l e d g ea r t i c u l a t i o nt o o l ，s t a n f o r du n i v ) 文献 3 2 】提出 r u l e - b a s e d 方法半自动地匹配两个o n t o l o g y ( s c h e m a ) t r a n s s c m ( t e la v i vu n i v ) 文献 3 3 】 d i k e ( u n i v o f r e g g i oc a l a b r i a , u n i v o f c a