最小编辑距离的定义：编辑距离（Edit Distance），又称Levenshtein距离。是指两个字串之间，由一个转成还有一个所需的最少编辑操作次数。许可的编辑操作包含将一个字符替换成还有一个字符。插入一个字符，删除一个字符。
比如将kitten一字转成sitting：
sitten（k→s）
sittin（e→i）
sitting（→g）
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
Thewords `computer' and `commuter' are very similar, and a change of just oneletter, p->m will change the first word into the second. The word `sport'can be changed into `sort' by the deletion of the `p', or equivalently, `sort'can be changed into `sport' by the insertion of `p'.
Theedit distance of two strings, s1 and s2, is defined as the minimum number ofpoint mutations required to change s1 into s2, where a point mutation is oneof:
1. change a letter,
2. insert a letter, or
3. delete a letter
这个问题怎样解决呢？
假设不常常做算法。那么看到这个问题会没有思路。由于把一个串儿编辑成还有一个串方法应该是非常多的，insert，delete。substitute组合有非常多种，那么怎样度量最小编辑距离呢？
以下给出一种经典的算法思路：分而治之。把复杂的问题拆解成简单的子问题（并如果子问题的解已知）。这个思路最常见的一种建模方法就是数学中的数列，用前面的已知项推出未知项。在计算机中又叫递归或者递推。
比如斐波拉契数列问题。
那么在此问题中，怎样能得到最小编辑距离的递推公式呢？我们思考问题最好从最简单最特殊的地方出发。
我们如果有两个字符串，情形有
1.两个都是空串 d('', '') = 0 -- ''= empty string
2.有一个是空串 d(s, '') = d('', s)= |s| -- i.e. length of s（连续删除或插入）
3.两个非空串 d(s1+ch1,s2+ch2)
此时，d(s1+ch1, s2+ch2)的结果得来无非是三种情况决定。第一种如果d(s1,s2)已知，我们把两个串的最后一个字符做替换操作。则d(s1+ch1, s2+ch2)= d(s1, s2) + if ch1=ch2 then 0 else 1。另外一种可能是如果d(s1,s2+ch2)已知。把第一个串的ch1删除，则d(s1+ch1, s2+ch2)= d(s1,s2+ch2)+1；第三中可能是如果d(s1+ch1,s2)已知，在第一个串末尾插入ch2。则d(s1+ch1, s2+ch2)= d(s1+ch1,s2)+1。那么究竟是哪一种情况得到了d(s1+ch1,s2+ch2)肯定是最小的那个决定，因此
d(s1+ch1,s2+ch2) =min[ d(s1, s2) + if ch1=ch2 then 0 else 1 ,d(s1+ch1, s2) + 1,d(s1,s2+ch2) + 1 ]
接下来我们量化定义d[i,j]是一个长度为i的串s和一个长度为j的串t的最小编辑距离。
那么
d[0,0]=0
d[0,j]=j;(前者插入j个字母或后者删除j个字母)
d[i,0]=i;(前者删除i个字母或后者插入i个字母)
d[i,j]=min{d[i-1,j-1]+(s[i]==t[j]?0:1), d[i-1,j]+1, d[i,j-1]+1 }
得到递推式后，求d[i,j]就easy了。定义一个二维数组distance[][]来存储最小编辑距离，以下试java代码：
package Algorithms;public class EditDistanceComputer {private int sWeight = 1;//替换操作substitute的权值，也就是代价overheadprivate int iWeight = 1;//插入操作insert的权值private int dWeight = 1;//删除操作delete的权值public static void main(String[] args){String s = "intention";String t = "execution";EditDistanceComputer editDC = new EditDistanceComputer();System.out.println(editDC.getMinEditDistance(s, t));}public void setWeight(int sWeight, int iWeight, int dWeight){this.sWeight = sWeight;this.iWeight = iWeight;this.dWeight = dWeight; }public int getMinEditDistance(String s, String t){int m = s.length();int n = t.length();//申请(m+1)*(n+1)矩阵空间int[][] distance = new int[m+1][n+1];//初始化特殊值for(int i=0;i<m+1;i++){distance[i][0] = i;}for(int i=0;i<n+1;i++){distance[0][i] = i;}//利用递推公式遍历填充整个距离矩阵for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){distance[i][j] = getMin(distance[i-1][j]+dWeight, distance[i][j-1]+iWeight, distance[i-1][j-1]+(s.charAt(i-1)==t.charAt(j-1)?0:sWeight));}}printMatrix(distance,m+1,n+1);return distance[m][n];}//打印矩阵public void printMatrix(int[][] matrix, int rownum, int colnum){for(int i=rownum-1;i>=0;i--){for(int j=0;j<colnum;j++){System.out.print(matrix[i][j]+"");}System.out.println();}}private int getMin(int a, int b, int c){return (a<b)?(a<c?
a:c):(b<c?b:c); } }
算法的时间复杂度O(m*n),空间复杂度O(m*n)。
我们已经计算除了最小编辑距离，那么怎样把s经过distance[i][j]次操作转换为t呢？看看前面的矩阵，我们得出distance[i][j]实际上有一条路径。假设记下这条路径，那么我们就行回溯，找到相应的操作。接下来我们定义记录每一次操作的回溯矩阵backtrace[][]
package Algorithms;enum TraceOperator {L,D,S}; //L:LEFT D:DOWN S:SLANTpublic class EditAlignment {private int sWeight = 1;//替换操作substitute的权值，也就是代价overheadprivate int iWeight = 1;//插入操作insert的权值private int dWeight = 1;//删除操作delete的权值private int m = 0;private int n = 0;int[][] distance = null;TraceOperator[][] backtrace = null;StringBuffer sb = null;public static void main(String[] args){String s = "intention";String t = "execution";EditAlignment editDC = new EditAlignment();System.out.println(editDC.getMinEditDistance(s, t));editDC.Alignment(s, t);}public void setWeight(int sWeight, int iWeight, int dWeight){this.sWeight = sWeight;this.iWeight = iWeight;this.dWeight = dWeight; }public void Alignment(final String s, final String t){sb = new StringBuffer(s);System.out.println("SourceString StringBuffer before Alignment: " + sb);if(backtrace == null || distance == null) System.exit(-1);int i = m;int j = n;while(backtrace[i][j] != null){switch(backtrace[i][j]){case S:if(s.charAt(i-1)!=t.charAt(j-1)){sb.replace(i-1, i, ""+t.charAt(j-1));System.out.println("source string: " + sb);System.out.println("target string: " + t);System.out.println("---------------------------------------");}i--;j--;break;case L:sb.insert(i, t.charAt(j-1));j--;System.out.println("source string: " + sb);System.out.println("target string: " + t);System.out.println("---------------------------------------");break;case D:sb.deleteCharAt(i-1);i--;System.out.println("source string: " + sb);System.out.println("target string: " + t);System.out.println("---------------------------------------");break;default:System.exit(-1);}}System.out.println("SourceString StringBuffer after Alignment: " + sb);}public int getMinEditDistance(final String s, final String t){m = s.length(); //看成二维矩阵的话，m相应行，也就是纵坐标。n相应列。也就是横坐标n = t.length();int a,b,c;distance = new int[m+1][n+1];backtrace = new TraceOperator[m+1][n+1];initMatrix(m+1, n+1);for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){a = distance[i-1][j]+dWeight;//deletion对于s的操作，下面都是以s为源串b = distance[i][j-1]+iWeight;//insertionc = distance[i-1][j-1]+(s.charAt(i-1)==t.charAt(j-1)?0:sWeight);//substitutionif(a == getMin(a,b,c)){distance[i][j] = a;backtrace[i][j]=TraceOperator.D;//deletion}else if(b == getMin(a,b,c)){distance[i][j] = b;backtrace[i][j]=TraceOperator.L;//insertiodn}else if(c == getMin(a,b,c)){distance[i][j] = c;backtrace[i][j]=TraceOperator.S;//substitution}}}printMatrix(distance,m+1,n+1);System.out.println();printMatrix(backtrace,m+1,n+1);return distance[m][n];}public void printMatrix(int[][] matrix, int rownum, int colnum){for(int i=rownum-1;i>=0;i--){for(int j=0;j<colnum;j++){System.out.print(matrix[i][j]+"");}System.out.println();}}public void printMatrix(TraceOperator[][] matrix, int rownum, int colnum){for(int i=rownum-1;i>=0;i--){for(int j=0;j<colnum;j++){System.out.print(matrix[i][j]+"");}System.out.println();}}private void initMatrix(int x, int y){for(int i=0;i<x;i++){distance[i][0] = i;}for(int i=0;i<y;i++){distance[0][i] = i;}for(int i=1;i<x;i++){backtrace[i][0] = TraceOperator.D ;}for(int i=1;i<y;i++){backtrace[0][i] = TraceOperator.L;}}private int getMin(int a, int b, int c){return (a<b)?
(a<c?a:c):(b<c?b:c); } }
算法的第一次改进：
原来的算法是创建一个大小为s*t的矩阵。假设全部字符串加起来是1000个字符那么长的话，那么这个矩阵就会是1M。假设字符串是10000个字符，那么矩阵就是100M。假设元素都是整数（这里是指数字。Int32）的话。那么矩阵就会是4*100M == 400MB这么大。
如今的算法版本号仅仅使用2*t个元素，这使得后面给出的样例成为2*10,000*4 = 80 KB。其结果是。不但内存占用更少，并且速度也变快了。由于这使得内存分配仅仅须要非常少的时间来完毕。当两个字符串的长度都是1k左右时，新算法的效率是旧算法的两倍！
来看看改进的算法吧，对于计算编辑距离，假设我们不须要回溯，而是仅仅想知道两者的相似度，那么上面的算法存储空间就是能够改进的，细致观察你会发现递推公式d[i,j]=min{ d[i-1,j-1]+(s[i]==t[j]?0:1), d[i-1,j]+1, d[i,j-1]+1}的计算过程以及距离矩阵。你会发现当前距离的计算仅仅和前一行以及当前行有关，即每次计算都仅仅须要斜向的[i-1,j-1]、横向的[i,j-1]和纵向的[i-1,j]。而我们如今不须要知道中间结果，仅仅须要终于结果。那么能够仅仅要两行存储空间，进行迭代计算就可以。如今仅仅须要cur_row[]和pre_row[]两个向量空间就可以。
以下是改进的代码：
package Algorithms;public class EditDistanceComputer1 {private int sWeight = 1;//替换操作substitute的权值，也就是代价overheadprivate int iWeight = 1;//插入操作insert的权值private int dWeight = 1;//删除操作delete的权值public static void main(String[] args){String s = "GUMBO";String t = "GAMBOL";EditDistanceComputer1 editDC = new EditDistanceComputer1();System.out.println(editDC.getMinEditDistance(s, t));}public void setWeight(int sWeight, int iWeight, int dWeight){this.sWeight = sWeight;this.iWeight = iWeight;this.dWeight = dWeight; }public int getMinEditDistance(String s, String t){int m = s.length();int n = t.length();int[] cur_row = new int[n+1];int[] pre_row = new int[n+1];int[] temp = null;for(int i=0;i<n+1;i++){pre_row[i] = i;}for(int i=1;i<=m;i++){cur_row[0] = i;for(int j=1;j<=n;j++){cur_row[j] = getMin(pre_row[j]+dWeight, cur_row[j-1]+iWeight, pre_row[j-1]+(s.charAt(i-1)==t.charAt(j-1)?0:sWeight));}printVector(cur_row,n+1);printVector(pre_row,n+1);System.out.println();//交换当前行和先前行，为进行下一轮迭代做准备，腾出pre_row的位置temp = cur_row;cur_row = pre_row;pre_row = temp;}return pre_row[n];}public void printVector(int[] vector,int colnum){for(int j=0;j<colnum;j++){System.out.print(vector[j]+"");}System.out.println();}private int getMin(int a, int b, int c){return (a<b)?
(a<c?
a:c):(b<c?
b:c); } }
改进后的算法时间复杂度O(m*n),空间复杂度O(2*n)
下图是对上述计算过程的解释：
最后，这个算法的时间复杂度还是O(m*n),空间复杂度O(2*n)，事实上还有其它算法，在某些应用场景更加高效。眼下先写到这儿。当前最高效的算法是某个公司的商业机密。只是，关于最小编辑距离应用很广泛，小到我们平时使用的IDE的代码自己主动补全，代码提示，搜索引擎关键词提示等等，大到远程屏幕更新。压缩传输字符串，以及机器识别中的距离度量等。都有这方面的原理。
參考：
Minimum edit distance
http://web.stanford.edu/class/cs124/lec/med.pdf
Dynamic ProgrammingAlgorithm (DPA) for Edit-Distance
/ll/AlgDS/Dynamic/Edit/
AN EXTENSION OF UKKONEN'SENHANCED DYNAMIC PROGRAMMING ASM （Approximate string matching）ALGORITHM
/publications/asm/asm.php
Fast Approximate String Matching in a Dictionary
http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.21.3317&rep=rep1&type=pdf
