编辑距离算法的优化与实现

1编辑距离算法的优化与实现摘要：在分析基于动态规划的编辑距离算法对文本相似度计算的不足的基础上，利用数据结构在空间效率和时间效率上优化该算法、采用中文分词的思想优化和改善该算法的时间效率和准确率，克服了原有的基于动态规划的计算方法所具有的效率低、准确率低、耗内存高的缺点。通过多种优化方案的实验测试和分析，结果表明优化后的算法取得了很好的准确率和时空效率，更好的用于文本相似度计算。关键词：编辑距离算法；文本相似度计算；算法优化；动态规划1引言文本相似度的计算在信息检索、文本分类、知识挖掘、网页去重、问答系统等诸多领域有着极为广泛的应用，长期以来一直是研究的热点和难点。人们在文本相似度计算中使用编辑距离算法，但该方法单纯以字为单位计算各个字符之间的编辑距离，插入删除替换三种基本操作的代价值的方法不够明确合理，从而使计算结果存在一定的偏差。故对传统的文本相似度检测编辑距离算法进行优化和改善，提出了一种基于改进编辑距离和中文分词相融合的计算文本相似度的方法，使优化改善后的算法具有较高的准确率和效率、较低的存储空间，更符合文本相似度计算的要求，有效提高文本相似度算法的效率和准确性，使文本相似度计算的性能进一步改善。2编辑距离算法4.3.1编辑距离定义编辑距离又称Levenshtein距离（也叫做EditDistance），是由俄国科学家VladimirLevenshtein于1965年在文献[1]中提出的，是一种常用的距离函数度量方法，在多个领域特别是文本相似度检测得到了广泛的应用。编辑距离是指两系列字符串之间只能通过插入、删除和替换三种基本操作把源字符串（S）转换成目标字符串（T）所需的最少基本操作次数。编辑距离值越大，则相似度越小。24.3.2编辑距离算法原理对于求两个字符串之间的编辑距离实际上可以转化为一个求最优解的问题，可以利用动态规划的思想[2]来计算，计算原理的步骤如下表2-1所示：表2-1编辑距离算法原理的计算步骤步骤描述1设置n为源字符串s的长度。设置m为目标字符串t的长度。如果n等于0，返回m并退出。如果m等于0，返回n并退出。构造一个矩阵d[m+1,n+1]含有0..m行和0..n列。2初始化矩阵第一行0..ñ。初始化矩阵第一列0..m。3检查s(ifrom1ton)中的每个字符。4检查t(jfrom1tom)中的每个字符。5如果s[i]等于t[j]，则编辑代价cost为0；如果s[i]不等于t[j]，则编辑代价cost为1。6设置矩阵单元格d[i,j]的值为下面的最小值:a.正上方单元格的值1:d[i-1,j]+1.b.左边单元格的值加1:d[i,j-1]+1.c.对角线单元格的值加上编辑代价cost的值:d[i-1,j-1]+cost.7在完成迭代(3,4,5,6)之后，d[m,n]便是编辑距离的值。本小节将演示如何计算源字符串GUMBO和目标字符串GAMBOL两个字符串之间的Levenshtein距离，计算步骤如下：3步骤1、2步骤3、6，当i=1步骤3、6，当i=2步骤3、6，当i=3步骤3、6，当i=4步骤3、6，当i=5步骤7，编辑距离是矩阵右下角的值，d[m,n]=2；源字符串GUMBO变换为目标字符串GAMBOL的过程，直观可看出的，即通过将A替换为U，并在末尾追加L字符，这跟计算的结果一致。4.3.3编辑距离以及文本相似度计算编辑距离D（S,T）的计算方法如下所述。首先假设Dij=D(s1…si,,t1…tj)，0≤i≤m,0≤j≤n,Dij表示从s1…si到t1…tj的编辑距离，那么（m+1）×(n+1)阶矩阵Dij可通过下面的（1）式计算得到：0i=0且j=0;Di-1j-1+(ifsi=tjthen0else1);Dij=MinDi-1,j+1;i0或j0；(1)式Di,j-1+1;GUMBO012345G1A2M3B4O5L6GUMBO012345G10A21M32B43O54L65GUMBO012345G101A211M322B433O544L655GUMBO012345G1012A2112M3221B4332O5443L6554GUMBO012345G10123A21123M32212B43321O54432L65543GUMBO012345G101234A211234M322123B433212O544321L6554324(1)式包含删除、插入、替换三种操作，该算法是从两字符串的左边开始比较，记录已经比较过的编辑距离，然后进一步得到下一个字符位置时的编辑距离。矩阵Dij能够通过从D00逐步逐列计算获取，最终Dmn表示D(S，T)的值，即S和T的编辑距离。文本相似度计算[3]：编辑距离越大，相似度越小。假设源字符串S与目标字符串T长度的最大值为Lmax，编辑距离为LD，相似度为SI，则相似度SI的计算如（2）式所示。SI=1-LD/Lmax(2)式4.3.4编辑距离算法核心代码publicintLevenshteinDistance(stringstrs1,stringstrs2){char[]str1=strs1.ToCharArray();char[]str2=strs2.ToCharArray();inti,j,temp;if(str1.Length==0){temp=str2.Length;}if(str2.Length==0){temp=str1.Length;}int[,]dist=newint[str1.Length+1,str2.Length+1];for(i=0;i=str1.Length;i++)dist[i,0]=i;for(i=0;i=str2.Length;i++)dist[0,i]=i;for(i=1;i=str1.Length;i++){for(j=1;j=str2.Length;j++){if(str1[i-1]==str2[j-1]){dist[i,j]=dist[i-1,j-1];}else{dist[i,j]=LowerOfThree(dist[i,j-1],dist[i-1,j-1],dist[i-1,j])+1;}5}}temp=dist[str1.Length,str2.Length];returntemp;}4.3.5编辑距离算法分析假设m,n分别表示源字符串S和目标字符串T的长度，则上述的基于动态规划的编辑距离算法，其算法的空间复杂度为O（mn），时间复杂度为O（mn）。尽管编辑距离算法在文本相似度检测方面具有一定的优势，具有简单易于计算，并有一定的正确率，但仍然存在一些问题。（1）此编辑距离算法忽略了序列长度对编辑距离产生的影响，没有考虑到算法所需的内存，因而造成所耗内存较大。（2）单纯以字为单位计算各个字符之间的编辑距离，计算出来的距离只是文字表面的距离，并没有充分考虑词语的概念，使得计算结果的语义准确率不高，特别是对中文的检测时常常得不到满意的结果。针对以上两个问题，下文提出了几种优化方案，分别是基于算法结构的内部调整优化以及基于词语相似度的文本计算，通过大量的实验测试证明了可降低计算所耗的存储空间，提高了算法的效率和准确率。3改进编辑距离算法3.1空间复杂度优化经过对上面的传统编辑距离算法计算过程的分析，发现算法中作为存储的二维矩阵，在每一个循环中，其实只有一行的数据参与了计算，之前的数据行都不再参与计算了。因此，从这个出发点入手，对算法结构进行调整，将二维数组改为两个一维数组。经测试，计算结果和速度没有太大的差异。但空间复杂度减少了很多，改进后空间复杂度降为：O（min(m,n））。设置n为源字符串s的长度，m为目标字符串t的长度。我们不妨设nm，即源字符串s的长度较小，那么空间复杂度优化的编辑距离算法步骤如表3-1：6表3-1空间复杂度优化的编辑距离算法步骤步骤描述1设置n为源字符串s的长度。设置m为目标字符串t的长度。如果n等于0，返回m并退出。如果m等于0，返回n并退出。构造两个一维数组v0[n+1]和v1[n+1]，串联0..n之间所有的元素。2初始化v0to0..n。3检查t(jfrom1tom)中的每个字符。4检查s(ifrom1ton)中的每个字符。5如果s[i]等于t[j]，则编辑代价cost为0；如果s[i]不等于t[j]，则编辑代价cost为1。6设置一维数组单元格v1[i]的值为下面的最小值:a.正上方单元格的值1:v0[i]+1.b.左边单元格的值加1:v1[i-1]+1.c.对角线单元格的值加上编辑代价cost的值:v0[i-1]+cost.7在完成迭代(3,4,5,6)之后，v1[n]便是编辑距离的值。本小节仍以源字符串GUMBO和目标字符串GAMBOL来演示如何计算这两个字符串之间的Levenshtein距离，计算步骤如下：步骤1、2步骤3、6，当i=1步骤3、6，当i=2GUMBOV0012345V1GAMBOLGUMBOv0012345V1G101234AMBOLGUMBO012345v0G101234V1A211234MBOL7步骤3、6，当i=3步骤3、6，当i=4步骤3、6，当i=5步骤3、6，当i=6步骤7，右下角的值便是编辑距离的值，v1[n]=2；传统的编辑距离算法会创建一个矩阵d[m+1,n+1],但此经过优化的算法将会创建两个一维数组v0[n+1]和v1[n+1]，其计算结果没有发生变化，但内存占用更少，其空间复杂度可为两个字符串长度的最小值O(min(m，n))。在经过空间复杂度优化的编辑距离算法，其编辑步数一样，因而相应的文本相似度计算的结果也一样。编辑距离算法的空间复杂度优化核心代码如下：publicintLevenshteinDistance(stringstrs1,stringstrs2){char[]str1=strs1.ToCharArray();char[]str2=strs2.ToCharArray();inti,j,temp;if(str1.Length==0){temp=str2.Length;GUMBO012345G101234V0A211234V1M322123BOLGUMBO012345G101234A211234V0M322123V1B433212OLGUMBO012345G101234A211234M322123V0B433212V1O544321LGUMBO012345G101234A211234M322123B433212V0O544321V1L6554328}if(str2.Length==0){temp=str1.Length;}int[,]dist=newint[2,str2.Length+1];for(i=0;i=str2.Length;i++)dist[0,i]=i;for(i=1;i=str1.Length;i++){dist[1,0]=i;for(j=1;j=str2.Length;j++){if(str1[i-1]==str2[j-1]){dist[1,j]=dist[0,j-1];}else{dist[1,j]=LowerOfThree(dist[0,j-1],dist[0,j],dist[1,j-1])+1;}}for(j=0;j=str2.Length;j++){dist[0,j]=dist[1,j];}temp=dist[1,str2.Length];returntemp;}3.2时间效率优化4.3.1编辑距离算法的时间效率优化思想在对上面的传统编辑距离算法仔细分析后，发现两个字符串相对应位置上的字符相同时，把这两个相对应的相同的字符删除掉后，对计算结果没有任何影响。删除这些相对应位置相同的字符后将会减少编辑计算的字符，即参与计算的两字符的长度变短，从而使得计算的时间效率加快，达到提高算法时间效率的效果。再者，针对于纯中文的文本，我们考虑到文本中的标点符号也会被当成一个独立的字符参与计算，但是这些标点符号对于我们所要计算的文本相似度来说毫9无意义。因此可采取的做法就是把这些标点符号