空间数据模式匹配应用范文

《地理与地理信息科学杂志》2014年第四期

1模式匹配的主要应用领域

1．1更新信息传播空间数据现势性是GIS的“生命”，直接影响着其使用价值与可持续发展。伴随着GIS空间数据更新理论研究和工程实践的不断深入，更新信息传播问题已成为生产单位、应用部门及学术界共同面临的新问题。由于数据库间在数据模式和数据实例之间存在多种潜在的语义差异，当利用一个新版GIS数据库中的更新变化要素及其相关信息对另一个GIS数据库中的对应要素进行更新（即更新信息传播）时，必须首先在两个数据库间进行模式匹配操作建立模式映射关系，以引导和简化变化发现、实体识别、更新集成等操作，从而在保证更新传播实施效率的同时，最大限度地维护目标数据库的自治性、完整性、正确性和一致性［6，7］。

1．2语义查询处理目前使用的空间数据查询方式大都是基于关键字匹配技术，如果用户输入的查询关键字与被查数据模式元素的名称不尽相同或有所偏差，则不能返回真正需要的信息或者会返回很多无用的信息。为解决传统查询方式的不足，提出了语义查询技术［8］。语义查询又称语义检索、概念匹配，是指在相关技术（如本体等）的支持下，首先使用户的查询请求和被检索的内容在语义上都是可被计算机理解、处理的，在此基础上对用户查询语句（如Select语句）和被查数据模式元素进行匹配，然后重写查询语句中的关键字使其与被查数据模式名称相一致，从而返回准确的查询数据。

1．3地理服务发现网络地理服务是利用地理数据和相关的功能实现诸如地址匹配、地图绘制、路程安排等基本地理操作任务的Internet应用，它允许开发者将GIS功能集成到自己的Web应用中，而不用自己在本地实现该GIS功能［9］。随着越来越多的网络地理信息服务的出现，快速准确找到用户需要的地理信息服务显得尤为重要［10］。在服务发现过程中，一旦服务请求者和提供者使用不同的术语表示同一个概念或者是同样的词表示不同的涵义，就会发生找不到匹配的服务和找到的服务不能完全满足需求的情况。另外，地理服务版本差异造成的语义异构也将增加服务发现的难度。与语义查询类似，通过模式匹配也可以有效解决这类问题。

2模式匹配相关研究内容综述

近些年来，模式匹配作为数据管理与应用中的基础性问题受到了全球的普遍关注，在数据库、人工智能、信息检索、知识管理、语义Web等众多领域引起了广泛的讨论和研究。概括而言，当前对模式匹配问题的研究主要集中在匹配实施方法、匹配效率优化、匹配结果表达、匹配质量评价4个方面。

