資料對齊-編輯距離演算法詳解（Levenshtein distance）
總結一句話：編輯距離就是從一個字串變到另外一個字串所需要最小的步驟
一：簡介
在資訊理論、語言學和電腦科學中，Levenshtein distance是用於測量兩個字串之間差異的字串度量。非正式的說就是兩個單詞之間的Levenshtein distance是將一個單詞更改為另一個單詞所需的單字元編輯（插入，刪除或替換）的最小步驟。
它以蘇聯數學家弗拉基米爾·萊文斯坦（Vladimir Levenshtein）的名字命名，作者在1965年提出的這個演算法。
Levenshtein distance也可以稱為編輯距離，儘管該術語也可以表示更大的距離度量系列。
Levenshtein distance與成對字串對齊密切相關。
這裡面主要內容為我對Levenshtein distance的英文翻譯，也加了一些我的想法~
二：演算法定義
1：定義
在兩個字串a和b之間的Levenshtein distance由下面 定義：
其中
當ai = bj時等於0，其他情況下等於1，
代表a的前i個位元組到b的前j個位元組的距離。
其中相對於a變化到b字串來說：
-
-
-
2：a small case
我們計算一下kitten和sitting之間的編輯距離
- k itten → s itten (替換 "k" -> "s")
- sitt e n → sitt i n (替換 "e" -> "i")
- sittin → sittin g (插入"g").
上面的變化過程所需要的步數就是最小的步數，所以他們之間的編輯距離就是"3"
3：演算法的上下界限
Levenshtein distance數值包含幾個上下界限
- 距離最小是兩個字串之間的長度的差值
- 距離最大是兩個字串中較長字串的長度
- 當且僅當字串相同時長度為0
- 當字串的長度相同時，距離的最大長度是 Hamming distance （下面會介紹一下）
- 兩個字串之間的距離小於等於與另外一個字串距離之和（三角形等式 a+b<c）
Hamming distance 是兩個相同長度的字串從頭開始分別比對兩個字串對應字元位置的值是否相同，不相同則距離加1，最後得到的結果就是 Hamming distance 例如abcd、abhg的距離為2，abcd、bcda的距離是4
三：應用場景
1：資料對齊
筆者在做一個關聯網路專案時，後臺有兩種特別資料：地址和公司，這兩種資料都是用 戶自己輸入的資料，所以特點就是同一個地點可能有多種不同的字串，就比如同一個地點：“北京市朝陽區IT產業園“，在後臺數據中可能有“北京朝陽區IT產業園”或者“北京朝陽區it園”等一系列資料，我們又不能去做模糊查詢（因為節點資料和邊關係為千萬級的，模糊查詢可能會匹配到大量的節點返回導致返回大量的資料影響專案穩定），我們就採用了資料對齊的方式解決這個問題，當用戶輸入一個地址時，我們通過編輯距離演算法就可以獲取到其他相關的資料顯示出來，就可以達到一個比較好的效果。具體的實現步驟就不在此介紹了。
2：拼寫糾錯
筆者所在公司就有一個公司內部提供的拼寫糾錯的元件，其中就有一部分使用了編輯距離演算法。下面是元件的簡單介紹：
糾錯主要解決 query 中輸入錯誤的情況，比如 query 為拼音，query中包含同音錯別字或不同音的別字，漏字的情況等等。 本糾錯主要基於兩種規則：拼音糾錯和編輯距離糾錯。 離線主要生成兩個詞典，即拼音詞典和編輯距離詞典。來源詞典主要來自於 cmc 資料，小區資料，topquery，以及白名單資料等。通過 ****指令碼 生成拼音詞典和編輯距 離詞典。指令碼執行完之後，會在 ***目錄 下生成詞典資料。拼音詞典的生成主要是將來源詞典中的詞轉換為拼音，編輯距離詞典的生成主要是省略某個字或者某個拼音的字母生成的。生成字典的程式碼在 tool 下。 線上糾錯邏輯 通過 make 編譯程式碼可以生成 so 目錄下的動態連結庫。 對外提供的是 java RPC 服務，通過 java jni 連結 c++動態連結庫。
主要糾錯邏輯如下：首先對 query 解析，判斷是全拼音或包含中文。若全是拼音，則會直接走對應的拼音糾錯召回結果，如果不能通過拼音解決，再走編輯距離召回，解決是否漏字母的情況；若是部分中文或全中文的 query，則先進行拼音糾錯，解決同音錯別字問題，若無召回，則先進行分詞，將前後相鄰 term 拼接在一起進行拼音和編輯距離的召回。
四：其他的編輯距離演算法
還有很多流行的編輯距離演算法，他們和Levenshtein distance演算法不同是使用了不同種類的方式去變換字串
- Damerau–Levenshtein distance: 可以對字串進行插入、刪除、替換、相鄰兩個字元之間的交換
- longest common subsequence (LCS) distance ：只允許對字串進行插入、刪除、替換
- Hamming distance ： 允許對字串進行替換，只可用於計算兩個相同長度字串的編輯距離
- Jaro distance ：只允許對字串進行交換
編輯距離通常定義為使用一組特定允許的編輯操作來計算的可引數化度量，併為每個操作分配成本（可能是無限的）
五：演算法實現
1：遞迴實現
這種演算法實現比較簡單，就是根據上述介紹的上下界限就可以得出邏輯了
//實現方法
private static int distance(String a, int len_a, String b, int len_b) {
//遞歸回歸點
if (len_a == 0)
return len_b;
if (len_b == 0)
return len_a;
int cos;
if (a.charAt(len_a-1) == b.charAt(len_b-1))
cos = 0;
else
cos = 1;
int re1 = distance(a, len_a - 1, b, len_b) + 1;
int re2 = distance(a, len_a, b, len_b - 1) + 1;
int re3 = distance(a, len_a - 1, b, len_b - 1) + cos;
//返回在a中刪除一個字元、在b中刪除一個字元、ab中均刪除一個字元獲得結果中取最小值
return re1 < re2 ? (re1 < re3 ? re1 : re3) : (re2 < re3 ? re2 : re3);
}
//測試
public static void main(String[] args) {
String a = "kitten";
String b = "sitting";
int re = distnace(a, a.length(), b, b.length());
System.out.println(re);
//輸出：3
}
複製程式碼
這種方式時間複雜度比較高，效率比較低，重複計算了好多字串，下面採用動態規劃演算法實現。
2：動態規劃實現
演算法原理部分就借用https://www.cnblogs.com/sumuncle/p/5632032.html 博主的部分文章吧=.=
演算法基本原理：假設我們可以使用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。
然後我們考慮一般情況，加一點動態規劃的想法，我們要想得到將s[1..i]經過最少次數的增加，刪除，或者替換操作就轉變為t[1..j]，那麼我們就必須在之前可以以最少次數的增加，刪除，或者替換操作，使得現在串s和串t只需要再做一次操作或者不做就可以完成s[1..i]到t[1..j]的轉換。所謂的“之前”分為下面三種情況：
- 1）我們可以在k個操作內將 s[1…i] 轉換為 t[1…j-1]
- 2）我們可以在k個操作裡面將s[1..i-1]轉換為t[1..j]
- 3）我們可以在k個步驟裡面將 s[1…i-1] 轉換為 t [1…j-1]
針對第1種情況，我們只需要在最後將 t[j] 加上s[1..i]就完成了匹配，這樣總共就需要k+1個操作。 針對第2種情況，我們只需要在最後將s[i]移除，然後再做這k個操作，所以總共需要k+1個操作。 針對第3種情況，我們只需要在最後將s[i]替換為 t[j]，使得滿足s[1..i] == t[1..j]，這樣總共也需要k+1個操作。而如果在第3種情況下，s[i]剛好等於t[j]，那我們就可以僅僅使用k個操作就完成這個過程。
最後，為了保證得到的操作次數總是最少的，我們可以從上面三種情況中選擇消耗最少的一種最為將s[1..i]轉換為t[1..j]所需要的最小操作次數。 演算法基本步驟：
- （1）構造 行數為m+1 列數為 n+1 的矩陣 , 用來儲存完成某個轉換需要執行的操作的次數，將串s[1..n] 轉換到 串t[1…m] 所需要執行的操作次數為matrix[n][m]的值；
- （2）初始化matrix第一行為0到n，第一列為0到m。Matrix[0][j]表示第1行第j-1列的值，這個值表示將串s[1…0]轉換為t[1..j]所需要執行的操作的次數，很顯然將一個空串轉換為一個長度為j的串，只需要j次的add操作，所以matrix[0][j]的值應該是j，其他值以此類推。
- （3）檢查每個從1到n的s[i]字元；
- （4）檢查每個從1到m的s[i]字元；
- （5）將串s和串t的每一個字元進行兩兩比較，如果相等，則讓cost為0，如果不等，則讓cost為1（這個cost後面會用到）;
- （6）
- a、如果我們可以在k個操作裡面將s[1..i-1]轉換為t[1..j]，那麼我們就可以將s[i]移除，然後再做這k個操作，所以總共需要k+1個操作。
- b、如果我們可以在k個操作內將 s[1…i] 轉換為 t[1…j-1] ，也就是說d[i,j-1]=k，那麼我們就可以將 t[j] 加上s[1..i]，這樣總共就需要k+1個操作。
- c、如果我們可以在k個步驟裡面將 s[1…i-1] 轉換為 t [1…j-1]，那麼我們就可以將s[i]轉換為 t[j]，使得滿足s[1..i] == t[1..j]，這樣總共也需要k+1個操作。（這裡加上cost，是因為如果s[i]剛好等於t[j]，那麼就不需要再做替換操作，即可滿足，如果不等，則需要再做一次替換操作，那麼就需要k+1次操作）
- 因為我們要取得最小操作的個數，所以我們最後還需要將這三種情況的操作個數進行比較，取最小值作為d[i,j]的值；
- d、然後重複執行3,4,5,6，最後的結果就在d[n,m]中；
private static int distance(String a, String b) {
int[][] dis = new int[a.length()+1][b.length()+1];
for (int i = 1; i <= a.length(); i++)
dis[i][0] = i;
for (int j = 1; j <= b.length(); j++)
dis[0][j] = j;
int cas;
for (int j = 1; j <= b.length(); j++) {
for (int i = 1; i <= a.length(); i++) {
if (a.charAt(i-1) == b.charAt(j-1))
cas = 0;
else
cas = 1;
int re = Math.min(dis[i - 1][j] + 1, dis[i][j - 1] + 1);
dis[i][j] = Math.min(re, dis[i - 1][j - 1] + cas);
}
}
return dis[a.length() - 1][b.length() - 1];
}
public static void main(String[] args) {
String a = "kitten";
String b = "sitting";
int re = distance(a, b);
System.out.println(re);
//輸出：3
}
複製程式碼
如果轉載此博文，請附上本文連結，謝謝合作~ ： juejin.im/user/5c3036…
如果感覺這篇文章對您有所幫助，請點選一下“喜歡”或者“關注”博主，您的喜歡和關注將是我前進的最大動力！