计算字符串相似度的矩阵算法

计算字符串相似度的矩阵算法

李彬

（武汉理工大学计算机学院  武汉  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的首字母对齐的情况下计算相似度指标为Q1，Str2右移一位计算的相似度指标为Q2，当Str2的首字母和Str1的尾字母对齐的情况下计算相似度指标为Qm(m=n2+n1-1)，然后计算最大相似度Qmax=max{Q1、Q2、．．．．．．、Qm}。

２.２.２算法实现

下面我们用两个字符串实现具体的算法。字符串S1的长度为n1，字符串S2的长度为n2，设n1>n2，记S=n1-n2；具体的令S1=“abcddacbcbdadcabbdca”,S2=“aadaccbddcabacd”，则n1=20，n2=15，S=5。下面所用的S1，S2，n1，n2，S都与这里的设置一致。

（１） 如图1所示，我们将两个字符串按如下方式填写： 

 

 

图1       匹 配 图

图中横向(首行)为字符串S1，纵向(首列)为字符串S2，矩阵中元素 (交叉点)为‘1’，表示相匹配，否则为‘0’(图中只表示出非零元素)。矩阵中划了一些斜线，斜线所经过的单元格表示S1与S2相匹配的位置和匹配的情况。第一条斜线必须覆盖字符串S2与S1的前n2个字母匹配的情况，依次下去，一共有S＋１条斜线。下面的图2，图3表示的是第一条斜线与第二条斜线的表示的情况，其余的斜线表示的情况依次类推。

 

         图2 第一条斜线表示的情况                      图3 第二条斜线表示的情况

拿第二条斜线说明一下：如图3表示S2的首字母和S1的第二个对齐。该斜线经过的单元格有四个元素不为零，说明有四个元素匹配，即是有底线的字母。斜线的间距（相邻的两条斜线的距离为１）表示字符串滑动的距离，也表示在两个字符串均不动的情况下，在字符串S2中加入空格所能影响到的距离。如第一条斜线和第二条斜线：从上面图2，图3中可以看出在S2中加入一个空格，在移动匹配中只能到第二条斜线所能表示的情况，依次类推。因此，在S2中加入的空格数所能达到的最远匹配可以用斜线的条数来表示。在S2中加入S个空格，可以在当前匹配的斜线后再划S条斜线。

（２）我们的目的是为了在加入空格后达到最大的匹配率，因此可以在n1 -n2+1条斜线中找到一条含非零值最多的路径，但要遵循一个原则：路径的查找必须遵循自左向右的原则，因为每移动一条斜线相当于插入一个空格，插入空格以后不能向回匹配只能向后匹配。现在我们要解决的问题就是在S+1条斜线中按照自左向右、自上向下的原则找一条含非零值最多的路径。

如图1所示，我们以S1和S2为例说明一下具体过程，这里字符串S1有20个字符，字符串S2有15个字符，斜线的条数等于20-15+1=6。这里我们将斜线覆盖的范围为转化为矩阵的形式，我们把他写成矩阵R1。矩阵R1的第一行代表左边第一条斜线，依次类推。矩阵元素表示斜线经过的单元格中的数值，也就是字符是否匹配。按照上面的原则：自左而右、自上而下，找到一条含‘1’最多的路径。为方便其见，我们把‘1’换成该行的行号。写成矩阵R2。

 

 

 

　　（３）我们现在就需要找到一条含非零值最多的路径。

　　我们定义非零值的个数为信息量，记为In。算法准则：因为遵从自左而右、自上而下的原则，所以第i行可以包含第i+1行的信息量，也就是说从第i行和第i+1行选取部分元素可以使第i行达到这两行的最大信息量。

我们从矩阵R2倒数第二行反向递推到第一行，那么第一行就含有下面所有行的最大信息量，也就是找到了最优路径。下面就上面的矩阵R2进行处理，用穷举法两两寻找最优划分(选取第i行左面元素和第i+1行右面的元素达到信息量最大)。

下面就以字符串S1和S2为例寻找信息量最大的路径。

ａ、先在倒数第二行取一个元素，再在倒数第一行取n2-1个元素（有底线的为所取的数值） ，计算信息量为3；

　　ｂ、在倒数第二行取两个元素，再在倒数第一行取n2-2个元素 ，

计算信息量为４；

　　ｃ、依次穷举计算，得到信息量最大的划分：  ，信息量为７； 

　　ｄ、将取得的倒数第二行元素和倒数第三行，重复步骤ａ、ｂ、ｃ，直到第一行为止。得到所有的划分结果为图4：

 

 

　                        图4　划分图　　　　　　　　　　　　　图5　改进的划分图

　　e、将划分的右上角元素置零，将右下角元素替代右上角元素，保留左上角元素。比如步骤ｃ的划分变为： ，则整个划分变为图5。

ｆ、在数值增大的地方加入空格，空格的个数为前后变化的数值的差值，(元素零除外)。S2插入空格如图６所示。 

 

　　　　　　　　　　　图6　相似度最大匹配图

　　ｇ、计算匹配率为（12/20）2，重叠率为1，则Q15=0.38。

　　如果插入的空格少于n1-n2，可以依据重叠率较大的情况在字符前或字符后插入。

同样可以计算Q1、Q2………Qm,在其中找到最大值。

２.２.３ 算法步骤

这里我们假设字符串s1的长度大于s2的长度，即n1>n2，记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行右面的元素达到信息量最大)。

ａ、先在R2的倒数第二行取一个元素，再在倒数第一行取n2-1个元素，计算这n2个元素的信息量；

ｂ、在倒数第二行取两个元素，再在倒数第一行取n2-2个元素，同样计算这n2个元素的信息量；

ｃ、依次穷举计算，得到信息量最大的划分；

ｄ、对倒数第二行元素和倒数第三行，重复步骤ａ、ｂ、ｃ，直到第一行为止；

e 、将划分的右上角元素置零，将右下角元素替代右上角元素，保留左上角元素；

ｆ、取得整个划分，在数值增大的地方加入空格，空格的个数为前后变化的数值的差值，(元素零除外)。

２.２.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].情报学报2005 ,24(6):696-701.

[3]　Monge AE , Elkan CP. The field2matching problem: algorithm and applications. In : Proceedings of the Second Internet Conference on Knowledge Discovery and Data Mining ,Oregon , Portland , 1996 , 8:267～270.

[4]　Nirenburg S ,Domashnev C ,Grannes DJ. Two approaches to matching in example-based machine translation[J]. In :Proceedings of TMI293 , Kyoto , Japan , 1993, 7:47～57.

[5] Anany Levitin,(译者)潘彦.《算法设计与分析基础》[M].清华大学出版社,2004.

[6]陈鑫,常致全.智能化搜索引擎原理及实现[J] .计算机应用2003 ,vol23:191-193.