字符串相似度矩阵算法

1、符串在任意的位置比对:abcddacbcb（字符中间没有空格）。字符串的长度记为 n计算字符串相似度的矩阵算法李彬（武汉理工大学计算机学院武汉430070 ）摘 要：用两个字符串滑动比较时匹配的字符数和两字符串滑动比较的重叠率定义了相似度的 衡量指标，在确定一个字符串较另一个字符串较少的情况下，设计了一种算法，实现了在字符 串匹配矩阵中确定插入空格的位置使相似度指标达到最大值，可以用于信息的模糊检索。 关键词：匹配率；相似度；匹配矩阵；信息量中图法分类号：TP301.6The Matrix Arithmetic of Comput ing Strin gs Similar DegreeLI B

2、in(Departme nt Of Computer Of Wuhan Uni versity of Techno logy Wu a n 430070 China )Abstract : The similar degree is defined based on the number of matching charsand theoverlaping ratio of two strings chars when two strings do comparison duringgliding.Designing a arithmetic under the sistuation that

3、 making sure the length of onestring is smaller than another strings and makeing sure the position of insertingblankspace in strings matching matrix makes similar degree gain the biggest value， thisarithmetic can used for the misty index of the information.Key Words: Matchi ng Ratio ； Similar Degree

4、 ； Match ing Matrix ； In formatio n Quan tity1引言随着现代科学技术的发展，生物学中的DAN序列的相似性的比较可以用于亲子鉴定等，医学中应用病毒基因的相似性来诊治疾病。与之相似，随着计算机的发展，字符串的相似问题也成 了计算科学中一个非常重要的问题，也提出了很多关于字符串匹配和相似度的算法，现有的计 算字符串相似度的方法按照计算所依据的特征的不同，可以划分为三种方法：基于字面相似的方法、基于统计关联的方法、基于语义相似的方法。三种方法各有优缺点，还有人提出了综合考 虑三种方法的多层特征方法2。其中，基于字面相似的计算方法主要有基于编辑距离的计算方法

5、和基于相同字或词的方法。字符串序列相似度计算在异构数据库操作、音乐乐谱分析、基因序列分析，信息检索等方面有较好的应用。本文通过定义的字符串相似度的衡量指标，利用匹配矩阵对字符串的相似度进行计算。对 于长度不相等的字符串，通过插入空格的方法使字符串的长度相等，根据设计的算法确定空格 的位置，使相似度的值达到最大，可以使模糊检索的信息更有意义。2计算字符串相似度的算法2.1构造字符串相似程度的指标给定两个长度相等的任意字符串Str仁“ abcddacbcb”和 Str2= “ aadaccbddc”，对两个字aadaccbddc（这里n=10）相同字母（d、a、c）的个数记为 m（这里m=3），两

6、字符串重叠的个数记为r（这里r=8）。根据上面给出的数据，我们给出下面的定义：定义1重叠率 两个长度相等的（包括在长度的短的字符串中加入空格，使其长度相等的情况）字符串在字符串移动匹配的过程中，重叠字符串的个数与字符串的长度的比率，即L -r/n。定义2匹配率 两个长度相等的（包括在长度的短的字符串中加入空格，使其长度相等 的情况）字符串在字符串移动匹配的过程中，对应位置字符相同的个数与字符串长度的比率， 即 M = m/n 。S1:abcddacbcbdadcabbdcaS2:aadaccbddcabacdS1:abcddacbcbdadcabbdcaS2: aadaccbddcabacd定

7、义3相似度 匹配率的平方与重叠率的乘积，即 M2（m, ） r n n这样定义相似度的目的是为了在匹配率相同的情况下，利用重叠率衡量相似度，同时减小 重叠率对相似度的影响，因为相似度是应该依赖于匹配率的。2 . 2算法设计与分析2 . 2 . 1算法原理鉴于以上相似度指标 Q的定义，我们只要考虑如何使匹配率最大，这样就可以得到最大的 相似度。如，我们保持上面的字符串不动，把下面的字符串自aadaccbddc.aadaccbddc左向右移动，每到一个位置时计算 Q值，然后取Q的最大值。Str1的长度记为n1, Str2的长 度记为n2,当Str2的尾字母和Str1的首字母对齐的情况下计算相似度指

8、标为Q, Str2右移一位计算的相似度指标为 Q,当Str2的首字母和Str1的尾字母对齐的情况下计算相似度指标为Qn（m=n2+ni-1），然后计算最大相似度Qax=maxQ、Q?、 .、Q 2 . 2 . 2算法实现下面我们用两个字符串实现具体的算法。字符串 S1的长度为n1,字符串S2的长度为n2, 设 n1n2,记 S=n1-n2；具体的令 S仁abcddacbcbdadcabbdca ” ,S2= “aadaccbddcabacd”， 则n1=20, n2=15, S=5下面所用的 Si, S2, n1, n2, S都与这里的设置一致。（1）如图1所示，我们将两个字符串按如下方式填写

