文档介绍：计算字符串相似度的矩阵算法李彬(武汉理工大学计算机学院武汉430070)摘要:用两个字符串滑动比较时匹配的字符数和两字符串滑动比较的重叠率定义了相似度的衡量指标,在确定一个字符串较另一个字符串较少的情况下,设计了一种算法,实现了在字符串匹配矩阵中确定插入空格的位置使相似度指标达到最大值,可以用于信息的模糊检索。关键词:匹配率;相似度;匹配矩阵;信息量中图法分类号:'SimilarDegreeLIBin(puterOfWu’hanUniversityofTechnologyWu’han430070China)Abstract:Thesimilardegreeisdefinedbasedonthenumberofmatchingcharsandtheoverlapingratiooftwostrings’’andmakeingsurethepositionofinsertingblankspaceinstrings’matchingmatrixmakessimilardegreegainthebiggestvalue,:MatchingRatio;SimilarDegree;MatchingMatrix;InformationQuantity1 引言随着现代科学技术的发展,生物学中的DAN序列的相似性的比较可以用于亲子鉴定等,医学中应用病毒基因的相似性来诊治疾病。与之相似,随着计算机的发展,字符串的相似问题也成了计算科学中一个非常重要的问题,也提出了很多关于字符串匹配和相似度的算法,现有的计算字符串相似度的方法按照计算所依据的特征的不同,可以划分为三种方法:基于字面相似的方法、基于统计关联的方法、基于语义相似的方法。三种方法各有优缺点,还有人提出了综合考虑三种方法的多层特征方法[2]。其中,基于字面相似的计算方法主要有基于编辑距离的计算方法[3]和基于相同字或词的方法[4]。字符串序列相似度计算在异构数据库操作、音乐乐谱分析、基因序列分析[1],信息检索等方面有较好的应用。本文通过定义的字符串相似度的衡量指标,利用匹配矩阵对字符串的相似度进行计算。对于长度不相等的字符串,通过插入空格的方法使字符串的长度相等,根据设计的算法确定空格的位置,使相似度的值达到最大,可以使模糊检索的信息更有意义。2 =“abcddacbcb”和Str2=“bddc”,对两个字符串在任意的位置比对:(字符中间没有空格)。字符串的长度记为n(这里n=10),相同字母(d、a、c)的个数记为m(这里m=3),两字符串重叠的个数记为r(这里r=8)。根据上面给出的数据,我们给出下面的定义:定义1重叠率两个长度相等的(包括在长度的短的字符串中加入空格,使其长度相等的情况)字符串在字符串移动匹配的过程中,重叠字符串的个数与字符串的长度的比