算法之美――求解 字符串间最短距离（动态规划） - 小熊不去实验室 - 博客频道 - CSDN.NET

把两个字符串变成相同的基本操作定义如下：
1. 修改一个字符（如把 a 变成 b）
2. 增加一个字符 (如 abed 变成 abedd)
3. 删除一个字符（如 jackbllog 变成 jackblog）
针对于 jackbllog到jackblog 只需要删除一个或增加一个 l 就可以把两个字符串变为相同。把这种操作需要的次数定义为两个字符串的距离 L, 则相似度定义为1/(L+1) 即距离加一的倒数。那么jackbllog和jackblog的相似度为 1/(1+1)=1/2=0.5 也就是所两个字符串的相似度是 0.5。

1. Definition of  Minimum Edit Distance 

Edit Distance用于衡量两个strings之间的相似性。

两个strings之间的Minimum edit distance是指把其中一个string通过编辑（包括插入，删除，替换操作）转换为另一个string的最小操作数。

如上图所示，d（deletion）代表删除操作，s（substitution）代表替换操作，i（insertion）代表插入操作。

（为了简单起见，后面的Edit Distance 简写为ED）

如果每种操作的cost（成本）为1，那么ED = 5.

如果s操作的cost为2（即所谓的Levenshtein Distance），ED = 8.

2. Computing Minimum Edit Distance

那么如何找到两个strings的minimun edit distance呢？要知道把一个string转换为另一个string可以有很多种方法（或者说"路径"）。我们所知道起始状态（第一个string）、终止状态（另一个string）、基本操作（插入、删除、替换），要求的是最短路径。

对于如下两个strings：

X的长度为n

Y的长度为m

我们定义D（i，j）为 X 的前i个字符 X[1...i] 与 Y 的前j个字符 Y[1...j] 之间的距离，其中0<i<n, 0<j<m，因此X与Y的距离可以用D(n,m)来表示。

假如我们想要计算最终的D(n,m)，那么可以从头开始，先计算D(i, j) （i和j从1开始）的值，然后基于前面的结果计算更大的D(i, j)，直到最终求得D(n,m)。

算法过程如下图所示：

上图中使用的是"Levenshtein Distance"即替换的成本为2.

请读者深入理解一下上图中的循环体部分： D(i,j)可能的取值为:

1. D(i-1, j) +1 ；

2. D(i, j-1) +1 ；

3. D(i-1, j-1) + 2 (当X新增加的字符和Y新增加的字符不同时，需要替换）或者 + 0（即两个字符串新增加的字符相同）

下图即对字符串 INTENTION 和 EXECUTION 一步步求ED形成的表。左上角画红圈的8就是两个字符串间的最小ED。

http://bylijinnan.iteye.com/blog/1627362
Init record[][] to all -1.

1.      * 解答：动态规划+备忘录 
2.      * 2012-11-04：主要思路还是递归。字符串记为A和B（当前比较的位置记为K，当前距离记为L），从第一个字符开始按位比较，分两种情况： 
3.      * 1、A和B在第K位的字符相等（L不变）。那好，各自向后移动，继续比较第K+1位 
4.      * 2、A和B在第K位的字符不相等（L=L+1）。采取递归，作三种操作，看哪种操作最后得到的距离最短： 
5.      * 一是A和B同时向后移动（相当于A和B同时删除这个字符），继续比较第K+1位 
6.      * 二是A移动B不移动，相当于A删除了这个字符，用剩余的字符与B作比较 
7.      * 三是A不移动B移动，相当于B删除了这个字符，用剩余的字符与A作比较 
8.      * 递归的好处就是可以递归得到这三种操作到最后得到的距离，哪个是最短 
9.      * 举个例子，A="abc",B="zbc"。我们可以一眼看出，采用第一种操作算得的距离最短（L=1） 
10.      * 但程序中要递归执行这另外两种操作并比较： 
11.      * A1="bc",B2="zbc" -->按位比较得到的L=1+3 
12.      * A2="abc",B2="bc" -->按位比较得到的L=1+3 
13.      * 因此程序会选择第一种操作，再接着进行第K+1位的比较 
14.      */  
15.       
16.     private static int[][] record;  //记录子问题的解，0表示子问题未求解  
17.       
18.     public static void main(String[] args) {  
19.         String strA = "abcd";  
20.         String[] strBB = {  
21.                 "",  
22.                 "z",  
23.                 "a",  
24.                 "ac",  
25.                 "adc"  
26.         };  
27.         for (String strB : strBB) {  
28.             int distance = distanceBetween(strA, strB);  
29.             System.out.println(distance);  
30.         }  
31.     }  
32.   
33.     public static int distanceBetween(String strA, String strB) {  
34.         int distance = -1;  
35.         if (strA != null && strB != null) {  
36.             int lenA = strA.length();  
37.             int lenB = strB.length();  
38.             if (lenA == 0 && lenB == 0) {  
39.                 distance = 0;  
40.             }  
41.             if (lenA != 0 && lenB == 0) {  
42.                 distance = lenA;  
43.             }  
44.             if (lenA == 0 && lenB != 0) {  
45.                 distance = lenB;  
46.             }  
47.             if (lenA != 0 && lenB != 0) {  
48.                 record = new int[lenA + 1][lenB + 1];  
49.                 char[] charArrayA = strA.toCharArray();  
50.                 char[] charArrayB = strB.toCharArray();  
51.                 distance = distanceHelp(charArrayA, charArrayB, 0, 0, lenA - 1, lenB - 1);  
52.             }  
53.         }  
54.         return distance;  
55.     }  
56.       
57.     //endA和endB是不变的，因此记录子问题的解可用record[beginA][beginB]来表示  
58.     public static int distanceHelp(char[] charArrayA, char[] charArrayB,  
59.                                      int beginA, int beginB, int endA, int endB) {  
60.         if (beginA > endA) {             //递归出口：A从头到尾每个字符遍历完了，B有两种情况：  
61.             if (beginB > endB) {         //1.B也同时遍历完了，说明这A=B  
62.                 return 0;     
63.             } else {  
64.                 return endB - beginB + 1;   //2.B还没遍历完，那B剩下的长度就是两个字符串不同的地方，即距离  
65.             }  
66.         }  
67.         if (beginB > endB) {  
68.             if (beginA > endA) {  
69.                 return 0;  
70.             } else {  
71.                 return endA - beginA + 1;  
72.             }  
73.         }  
74.           
75.         int distance = -1;  
76.         if (charArrayA[beginA] == charArrayB[beginB]) {  
77.             distance = record[beginA + 1][beginB + 1];  
78.             if (distance == 0) {  
79.                 distance = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB);  
80.             }  
81.         } else {  
82.             int d1 = record[beginA + 1][beginB];  
83.             if (d1 == 0) {  
84.                 d1 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB, endA, endB);   
85.             }  
86.             int d2 = record[beginA][beginB + 1];  
87.             if (d2 == 0) {  
88.                 d2 = distanceHelp(charArrayA, charArrayB, beginA, beginB + 1, endA, endB);   
89.             }  
90.             int d3 = record[beginA + 1][beginB + 1];  
91.             if (d3 == 0) {  
92.                 d3 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB);   
93.             }  
94.             distance = min(d1, d2, d3) + 1;  
95.         }  
96.         record[beginA][beginB] = distance;  
97.         return distance;  
98.     }  

Read full article from 算法之美――求解 字符串间最短距离（动态规划） - 小熊不去实验室 - 博客频道 - CSDN.NET