9、：abcddacbcTdaacabbdcaa: :XX X11 11 1a11L、V V111 1d、X弋111 1ar r i i、R 11 11 1c1、1 11 1c1 ,s sXA AL L1 11V V11d1L Li i、X X. .*、.1 1ai i、1 1c111 1、.、-1 1ai i1 1、I、*、1 1b1i1 1ai i1 11s sI、K K1 1c11X Xd1 1i i1 17、图1匹配图图中横向（首行）为字符串S1,纵向（首列）为字符串S2,矩阵中元素（交叉点）为 1表示相 匹配，否则为 0（图中只表示出非零元素）。矩阵中划了一些斜线，斜线所经过的单元格表示

10、S1与S2相匹配的位置和匹配的情况。第一条斜线必须覆盖字符串S2与S1的前n2个字母匹配的情况，依次下去，一共有S+1条斜线。下面的图 2，图3表示的是第一条斜线与第二条斜线的表示的情况，其余的斜线表示的情况依次类推。图2第一条斜线表示的情况图3第二条斜线表示的情况拿第二条斜线说明一下：如图3表示S2的首字母和S1的第二个对齐。该斜线经过的单元格有四个元素不为零，说明有四个元素匹配，即是有底线的字母。斜线的间距（相邻的两条斜 线的距离为1）表示字符串滑动的距离，也表示在两个字符串均不动的情况下，在字符串S2中加入空格所能影响到的距离。如第一条斜线和第二条斜线：从上面图2，图3中可以看出在S2R

11、10 01 01 10 00 010 0 00 00 11 0 0 11 00 00 0 0 0 0 0 01 0 0 0 1 0 0 0 0 1 0 0 0 11 1 0 0 0 0 00 0 111100 1 0 0 0 1 0F205 0050005555|000 信息量为 600000060006|060，信息量a、b、c，直到第一行为止。得到所有的划分结果为图 4：1|0 0 0 0 0 0 0 0 00 00 1 00 0|2 0 0 2 2 0 00 2 00 0 00 03 3 3|0 0 03000300000004 44 |0 0000040 5 0 0 5 0 0 0 5

12、 5 5510 0 06 0 0 00 0 0 6 0 0 0 6 0|01|0 3 3 3 4 445、5 -5 5 0 6 0001|33 3 44 4 5 5 5 5 06 000 3 33|44 4 5 5 5 5 0 6 000 0 0 044 4|55 5 5 06 0050 050 005 55 5|06060 00 0 0 06 0 00 6 C)|6_0中加入一个空格，在移动匹配中只能到第二条斜线所能表示的情况，依次类推。因此，在S2中加入的空格数所能达到的最远匹配可以用斜线的条数来表示。在S2中加入S个空格，可以在当前匹配的斜线后再划 S条斜线。(2)我们的目的是为了在加入

13、空格后达到最大的匹配率，因此可以在n1 - n2+1条斜线中找到一条含非零值最多的路径，但要遵循一个原则：路径的查找必须遵循自左向右的原则，因 为每移动一条斜线相当于插入一个空格，插入空格以后不能向回匹配只能向后匹配。现在我们 要解决的问题就是在 S+1条斜线中按照自左向右、自上向下的原则找一条含非零值最多的路径。如图1所示，我们以S1和S2为例说明一下具体过程，这里字符串S1有20个字符，字符串S2有15个字符，斜线的条数等于 20-15+仁6。这里我们将斜线覆盖的范围为转化为矩阵的形式， 我们把他写成矩阵 R。矩阵Ri的第一行代表左边第一条斜线，依次类推。矩阵元素表示斜线经 过的单元格中的

14、数值，也就是字符是否匹配。按照上面的原则：自左而右、自上而下，找到一 条含1最多的路径。为方便其见，我们把 1换成该行的行号。写成矩阵R2。(3) 我们现在就需要找到一条含非零值最多的路径。我们定义非零值的个数为信息量，记为In。算法准则：因为遵从自左而右、自上而下的原则，所以第i行可以包含第i+1行的信息量，也就是说从第 i行和第i+1行选取部分元素可以 使第i行达到这两行的最大信息量。我们从矩阵R2倒数第二行反向递推到第一行，那么第一行就含有下面所有行的最大信息量， 也就是找到了最优路径。下面就上面的矩阵 Ra进行处理，用穷举法两两寻找最优划分(选取第i 行左面元素和第i+1行右面的元素达

15、到信息量最大 )。下面就以字符串S1和S2为例寻找信息量最大的路径。a、先在倒数第二行取一个元素，再在倒数第一行取 n2-1个元素(有底线的为所取的数值)0|50050005555000，计算信息量为3;6100000060006060b、 在倒数第二行取两个元素，再在倒数第一行取n2-2个元素 凶0050005555000 .60|0000060006060 计算信息量为4;c、 依次穷举计算，得到信息量最大的划分：d、 将取得的倒数第二行元素和倒数第三行，重复步骤1|000 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0|20|2 0 0 0 0 2 2 2 2 0

