编辑距离：我和你到底有多远？（二）
上一篇编辑距离：我和你到底有多远？（一）讲了编辑距离的原理，这一篇讲代码实现。
【串和序列处理 2】字符串编辑距离算法这篇文章中，给出了heartraid写的Java实现代码。这里面需要注意的一点是，代码中构建的是D[len(A)][len(B)]，而不是我们之前讲的D[len(A)+1][len(B)+1]，即把我们之前说的id的D[0][]和D[][0]行去除掉了。因此，读代码时，D[0][0]相当于我们之前讲的D[1][1]。
代码如下：
package net.hr.algorithm.stroper;
/**
* 字符串编辑距离
*
* 这是一种字符串之间相似度计算的方法。
* 给定字符串S、T，将S转换T所需要的插入、删除、替代操作的数量叫做S到T的编辑路径。
* 其中最短的路径叫做编辑距离。
*
* 这里使用了一种动态规划的思想求编辑距离。
*
* @author heartraid
*
*/
public class StrEditDistance {
/**字符串X*/
private String strX="";
/**字符串Y*/
private String strY="";
/**字符串X的字符数组*/
private char[] charArrayX=null;
/**字符串Y的字符数组*/
private char[] charArrayY=null;
public StrEditDistance(String sa,String sb){
this.strX=sa;
this.strY=sb;
}
/**
* 得到编辑距离
* @return 编辑距离
*/
public int getDistance(){
charArrayX=strX.toCharArray();
charArrayY=strY.toCharArray();
return editDistance(charArrayX.length-1,charArrayY.length-1);
}
/**
* 动态规划解决编辑距离
*
* editDistance(i,j)表示字符串X中[0.... i]的子串 Xi 到字符串Y中[0....j]的子串Y1的编辑距离。
*
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 字符串X(0...i)与字符串Y(0...j)的编辑距离
*/
private int editDistance(int i,int j){
if(i==0&&j==0){
//System.out.println("edit["+i+","+j+"]="+isModify(i,j));
return isModify(i,j);
}
else if(i==0||j==0){
if(j>0){
//System.out.println("edit["+i+","+j+"]=edit["+i+","+(j-1)+"]+1");
if(isModify(i,j) == 0) return j;
return editDistance(i, j-1) + 1;
}
else{
//System.out.println("edit["+i+","+j+"]=edit["+(i-1)+","+j+"]+1");
if(isModify(i,j) == 0) return i;
return editDistance(i-1,j)+1;
}
}
else {
//System.out.println("edit["+i+","+j+"]=min( edit["+(i-1)+","+j+"]+1,edit["+i+","+(j-1)+"]+1,edit["+(i-1)+","+(j-1)+"]+isModify("+i+","+j+")");
int ccc=minDistance(editDistance(i-1,j)+1,editDistance(i,j-1)+1,editDistance(i-1,j-1)+isModify(i,j));
return ccc;
}
}
/**
* 求最小值
* @param disa 编辑距离a
* @param disb 编辑距离b
* @param disc 编辑距离c
*/
private int minDistance(int disa,int disb,int disc){
int dismin=Integer.MAX_VALUE;
if(dismin>disa) dismin=disa;
if(dismin>disb) dismin=disb;
if(dismin>disc) dismin=disc;
return dismin;
}
/**
* 单字符间是否替换
*
* isModify(i,j)表示X中第i个字符x(i)转换到Y中第j个字符y(j)所需要的操作次数。
* 如果x(i)==y(j)，则不需要任何操作isModify(i, j)=0； 否则，需要替换操作，isModify(i, j)=1。
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 需要替换，返回1；否则，返回0
*/
private int isModify(int i,int j){
if(charArrayX[i]==charArrayY[j])
return 0;
else return 1;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
System.out.println("编辑距离是："+new StrEditDistance("eeba","abac").getDistance());
}
}
我跑了一下，完全没有问题。
不过，我还是想要加入相邻字母交换功能，所以对其进行了修改。
主要修改在isModify()函数中。判断若D[i][j]与D[i-1][j-1]可以互换，则swap。
修改的函数需要满足两点：
* 1.若点（i，j）可以swap，则在（i+2，j+2)及以上才可以再次swap；
* 2.若再次查询（i，j）点时，仍然返回0；
对于1的解决方法是：记录当前swap的i和j，再次比较时，相差大与1才可以swap；
对于2的解决方法是：设定二维数组，若已存在，直接返回值。
修改后的代码如下：
package com.arthur.editdistance;
import com.dzgz.util.Utils;
/**
* 字符串编辑距离
*
* 这是一种字符串之间相似度计算的方法。
* 给定字符串S、T，将S转换T所需要的插入、删除、替代操作的数量叫做S到T的编辑路径。
* 其中最短的路径叫做编辑距离。
*
* 这里使用了一种动态规划的思想求编辑距离。
*
* @author heartraid
* @author arthur——根据heartraid的代码修改。增加了相邻字母交换（swap）的编辑操作。
*
*/
public class StrEditDistance {
/**字符串X*/
private String strX="";
/**字符串Y*/
private String strY="";
/**字符串X的字符数组*/
private char[] charArrayX=null;
/**字符串Y的字符数组*/
private char[] charArrayY=null;
/**arthur:是否两个相邻字母进行swap的counter。偶数时可以swap。**/
private int counterI = 0;
private int counterJ = 0;
private int[][] resultArray;
public StrEditDistance(String sa,String sb){
this.strX=sa;
this.strY=sb;
System.out.println("Edit Distance of "+sa+" and "+sb+" is:");
//arthur.初始化距离结果数组
resultArray = new int[sa.length()][sb.length()];
for(int i=0;i<sa.length();i++){
for(int j=0;j<sb.length();j++){
resultArray[i][j] = -1;
}
}
}
/**
* 得到编辑距离
* @return 编辑距离
*/
public int getDistance(){
charArrayX=strX.toCharArray();
charArrayY=strY.toCharArray();
return editDistance(charArrayX.length-1,charArrayY.length-1);
}
/**
* 动态规划解决编辑距离
*
* editDistance(i,j)表示字符串X中[0.... i]的子串 Xi 到字符串Y中[0....j]的子串Y1的编辑距离。
*
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 字符串X(0...i)与字符串Y(0...j)的编辑距离
*/
private int editDistance(int i,int j){
if(i==0&&j==0){
//System.out.println("edit["+i+","+j+"]="+isModify(i,j));
return isModify(i,j);
}
/* if(i<0 || j<0){
return 0; //arthur:此处可以替代上面的if(i==0&&j==0)
}*/
else if(i==0||j==0){
if(j>0){
//System.out.println("edit["+i+","+j+"]=edit["+i+","+(j-1)+"]+1");
if(isModify(i,j) == 0) return j;
return editDistance(i, j-1) + 1;
}
else{
//System.out.println("edit["+i+","+j+"]=edit["+(i-1)+","+j+"]+1");
if(isModify(i,j) == 0) return i;
return editDistance(i-1,j)+1;
}
}
else {
//System.out.println("edit["+i+","+j+"]=min( edit["+(i-1)+","+j+"]+1,edit["+i+","+(j-1)+"]+1,edit["+(i-1)+","+(j-1)+"]+isModify("+i+","+j+")");
int ccc=minDistance(editDistance(i-1,j)+1,editDistance(i,j-1)+1,editDistance(i-1,j-1)+isModify(i,j));
// System.out.println("i is:"+i+".j is:"+j+".min ccc is:"+ccc);
return ccc;
}
}
/**
* 求最小值
* @param disa 编辑距离a
* @param disb 编辑距离b
* @param disc 编辑距离c
*/
private int minDistance(int disa,int disb,int disc){
int dismin=Integer.MAX_VALUE;
if(dismin>disa) dismin=disa;
if(dismin>disb) dismin=disb;
if(dismin>disc) dismin=disc;
return dismin;
}
/**
* 单字符间是否替换
*
* isModify(i,j)表示X中第i个字符x(i)转换到Y中第j个字符y(j)所需要的操作次数。
* 如果x(i)==y(j)，则不需要任何操作isModify(i, j)=0； 否则，需要替换操作，isModify(i, j)=1。
* @param i 字符串X第i个字符
* @param j 字符串Y第j个字符
* @return 需要替换，返回1；否则，返回0
*/
private int isModify(int i,int j){
if(resultArray[i][j] != -1){
return resultArray[i][j];
}
if(charArrayX[i]==charArrayY[j]){
resultArray[i][j] = 0;
return 0;
}
//arthur:添加可以相邻字母swap的操作。
/**
* 需要满足：
* 1.若点（i，j）可以swap，则在（i+2，j+2)及以上才可以再次swap；
* 2.若再次查询（i，j）点时，仍然返回0；（方法：设定二维数组，若已存在，直接返回值。不需要再查找）。
* 代码如下：
* if(resultArray[i][j] != -1){
return resultArray[i][j];
}
*/
if((i-counterI)>1 && (j-counterJ)>1 && charArrayX[i]==charArrayY[j-1] && charArrayX[i-1]==charArrayY[j]){
// System.out.println("Before Swap:i is:"+i+" j is:"+j+" counterI is:"+counterI+", counterJ is:"+counterJ);
counterI = i;
counterJ = j;
// System.out.println("After Swap:i is:"+i+" j is:"+j+" counterI is:"+counterI+", counterJ is:"+counterJ);
resultArray[i][j] = 0;
return 0;
}else{
resultArray[i][j] = 1;
return 1;
}
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
System.out.println(new StrEditDistance("eeba","abac").getDistance());
System.out.println(new StrEditDistance("sososs","ssooss").getDistance());
System.out.println(new StrEditDistance("abc","ca").getDistance());
System.out.println(new StrEditDistance("ca","abc").getDistance());
}
}
不过，加入了swap操作之后，会有个问题。
文章有关编辑距离计算的一点整理。中提到，对于abc和ca来说，编辑距离到底是几？
若按照L氏距离计算，距离应该为3；按照D氏距离计算，距离应该是2。
作者对这种现象的解释如下：
大体情况是这样的，L和D自己对编辑距离的定义是没有问题的，符合泛函理论中对距离定义的三个要素条件。后来一些人就想将L和D的距离定义融合在一起，成为了Damerau–Levenshtein distance（以下简称D-L距离），认为这样就既可以克服了D定义只能识别单一编辑操作引起的错误的局限，又弥补了L定义不包含相邻字符互换操作的遗憾。其实上面的公式1计算的就是D-L距离。但是这个D-L距离并不满足泛函理论中所要求的距离定义的三要素标准，它不满足三角不等式，所以这个定义是有问题的，数学上具有不严谨性。于是也就有了将abc与ca的编辑距离错算为3的情况。但是由于这个错误并不影响工程中的应用，并且这个公式能够给实际工作带来便利，就一直沿用了下来。
下面引用wiki上的相关段落：
Let us calculate pair-wise distances between the strings TO, OT and OST using this algorithm. The distance between TO and OTis 1. The same for OT vs. OST. But the distance between TO and OST is 3, even though the strings can be made equal using one deletion and one transposition. Clearly, the algorithm does not compute precisely the value we want. Furthermore, the triangle inequality does not hold.
In reality this algorithm calculates the cost of the so-called optimal string alignment, which does not always equal the edit distance.
也就是说，我所用的D-L距离，并不满足泛函理论中的三要素标准，数学上不够严谨。但是并不影响工程使用。
从代码上来看，swap操作仅限于相邻字母间的swap。而对于abc和ca，其实相当于非相邻字母swap操作对待了，因此在计算时，距离仍为3.这种情况只能发生在一个字符串长度为2的情况下，如果需要改进代码的话，可以对字符串长度增加一个判断。若有字符串B长度为2，取editDistance(A,B)=min(editDistance(A,B), editDistance(A,swap(B))+1)即可。
而对于长度均大于2的swap操作，如abcd和cbad，只能是距离为2了。否则，添加非相邻字母的swap操作，好像很麻烦的样子。
扩展：
查资料发现，其实编辑距离是“String Metric”（字符串度量）的一种常用的距离表示。String Metric的维基百科定义如下：
In mathematics and computer science, a string metric (also known as a string similarity metric or string distance function) is a metric that measures similarity or dissimilarity (distance) between two text strings for approximate string matching or comparison and in fuzzy string searching.
而除了L氏距离，还有许多其他表示字符串度量的方法，如下（List of string metrics）：
Hamming distance
Levenshtein distance and Damerau–Levenshtein distance
Needleman–Wunsch distance or Sellers' algorithm
Smith–Waterman distance
FASTA
BLAST
Gotoh distance or Smith-Waterman-Gotoh distance
Monge Elkan distance
Block distance or L1 distance or City block distance
Jaro–Winkler distance
Soundex distance metric
Simple matching coefficient (SMC)
Dice's coefficient
Jaccard similarity or Jaccard coefficient or Tanimoto coefficient
Tversky index
Overlap coefficient
Variational distance
Hellinger distance or Bhattacharyya distance
Information radius (Jensen–Shannon divergence)
Skew divergence
Confusion probability
Tau metric, an approximation of the Kullback–Leibler divergence
Fellegi and Sunters metric (SFS)
Maximal matches
Lee distance
在维基百科中有相应的链接，若有时间，可以找来看看。
参考资料：