2．1匹配实施方法研究目前，大多数系统的模式匹配任务是在图形界面支持下靠操作员手动完成的，该方式不仅要求操作员充分了解模式元素的语义内涵，而且随着待匹配模式元素数据的增加，其费时、费力、易出错的缺陷也将变得更加突出。另外，用户需求的变化、数据源的变化等都可能造成模式的变化，从而导致这些模式间的匹配关系发生变化。显然，如果仅仅依靠手工匹配无法适应这种复杂动态的匹配需求。为了尽量减少模式匹配过程中用户的参与，提出了多种自动（或半自动）的匹配方法及系统。Rahm等根据匹配所依据的信息类型及其结合方式对各种模式匹配方法进行了层次式划分（图2），结合图2的分类体系又对2001年以前的典型匹配方法及系统进行了比较权威的总结和评述［13］。在此分类体系基础上，Shvaiko等根据所用技术的特征（Heu－risticorformal，Implicitorexplicit）对其中基于模式的匹配方法做了更为详细的划分［14］。潘超等则进一步总结了2010年之前的主要方法及系统［15］。本文依据图2所示的分类结果，对模式匹配方法的基本策略和问题做简要评述。（1）单匹配，主要利用某一种类型的信息识别语义相关模式元素，可进一步划分为基于模式的匹配和基于实例的匹配两类。1）基于模式的匹配方法，主要通过对比模式元素本身所包含的信息（如名称标签、描述性元数据、数据类型、数据长度、结构关联关系等）判断元素是否匹配。由于数据模式设计本身是一项灵活性很大的主观活动，不同的设计者可能采用不同的机制和元素来抽象和模拟相同的现实事物或现象，并且所形成的模式结构的语义信息大部分隐含在设计者的大脑中，而模式元素本身所承载的一部分外在显式信息对模式匹配而言是不明确、不完整、易混淆的。因此，该类方法往往产生错配、漏配等情况，质量和效果不高。针对这一情况，文献［16］提出了基于信息论的模式匹配模型，尝试解决模式信息丢失或者不完整情况下的模式匹配问题。2）基于实例的匹配方法，主要依据属性字段数据值的统计概括信息（如最大值、最小值、平均值、方差）或部分重叠对应实体的属性值，来匹配识别两个数据集（如关系表）之间语义相关的属性字段，一般不能确定数据集之间的匹配关系。由于概括信息是确定属性是否匹配的必要但不充分信息，因此如果单独用其进行匹配常常会产生一些错配或漏配现象。针对这种情况有两种改进途径：一是将概括信息与其他类型的信息结合构成混合匹配；二是通过进一步分析比较数据集之间部分对应实体（或重复记录）的属性值来确定相关的属性，但这种方式目前通常以预先手动建立实体对应关系为基础，自动化程度低，属性相关性对比分析和度量模型较单一，尚没有充分考虑语义相关属性在具体属性值上的各种表达差异，仍有很大的扩展改进空间。（2）多匹配，主要利用多种类型的信息或方法识别语义相关模式元素，可以进一步划分为混合匹配与复合匹配两大类。1）混合匹配主要通过综合使用多种匹配指标或信息源（如名称信息、元数据描述信息、数据约束信息、实例概括统计信息、属性依赖关系等）来确定匹配元素。混合匹配在确定一对模式元素是否匹配时，同时考虑了多种匹配标准，对于不符合标准的候选成员能够较早地被删除。因此，这种方法与单独执行多种匹配方法相比，可以减少比较模式信息的遍历次数，不仅能取得较好的匹配性能和效果，而且匹配效率也得到了提高。但由于多种来源的信息具有不同的表达形式，一般并不能被直接应用于混合匹配，常常需要制定高效的策略和规则对其进行规范化处理。混合匹配所依据的匹配信息和规则往往由设计者事先规定，一般不易进行调整和修改，灵活性较低。2）复合匹配主要通过对多个独立匹配方法（如基于模式的匹配、基于实例的匹配、混合匹配等）所取得结果的组合分析来确定匹配元素。复合匹配允许用户根据应用需要，灵活地选择现有方法并按不同的顺序（如并行顺序、串行顺序、混合顺序）加以执行。在串行执行时，前面匹配方法所取得的匹配结果，可以用作后面匹配方法的输入，从而达到反复修改匹配结果的目的。复合匹配是以单个匹配方法为基础的，为保证其效率和效果，不仅要尽可能地提高每个成员匹配方法的效率和效果，而且应该选择正确的执行顺序、制定合理的结果重用和组合策略［19］。静态组合的匹配算法和人工调节的匹配参数难以适应自动匹配的要求，如何对现有的匹配算法进行动态选择、搭配、组合、重用以及对匹配参数进行自动调节是复合匹配面临的一个有待深入研究的重要问题。每种匹配技术都各有其优点和适用范围，综合使用多种匹配信息或方法能够充分发挥不同技术间的互补性优势，有效提高匹配系统的匹配质量和通用性。但随着匹配信息或方法的增加，系统的复杂性也将随之增加。

