字符串相似度矩阵算法字符串似度矩阵算法字符串相似度矩阵算法字符串相似度矩阵算法.doc

字符串相似度的矩阵算法 李彬 （武汉理工大学计算机学院 武汉 430070） 摘 要：用两个字符串滑动比较时匹配的字符数和两字符串滑动比较的重叠率定义了相似度的衡量指标，在确定一个字符串较另一个字符串较少的情况下，设计了一种算法，实现了在字符串匹配矩阵中确定插入空格的位置使相似度指标达到最大值，可以用于信息的模糊检索。 关键词：匹配率；相似度；匹配矩阵；信息量 中图法分类号：TP301.6 The Matrix Arithmetic of Computing Strings Similar Degree LI Bin （ Department Of Computer Of Wu’han University of Technology Wu’han 430070 China） Abstract：The similar degree is defined based on the number of matching chars and the overlaping ratio of two strings’ chars when two strings do comparison during gliding.Designing a arithmetic under the sistuation that making sure the length of one string is smaller than another strings’ and makeing sure the position of inserting blank space in strings’ matching matrix makes similar degree gain the biggest value，this arithmetic can used for the misty index of the information. Key Words: Matching Ratio；Similar Degree；Matching Matrix；Information Quantity 1　引言 随着现代科学技术的发展，生物学中的DAN序列的相似性的比较可以用于亲子鉴定等，医学中应用病毒基因的相似性来诊治疾病。与之相似，随着计算机的发展，字符串的相似问题也成了计算科学中一个非常重要的问题，也提出了很多关于字符串匹配和相似度的算法，现有的计算字符串相似度的方法按照计算所依据的特征的不同,可以划分为三种方法:基于字面相似的方法、基于统计关联的方法、基于语义相似的方法。三种方法各有优缺点，还有人提出了综合考虑三种方法的多层特征方法[2]。其中,基于字面相似的计算方法主要有基于编辑距离的计算方法 [3]和基于相同字或词的方法 [4]。字符串序列相似度计算在异构数据库操作、音乐乐谱分析、基因序列分析[1]，信息检索等方面有较好的应用。 本文通过定义的字符串相似度的衡量指标，利用匹配矩阵对字符串的相似度进行计算。对于长度不相等的字符串，通过插入空格的方法使字符串的长度相等，根据设计的算法确定空格的位置，使相似度的值达到最大，可以使模糊检索的信息更有意义。 2　计算字符串相似度的算法 ２.１构造字符串相似程度的指标 给定两个长度相等的任意字符串Str1=“abcddacbcb”和Str2=“aadaccbddc”，对两个字符串在任意的位置比对： （字符中间没有空格）。字符串的长度记为n（这里n=10），相同字母(d、a、c)的个数记为m(这里m=3)，两字符串重叠的个数记为r(这里r=8)。根据上面给出的数据，我们给出下面的定义： 定义1重叠率 两个长度相等的（包括在长度的短的字符串中加入空格，使其长度相等的情况）字符串在字符串移动匹配的过程中，重叠字符串的个数与字符串的长度的比率，即。 定义2 匹配率 两个长度相等的（包括在长度的短的字符串中加入空格，使其长度相等的情况）字符串在字符串移动匹配的过程中，对应位置字符相同的个数与字符串长度的比率，即。 定义3 相似度 匹配率的平方与重叠率的乘积，即。 这样定义相似度的目的是为了在匹配率相同的情况下，利用重叠率衡量相似度，同时减小重叠率对相似度的影响，因为相似度是应该依赖于匹配率的。 ２.２算法设计与分析 ２.２.１算法原理 　　鉴于以上相似度指标Q的定义，我们只要考虑如何使匹配率最大，这样就可以得到最大的相似度。 如，我们保持上面的字符串不动，把下面的字符串自左向右移动，每到一个位置时计算Q值，然后取Q的最大值。Str1的长度记为n1，Str2的长度记为n2，当Str2的尾字母和Str1