还剩3页未读,继续阅读
文本内容:
蚃肃荿莃螅袆芅莂袈肂膁蒁薇袄肇蒁蚀肀羃蒀袂袃莁葿薂膈芇蒈蚄羁膃蒇螆膇聿蒆袈罿莈薅薈螂芄薅蚀羈膀薄螃螀肆薃薂羆肂薂蚅衿莁薁螇肄芇薀衿袇膃薀蕿肃聿虿蚁袅莇蚈螄肁芃蚇袆袄腿蚆蚆聿膅芃螈羂肁节袀膇莀芁薀羀芆芀蚂膆膂艿螄羈肈莈袇螁莆莇薆羇节莇蝿螀芈莆袁肅膄莅薁袈肀莄蚃肃荿莃螅袆芅莂袈肂膁蒁薇袄肇蒁蚀肀羃蒀袂袃莁葿薂膈芇蒈蚄羁膃蒇螆膇聿蒆袈罿莈薅薈螂芄薅蚀羈膀薄螃螀肆薃薂羆肂薂蚅衿莁薁螇肄芇薀衿袇膃薀蕿肃聿虿蚁袅莇蚈螄肁芃蚇袆袄腿蚆蚆聿膅芃螈羂肁节袀膇莀芁薀羀芆芀蚂膆膂艿螄羈肈莈袇螁莆莇薆羇节莇蝿螀芈莆袁肅膄莅薁袈肀莄蚃肃荿莃螅袆芅莂袈肂膁蒁薇袄肇蒁蚀肀羃蒀袂袃莁葿薂膈芇蒈蚄羁膃蒇螆膇聿蒆袈罿莈薅薈螂芄薅蚀羈膀薄螃螀肆薃薂羆肂薂蚅衿莁薁螇肄芇薀衿袇膃薀蕿肃聿虿蚁袅莇蚈螄肁芃蚇袆袄腿蚆蚆聿膅芃螈羂肁节袀膇莀芁薀羀芆芀蚂膆膂艿螄羈肈莈袇螁莆莇薆羇节莇蝿螀芈莆袁肅膄莅薁袈肀莄蚃肃荿莃螅袆芅莂袈肂膁蒁薇袄肇蒁蚀肀羃蒀袂袃莁葿薂膈芇蒈蚄羁膃蒇螆膇聿计算字符串相似度的矩阵算法李彬(武汉理工大学计算机学院武汉430070)摘要用两个字符串滑动比较时匹配的字符数和两字符串滑动比较的重叠率定义了相似度的衡量指标,在确定一个字符串较另一个字符串较少的情况下,设计了一种算法,实现了在字符串匹配矩阵中确定插入空格的位置使相似度指标达到最大值,可以用于信息的模糊检索关键词匹配率;相似度;匹配矩阵;信息量中图法分类号TP
301.6The__trixArithmeticofComputingStringsSimilarDegreeLIBin(DepartmentOfComputerOfWu’hanUniversityofTechnologyWu’han430070China)Abstract Thesimilardegreeisdefinedbasedonthenumberof__tchingcharsandtheoverlapingratiooftwostrings’charswhentwostringsdocomparisonduringgliding.Designingaarithmeticunderthesistuationthat__kingsurethelengthofonestringis__allerthananotherstrings’and__keingsurethepositionofinsertingblankspa__instrings’__tching__trix__kessimilardegreegainthebiggestvalue,thisarithmeticcanusedforthemistyindexoftheinfor__tion.KeyWords:__tchingRatio;SimilarDegree;__tching__trix;Infor__tionQuantity1 引言随着现代科学技术的发展,生物学中的DAN序列的相似性的比较可以用于亲子鉴定等,医学中应用病毒基因的相似性来诊治疾病与之相似,随着计算机的发展,字符串的相似问题也成了计算科学中一个非常重要的问题,也提出了很多关于字符串匹配和相似度的算法,现有的计算字符串相似度的方法按照计算所依据的特征的不同可以划分为三种方法:基于字面相似的方法、基于统计关联的方法、基于语义相似的方法三种方法各有优缺点,还有人提出了综合考虑三种方法的多层特征方法
[2]其中基于字面相似的计算方法主要有基于编辑距离的计算方法
[3]和基于相同字或词的方法
[4]字符串序列相似度计算在异构数据库操作、音乐乐谱分析、基因序列分析
[1],信息检索等方面有较好的应用本文通过定义的字符串相似度的衡量指标,利用匹配矩阵对字符串的相似度进行计算对于长度不相等的字符串,通过插入空格的方法使字符串的长度相等,根据设计的算法确定空格的位置,使相似度的值达到最大,可以使模糊检索的信息更有意义2 计算字符串相似度的算法2.1构造字符串相似程度的指标给定两个长度相等的任意字符串Str1=“abcddacbcb”和Str2=“aadac___dc”,对两个字符串在任意的位置比对(字符中间没有空格)字符串的长度记为n(这里n=10),相同字母d、a、c的个数记为m这里m=3,两字符串重叠的个数记为r这里r=8根据上面给出的数据,我们给出下面的定义定义1重叠率两个长度相等的(包括在长度的短的字符串中加入空格,使其长度相等的情况)字符串在字符串__匹配的过程中,重叠字符串的个数与字符串的长度的比率,即定义2匹配率两个长度相等的(包括在长度的短的字符串中加入空格,使其长度相等的情况)字符串在字符串__匹配的过程中,对应位置字符相同的个数与字符串长度的比率,即定义3相似度匹配率的平方与重叠率的乘积,即这样定义相似度的目的是为了在匹配率相同的情况下,利用重叠率衡量相似度,同时减小重叠率对相似度的影响,因为相似度是应该依赖于匹配率的2.2算法设计与分析2.2.1算法原理 鉴于以上相似度指标Q的定义,我们只要考虑如何使匹配率最大,这样就可以得到最大的相似度如,我们保持上面的字符串不动,把下面的字符串自左向右__,每到一个位置时计算Q值,然后取Q的最大值Str1的长度记为n1,Str2的长度记为n2,当Str2的尾字母和Str1的首字母对齐的情况下计算相似度指标为Q1,Str2右移一位计算的相似度指标为Q2,当Str2的首字母和Str1的尾字母对齐的情况下计算相似度指标为Qmm=n2+n1-1,然后计算最大相似度Q__x=__x{Q
1、Q
2、......、Qm}2.2.2算法实现下面我们用两个字符串实现具体的算法字符串S1的长度为n1,字符串S2的长度为n2,设n1n2,记S=n1-n2;具体的令S1=“abcddacb___adcabbdca”S2=“aadac___dcabacd”,则n1=20,n2=15,S=5下面所用的S1,S2,n1,n2,S都与这里的设置一致
(1)如图1所示,我们将两个字符串按如__式填写图1匹配图图中横向首行为字符串S1,纵向首列为字符串S2,矩阵中元素交叉点为‘1’,表示相匹配,否则为‘0’图中只表示出非零元素矩阵中划了一些斜线,斜线所经过的单元格表示S1与S2相匹配的位置和匹配的情况第一条斜线必须覆盖字符串S2与S1的前n2个字母匹配的情况,依次下去,一共有S+1条斜线下面的图2,图3表示的是第一条斜线与第二条斜线的表示的情况,其余的斜线表示的情况依次类推图2第一条斜线表示的情况图3第二条斜线表示的情况拿第二条斜线说明一下如图3表示S2的首字母和S1的第二个对齐该斜线经过的单元格有四个元素不为零,说明有四个元素匹配,即是有底线的字母斜线的间距(相邻的两条斜线的距离为1)表示字符串滑动的距离,也表示在两个字符串均不动的情况下,在字符串S2中加入空格所能影响到的距离如第一条斜线和第二条斜线从上面图2,图3中可以看出在S2中加入一个空格,在__匹配中只能到第二条斜线所能表示的情况,依次类推因此,在S2中加入的空格数所能达到的最远匹配可以用斜线的条数来表示在S2中加入S个空格,可以在当前匹配的斜线后再划S条斜线(2)我们的目的是为了在加入空格后达到最大的匹配率,因此可以在n1-n2+1条斜线中找到一条含非零值最多的路径,但要遵循一个原则路径的查找必须遵循自左向右的原则,因为每__一条斜线相当于插入一个空格,插入空格以后不能向回匹配只能向后匹配现在我们要解决的问题就是在S+1条斜线中按照自左向右、自上向下的原则找一条含非零值最多的路径如图1所示,我们以S1和S2为例说明一下具体过程,这里字符串S1有20个字符,字符串S2有15个字符,斜线的条数等于20-15+1=6这里我们将斜线覆盖的范围为转化为矩阵的形式,我们把他写成矩阵R1矩阵R1的第一行代表左边第一条斜线,依次类推矩阵元素表示斜线经过的单元格中的数值,也就是字符是否匹配按照上面的原则自左而右、自上而下,找到一条含‘1’最多的路径为方便其见,我们把‘1’换成该行的行号写成矩阵R2 (3)我们现在就需要找到一条含非零值最多的路径 我们定义非零值的个数为信息量,记为In算法准则因为遵从自左而右、自上而下的原则,所以第i行可以包含第i+1行的信息量,也就是说从第i行和第i+1行选取部分元素可以使第i行达到这两行的最大信息量我们从矩阵R2倒数第二行反向递推到第一行,那么第一行就含有下面所有行的最大信息量,也就是找到了最优路径下面就上面的矩阵R2进行处理,用穷举法两两寻找最优划分选取第i行左面元素和第i+1行右面的元素达到信息量最大下面就以字符串S1和S2为例寻找信息量最大的路径a、先在倒数第二行取一个元素,再在倒数第一行取n2-1个元素(有底线的为所取的数值),计算信息量为3; b、在倒数第二行取两个元素,再在倒数第一行取n2-2个元素,计算信息量为4; c、依次穷举计算,得到信息量最大的划分,信息量为7; d、将取得的倒数第二行元素和倒数第三行,重复步骤a、b、c,直到第一行为止得到所有的划分结果为图4 图4 划分图 图5 改进的划分图 e、将划分的右上角元素置零,将右下角元素替代右上角元素,保留左上角元素比如步骤c的划分变为,则整个划分变为图5f、在数值增大的地方加入空格,空格的个数为前后变化的数值的差值,元素零除外S2插入空格如图6所示 图6 相似度最大匹配图 g、计算匹配率为(12/20)2,重叠率为1,则Q15=
0.38 如果插入的空格少于n1-n2,可以依据重叠率较大的情况在字符前或字符后插入同样可以计算Q
1、Q2………Qm在其中找到最大值2.2.3算法步骤这里我们假设字符串s1的长度大于s2的长度,即n1n2,记S=n1-n2第一步将字符串s1的字符依次写成一行,将字符串s2的字符依次写成一列,然后依次比对,字符相同的就记为1,不同的就记为0,生成矩阵R,矩阵元素R[i,j]表示s2的第i个元素与s1的第j个元素是否相同;第二步生成矩阵R1,R1的行数等于S+1,列数等于n2,R1[i,j]=R[j,j+i-1];第三步将矩阵R1的非零元素换成所在行的数字,生成矩阵R2第四步从矩阵R2倒数第二行反向递推到第一行,那么第一行就含有下面所有行的最大信息量,也就是找到了最优路径下面就上面的矩阵R2进行处理,用穷举法两两寻找最优划分选取第i行左面元素和第i+1行右面的元素达到信息量最大a、先在R2的倒数第二行取一个元素,再在倒数第一行取n2-1个元素,计算这n2个元素的信息量;b、在倒数第二行取两个元素,再在倒数第一行取n2-2个元素,同样计算这n2个元素的信息量;c、依次穷举计算,得到信息量最大的划分;d、对倒数第二行元素和倒数第三行,重复步骤a、b、c,直到第一行为止;e、将划分的右上角元素置零,将右下角元素替代右上角元素,保留左上角元素;f、取得整个划分,在数值增大的地方加入空格,空格的个数为前后变化的数值的差值,元素零除外2.2.4算法性能分析下面按照一般的算法分析对此算法进行分析
[5]
(1)构造匹配矩阵为n1*n2
(2)进行__匹配的次数为:n1+n2-1
(3)构造寻优路径矩阵n1-n2+1*n1
(4)寻找最优路径计算Q n1*n1-n2
(5)寻找最大的Q值算法的空间效率为n1*n2+n1-n2+1*n1+2*n1+n2-2算法的计算次数为n1+n2-1*n1*n1-n2算法的计算次数比穷举法的次数减少了很多,像文中的例子,利用穷举法是O,当然如果再增大的话,会更大,因为穷举法的次数是O本文中的算法的计算次数是O特别的,当时,就不必进行这样的计算,只需要进行__匹配就可以了3 结论文中用两个字符串滑动比较时匹配的字符数和两字符串滑动比较的重叠率定义了相似度的衡量指标,在确定一个字符串较另一个字符串较少的情况下,设计了一种算法,实现了在字符串匹配矩阵中确定插入空格的位置使相似度指标达到最大值,算法的计算次数明显的减少了,可以使模糊信息检索高效有意义____
[1]孙啸陆祖宏谢建明.生物信息学基础[M].清华大学出版社
2005.
[2]章成志.基于多层特征的字符串相似度计算模型[J].情报学报2005246:696-
701.
[3] MongeAEElkanCP.Thefield2__tchingproblem:algorithmandapplications.In:Pro__edingsoftheSecondInternetConferen__onKnowledgeDiscoveryandDataMiningOregonPortland19968:267~
270.
[4] NirenburgSDo__shnevCGrannesDJ.Twoapproachesto__tchinginexample-based__chinetranslation[J].In:Pro__edingsofTMI293KyotoJapan19937:47~
57.
[5]AnanyLevitin译者潘彦.《算法设计与分析基础》[M].清华大学出版社
2004.
[6]陈鑫常致全.智能化搜索引擎原理及实现[J].计算机应用2003vol23:191-
193.芅薇蚈肇芄芇蒁羃芃荿蚆衿芃薁葿袅节芁螅螁芁莃薇聿芀蒆螃羅艿薈薆袁莈芈螁螇莇莀薄肆莇蒂螀肂莆蚅薂羈莅莄袈袄羁蒇蚁螀羀蕿袆肈羀艿虿羄罿莁袄袀肈蒃蚇螆肇薅蒀膅肆莅蚅肁肅蒇薈羇肄薀螄袃肄艿薇蝿肃莂螂肈膂蒄薅羄膁薆螀袀膀芆薃螆腿蒈蝿螂膈薁蚁肀膈芀袇羆膇莃蚀袂膆蒅袅螈芅薇蚈肇芄芇蒁羃芃荿蚆衿芃薁葿袅节芁螅螁芁莃薇聿芀蒆螃羅艿薈薆袁莈芈螁螇莇莀薄肆莇蒂螀肂莆蚅薂羈莅莄袈袄羁蒇蚁螀羀蕿袆肈羀艿虿羄罿莁袄袀肈蒃蚇螆肇薅蒀膅肆莅蚅肁肅蒇薈羇肄薀螄袃肄艿薇蝿肃莂螂肈膂蒄薅羄膁薆螀袀膀芆薃螆腿蒈蝿螂膈薁蚁肀膈芀袇羆膇莃蚀袂膆蒅袅螈芅薇蚈肇芄芇蒁羃芃荿蚆衿芃薁葿袅节芁螅螁芁莃薇聿芀蒆螃羅艿薈薆袁莈芈螁螇莇莀薄肆莇蒂螀肂莆蚅薂羈莅莄袈袄羁蒇蚁螀羀蕿袆肈羀艿虿羄罿莁袄袀肈蒃蚇螆肇薅蒀膅肆莅蚅肁肅蒇薈羇肄薀螄袃肄艿薇蝿肃莂螂肈膂蒄薅羄膁薆螀袀膀芆薃螆腿蒈蝿螂膈薁蚁肀膈芀袇羆膇莃蚀袂膆蒅袅螈芅薇蚈肇芄芇蒁羃芃荿蚆衿芃薁葿袅节芁螅螁芁莃薇聿芀蒆螃羅艿薈薆袁莈芈螁PAGE5。