2．2匹配效率优化研究当前模式匹配的难点，不仅在于缺乏切实可行的判别模式元素是否匹配相关的策略和规则，更在于依据判别规则执行模式匹配的代价偏高，必须进行大量的计算比较才能确定获取潜在的匹配元素。模式匹配中最常用的两两比较法，也称嵌套循环法或笛卡尔法，是将两个待匹配模式元素集合做笛卡尔乘积，根据用户所定义的规则和策略，对结果集中的每对元素进行比较，如果比较结果满足所定义的规则条件，则认为它们是匹配元素。该方法简单，能够最大限度地保证匹配结果的质量和精度，但是随着待匹配元素数量的不断增加，所需的处理时间和系统资源的消耗将呈指数级增长，在实际应用中的可行性和使用价值并不高。因此，必须加强模式匹配效率优化模型及算法的研究。目前，只有少数几个系统考虑处理了模式匹配的执行效率问题，根据模式匹配策略的不同，提出了不同的模式匹配执行效率优化技术。概括而言，现有模式匹配执行效率优化所采取的基本策略主要有如下5种［20］：1）分而治之，先将待匹配的模式元素集划分为不同的块（Blocks）、区（Partitions）或簇（Clusters），然后在块（区或簇）之间执行模式匹配。该策略降低了匹配比较的搜索空间，效率较高，但可能降低匹配质量。2）模式过滤，依据相关的上下文信息或通过问卷调查预先排除掉一些模式元素，从而降低比对次数，提升匹配效率。3）避免重复，在模式匹配执行过程避免一些相同子任务的重复执行。4）改善数据结构，利用诸如索引、Hash表等特殊类型的数据结构，减少待匹配模式元素间的比较次数，从而提高执行效率。5）优化模式元素相关性度量模型（如编辑距离等）的计算效率等。随着大数据时代的到来，势必出现大模式的匹配问题。大模式的“大”不仅意味着数量的大，还代表着模式种类多、结构杂、差别大、变化快等。由于目前尚没有对大模式匹配问题给予充分的考虑和有效的处理，若采用现有策略执行匹配将会因时间复杂度过高而得不到理想的匹配结果。针对大模式匹配执行效率问题，可通过大模式聚类分割技术加以解决［21］。目前这一技术仍需攻克3个核心问题：如何分割模式；如何选择需要进行匹配的模式片断；如何避免模式分割可能造成的结果遗漏。

2．3匹配结果表达研究匹配结果（模式映射）表达的主要任务是存储和组织通过匹配识别发现的相关模式元素及其映射关系，并构建相应的存取和检索方法，以引导和简化各种应用处理中的其他操作。目前，有一些匹配工具把模式映射保存在纯文本文件中，而且不同工具定义的模式映射文件格式不同，缺乏足够的语义表现力和处理能力，使得模式映射的读取过程较烦琐，造成不同系统间难于共享模式映射，通用性不强；还有一些匹配工具使用关系数据库存储和管理模式映射，但由于模式映射的半结构化特征，往往导致数据表中出现很多值为NULL的字段，从而造成非常大的冗余，使得很多复杂的匹配关系（如条件匹配、部分匹配、计算匹配等［22］）无法得到有效的表达，且每当待匹配元素数目发生变化时，将可能导致整个数据表的结构重构，不便于模式映射的管理和维护。针对上述模型及方法的不足，一些学者开始尝试利用基于逻辑的语言（如一阶逻辑、描述逻辑、Datalog等）或半结构化模型（如XML、RDF等）来表达和存储模式映射。例如，文献［23］利用一阶逻辑表达XML模式与OWL本体间的语义映射；为评价对比现有基于逻辑的映射语言的共性与差别，文献［24］采用分布式一阶逻辑来统一现有的各种映射语言；文献［25］采用巴克斯范式（Backus－NaurForm，BNF）来表达语义映射；文献［26］提出了一种新的映射语言———RDFMappingSchema来表达XML数据和RDF数据之间的语义映射；文献［27］在BRICKS系统中采用XML来存储和管理模式映射。目前大部分模式匹配研究的重点仍集中在如何发现和找到语义相关元素匹配对，有关匹配结果表达的研究才刚刚起步［28］，有些表达语言或模型的提出尚处于思想萌芽阶段，也只是仅仅给出了一些示例性的表达结果，仍缺乏系统性的研究，更没有形成统一的表达语言或模型。即使是同一种语言或模型，表达映射的方式也不尽相同，所支持的功能和算子差别较大［29］。匹配结果表达的研究仍然面临着许多开放性问题，如表达模型能够支持的映射关系类型及语义转换函数种类、匹配结果的检索与编辑、匹配结果的有效性检验、匹配结果的可视化等。

