基于编辑距离的字符串模式匹配算法研究

《基于编辑距离的字符串模式匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于编辑距离的字符串模式匹配算法研究第1章绪论1.1研究背景及其意义随着人类社会的不断快速发展，科学信息技术同样产生了翻天覆地的变化，大量的大规模数据产生于人类社会中的各种不同的应用领域。然而，由于大规模数据都具有高度自治性，从而导致了不同应用领域之间的数据异构性。因此，大规模数据间的相互转换操作就显得尤为重要。而随着Inter的不断迅速发展，就更加需要紧密联系不同应用领域中的大规模数据，而数据集成作为核心的方法，能够实现不同应用领域中大规模数据的共享。模式匹配起源于对模式集问题的研究，早期模式匹配工作就是为了给模式

2、集成提供服务。模式集成是从给定的一组独立开发的模式中构造一个全局视图的过程。由于模式是单独开发的，因此不同的模式使用不同的结构和术语。因此，模式集成的第一步就是确认这些模式间的关系，这就需要模式匹配操作。当这些关系被确认后，匹配的元素就可以统一的出现在集成模式中。随着模式集成问题的不断研究和发展变化，模式匹配的应用已经开始转变到数据仓库领域中。数据仓库是一种支持决策的数据库，它的数据是通过提取一组数据源中的数据。而在这个提取过程，就是要将数据源的数据按照一定标准转换为数据仓库的数据。近些年来，电子商务[1]的出现，对

3、于模式匹配的研究更进了一步。模式匹配进一步应用到电子商务的信息转换过程中。在电子商务过程中，交易双方要频繁交换描述商务交易的信息。任何一个交易方都使用自己的信息模式。不同的信息模式可能包含不同的名称、不同的数据类型，允许值的范围也不同。信息转换问题实际上是不同消息模式转换的问题，而不同消息模式转换问题实际上就是一个模式匹配问题。模式匹配(Schemamatching)就是找出两种模式成员之间上的语义关系而进行的操作。在模式匹配中，输入参数是两个模式，输出参数是匹配结果，即两种模式中元素之间的某种映射关系，而每一种匹配

4、结果都表示在两种模式中的某些元素存在逻辑上的对应关系。......1.2国内外研究现状近些年来，模式匹配作为大规模数据处理中的基础性问题受到了全球的普遍关注。匹配是对模式进行处理的一个基本操作，该操作将模式中的每一个元素找出与另一个模式存在语义对应关，即映射。因此，模式匹配工作仍然是以人工的为主的方式进行匹配。因此需要找出一种可以应用于不同的数据模型和应用领域，通用范围广、自动化程度高的一种综合模式匹配方法。模式匹配系统应用在很多领域中，这是模式匹配原型系统一大特点，例如XML文档的转换和XML模式聚类等领域。如XM

5、L文档自动转换系统[15]是应用在E-Business领域的一个典型系统是的Xtra[16]系统。Xtra系统中在进行文档转换过程，定义了一系列模式转换操作集合、一个评价这些操作集合的代价模型、一个记录算法来记录两个模式转换中的有效操作顺序集合。然后，使用XSLTGenerator将脚本转换成XSLT，再使用一个XSLTExecutor,将源XML文档和与生成的XSLT合成起来，最终生成目标XML文档。在Cupid、A、S-Match[17,18]、XClust、ARTEMIS[19]等模式匹配系统中，采用了多种匹配

6、策略，如名称匹配、结构匹配和上下文匹配等，同时也考虑到了其它方面的模式和实例信息，以此期望得到更优的匹配结果。其中，最具有代表性的是Cupid模式匹配算法。Cupid系统是基于名称、数据类型和与约束的语言学匹配。在匹配过程中，将转换成为一颗标记树进行有底到顶的遍历匹配，对成员之间的结构相似度后加权得到结构相似系数ssim；最后，通过加权值公式(1-1)来进行模式匹配。.......第2章模式匹配技术的描述与分类近年来，模式匹配己成为数据库研究的一个热点的，它的目标是寻找两个或多个模式的元素之间语义上的对应关系。在模式

7、集成、异构数据源集成、语义查询处理、数据仓库、电子商务等领域都有着广泛的研究。2.1模式匹配概述模式匹配[22]是在作为输入的模式中有对应语义关系的元素间产生一个映射。模式匹配的目标是寻找两个或多个模式的元素之间语义上的对应关系。而匹配结果元素包含有以下几种情况，即是空、是一个匹配元素、多个匹配元素或者多个模式元素可能会对应于一个或多个匹配元素，模式元素匹配结果并不是唯一的。而通常情况下的模式匹配关系的基数的情况也并不是唯一的，其包含有1:1，1:N，N:1，N:M四种匹配关系基数，而元素匹配的结果是1:1，1:N，

8、N:1这三种情况。目前，大多的匹配研究工作都是围绕1:1的关系基数来进行的。......2.2模式匹配的分类基于模式的匹配又被分为元素匹配和结构匹配。再往下，元素匹配可分为基于语言学特征的匹配(Linguisticmatch)和基于约束的匹配(Constraintbased)，则结构匹配下面只有一个基于约束的匹配。基于实例的匹配被划为元素匹配，