（计算机软件与理论专业论文）基于素数的多源模式匹配方法的研究.pdf

摘要 摘要 随着i n t e r n e t 的普及，出现了很多基于w e b 的可检索的在线数据库， 其中隐藏了大量的信息，我们称之为“深n j ( d e e pw e b ) ”。这些可检索在 线数据库的出现给数据集成领域带来了许多新的问题，而模式匹配是数据 集成过程中的一个关键操作。对隐藏的海量数据的集成首先要对各在线数 据库源查询界面使用的模式完成匹配。本文对国内外关于模式匹配的研究 现状进行了综合分析，从个全新的角度对大规模在线数据库查询界面进 行匹配的模式匹配方法进行了研究。 首先，介绍了多源模式匹配方法和一般模式匹配方法的异同点，深入 分析了现有的两种多源模式匹配方法，指出了两种方法各自的优点和存在 的不足。 其次，在两种方法的基础上，提出了一种基于素数的多源模式匹配方 法。将素数理论引入到模式匹配过程中，将属性间单纯的字符匹配转换成 数学运算，提高了匹配效率，并保留了现有多源模式匹配方法的优点。该 方法弥补了当前研究中无法完成复杂匹配的同时保留模式模型的不足，方 便了后续元查询系统的设计。 再次，分别提出了属性素数化算法、组属性挖掘算法、同义词发现算 法和匹配选择算法，同时提出了基于素数的多源模式匹配方法的具体实现 算法，并给出了褶应的算法分析。 最后，在四个领域2 0 0 多个实际在线数据库源上进行了实验，分析了 实验结果，证明了算法的正确性。 关键词深网；多源模式匹配；数据集成；元查询系统；素数 燕山大学工学硕士学位论文 a b s t r a c t w i t ht h ep o p u l a r i z a t i o no ft h ei n t e r a c t ，al a r g en u m b e ro fr e t r i e v e do n l i n e d a t a b a s e sb a s e do nw e bh a v ea p p e a r e dw h i c h & r ec a h e d d e e pw e b t h e r ea r e l a r g ea m o u n t so fi n f o r m a t i o nh i d d e ni nt h e m t h ea p p e a r a n c e so f t h e s er e t r i e v e d o n l i n ed a t a b a s e sh a v eb r o u g h tal o to fn e wp r o b l e m st or e s e a r c hf i e l do fd a t a i n t e g r a t i o n , a n ds c h e m am a t c h i n gi sak e yo p e r a t i o nd u r i n gt h ep r o c e s so ft h e d a t ai n t e g r a t i o n w h e nam a s so fd a t ah i d d e ni nt h ed e e pw e ba r en e e d e dt ob e i n t e g r a t e d ，t h ef i r s ts t e p i st om a t c ht h es c h e m a sw h i c ha r eu s e db yq u e r y i n t e r f a c e so f d i f f e r e n tr e t r i e v e do n l i n ed a t a b a s e s t h ea c t u a l i t yo f t h et e c h n o l o g y a b o u ts c h e m am a t c h i n gi ni n t e r n a la n de x t e r n a li sa n a l y z e ds y n t h e t i c a l l yi nt h i s p a p e r ，a n ds c h e m am a t c h i n gm e t h o d s f o rl a r g es c a l eo f s c h e m a sa c r o s st h eq u e r y i n t e r f a c e so fd i f f e r e n tr e t r i e v e do n l i n ed a t a b a s e sa r er e s e a r c h e df r o man e w p o i n to f v i e w , f i r s t ：l y ，t h es i m i l a r i t i e sa n dd i s s i m i l a r i t i e sb e t w e e nm u l t i p i es o u r c e ss c h e m a m a t c h i n gm e t h o d sa n dc o e n f l l o ns c h e m am a t c h i n gm e t h o d s a r ei n t r o d u c e d ，t h e t w ok i n d so fe x i s t i n gm u l t i p l es o u r c e ss c h e m am a t c h i n gm e t h o d sa r ea n a l y z e d d e e ! ：i 取a n dt h em e r i t sa n dl a c k si ne a c hm e t h o da r ep o i n t e d o u t s e c o n d l y , o nt h eb a s i so ft h et w om e t h o d s ，am u l t i p l es o u r c e ss c h e m a m a t c h i n gm e t h o db a s e do 歉p r i m en u m b e r i sp r o p o s e d p r i m en u m b e ri s i n t r o d u c e dt ot h ep r o c e s so ft h es c h e m am a t c h i n g ，w h i c hc h a n g e st h ec h a r a c t e r m a t c h i n gt ot h em a t h e m a t i c a lo p e r a t o r , t h ee f f i c i e n c y o ft h em a t c h i n gi s i m p r o v e do b v i o u s l y , a n dt h ea d v a n t a g e s o ft h ee x i s t i n gs c h e m am a t c h i n g m e t h o d sa r ek e p t t h en e wm e t h o dm a d eu pt h ed e f i c i e n c yt h a tt h ee x i s t i n g m e t h o d sw h i c hc a nc o m p l e t et h ec o m p l e xm a t c h i n gb u tc a n tr e s e i v et h e s c h e m am o d e la tt h es a m et i m e s oo u rm e t h o di sc o n v e n i e n tt ot h ed e s i g no f t h em e t a q u e r i e rs y s t e n l a b s t r a c t 一 t h i r d l y , t h ea l g o r i t h m so fp u t t i n ga t t r i b u t e st op r i m en u m b e r ，m i n i n gt h e g r o u po fa t t r i b u t e s ，d i s c o v e r i n gt h es y n o n y ma n d s e l e c t i n gt h ee x c e i l e n c e m a t c h i n ga r ep r o p o s e di nt h ep a p e r , t h ec o n c r e t ea l g o r i t h mo ft h em u l t i p l e s 0 1 1 r c e ss c h e m am a t c h i n gm e t h o db a s e do n p r i m en u m b e ri sa l s op r o p o s e d ，t h e c o r r e s p o n d i n ga l g o r i t h ma n a l y s e sa r ep r o v i d e d f i n a l l y , t h ee x p e r i m e n ti sd e m o n s t r a t e do nm o r et h a n2 0 0o i l l i n ed a t a b a s e s o l t e e si n o u rd o m a i n s ，t h ee x p e r i m e n tr e s u l t sa r ea n a l y z e d ，a n dt h ec o 仃e c t n e s s o f t h ea l g o r i t h mi sp r o v e d k e y w o r d sd e e pw e b ；m u l t i p l es o l l r c e ss c h e m am a t c h i n g ；d a t ai n t e g r a t i o ； m e t a q u e r i e rs y s t e m ；p r i m en u m b e r 第1 章绪论 1 1 研究背景 第1 章绪论 经过几十年的发展，互联网( i n t e m e t ) 已经成为新经济时代的标志，它 极大地影响了人类的生活方式、商业模式，并将在新世纪继续对人类社会 的进步起着巨大的推动作用。随着网络的普及，人们越来越习惯于从网络 中检索自己所需要的信息和数据。通常人们在查询网络信息时最先想到的 是在某一搜索引擎中输入待查询内容的一个或几个关键字，然后在命中记 录中选择自己需要的信息。如果命中记录为零，人们通常会使用更多的关 键词，或者使用同义词、近义词来深化检索。若仍没有结果，人们可能会 认为所需信息在网络中并不存在，继而放弃查询。但事实可能并非如此。 人们所需的信息在网络中可能是大量存在的。只是传统的搜索引擎无法或 者没有索引这些信息而己。记录这些信息的网页就是d e e pw e b ，或者称 为深网、隐往网、隐蔽网1 2 ，”。 对深网的研究只有1 0 年左右的时间。1 9 9 4 年，j i l le l l s w o r t h 博士首次 提出隐性网的概念，但并没有引起足够的重视。直到2 0 0 0 年以后，才有相 关的研究论文及成果发表，并迅速引起了热烈的讨论。到目前为止，学术 界仍然没有对深网的概念达成共识。2 0 0 0 年，b r i g h t p l a n e t 公司首创了“深 网”术语，用该术语来表述那些将信息内容储存在可检索的在线数据库中 而仅仅响应在自身查询界面上提交的查询提问的网站。 1 1 1 深网的规模 与“深网”相对应的概念是“表面网”，“表面网”包括的内容基本上 都是非结构化的h t m l 信息，而“深网”包括的内容大多数是结构化的数 据库信息。b r i g h t p l a n e t 公司根据2 0 0 0 年3 月1 3 日至3 0 日搜集的数据， 对深网的规模和相关性进行了研究，结果显示：深网中的公共信息是表面 燕山人学工学硕士学位论文 网中信息的4 0 0 5 0 0 倍；深网的容量是7 5 0 0t b ，而表面网只有1 9t b ： 深网有近5 5 0 0 亿个独立文件，而表面网只有1 0 亿个；目前存在的深网网 站已经突破2 0 万个；6 0 个最大的深网网站共包含7 5 0t b 的信息，比表面 网信息的4 0 倍还多；深网的月流量通常比表面网要多出5 0 ，并且更容 易被链接；深网是i n t e r n e t 上增长最快的新信息类型；在内容上，深网网 站比传统的表面网站要更专、更深；深网内容的全部价值是表面网的1 0 0 0 至2 0 0 0 倍；深网的信息内容与所有的信息需求、市场和领域高度相关；一 半以上的深网内容存储在专题数据库中；9 5 的深网信息可以公共获取而 无需付费或订阅。 随着各高校、图书馆、企业及政府部门等社会信息机构拥有的海量信 息逐步数字化，深网的规模也不断扩大。这些机构数据库中的信息正在呈 指数级数增长，构成了深网中增长最快、增量最大的部分，同时这些数据 库中的信息具有文档质量好，信息价值高的特点。在2 0 0 4 年7 月，美国伊 利诺大学计算机科学系的一份报告【4 】中指出“深网已有大约3 0 7 万个站点、 4 5 万个数据库和1 2 5 8 万个界面，并且一直在快速增长，2 0 0 0 年到2 0 0 4 年期间增长了3 7 倍。” 可见深网的规模已经远远大于表面网，并且持续性的高速增长着，因 此，对深网的研究有着巨大的应用价值。 1 1 2 深网的内容 深网的内容随着信息技术的发展和社会观念的演变而不断变化。参考 文献 5 中根据目前深网形成的不同原因，将其内容归纳为以下几种： ( 1 ) 未被链接的网页根据搜索引擎原理，若没有任何其他网页链接指 向某一个网页，搜索引擎的s p i d e r 程序就不能沿着其他网页中的u r l 爬 行到该网页，也就不能将该网页的相关信息搜集到索引库，那么通过搜索 引擎就无法找到这些未被链接的孤岛网页。未被链接的网页是深网基本的 组成部分。 ( 2 ) 动态生成的网页当搜索引擎的s p i d e r 程序遇到大量由c g i 、a s p 、 a v a s c r i p t 等专门制作动态网页的脚本语言所编写的网页或者u r l 中包含 2 第1 章绪论 “? ”的动态网页时，一般不会考虑索引该网页。这使得动态生成的网页 成为深网的一个组成部分。 ( 3 ) 网上可检索的在线数据库网上可检索在线数据库中存储的绝大 部分都是结构化的数据。这些数据“隐藏”在可检索的在线数据库的网络 检索界面的后端，存储在a c c e s s 、o r a c l e 、s q ls e r v e r 、d b 2 等数据库系 统中。当需要检索数据时，用户必须使用该在线数据库网站的搜索工具进 行查询，在交互式检索窗体中输入检索提问式或者选择检索选项，在数据 库响应请求后，将相应的检索结果按一定的排序规则显示在网页上。目前 i n t e r n e t 上的可检索数据库可以分为两种类型：可自由获取的公共数据库和 需订阅或者付费的数据库。由于搜索引擎的s p i d e r 程序尚不具备在交互式 检索窗体中填写或选择所需字段信息的能力，所以无法向数据库提交检索 提问式。同时，对于一些必须使用用户名和密码登录的需注册或者付费的 网站的数据库来说，搜索引擎的s p i d e r 程序同样没有足够的能力注册后登 录系统。无论是哪种类型的数据库，搜索引擎都无法获取其中的数据，而 有价值的网络信息一般都存储在数据库中。因此，网上可检索的数据库是 深网最大的组成部分，也是深网信息规模大、质量高的最主要原因。 ( 4 ) 实时数据针对信息用户对股票、天气、航班等即时信息的强烈需 求，许多网站提供动态更新的实时数据服务。实时数据信息量大、更新频 繁、时效性强。对一般用户来说，失去时效后的实时数据几乎没有搜索价 值。因此，大多数搜索引擎都放弃索引实时数据，使得这些数据也成为深 网的个组成部分。 f 5 谙口分非h t m l 格式文件搜索引擎曾一度只能搜索h t m l 格式的 文件。随着技术的发展，搜索引擎已经开始涉足非h t m l 格式领域的信息 挖掘，但仍有大量非h t m l 格式的文件埋在深网中。 ( 6 ) 需要密码或注册的网站 目前许多网站需要注册并使用用户名和 密码登录后才能访问。因此，这部分网站中的数据也被埋藏在深网中。 综上所述，深网最重要的组成部分是广泛分布于i n t e r n e t 上的可检索 的在线数据库。这些在线数据库中隐藏了大量的专业信息，并且由于其数 据源规模增长迅速，通常将这些可检索的在线数据库称为深网。如果可以 燕山大学工学硕士学位论文 集成这些极具价值的海量信息，就可以在很大程度上提高人们在网络中检 索数据信息的能力。但是，这些海量信息是隐藏在可检索在线数据库的查 询界面之后的，所以，如何对这部分信息进行集成，就成为数据集成领域 的一个新的研究重点。由于模式匹配是数据集成过程中的关键操作，对各 可检索在线数据库查询界面使用的模式完成匹配，就成为对隐藏的海量信 息进行集成的关键。因此，对可检索在线数据库的模式匹配技术的研究具 有重大意义。 1 2 研究现状 在处理模式时的一个基本操作是匹配，该操作将在作为输入的模式中 有语义对应关系的元素间产生一个映射。自上世纪8 0 年代就已经开始对模 式匹配技术进行研究。模式匹配已经在许多领域发挥了十分重要的作用， 像面向w e b 的数据集成、电子商务、模式集成、应用演变、数据仓库、 w e b 站点的创建和管理以及基于组件的开发等等。近年来，随着可检索在 线数据库数量的不断增多，出现了类专门针对这类数据库查询界面使用 的模式进行匹配的多源模式匹配方法。 1 2 1一般模式匹配方法的发展历史和研究现状 早期关于模式匹配的研究是从模式集成开始的。模式集成是从给定的 组独立开发的模式中构造一个全局视图的过程。由于模式是单独开发的， 因此不同的模式使用不同的结构和术语。当要集成的模式来自不同领域时， 备模式所使用的结构和术语显然是不同的；而当要集成的模式来自相同领 域时，由于模式是由不同人员开发的，各模式使用的结构和术语也不尽相 同。因此，模式集成的第一步就是确认这些模式间的关系，这就需要模式 匹配操作。当这些关系被确定后，匹配的元素就可以统一的出现在集成的 模式中。 进入九十年代，随着模式集成问题的发展变化，模式匹配开始应用于 将数据源集成到数据仓库的过程中。数据仓库是支持决策的数据库，是从 4 第l 章绪论 一组数据源中提取出来的。这个提取过程需要将数据从数据源的数据格式 转换到数据仓库的数据格式。在设计转换方法时，匹配操作是十分必要的。 给定一个数据源，创建一种合理的转换方法首先要找到同时出现在这个数 据源和数据仓库中的那些元素。这是一个模式匹配过程。创建了最初的映 射后，数据仓库设计者需要检查每一个元素的详细语义，并创建转换方法 使这些语义和数据仓库中的目标语义一致，最终完成数据源到数据仓库的 集成工作。 在最近的二十年，电子商务的出现进一步推动了模式匹配的研究。模 式匹配开始应用到电子商务的信息转换过程中。在电子商务过程中，交易 双方要频繁交换描述商务交易的信息。任何一个交易方都使用自己的信息 模式。不同的信息模式可能包含不同的名称、不同的数据类型，允许值的 范围也不同。信息转换问题实际上是不同消息模式转换的问题，而不同消 息模式转换问题实际上是一个模式匹配问题。目前主要是人为的指定不同 信息模式间的相关性，而通过模式匹配操作在两个不同的信息模式问生成 一个直观的映射，就可以很容易的找到信息模式间的相关性，很大程度上 减少人工干预，提高了电子商务交易过程中信息交换的效率。 国外对于模式匹配技术的研究开始的较早，已经有了一定的研究成果 和一部分模式匹配方法的原型系统。但其中大部分成果是基于两个输入模 式完成匹配的。例如，斯坦福大学的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 n t 0 0 1 ) 方法m ，7 1 ，华盛顿大学的l s d ( l e a r n i n gs o u r c ed e s c r i p t i o n s ) 方法【8 9 1 以 及q o m ( q u i c ko n t o l o g ym 印p i n g ) 方法【1 0 1 1 】等等。 1 _ 2 2 多源模式匹配方法的发展历史和研究现状 随着深网数量的迅速增多，同一领域中出现了大量的可检索的在线数 据库，这些可检索的在线数据库都可以提供有结构的信息。这部分信息不 能通过静态的u r l 链接访问到，只能在数据库的查询界面上输入一定的查 询条件后，作为数据库提供的动态查询结果被访问。每一个在线数据库源 都在它的查询界面上通过自己规定的属性接受查询。因此，要完成对相同 领域在线数据库源中海量信息的集成，首先要完成查询界面间的模式匹配 燕山大学工学硕士学位论文 工作。而多源模式匹配方法是近年来针对可检索在线数据库查询界面的匹 配问题出现的类新的模式匹配方法。 多源模式匹配方法是同时对输入模式集合中的所有模式进行处理来完 成匹配的。模式集合中各模式的结构可以是相同的，也可以是不同的。多 源模式匹配方法在完成匹配的过程中不再需要人工的干预，匹配效率较高， 因此较适合于大规模的模式匹配工作。 现有的多源模式匹配方法主要有两种。2 0 0 3 年美国伊利诺大学计算机 科学系的b i nh e 等人首先提出了一种针对在线数据库查询界面的模式匹 配方法 1 2 。5 1 ，该方法采用统计学思想，同时对模式集合中所有的模式进行 处理，是第一个对可检索的在线数据库查询界面完成模式匹配工作的成形 的多源模式匹配方法。2 0 0 4 年b i nh e 等人又提出了在线数据库查询界面 闯的复杂匹配发现方法f 1 6 啦】，该方法将数据挖掘思想引入到模式匹配过程 中，能够发现查询界面间存在的复杂匹配。而在2 0 0 5 年，b i nh e 等人设 计了元查询系统【2 3 也轴，将多源模式匹配方法应用到其中，初步解决了同一 领域中可检索在线数据库源的集成问题。 1 3 本文的研究内容 在对现有的多源模式匹配方法进行分析比较的基础上，提出了本文的 观点，并针对现有方法的不足进行了补充，主要分为以下两个方面： 第一，考虑到现有方法在保留最终匹配模型的同时不能完成复杂匹配 的问题，将两种多源模式匹配方法进行了有机地结合，使得改进后的方法 可以完成简单匹配和复杂匹配，同时保存最终的模式模型以及模型中各属 性的使用频率，方便了后续元查询系统的设计。 第二，考虑到现有多源模式匹配方法直接对模式属性进行操作，单纯 依靠字符完成匹配，需要反复扫描模式集合。计算量大，时间复杂度高的 问题，将素数理论引入到模式匹配过程中，将字符匹配转换成数学运算， 使改进后方法的时间复杂度控制在多项式级别内，进一步提高了匹配效率。 最后提出了基于素数的多源模式匹配算法，给出了算法分析，并利用 6 第1 章绪论 四个领域中2 1 1 个实际在线数据库源中的模式信息对算法进行了验证，并 对相同数据下现有多源模式匹配方法产生的匹配结果和匹配的效率进行了 比较和分析。 1 4 研究意义 本文指出了现有两种多源模式匹配方法的不足之处，并在此基础上提 出了种新的匹配方法。所提出的基于素数的多源模式匹配方法克服了现 有多源模式匹配方法的不足，进一步提高了匹配效率，将该方法应用到元 查询系统中，可以更全面更快速的完成对同一领域中在线数据库源的集成 工作，因此有着很好的应用前景。同时，对于多源模式匹配方法的研究还 处于起步阶段，基于素数的多源模式匹配方法的提出必将为后续多源模式 匹配的研究工作奠定坚实的基础。 1 5 本文结构 第2 章主要介绍了一般模式匹配方法的分类标准，现有的一些原型系 统；详细介绍了现有的多源模式匹配方法以及一般模式匹配方法和多源模 式方法的异同点。 第3 章主要介绍了基于素数的多源模式匹配方法的模型构建过程以及 属性的预处理过程，指出了将素数引入到模式匹配过程中的作用，提出了 属性素数化算法，并对算法进行了相应的分析。 第4 章主要介绍了经常同时出现在相同模式实例中的组属性的挖掘方 法，不同时出现在任何模式实例中的同义词的发现方法，对同义词匹配的 选择方法，最终匹配模型的生成方法，以及对模型中包含的频繁使用属性 的概率评估方法。分别提出了组属性挖掘算法、同义词匹配发现算法和匹 配选择算法，最后提出了基于素数的多源模模式匹配算法，并对各算法给 出了相应的算法分析。 第5 章通过具体的实验对基于素数的多源模式匹配算法进行验证，将 燕山人学工学硕士学位论文 该算法得到的匹配结果和现有多源模式匹配方法得到匹配结果进行比较 并对各种方法完成匹配的效率进行分析。 最后，总结了本文的工作并提出了下一步设想。 第2 章模式匹配方法概述 2 1 引言 第2 章模式匹配方法概述 经过2 0 年的研究，已经提出了许多模式匹配方法，这些方法应用的领 域、使用的匹配标准、针对的模式类型各不相同，因此对现有的模式匹配 方法进行分类，可以方便用户根据具体情况选择合适的匹配方法完成匹配 任务。目前的模式匹配方法在完成匹配的过程中多需要人为的干预，需要 手动的指出匹配，随着要集成w e b 数据源的增多，人为的干预在很大程度 上降低了匹配的效率。因此，近年来出现了面向大规模模式的多源模式匹 配方法。 2 2 一般的模式匹配方法 下面将对一般的模式匹配方法进行介绍，首先介绍目前对一般模式匹 配方法的一些分类标准，其次将对现有的一些模式匹配方法的原型系统进 行简要的分析。 2 2 1一般模式匹配方法分类 当进行模式匹配操作时，需要从现有的模式匹配方法中选择恰当的方 法。如果单独选择种模式匹配方法完成匹配任务，需要考虑所选择方法 针对的模式类型和该方法针对的匹配基数以及该方法是否使用辅助信息等 问题。如果选择使用多种模式匹配方法共同完成匹配任务，则需要考虑是 混合多种模式匹配方法，使用多个匹配标准来完成匹配；还是将多个模式 匹配方法产生的匹配结果相结合，得到最终的匹配结果。根据这种情况， 对现有的模式匹配方法迸行分类，可以方便用户对所需的模式匹配方法进 行选择。 茎生盔兰三主堡主兰望笙苎 对于单独的模式匹配方法，主要有五种分类标准 3 0 - s 3 】，这些分类的标 准是对一般模式匹配方法从大到小进行分类的，如图2 1 所示。 一般的模式匹配方法 单独的模式匹配方法联合的模式匹配方法 基于模式的模 式匹配方法 基于实例的模 式匹配方法 混合的模式匹 配方法 合成的模式匹 配方法 元素级模式 匹配方法 结构级模式 匹配方法 元素级模式 匹配方法 手动合成的模 式匹配方法 自动合成的模 式匹配方法 基于语言的 模式匹配方 法 基于约束的 模式匹配方 法 基于约束的 模式匹配方 法 基于语言的 模式匹配方 法 基于约束的 模式匹配方 法 图2 - 1 一般模式匹配方法分类p ” f i g u r e2 - 1c 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 ga p p r o a c h e s 【3 0 】 ( 1 1 基于模式的和基于实例的模式匹配方法基于模式的模式匹配方 法仅考虑模式信息，并不考虑实例数据。可用的模式信息包括像名称、描 述、关系、约束等模式元素的通用属性和模式结构。通常情况下，基于模 式的模式匹配方法能够发现多个候选匹配，每一个候选匹配都有一个在 o 。1 范围内的数字化的匹配相似度值，通过e e 较这些数字化的相似度值可 以得出最优的候选匹配。基于实例的模式匹配方法考虑实例级数据，通过 实例级数据可以发现模式元素表示的内容和意义。特别是在没有给定任何 第2 章模式匹配方法概述 模式信息的情况下，可以通过实例数据手动的或自动的构造出模式。在基 于模式的模式匹配方法发现的候选匹配具有相同相似度的情况下，应用基 于实例的模式匹配方法可以进一步选择出正确的候选匹配。 ( 2 ) 元素级的和结构级的模式匹配方法元素级的模式匹配方法为第 一个输入模式中每一个元素找到在第二个输入模式中与之相匹配的元素： 元素级的模式匹配方法可以考虑到原子级别的元素，像x m l 模式中的属 性或关系模式中的列；同时元素级的模式匹配方法也可以应用到粗粒度非 原子级别的元素匹配，像文件记录、实体、关系表、x m l 元素间的匹配。 结构级的模式匹配方法考虑同时出现在一个结构中的元素组合间的匹配， 在理想状态下，两个模式结构中的所有组件可以完全匹配，通常情况下只 需要匹配一部分组件。和结构级的模式匹配方法相比，元素级的模式匹配 方法仅仅考虑元素，而忽路了元素的子结构和自身的成分。 f 3 1 基于语言学的和基于约束的模式匹配方法基于语言学的模式匹 配方法使用名称和文本找到语义上相似的模式元素，像基于名称的模式匹 配方法和基于描述的模式匹配方法，这些匹配方法使用相同或相似的名称 或者使用模式中包含的用自然语言书写的注释对模式元素进行匹配。基于 约束的模式匹配方法要求输入的模式都具有像数据类型、值域、唯一性、 关系类型和基数等的约束信息，如果两个输入模式都包含这种约束信息， 基于约束的模式匹配方法就可以根据这些约束信息确定模式元素间语义上 的相似性。 ( 4 1 匹配基数所有模式匹配方法的匹配结果都是使一个模式中的一 个或多个元素和另外一个模式中的个或多个元素间产生匹配关系。因此 存在一般的匹配基数，即l ：1 匹配和面向集合的1 ：n 、n ：l 和m ：n 的 匹配基数。元素级的模式匹配方法只能够完成匹配基数是1 ：1 、1 ：n 和r l ： 1 的匹配。要获得m ：n 的匹配通常需要考虑嵌入模式元素中的结构信息， 这需要结构级的模式匹配方法来完成匹配。 f 5 1 辅助信息大部分模式匹配方法在完成匹配的过程中不仅需要输 入模式，而且需要像字典、全局模式、以前的匹配决策和用户输入等的辅 助信息来帮助完成匹配任务。 燕山大学工学硕士学位论文 通常情况下，由于一种模式匹配方法只使用单一的一种匹配标准完成 匹配刚联合多个模式匹配方法得到的匹配结果往往要优于单独使用一种 模式匹配方法得到的匹配结果。联合多种模式匹配方法主要有两种方式： 混合的模式匹配方法和合成的模式匹配方法。 混合的模式匹配方法是宣接将多个匹配方法相结合，以多种匹配标准 或多种辅助信息为基础确定匹配。和单独执行多个模式匹配方法得到的匹 配结果和完成匹配的效率相比，这种方法提供的匹配结果更为准确，完成 匹配的效率也更高。 合成的模式匹配方法是将多种单独执行的模式匹配方法产生的匹配结 果相结合，这些单独执行的模式匝配方法也可以包括混合的模式匹配方法。 在选择匹配方法、确定各种匹配方法使用的次序以及联结多个匹配结果的 时候可以由用户手动完成，也可以由合成后的模式匹配方法自动完成。自 动的完成方式减少了用户交互的次数，但这种合成的模式匹配方法很难适 应不同领域的应用：而手动的完成方式允许用户选择完成匹配的方法，各 种匹配方法执行的次序以及最终匹配结果的结合方式，这种方式较容易实 现并为用户提供了足够的控制权限，但降低了匹配过程中的自动化程度。 和混合的模式匹配方法相b k 较，合成的模式匹配方法结合匹配方法的方式 更为灵活。 2 2 2 一般模式匹配方法的原型系统 目前已经开发了许多可以半自动完成模式匹配的原型系统，例如， a u t o p l e x 3 4 1 、a u t o m a t c h 35 1 、c l i o t 3 6 埘1 、g l u e 4 0 1 、c o m a ( c o m b i n a l i o no f m a t c h i n ga l g o r i t h s ) t * 1 1 、c u p i d 曩d i k e l 4 y - 4 7 、l s d 、s e m i m 4 8 们、s f ( s i m i l a r i t y f 1 0 0 d i n g ) 【5 0 剐】等等。然而，它们中的大部分是由于特殊的应用需求而开发 出来的，其中仅有很少的几种方法是以一个通用化的方式解决模式匹配问 题的，这种通用化的方式能够适用于不同的应用需求和模式语言。下面简 单的介绍几种通用的模式匹配方法的原型系统。 2 2 2 1 c u p i d 方法c u p i d 方法【4 2 1 是微软研究院的j m a d h a v a n 等开发的 一个通用的模式匹配方法，该方法将语言和结构方面的模式匹配技术相结 1 2 第2 苹模式匹配方法概述 合，是种混合的模式匹配方法，可用来完成x m l 模式和关系模式的匹 配工作。c u p i d 方法首先将输入的模式表示成一个图，然后自顶向下和自 底向上相结合对该图进行遍历。整个匹配过程分为三个阶段：第一个阶段 计算语言的相似度，算法使用了分类、串结构相似和同义词等方法；第二 个阶段计算结构相似度，c u p i d 方法更多的依赖叶子进行匹配；第三阶段 为映射生成阶段。c u p i d 方法适用于数据库模式匹配，和其他的像d i k e 方 法和a r t e m i s ( a n a l y s i s o fr e q u i r e m e n t s ：t o o le n v i r o n m e mf o r m u l t i p l e i n f o r m a t i o ns y s t e m s ) 方法【5 2 】等混合的模式匹配方法相比较，该方法具有更 好的性能，但是c u p i d 方法只能完成匹配基数是1 ：1 和n ：1 的模式匹配 工作。 2 2 2 2 c o m a 方法c o m a 方法】是一种合成的模式匹配方法。该方法 提供了一个承载不同模式匹配算法的可扩展的外部知识库，提供了一个连 接已经获得的匹配结果的框架，同时提供了一个评价不同匹配方法效率的 平台。c o m a 方法的外部知识库中提供了6 种单独的模式匹配方法和5 种 混合的模式匹配方法。目前，外部知识库中的大多数模式匹配方法是利用 模式信息来完成匹配的，如元素和结构属性。c o m a 方法还提供了一个特 殊的匹配器对以上模式匹配方法产生的结果进行筛选过滤。结台策略应用 于匹配处理过程的不同部分，例如，对各个模式匹配方法产生结果的聚合 和对候选匹配的选择。c o m a 方法把输入模式转换成具有根节点的有向无 环图，在图上应用所有的匹配算法对图进行操作。每一个模式元素都是通 过从模式图的根节点到相关节点的完全路径唯一标识的。和c u p i d 方法相 比较，c o m a 方法是一种更灵活的体系结构，并且c o m a 方法的性能要 优于a u t o p l e x 、l s d 、s f 和s e m i n t 等模式匹配方法。 2 2 2 3 s f 方法s f 方法【5 0 】是一种混合的模式匹配方法。该方法首先把 输入的模式转换成标记图的形式，通过定点计算决定图中相关节点间的一 致性。它应用了一个简单的名字匹配器，通过它建立一个初始的元素级映 射并把它反馈给结构化s f 匹配器。s f 不像其他的基于模式的匹配技术， 它没有利用外部知识库中的术语关系，而是完全依赖于元素名字间的字符 串相似度。在匹配的最后阶段，通过指定各种不同的过滤器选择出结构化 燕山大学工学硕士学位论文 匹配器产生匹配结果的一个最优的子集。但s f 方法只能完成匹配基数的1 ： 1 的模式匹配工作。 2 2 2 4 c l i o 方法c l i o 方法【3 7 是由i b m 研究院开发的，用于半自动的创 建一个给定目标模式和一个新的数据源模式之间的匹配映射，创建过程中 需要人工的干预。它由一个模式阅读器的集合组成，这些阅读器对一个给 定模式进行阅读，并且把它转换成内部表示；系统中还包含一个一致性引 擎，用来指出模式间或数据库间的匹配部分；还有一个映射产生器，这个 映射产生器产生视图定义从而把源模式中的数据映射到目标模式的数据 中。其中一致性引擎利用了元素级的匹配，而这些匹配是从一个知识库中 获得的，或者是由一个用户通过图形界面输入的。 这些通用的模式匹配方法的原型系统都是对两个输入模式进行处理， 得到两个模式间的有语义对应关系元素，利用这些元素进一步完成少数几 个模式问的模式匹配工作。并且大多数方法只能半自动化的完成匹配，且 完成匹配的效率较低，无法适应i n t e m e t 上可检索在线数据库中大规模模 式的匹配任务，因此近年来出现了满足大规模模式匹配需要的多源模式匹 配方法。 2 3 现有的多源模式匹配方法 近年来，w 曲上可检索在线数据库源中隐藏的有价值的信息的数量越 来越大。由于这部分信息无法通过静态的u r l 链接访问，只能通过在再现 数据库查询界面上提交动态查询后，作为查询的结果被访问。因此如何集 成大量可检索在线数据库源中隐藏的海量信息就成为数据集成领域的一个 新的研究重点。 元查询系统【2 3 l 初步解决了对w e b 上相同领域中可检索在线数据库源 的集成问题。元查询系统是指建立一个查询门户，系统将用户在其查询界 面上输入的查询条件在相同领域的若干在线数据库源中进行查找，最终反 馈给用户最优的查询结果。元查询系统的核心操作之一是模式匹配。对各 个在线数据库的查询界面进行匹配，这是实现对隐藏在各在线数据库查询 1 4 第2 章模式匹目b 方法概述 界面后的海量数据集成必需的操作。 2 3 1元查询系统简介 开发元查询系统的目的是帮助用户集成和使用i n t e r n e t 上相同领域中 可检索在线数据库源中隐藏的有价值的海量信息。该系统的提出主要是考 虑这样的情况：现有一个用户想以最低的价格在i n t e r n e t 上购买一本书。 则该用户在购买书时遇到了两个困难：其一，他要找到尽可能多的和书籍 相关的在线数据库源，以便对各个在线数据库源提供的书籍价格进行比较。 从而选择出价格最低者；其二，由于各在线数据库源使用的查询模式各不 相同，用户要了解每个查询界面的查询细节才可以对该数据库源实旌查询。 由此可知，元查询系统研究的主要内容是： 首先，对于相同领域存在的大量在线数据库源，通过匹配各查询界面， 集成尽可能多的在线数据库源。 其次，对从各在线数据库源中得到的查询结果，进行比较和分析，反 馈给用户最优的结果。 元查询系统的主要操作过程如下： 首先，抽取查询界面。给定各在线数据库源h t m l 格式的查询界面， 抽取出其中需要匹配的属性信息。 其次，匹配查询界面。找到各查询界面上使用属性间对应的语义关系， 得到各查询界面上有同义词对应关系的属性组，以便确定元查询系统门户 网站查询界面上使用的属性。 最后，进行查询处理。将用户的查询要求通过匹配的属性分散到各在 线数据库源中，将各在线数据库源中查询到的结果集中，选择最优者反馈 给用户。 显而易见，其中的关键操作是第二步模式匹配，它是元查询系统 整个操作过程的核心。目前有很多种模式匹配方法，在元查询系统中采用 了种多源模式匹配方法m g s 框架【l 。 现有的多源模式匹配方法主要有两种：全局的评估方法和局部的评估 方法。全局的评估方法以假设存在一个隐藏的模式模型为基础，需要列出 燕山大学工学硕士学位论文 所有可能的模式模型，每一个模型都可以表示输入模式集合中各查询面上 使用属性间的匹配关系，已经存在的原型系统是m g s 框架。而局部的评 估方法则是独立的列出所有的匹配，已经存在的原型系统是d c m 框架【”l 。 2 3 2 基于m g s 框架的多源模式匹配方法 m g s 框架以假设存在一个隐藏的模式模型为基础，采用统计学的方法 完成对相同领域各在线数据库源的模式匹配工作。该框架分三个阶段完成 匹配工作。首先是假设建模阶段，这个阶段为假设的隐藏模型具体的指定 一个参数化的结构，这个模型用来捕获在模式匹配过程中要解决的目标问 题，这样的目标问题如找到各在线数据库源查询界面上属性间简单的1 ：l 匹配；其次是假设生成阶段，这个阶段生成能够产生输入模式集合中全部 模式实例的所有可能的模式模型；最后是假设选择阶段，这个阶段要选择 和输入模式集合有最充分统计一致性的模型，这个模型可以产生所有输入 的模式实例并且它的结构能够回答目标问题。 m g s 框架的最终结果是一个包括所有频繁使用属性及其使用概率的 模型，如例1 所示。 铡1 ；i = f ， ，3 ，4 ， 1 4 ， 。其中i i = a u t h o r , s u b j e c t ，t i t l e ，i s b n ，1 2 = t i t l e ，c a t e g o r y , f i r s tn a m e ，l a s tn a m e ，1 3 = f i r s tn a m e ， l a s tn a l l l e ，i s b n ，c a t e g o r y ，1 4 = a u t h o r , c a t e g o r y , t i t l e ，1 5 2 t i t l e ，i s b n ， s u b j e c t ，f i r s tn a m e ，l a s tn a m e 。 对例1 中的模式集合i 执行m g s 框架，得到6 个候选模型，如图2 2 所示，对每个模型中的属性进行概率评估，并反复筛选候选模型，褥到两 个最终模型m 4 和m 6 。 对于例1 中的模式集合i ，m g s 框架对列出的6 个候选模型中使用的 属性分别进行概率评估，而最终合理的模型只有2 个，因此算法的消耗比 较大。最终得到的两个模型m 4 和m 6 中，很好的发现了简单匹配 s u b j e c t = f c a t e