2．4匹配质量评价研究虽然人们对模式匹配问题进行了广泛研究，但大部分的自动匹配方法还停留在高度实验阶段，而得不到广泛的实际性应用。其中也有一些较为实用的系统出现，而这些系统却依旧需要大量的人机交互或后处理工作，还远远满足不了实际需要。当前有关自动匹配质量的研究主要集中在质量评价模型和策略上，概括而言，各种自动匹配方法及系统的匹配质量可以从有效性（Effectiveness）、效率（Efficiency）、通用性（Genericity）和易用性（Ease－of－use）4个方面加以评价［30］：1）有效性：主要考虑匹配结果的正确性和召回率，通常用Precision和Recall两个单项指标及F－Measure（a）、F－Measure、Overall等几个综合指标加以衡量。2）效率：主要考虑系统执行匹配时所消耗的资源，如时间、内存等，通常情况下只采用时间指标来评价匹配效率。3）通用性：主要考虑系统的应用领域、所支持的数据模型或类型及系统是否可以支持在线匹配或离线匹配。目前还没有评价匹配系统通用性的定量指标或模型。4）易用性：不论全自动匹配能否实现，用户的参与及交互总是需要的，易用性主要考虑通过自动匹配能够节省多少人力，一般应综合考虑匹配执行的预处理与后处理两个阶段。然而，现有的评价策略常常将预处理阶段的人力参与忽略掉，只考虑后处理阶段用于添加遗漏匹配、移除或修改错误匹配的人力参与。上述的有效性指标可在一定程度上反映模式匹配后处理阶段的人力参与情况，但由于这些指标的取值介于0～1，直接用其评价人力参与情况还不太恰当。针对这种情况，Bogdan等提出了简单可用性（SimpleUsability）模型和简单成本（SimpleCost）模型，这两个模型分别根据人机交互过程中拖拽、单击、双击3种不同的鼠标行动及其执行成本来评价人力参与情况。以上单因素评价模型彼此间是相互矛盾的，仅利用其中的任何一种都不能全面客观地评价匹配系统，因此，需要将这些指标综合起来考虑，对匹配系统进行总体上的质量评价，这实际上是一个多目标模糊决策难题。文献从有效性和效率两方面讨论分析了匹配系统的总体评价方法，但却忽略了通用性和易用性两方面的因素。总体而言，目前人们虽然认为自动匹配的质量评价与控制是一个很重要的问题，却没有高度重视它，自动匹配质量问题的研究还没有全面深入地展开。

3结语

经过近30年的不懈努力，模式匹配问题研究已取得了较为丰富的学术成果，从最初的利用元素自身的各种信息进行模式匹配，到后来集成各种类型的结构信息、数据实例信息来辅助匹配，再到近年来为模式匹配方法寻找理论支持，提供人性化的用户干预工具等。但由于模式匹配本身的主观性与复杂性，目前仍然存在着一些问题和不足。现有大多数研究主要集中在匹配方法上，一般只专注于不同模式之间的简单匹配（即1∶1匹配），不能有效识别复杂匹配（即1∶N、M∶l和M∶N匹配），应用往往局限于特定领域或特定模式，通用性有待提高。对模式匹配的不确定性、模式通用表达模型、匹配方法的质量评价、模式结果的后处理分析、匹配结果的存储管理及可视化维护等问题尚缺乏整体系统的分析和全面深入的研究。从文献资料上看，目前针对空间数据模式匹配的研究仍比较薄弱，有关空间数据模式匹配问题的阐述大多是一些附带的概念性解释，缺乏针对性的深入分析，仅有少数研究侧重于具体方法的设计及原型系统的实现。与空间数据模式种类多、规模大、结构复杂的特点相比，现有研究尚不能满足一个理想模式匹配系统在通用性、强壮性、灵活性、交互性和扩展性等方面的要求。因此，很有必要进一步积极开展针对空间数据模式匹配的系统性研究工作，从而为空间数据资源的高效共享与灵性服务提供理论支持与技术保障。

作者：王育红景海涛薛华柱单位：河南理工大学测绘与国土信息工程学院