字元串編輯距離
指的是字元串A向字元串B轉換的最小步數。比如字元串“ABC”轉換成“A”最少需要删除“B”,“C”兩個字元。字元串操作有三種，一個是新增插入，一個是删除，一個是替換。該算法最早由 levenshtein提出。
從A字元串向B字元串轉換，最重要的是考慮不要重複操作，比如 “abd”轉換成“abcd”隻需要插入一個“c”,而不用删去“d”再插入“cd”。這就要看Levenshtein Distance算法的思想了。
算法基本原理：假設我們可以使用d[ i , j ]個步驟，表示将串s[ 1…i ] 轉換為串t [ 1…j ]所需要的最少步驟個數，在最基本的情況下，即在i等于0時，也就是說串s為空，那麼對應的d[0,j] 就是至少增加j個字元，使得s轉化為t。在j等于0時，也就是說串t為空，那麼對應的d[i,0] 就是減少i個字元，使得s轉化為t。
原理看起來複雜，其實就是規定了一個二維數組 d。d[i][j]表示長度為i的字元串S向長度為j的字元串T的編輯距離。那麼我們知道，比如說字元串S =“abceh“要編輯成字元串T=“bbeh”,為了下标對應，我們可以設定一個二維數組d[5+1][4+1]。根據我們的設定，d[0][0]表示的就是長度為0的S（即為空）轉換成長度為0的T（也為空），需要0步操作。表格如下：
黃色表格就是d[0][0]的值，橙色的是d[0][1]的值，表示的就是長度為0的S（即為空）轉換成長度為1的T（即“b”），我們初始化的時候可以輕易算出表格上方，左方的所有步數。我們現在開始求d[1][1]（表格中？問号）的值，它表示的是長度為1的字元串S（即“a”）編輯成長度為1的字元串T（即“b“）的距離。我們可以輕易知道這個值最小是1，操作是替換，既不是新增插入，也不是删除。于是表格便成了：
我們的繼續求下一個問号所在的步數d[1][2]。我們為什麼要求這個從“a”轉換成“bb”的步數呢？原因就是為了比較字元編輯時候，插入、删除、替換哪個操作是最優操作。比如這裡，”a”轉換成“bb”，剛剛我們已經求出了“a”轉換成“b”的最短編輯距離是1（也就是d[1][1]），是以現在變成了求“b”到“bb”的最短編輯距離，因為字元串“a”在d[1][1]的時候已經被我們轉換成“b”了。是以d[1][2]的值應該為d[1][1]+1。我們以此類推添加表格的第一行。
求第二行d[2][1]（也就是“ab”=>“b“）的時候，這裡有一個注意的地方，就是對于“ab”=>“b”的情況，Levenshtein 是使用替換而不是删除操作，也就是把“a”替換成空字元。是以這裡我們對字元“ab”的最優操作是把“a”替換成空字元，再拿“ b”與“b”比較。也就是d[2][1] = d[1][0]+(S[2-1]==T[1-1]?0:1) 這裡S,T的下标記得-1，因為是取數組下标。是以我們得出結論：
- d[m][n]步如果是新增，那麼d[m][n] = d[m][n-1]+1。
- d[m][n]步如果是删除，那麼d[m][n] = d[m-1][n]+1。
- d[m][n]步如果是替換，那麼d[m][n] = d[m-1][n-1]+ (S[m -1] == T[n -1]?0:1)。
- d[i][j]的最優解就是它上一步的最優解加上上面三步的最小值。
Levenshtein Distance算法的用最優解累加的方法求出最優編輯距離。這也是一種窮舉的辦法。PHP中就有levenshtein函數。我們現在自己實作一下這個算法的代碼：
function countDistance($s,$t){
$lens = strlen($s);
$lent = strlen($t);
if($lens == ){
return $lent;
}
if($lent == ){
return $lens;
}
$dp = array();
for($i = ; $i <= $lens; $i++){
//初始化第0列
$dp[$i][] = $i;
}
for($j = ;$j<= $lent;$j++){
//初始化第0行
$dp[][$j] = $j;
}
for($i = ;$i<= $lens;$i++){
for($j =;$j <= $lent;$j ++){
//插入
$insert = $dp[$i][$j-] + ;
//删除
$del = $dp[$i-][$j]+;
//替換
$modi = $dp[$i-][$j-] + ($s[$i -] == $t[$j -]?:);
$dp[$i][$j] = min($insert,$del,$modi);
}
}
return $dp[$lens][$lent];
}
我們上面簡單的例子基本上實作了Levenshtein算法，當然還有兩個缺點：
- 中文字元等操作的情況。
- 二維數組很占空間，比如2個1000字元的字元串，所需要的二維數組很龐大。需要改寫。