信息集成中的字符串匹配技术研究，本文主要内容关键词为：字符串论文,技术研究论文,信息论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
收修改稿日期：2007-06-11
【分类号】 TP393
信息集成是指综合运用查询处理、中间件、包装器等技术，把相互关联的分布式异构信息源集成在一起，实现变异构为同构，最终实现信息语义的统一[1，2]，从而有效地实现信息的共享[3]。在信息集成中，一个关键问题就是不同数据源模式中对等实体的识别，即匹配问题[4，5]。
1 匹配的内涵
匹配的目标是发现不同模式结构相关实体之间的映射关系，基本思想是：首先通过对标识结点的分析推得相关结点间的对应关系，然后根据获得的对应关系，通过运用各种筛选技术（Filtering）来确定最终的映射集。
一般匹配系统中输入的是两个分布在不同信息源中的实体（如表格、XML元素、属性、规则、断言等），而输出的则是这些实体间所蕴含的关系（如相等、包含、兼容等）[4]，其结果可以采用一个四元组的映射〈id，e，e′，n〉进行描述。其中，n是反映两个模式不同实体（e，e′）间的对应关系的相似系数（Coefficients），其大小直接反映了两个模式不同实体间的相似程度。当n为1时，表示e和e′完全相同；当n为0时，表示e和e′完全不同[4，5]，n的值域为[0，1]。
至今，人们已经提出了多种匹配算法，每种算法都各有优缺点。许多匹配系统都是对它们的综合使用，如Cupid[6]、COMA[7]、S-Match[8]、SF（Similarity Flooding）[9]、Artemis、OLA等[4]。Shvaiko和Euzenat[4] 吸收了Rahm和Bernstein[5] 的分类思想，提出了基于粒度/输入解释的分类（Granularity/Input Interpretation Classification）和基于输入信息类别的分类（Kind of Input Classification）的综合分类体系。下面，笔者将对Shvaiko & Euzenat分类体系中元素层匹配算法中的基于字符串的匹配技术进行分析，具体包括基于编辑距离、基于标记和N元文法的匹配算法。
2 字符串匹配技术
字符串匹配技术的基本思想是：将字符串看作是字符序列，字符串间相同的字符越多，则表明这两个字符串越相似，即两个实体间的相似系数就越大。字符串匹配技术本身可以细分为词缀匹配法（前缀匹配法和后缀匹配法）、基于编辑距离的匹配法、N元文法以及基于标记的相似度法[10] 等。
2.1 词缀匹配法
词缀匹配法是字符串匹配中最简单的方法，可分为前缀匹配法和后缀匹配法。前缀匹配法（Prefix）[4，12，13] 的基本思想是：先输入源字符串和目标字符串，然后检测源字符串是否以目标字符串开头。如果是，则返回相等关系，或相似性系数为1；否则返回idk（I don' t know）或相似性系数为0。
后缀匹配法（Suffix）[4，12，13] 的基本原理和前缀匹配法相似，不同的是它检测的是源字符串是否以目标字符串为结尾。如果是，则返回相等关系，或相似性系数为1；否则返回idk或相似性系数为0。
在匹配同根字符串的应用中，词缀匹配法非常有效。但要注意的是，词语形式上的一致不等于其语义上的一致性，如单词hot与hotmail，myself与yourself等；同理，词语形式上的不一致不等于其在语义上的不一致。因此，需通过其它匹配技术来进一步确认，以提高准确率，这也是出现混合式匹配系统（Hybrid Matcher）和组合式匹配系统（Composite Matcher）的原因之一[6，7]。在实际应用中，无论是前缀法还是后缀法，都要考虑词缀的相对长度以及词缀在整个字符串中的比例，通过设置阈值来控制结果的输出。
2.2 基于编辑距离（Edit Distance）的匹配法[4，12]
编辑距离即将一个字符串转换成另一个字符串所需要进行插入、删除、替换等相关编辑操作的次数。基于编辑距离的匹配法是先输入两个字符串，然后计算两个字符串间的编辑距离，计为d。m取较长的字符串的长度，即m=Max（字符串1，字符串2），n为d与m的比值，即：n=d/m。当n小于阈值时，则返回相等关系或1，否则返回idk或0。
显然，这是一个递归计算过程，可以通过动态规划技术来实现。
Sellers算法是对Levenshtein算法的改进，也称为Needleman-Wunch Distance，其主要的改进是修改了权值的计算方法，即在对字符串进行替换、插入和删除时，每操作一次的权值W并不固定为1，而是根据相关参数来确定。只有当W被赋予1时，才和Levenshtein算法一致。
Smith和Waterman[15] 则在Levenshtein算法的基础上，提出了从不同字符串间求最大相同子字符串的算法：
William Winkler在Jaro矩阵法的基础上对含有相同前缀的匹配字符串的权值计算进行了修正，提出了Jaro-Winkler矩阵法，使得最终的输出结果值为：
JaroWinklerScore（s,t）=JaroScore（s,t）+（prefixLength×PREFIXSCALE×（1.0-JaroScore（s,t）））（4）
其中，prefixLength是相同前缀的长度，PREFIXSCALE是一个常量，可根据相同前缀的长度进行调整。
2.3 基于标记（Token-based）的相似度法[4，8，10]
基于标记的相似度匹配法的基本思想是：将源字符串和目标字符串分别看成是由非停用词构成的文献向量S和T，然后计算出两向量间的相似度值Sim，当Sim大于系统设定的阈值时，则这两个字符串是相匹配的，系统返回相等关系或1，否则不相匹配，返回idk或0。
该算法思想的核心是标记相似度值Sim的计算，它直接决定着匹配结果的准确率。在信息检索领域中，计算相似度的方法有很多，如基于项匹配个数的、基于“距离”的、基于概率的、内积法以及余弦相似度法等。
Matching系数法（Matching Coefficient）是基于项匹配个数的最简单的一种算法，直接把S和T中相同的词项（Term）数作为相似度值。Dice系数法（Dice Coefficient）对相似度值的定义作了改进，把相似度值限定在0-1间：
Sim（S,T）=（2｜S∩T｜）/（｜S｜+｜T｜）（5）
Dice系数法提高了相似度值的精确率，但其在针对具有较少相同词项的匹配问题时，就显得不足，Jaccard系数法（Jaccard Coefficient）填补了这一缺陷，其算法公式为：
Sim（S,T）=｜S∩T｜/（｜S｜+｜T｜-｜S∩T｜）（6）
Overlap系数法（Overlap Coefficient）与Dice系数法相近，将相似度值定义为｜S∩T｜和Min｛｜S｜，｜T｜｝的比值。当一个字符串是另一个字符串的子串时，该法较为实用。
公式（5）、（6）中：｜S∩T｜表示源字符串向量S和目标字符串T中包含的相同非零项的个数，｜S｜表示向量S中非零项的个数，｜T｜表示向量T中非零项的个数。
内积相似度法（Inner Product）和余弦相似度法（Cosine Coefficient）都引入了权重的思想，弥补了上述算法中不能区分不同词项在不同文献中重要程度的缺陷。内积相似度法算法可用下面的公式来表达：
余弦相似度法（Cosine Coefficient）实际上是对内积相似度法的一种规范，其规范化的基础是向量的欧氏长度（L[，2]）[13]（其本身即是一种基于距离的计算相似度值的方法），在实践中使用较为广泛。其算法公式为：
内积相似度法和余弦相似度法中权重的选取是关键。目前，权值计算的方式主要有：
（1）1-0法，即词项出现，权值为1，否则为0。该加权法的缺陷在于否认了词项出现的次数对权值的影响。
（2）按词项出现的次数来确定，分别记为0，1，2，…。此方法的缺陷在于没有考虑到词项出现的次数还与字符串的长短有关。
在对简单的名称字符串进行匹配时，可以使用Jaccard系数法，它不仅实现起来简单，而且准确率也较高。但在对复杂名称、长字符串甚至实例进行匹配时，实践证明采用余弦相似度法与TF-IDF加权法相结合会更好。其中，可以根据具体的信息集成对象或匹配对象采用具体的方式（如最大tf规范、对数tf规范和余弦规范化等[14]）对tf进行规范，以提高余弦相似度法的准确性。
Raymond Mooney[10] 给出了另外两种基于TF-IDF加权法的名称间相似度计算方法，即IF-IDF法和SoftTF-IDF法：
基于概率的相似度计算法是建立在信息熵统计的基础上的，其中，文献向量中的元素是字符串中非停用词在文献中出现的概率，其基本原理是不同字符串间的匹配程度可决定它们之间信息熵差的大小β（S,T）。即字符串S和T之间的相似度值可定义为[14]：
Sim（S,T）=1-β（S,T）（11）
这一类的算法研究成果也很多，如Bhattacharyya法等[21]。
最后将m与设定的阈值比较，如果大于阈值，则返回相等关系或1，否则返回idk或0。
3 结语
基于编辑距离的匹配法对Wordnet[19] 中未登录词（Unknown Word）和缩写词的匹配较为有效，一般在数据库和XML模式匹配中用的较多。但也会出现歧义等问题，如Cool与Cook，根据前面的阈值进行计算，返回的是相等关系，但它们实质上是无关的；而Hill与Mountain在一定程度上却是相似的。
基于N-gram的匹配法与基于编辑距离的匹配法一样，对简写词、缩写词和形态上有细微差别的字符串进行匹配时较为有效，目前，被广泛用于针对数据库和XML模式的匹配系统。但大量实验证明，与基于编辑距离的匹配法相比，N-gram法的结果较为“悲观”。表1是S-Match[8] 系统对这两种算法的比较。
基于标记的匹配法的优势在于：不像基于编辑距离的匹配法和N元文法那样受字符串顺序的约束，而且基于TF-IDF加权法的相似度计算法还同时考虑到了词频、字符串的长度和区分词之间的关系，有效提高了相似度计算的准确性，进而提高了匹配的准确性。例如，要求识别字符串S，T，W之间的匹配关系，S=“name of the student”，T=“age of the student”，W=“student_name”。如果用Jaccard相似度计算法，可得结果：〈1，S，T，1〉，〈2，S，W，0〉；用基于TF-IDF加权法的相似度计算法则可得结果：〈1，S，T，0〉，〈2，S，T，0〉。显然，后者的结果是正确的。
从上面几种字符串匹配方法中可以看到，字符串匹配方法实际上是以词形为切入点的，它实现的是名称或名称描述在形式上的匹配，因此实现起来较为简单；但字符串匹配技术过于“机械”，即使在后来的研究中提出了权重的概念，但依然是建立在词项本身的基础上。自然语言中大量同义词、多义词的存在，导致了不同实体的命名即使在词形上存在对应关系也不等于其语义上也存在相应的对应关系，因此，仅仅根据字符串匹配方法所获得的匹配结果是不可靠的，还应综合考虑这些实体的其它相关属性，其中最重要的是结构属性，也就是说，要考虑这些实体在不同模式中的具体位置信息，即语境信息。因此，字符串匹配方法需要结合其它匹配方法，诸如结构匹配方法（Structure-based）或各种基于语义的匹配方法（Semantic Matching）等，从而实现对匹配结果进行进一步的考证与综合应用，以提高准确率[12]。因此，如何从自然语言处理的角度，综合运用查询优化、相关反馈等技术，从实体概念的本身，也就是从语法、语义以及语用的角度进一步完善和发展信息集成的匹配技术，应该是信息集成研究的一个重要发展方向[4，12，20]。