編輯距離是指利用字元操作，把字元串A轉換成字元串B所需要的最少操作數。在這裡定義的單字元編輯操作有且僅有三種：
- 插入（Insertion）
- 删除（Deletion）
- 替換（Substitution）
譬如，"kitten" 和 "sitting" 這兩個單詞，由 "kitten" 轉換為 "sitting" 需要的最少單字元編輯操作有：
1.kitten → sitten (substitution of "s" for "k")
2.sitten → sittin (substitution of "i" for "e")
3.sittin → sitting (insertion of "g" at the end) 是以，"kitten" 和 "sitting" 這兩個單詞之間的編輯距離為 3 。
一般來說，兩個字元串的編輯距離越小，則它們越相似。如果兩個字元串相等，則它們的編輯距離（為了友善，本文後續出現的“距離”，如果沒有特别說明，則預設為“編輯距離”）為0（不需要任何操作）。
不難分析出，兩個字元串的編輯距離肯定不超過它們的最大長度（可以通過先把短串的每一位都修改成長串對應位置的字元，然後插入長串中的剩下字元）。
形式化定義
問題描述
給定兩個字元串A和B，求字元串A至少經過多少步字元操作變成字元串B。
問題解決
- 當其中某個字元串長度為0的時候,編輯距離就是另一個字元串的長度. (我們可以了解為, 對長度為0的字元串一直插入字元變成另一個字元串)
-
當字元串不等的時候, 我們總是習慣性的從字串開頭開始看.
那麼A[0] = B[0];的時候, 那麼此時編輯距離依舊是0, 我們可以直接去除字元串的第一個字元了. 因為此時A與B的編輯距離應該是等于A[1]..A[A.length-1], B[1]..B[B.length-1]兩者的編輯距離的.
如果A[0] != B[0], 那麼此時我們要考慮的很多了, A[0] 會不會與B[1]相等, 這樣隻要添加一個字元就可以了. B[0] 會不會與A[1]相等, 或者A[1]與B[1]也不相等. 這樣
若我們從後面往前看,ij代表a,b 的長度,我們讓求編輯距離的方法為f
當 a[i] = a [j] 時候,f(i, j) = f(i-1, j-1);
a[i] != a [j] 時候,f(i, j) = f(i-1, j-1) + 1; 或者是 f(i, j-1) +1 或者是f(i-1, j) + 1;
那麼此時動态轉移方程為
f(i,j) = max(i,j) if i與j其中一個為0<br>
f(i,j) = f(i-1,j-1) if a[i]=a[j]
f(i,j) = min (f(i-1,j-1) + 1,
f(i, j-1) + 1,
f(i-1, j) + 1); 這是一個動态規劃問題.使用公式我們可以很快寫出遞歸方法
public static int getEditDistanceByRecursion(String a, String b, int aIndex, int bIntex) {
if (Math.min(aIndex, bIntex) == 0) {
return Math.max(aIndex, bIntex);
}
if (a.charAt(aIndex) == b.charAt(bIntex)) {
return getEditDistanceByRecursion(a, b, aIndex - 1, bIntex - 1);
}
return Math.min(getEditDistanceByRecursion(a, b, aIndex - 1, bIntex - 1) + 1,
Math.min(getEditDistanceByRecursion(a, b, aIndex, bIntex - 1) + 1,
getEditDistanceByRecursion(a, b, aIndex - 1, bIntex) + 1));
} 但是遞歸的最大缺點為重複計算. 多次計算同一個結果. 我們需要一個表來存儲重複計算的結果.
代碼如下
public static int getEditDistance(String origin, String target) {
if (TextUtils.isEmpty(origin) && TextUtils.isEmpty(target)) {
return 0;
}
if (TextUtils.isEmpty(origin)) {
return target.length();
}
if (TextUtils.isEmpty(target)) {
return origin.length();
}
int[][] dp = new int[origin.length() + 1][target.length() + 1];
for (int i = 0; i <= origin.length(); i++) {
dp[i][0] = i;
}
for (int j = 0; j <= target.length(); j++) {
dp[0][j] = j;
}
for (int i = 1; i <= origin.length(); i++) {
for (int j = 1; j <= target.length(); j++) {
if (origin.charAt(i - 1) == target.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
dp[i][j] = Math.min(dp[i][j], Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
}
}
return dp[origin.length()][target.length()];
} 如果我們需要求兩個字元串的相識度,則是:
public static float getSimilarity(String origin, String target) {
if (TextUtils.isEmpty(origin) || TextUtils.isEmpty(target)) {
return 0f;
}
return 1.0f - getEditDistance(origin, target) / (float) Math.max(origin.length(), target.length());
} 應用與思考
編輯距離是NLP基本的度量文本相似度的算法，可以作為文本相似任務的重要特征之一，其可應用于諸如拼寫檢查、論文查重、基因序列分析等多個方面。但是其缺點也很明顯，算法基于文本自身的結構去計算，并沒有辦法擷取到語義層面的資訊。
由于需要利用矩陣，故空間複雜度為O(MN)。這個在兩個字元串都比較短小的情況下，能獲得不錯的性能。不過，如果字元串比較長的情況下，就需要極大的空間存放矩陣。例如：兩個字元串都是20000字元，則 LD 矩陣的大小為：20000 * 20000 * 2=800000000 Byte=800MB。
參考資料
[2] https://en.wikipedia.org/wiki/Levenshtein_distance [3] https://www.dreamxu.com/books/dsa/dp/edit-distance.html [4] https://www.jianshu.com/p/a96095aa92bc [5] https://www.jianshu.com/p/a617d20162cf