字串的編輯距離實例詳解
- 零下一度原創
- 2017-06-30 09:34:252029瀏覽
動態規劃的演算法題往往都是各大公司筆試題的常客。在不少演算法類的微信公眾號中，關於「動態規劃」的文章屢見不鮮，都在試圖用最淺顯易懂的文字來描述講解動態規劃，甚至有的用漫畫來解釋，認真讀每一篇公眾號推送的文章其實都能讀懂，都能對動態規劃有個大概了解。
什麼是動態規劃？通俗地理解來說，一個問題的解決辦法一看就知道（窮舉），但不能一個一個數啊，你得找到最優的解決辦法，換句話說題目中就會出現類似“最多”、“最少”，“一共有多少種”等提法，這些題理論上都能使用動態規劃的思想來求解。 動態規劃與分治方法類似，都是透過組合子問題的解來求解原問題，但它對每個子問題只求解一次，將其保存在表格中，無需重新計算，通常用於求解最最佳化問題——《演算法導論》#。
編輯距離（Edit Distance），本文指的是Levenshtein距離，也就是字串S1透過插入、修改、刪除三種運算最少能轉換成字串S2#的次數。例如：S1 = abc，S2 = abf，編輯距離d = 1#（只需將c修改為f）。在本文中將利用動態規劃的演算法思想對字串的編輯距離求解。
定義：S1、S2表示兩個字串，S1(i)表示S 1的第一個字元，d[i, j]表示#S1的第i個前綴到S2的第j個前綴（例如:S1 = ” abc”,S2 = ”def”,求解S1到#S2的編輯距離為d[ 3, 3]）。
若S1 = ”abc”, S2 = ”dec”，此時它們的編輯距離為d[3, 3] = 2 ，觀察兩個字串的最後一個字元是相同的，也就是說S1(3) = S2(3)不需要做任何變換，故S1 = ”abc”, S2 = ”dec” <= > S1' = ”ab”, S2' = ”de”，即當S1[i] = S[j]時，d [i, j] = d[i-1,j -1]。得到公式：d[i, j] = d[i - 1, j - 1] (S1[i] = S2[j])
上面一條得出了當S1[i] = S2[j]的計算公式，顯然還有另一個情況就是S1[i] ≠ S2[j]，若S1 = ”abc”, S2 = ”def”。 S1變換到S2的過程可以「修改##」，但也可以透過「插入」、「##刪除#”使得S1#變換為#S2。
1)在
字串末位插入字元「f」，此時S1 = ”abcf”，S2 = ”def”,此時即S1[i] = S2[j]的情況，S1變換為S2的編輯距離為##d[4, 3] = d[ 3, 2]。所以得出d[i, j]=d[i, j - 1] + 1。 （+1是因為S1新增了」f」） 2 )在S2
字串末位元插入字元“c”，此時S1 = ”abc” ，S2 = ”defc”#，此時即S1[i] = S[j]#的情況，S1變換為S2的編輯距離為#d[3, 4] = d[2, 3] 。所以得出d[i, j]=d[i - 1, j] + 1，實際上這是對S1做了 刪除。 （+1是因為S2新增了」c”） 3 )將S1
字串末位元字元修改為”f”##S1 = ”abf”，S2 = ”def”#，此時即#S1[i] = S[j] 的情況，S1變換為S2的編輯距離為d[3, 3] = d[2, 2]。所以得出d[i, j] = d[i – 1, j - 1] + 1。 （+1是因為S1修改了“c”##） 綜上，得出遞推公式： => # 不妨用表格表示動態規劃對S1=”abc”，S2=“def”的求解過程。 可以看出紅色方塊即是最終所求的編輯距離，整個求解過程就是填滿這個表— —二維數組。以下是Java、Python分別對字串編輯距離的動態規劃求解。 Java # Python3 
1 package com.algorithm.dynamicprogramming; 2 3
/** 4 * 动态规划——字符串的编辑距离 5 * s1 = "abc", s2 = "def" 6
* 计算公式： 7 * | 0
i = 0, j = 0 8 * | j
i = 0, j > 0 9 * d[i,j] = | i
i > 0, j = 0 10 * | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]) s1(i) = s2(j) 11
* | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1) s1(i) ≠ s2(j) 12 * 定义二维数组[4][4]： 13
* d e f d e f 14 * |x|x|x|x| |0|1|2|3| 15
* a |x|x|x|x| => a |1|1|2|3| => 编辑距离d = [3][3] = 3 16 * b |x|x|x|x|
b |2|2|2|3| 17 * c |x|x|x|x| c |3|3|3|3| 18 * 19 * Created by yulinfeng on 6/29/17. 20
*/ 21 public class Levenshtein { 22 23 public static void main(String[] args) { 24
String s1 = "abc"; 25 String s2 = "def"; 26 int editDistance = levenshtein(s1, s2); 27
System.out.println("s1=" + s1 + "与s2=" + s2 + "的编辑距离为：" + editDistance); 28 } 29 30 /** 31
* 编辑距离求解 32 * @param s1 字符串s1 33 * @param s2 字符串s2 34 * @return 编辑距离 35
*/ 36 private static int levenshtein(String s1, String s2) { 37 int i = 0; //s1字符串中的字符下标 38
int j = 0; //s2字符串中的字符下标 39 char s1i = 0; //s1字符串第i个字符 40
char s2j = 0; //s2字符串第j个字符 41 int m = s1.length(); //s1字符串长度 42
int n = s2.length(); //s2字符串长度 43 if (m == 0) {
//s1字符串长度为0，此时的编辑距离就是s2字符串长度 44 return n; 45 } 46
if (n == 0) { 47 return m; //s2字符串长度为0，此时的编辑距离就是s1字符串长度 48 }
int[][] solutionMatrix = new int[m + 1][n + 1]; //求解矩阵 50
/** 51 *
d e f 52 * |0|x|x|x| 53
* a |1|x|x|x| 54
* b |2|x|x|x| 55
* c |3|x|x|x| 56 */ 57 for (i = 0; i < m + 1; i++) { 58 solutionMatrix[i][0] = i; 59 } 60
/** 61 * d e f 62
* |0|1|2|3| 63
* a |x|x|x|x| 64
* b |x|x|x|x| 65
* c |x|x|x|x| 66 */ 67 for (j = 0; j < n + 1; j++) { 68 solutionMatrix[0][j] = j; 69 } 70
/** 71 * 上面两个操作后，求解矩阵变为 72
* d e f 73
* |0|1|2|3| 74
* a |1|x|x|x| 75
* b |2|x|x|x| 76
* c |3|x|x|x| 77
* 接下来就是填充剩余表格 78
*/ 79 for (i = 1; i < m + 1; i++) { //i = 1,j = 1, 2, 3，以行开始填充 80 s1i = s1.charAt(i - 1); 81
for (j = 1; j < n + 1; j++) { 82 s2j = s2.charAt(j - 1); 83 int flag = (s1i == s2j) ? 0 : 1;
//根据公式，如果s1[i] = s2[j]，则d[i,j]=d[i-1,j-1]，如果s1[i] ≠ s2[j]，则其中一个公式为d[i,j]=d[i-1,j-1]+1 84
solutionMatrix[i][j] = min(solutionMatrix[i][j-1] + 1, solutionMatrix[i-1][j] + 1, solutionMatrix[i-1][j-1] + flag); 85
} 86 } 87 return solutionMatrix[m][n]; 88 } 89 90 /** 91 * 根据公式求解编辑距离 92
* @param insert s1插入操作 93 * @param delete s1删除操作 94 * @param edit s1修改操作 95 * @return 编辑距离 96
*/ 97 private static int min(int insert, int delete, int edit) { 98 int tmp = insert < delete ? insert : delete; 99
return tmp < edit ? tmp : edit;100 }101 } 1 ''' 2 动态规划——字符串的编辑距离 3 s1 = "abc", s2 = "def" 4
计算公式： 5 | 0
i = 0, j = 0 6 | j
i = 0, j > 0 7 d[i,j] = | i
i > 0, j = 0 8 | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]) s1(i) = s2(j) 9
| min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1) s1(i) ≠ s2(j)10
定义二维数组[4][4]：11 d e f d e f12 |x|x|x|x|
|0|1|2|3|13 a |x|x|x|x| => a |1|1|2|3| => 编辑距离d = [4][4] = 314 b |x|x|x|x|
b |2|2|2|3|15 c |x|x|x|x| c |3|3|3|3|16 '''17 def levenshtein(s1, s2):18 i = 0
#s1字符串中的字符下标19 j = 0 #s2字符串中的字符下标20 s1i = "" #s1字符串第i个字符21
s2j = "" #s2字符串第j个字符22 m = len(s1) #s1字符串长度23 n = len(s2) #s2字符串长度24
if m == 0:25 return n #s1字符串长度为0，此时的编辑距离就是s2字符串长度26 if n == 0:27
return m #s2字符串长度为0，此时的编辑距离就是s1字符串长度28
solutionMatrix = [[0 for col in range(n + 1)] for row in range(m + 1)] #长为m+1，宽为n+1的矩阵29 '''30
d e f31 |0|x|x|x|32 a |1|x|x|x|33 b |2|x|x|x|34
c |3|x|x|x|35 '''36 for i in range(m + 1):37 solutionMatrix[i][0] = i38 '''39
d e f40 |0|1|2|3|41 a |x|x|x|x|42 b |x|x|x|x|43
c |x|x|x|x|44 45 '''46 for j in range(n + 1):47 solutionMatrix[0][j] = j48 '''49
上面两个操作后，求解矩阵变为50 d e f51 |0|1|2|3|52 a |1|x|x|x|53
b |2|x|x|x|54 c |3|x|x|x|55 接下来就是填充剩余表格56 '''57 for x in range(1, m + 1):58
s1i = s1[x - 1]59 for y in range(1, n + 1):60 s2j = s2[y - 1]61 flag = 0 if s1i == s2j else 162
solutionMatrix[x][y] = min(solutionMatrix[x][y-1] + 1, solutionMatrix[x-1][y] + 1, solutionMatrix[x-1][y-1] + flag)63 64
return solutionMatrix[m][n]65 66 def min(insert, delete, edit):67 tmp = insert if insert < delete else delete68
return tmp if tmp < edit else edit69 70 s1 = "abc"71 s2 = "def"72 distance = levenshtein(s1, s2)73 print(distance)
以上是字串的編輯距離實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！