16、 00 0 0 0 200200 0 0 00 0 0 03 3J J3 31 1 0 0 0 0 0 03 3 0 0 0 0 0 0 3 3 0 00 00 0 0 00 00 0 0 0 4 4 4 4410 0 0 0 0 0 0 0 0 0 4 40 0 5 5 0 0 0 0 5 5 0 0 D D 0 0 5_5_55|05_5_55|0 0 0 D D6 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 0 0 0 0 0 0 6|6|0 0 6 6 0 0图4划分图1IO33344455551IO3334445555 0 0 SOSO0 0 0|30|3 3333

17、4455550644555506 0 00 00 03 3 3 33 31 1 4 4 4 4 4 4 5 5 5 5 5 5 5 5 0 0 d d0 00 00 00 0 0 0 0 0 4 4 4 4_4_4 1515 5 5 5 5 5 5 0 0 6 60 00 05 50 0 0 0 5 5 0 0 0 00 0 5_5_55|05_5_55|0 6 60 06 60 00 0 0 0 0 0 0 0 5 5 0 0 0 0 0 6|6|0 0 6 60图5改进的划分图(元素零除外)。g、计算匹配率为( 如果插入的空格少于 同样可以计算Q、Q,Q 2 . 2 . 3算法步骤e、将划

18、分的右上角元素置零，将右下角元素替代右上角元素，保留左上角元素。比如步骤05 00500055551060c的划分变为：，则整个划分变为图 5。600 0 0 006 0 0 06 |060f、在数值增大的地方加入空格，空格的个数为前后变化的数值的差值, S2插入空格如图6所示。S1:abcddacbcbdadcabbdcaS2:aa dac_cbd_dcaba_cd图6相似度最大匹配图212/20 )，重叠率为 1，则 Q5=0.38。n1-n2，可以依据重叠率较大的情况在字符前或字符后插入。 m在其中找到最大值。这里我们假设字符串si的长度大于s2的长度，即n1n2,记S=n1-n2。第一

19、步：将字符串s1的字符依次写成一行，将字符串s2的字符依次写成一列，然后依次比对，字符相同的就记为1，不同的就记为0，生成矩阵R,矩阵元素Ri , j表示s2的第i个元素与s1的第j个元素是否相同；第二步：生成矩阵 R, R1的行数等于S+1，列数等于n2, Ri , j=Rj , j+i-1;第三步：将矩阵 R1的非零元素换成所在行的数字，生成矩阵Rao第四步：从矩阵R2倒数第二行反向递推到第一行，那么第一行就含有下面所有行的最大信息量，也就是找到了最优路径。下面就上面的矩阵 艮进行处理，用穷举法两两寻找最优划分 (选取第i行左面元素和第i+1行右面的元素达到信息量最大)。a、 先在R的倒数

20、第二行取一个元素，再在倒数第一行取n 2-1个元素，计算这n2个元素的信息量；b、 在倒数第二行取两个元素，再在倒数第一行取n2-2个元素，同样计算这 n2个元素的信息量；c、 依次穷举计算，得到信息量最大的划分；d、 对倒数第二行元素和倒数第三行，重复步骤a、b、c，直到第一行为止；e、 将划分的右上角元素置零，将右下角元素替代右上角元素，保留左上角元素；f、 取得整个划分，在数值增大的地方加入空格，空格的个数为前后变化的数值的差值，(元素零除外)。2 . 2 .4算法性能分析下面按照一般的算法分析对此算法进行分析5。(1) 构造匹配矩阵为：n1* n2(2) 进行移动匹配的次数为：n1+n 2-1(3) 构造寻优路径矩阵：(n1-n 2+1)* n1(4) 寻找最优路径计算Q n1*(n1-n2)(5) 寻找最大的Q值。算法的空间效率为：n 1* n2+( n1- n2+1)* n1+2* n1+n 2-2 算法的计算次数为：(n 1+ n2-1)* n1*( n1-n2)算法的计算次数比穷举法C：；：2的次数减少了很多，像文中的例子，利用穷举法是0(n 15)，当然如果n1-n2再增大的话，会更大，因为穷举法的次数是0(n 1(n12)。本文中的算法的计算次数是 0(n12)。特别的，当n1二n2时，就不必进行这样的计算，只需