更多博文請關(guān)注：https://blog.bigcoder.cn

一. 什么是Levenshtein Distance

Levenshtein Distance，一般稱為編輯距離（Edit Distance，Levenshtein Distance只是編輯距離的其中一種）或者萊文斯坦距離，算法概念是俄羅斯科學(xué)家弗拉基米爾·萊文斯坦（Levenshtein · Vladimir I）在1965年提出。此算法的概念很簡單：Levenshtein Distance指兩個字串之間，由一個轉(zhuǎn)換成另一個所需的最少編輯操作次數(shù)，允許的編輯操作包括：

• 將其中一個字符替換成另一個字符（Substitutions）。
• 插入一個字符（Insertions）。
• 刪除一個字符（Deletions）。

二. 解題思路

假如，我們定義個方法，入?yún)閮蓚€字符串，返回兩個字符串的編輯距離：

public static int editDistance(String a,String b)

假設(shè)我們有“kitte”、“Sitti”兩個字符串，我們暫且將這兩個字符串成為”A“和”B“，我們的編輯操作大致可分為三種類型：

• 選擇一：將B字符串最后一個字符替換，使得兩個字符串相等

因為這個操作使得最后一個字符相等，那么我們只需要繼續(xù)計算minDistance(A[i-1],B[j-1])的編輯距離即可（A[i-1]，其中i代表A字符串的長度，A[i-1]表示A字符串（0~length-1）的子串）

• 選擇二：將B字符串增加一個字符，使得兩個字符串最后一個字符相等：

這樣我們只需要繼續(xù)計算minDisnace(A[i-1]，B[j])的編輯距離即可

• 選擇三：將B字符串最后一個字符刪除

實際上，刪除B字符串的最后一個字符與在A字符串添加一個字符是等價的：

因為他們的編輯過程都為1，最后都需要繼續(xù)計算minDistance(A[i],B[j-1])的編輯距離。

需要注意的是，大家不要站在上帝視角認(rèn)為此種情況下選擇第一種方式，將最后一個字符替換即是最優(yōu)解。因為小范圍的最佳解，并不一定是大范圍的最佳解，我們只有枚舉出所有可能的情況才能得出最小的編輯距離。

綜上所述，我們可以得出編輯距離算法的狀態(tài)轉(zhuǎn)移方程：

三. 動態(tài)規(guī)劃

了解動態(tài)規(guī)劃的同學(xué)應(yīng)該都知道DP算法，需要借助DP數(shù)組去完成，但是DP數(shù)組的初始化會困擾很多同學(xué)，這里我可以給大家提供一個技巧，對于DP數(shù)組需要初始化哪些數(shù)據(jù)，我們可以觀察狀態(tài)轉(zhuǎn)移方程依賴與哪些狀態(tài)，以上面的例子來說：

lev(i,j)需要依賴于lev(i-1,j)、lev(i,j-1)、lev(i-1,j-1)三種狀態(tài)：

這樣我們就需要把這個二維數(shù)組藍(lán)色部分初始化好后，才能根據(jù)初始化好的數(shù)組，將整個二維數(shù)組填滿，當(dāng)填滿的那一刻，我們的最優(yōu)解也就達(dá)到了。

至于計算的路徑，我們從初始化好的狀態(tài)以及依賴態(tài)的位置，我們可以得出兩種計算路徑：

這里就是我對動態(tài)規(guī)劃DP數(shù)組的初始化以及計算路徑的明確技巧。

可以使用動態(tài)規(guī)劃的方法去測量DP的值，步驟大致如下：

• 初始化一個DP矩陣(M,N)，M和N分別是兩個輸入字符串的長度。
• 矩陣可以從左上角到右下角進(jìn)行填充，每個水平或垂直跳轉(zhuǎn)分別對應(yīng)于一個插入或一個刪除。
• 通過定義每個操作的成本為1，如果兩個字符串不匹配，則對角跳轉(zhuǎn)的代價為1，否則為0，簡單來說就是：
  • 如果[i][j]位置的兩個字符串相等，則從[i][j]位置左加1，上加1，左上加0，然后從這三個數(shù)中取出最小的值填充到[i][j]。
  • 如果[i][j]位置的兩個字符串不相等，則從[i][j]位置左、左上、上三個位置的值中取最小值，這個最小值加1（或者說這三個值都加1然后取最小值），然后填充到[i][j]。
• 按照上面規(guī)則LD矩陣(M,N)填充完畢后，最終矩陣右下角的數(shù)字就是兩個字符串的LD值。

這里不打算證明上面動態(tài)規(guī)劃的結(jié)論（也就是默認(rèn)這個動態(tài)規(guī)劃的結(jié)果是正確的），直接舉兩個例子說明這個問題：

• 例子一（兩個等長字符串）：son和sun。
• 例子二（兩個非等長字符串）：doge和dog。

例子一：

初始化LD矩陣(3,3)：

		s	o	n
	0	1	2	3
s	1
u	2
n	3

計算[0][0]的位置的值，因為's' = 's'，所以[0][0]的值 = min(1+1, 1+1, 0+0) = 0。

		s	o	n
	0	1	2	3
s	1	0
u	2
n	3

按照這個規(guī)則計算其他位置的值，填充完畢后的LD矩陣`如下：

		s	o	n
	0	1	2	3
s	1	0	1	2
u	2	1	1	2
n	3	2	2	1

那么son和sun的LD值為1。

例子二：

初始化LD矩陣(4,3)：

		d	o	g
	0	1	2	3
d	1
o	2
g	3
e	4

接著填充矩陣：

		d	o	g
	0	1	2	3
d	1	0	1	2
o	2	1	0	1
g	3	2	1	0
e	4	3	2	1

那么doge和dog的LD值為1。

四. 代碼實現(xiàn)

public static int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        throw new RuntimeException("參數(shù)不能為空");
    }
    int[][] dp = new int[word1.length() + 1][word2.length() + 1];
    //初始化DP數(shù)組
    for (int i = 0; i <= word1.length(); i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i <= word2.length(); i++) {
        dp[0][i] = i;
    }
    int cost;
    for (int i = 1; i <= word1.length(); i++) {
        for (int j = 1; j <= word2.length(); j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                cost = 0;
            } else {
                cost = 1;
            }
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost);
        }
    }
    return dp[word1.length()][word2.length()];
}

private static int min(int x, int y, int z) {
    return Math.min(x, Math.min(y, z));
}

五. 編輯距離的應(yīng)用

• 搜索建議：當(dāng)我們Google搜索Jave時，Google會智能的提醒我們是否在搜索Java
• DNA分析
• 抄襲偵測

…

本文參考至：

• 編輯距離 - 編輯距離 - 力扣（LeetCode） (leetcode-cn.com)
• Levenshtein Distance（編輯距離）算法與使用場景 - throwable - 博客園 (cnblogs.com)