文章出處：極客時間《數(shù)據(jù)結(jié)構(gòu)和算法之美》-作者：王爭。該系列文章是本人的學(xué)習(xí)筆記。

萊文斯坦距離

在搜索引擎中會有搜索詞糾錯的功能。這個功能背后的原理是編輯距離。

編輯距離

編輯距離是量化兩個詞之間的相似度。 編輯距離是指將一個字符串變?yōu)榱硗庖粋€字符串，需要的最少編輯操作次數(shù)。編輯操作包含新增一個字符、修改一個字符、刪除一個字符。編輯次數(shù)越少，編輯距離越小，兩個字符串相似度越大。如果兩個字符串完全相同，編輯距離為0。

根據(jù)所包含的編輯操作種類的不同，編輯距離有多種不同的計算方式，比較著名的有萊文斯坦距離（Levenshtein distance）和最長公共子串長度（Longest common substring length）。其中，萊文斯坦距離允許增加、刪除、替換字符這三個編輯操作，最長公共子串長度只允許增加、刪除字符這兩個編輯操作。

萊文斯坦距離

用萊文斯坦距離替換兩個字符串的過程。

回溯解法

萊文斯坦距離將一個字符串替換為另外一個字符串，計算最少的編輯次數(shù)。需要考慮字符串中每一位上的字符。如果字符相同怎么處理，字符不同怎么處理。這是一個多階段決策最優(yōu)解模型。

貪心、回溯、動態(tài)規(guī)劃都可以解決這類問題。我們先用回溯法解決，看是不是有重復(fù)子問題。如果沒有，回溯就是最優(yōu)解；如果有重復(fù)子問題，那就需要用動態(tài)規(guī)劃優(yōu)化。

回溯是一個遞歸處理問題的過程。假設(shè)我們要把a(bǔ)字符串替換為b字符串。如果a[i]和b[j]匹配，則i++,j++。如果不匹配，可以采取的措施有：
1 刪除a[i]，然后遞歸考察a[i+1]和b[j]；
2 在a[i]前面插入字符b[j]，然后遞歸考察a[i]和b[j+1]；
3 將a[i]替換為b[j]，然后遞歸考察a[i+1]和b[j+1]。

翻譯成代碼：

public class LevenshteinDistance {private char[] a = "mitcmu".toCharArray();private char[] b = "mtacnu".toCharArray();private int n = a.length;private int m = b.length;private int minEdist = Integer.MAX_VALUE;private void lwstBT(int i,int j,int edist){if(i==n || j==m){if(j<m) {edist += m-j;}if(i<n){edist += n-i;}minEdist = Math.min(edist,minEdist);return;}if(a[i]==b[j]){lwstBT(i+1,j+1,edist);}else{lwstBT(i+1,j,edist+1);//刪除a[i]lwstBT(i,j+1,edist+1);//在a[i]前面插入b[j]lwstBT(i+1,j+1,edist+1);//修改a[i]=b[j]}}public void lwstBT(){lwstBT(0,0,0);}public static void main(String[] args){LevenshteinDistance l = new LevenshteinDistance();l.lwstBT();System.out.println(l.minEdist);} }

我們依據(jù)回溯代碼來看下遞歸樹。

遞歸樹的每一個節(jié)點(diǎn)表示一種狀態(tài)，用(i,j,edist)表示，i表示指針在a字符串的位置，j表示指針在b字符串的位置，(i,j)都表示將要處理的字符位置，edist表示到達(dá)(i,j)時已經(jīng)執(zhí)行的編輯次數(shù)。遞歸樹中的一條邊對應(yīng)一種處理方式。

從樹中能夠看出(i,j)相同的節(jié)點(diǎn)很多。例如(2,2)、（2,3）。同一個狀態(tài)的節(jié)點(diǎn)只要保留一個編輯距離最小的就可以。因為我們的目標(biāo)就是找編輯距離最小的。這樣也可以避免遞歸樹節(jié)點(diǎn)指數(shù)級增長。

我們接著看下狀態(tài)轉(zhuǎn)移方式。狀態(tài)(i,j)可能從(i-1,j-1)、(i-1,j)、(i,j-1)這三個狀態(tài)的任一狀態(tài)轉(zhuǎn)變過來。

狀態(tài)表法

接下來我們按照這種方式，計算狀態(tài)轉(zhuǎn)移表。我們畫出一個二維狀態(tài)表，表中的行、列表示字符串在a、b中的位置，表中的數(shù)值表示從（0，0）到這個位置需要執(zhí)行的最短編輯次數(shù)。需要說明的是這個編輯次數(shù)是包含本次操作的。與遞歸樹的狀態(tài)中數(shù)值的含義略微不同。

這里說一下填表的過程。
(0,0):m->m 不需要編輯。
(0,1)m->mt 需要 一次編輯。
…
這張表比較難填寫，我沒明白怎么填寫的。如果從（0，0）開始算后面還能算明白，想往回遞推就搞不懂了。
比較簡單的理解就是想決定(2,2)的值，從(1,1). (1,2). (2,1)三個值中選擇一個最小值，再加1。就對了。加1是因為a!=t。（圖下面有補(bǔ)充2021-1-1）

這里補(bǔ)充一下之前不能理解的地方。例如想要到達(dá)dp[2][2]這個狀態(tài)，就是說想要字符串"mit"變?yōu)?#34;mta"。
我們已經(jīng)知道dp[1][1]=1，也就是說從"mi"最少有1次操作，可以變?yōu)?#34;mt"。這個時候，我們在"mi"變成的"mt"后面添加一個t，在"mt"字符串后面添加一個a，我們將t替換為a(mtc->mta)，就可以實(shí)現(xiàn)將字符串"mit"變?yōu)?#34;mta"。也就是說dp[1][1]+1。這里需要說明的是，如果同時追加的都是a字符的話，那就不用編輯操作。（mta->mta）不需要操作，那這時候的編輯次數(shù)就是dp[i-1][j-1]。
我們已經(jīng)知道dp[1][2]=2，也就是說從"mi"變?yōu)?#34;mta"需要2次操作。這時候在mi后面追加字符t，那么只需要把字符t刪除(mtat->mta)，就能實(shí)現(xiàn)從"mit"變?yōu)?#34;mta"。也就是說dp[1][2]+1。
我們已經(jīng)知道dp[2][1]=1，也就是說從"mit"變?yōu)?#34;mt"需要1次操作。那么只需要在后面添加一個a字符(mt->mta)，就能實(shí)現(xiàn)從"mit"變?yōu)?#34;mta"。也就是說dp[2][1]+1。

狀態(tài)轉(zhuǎn)移方程

根據(jù)狀態(tài)轉(zhuǎn)移方式很容易得到狀態(tài)轉(zhuǎn)移方程。
如果a[i]=b[j]

min_edist(i.j) = min(min_edist(i-1,j)+1,min_edist(i,j-1)+1,min_edist(i-1,j-1));

如果a[i]!=b[j]

min_edist(i.j) = min( min_edist(i-1,j)+1,min_edist(i,j-1)+1,min_edist(i-1,j-1)+1 );

DP代碼：

public int lwstDP(char[] a, int n, char[] b, int m) {int[][] minDist = new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(i==0 && j==0){minDist[0][0] = a[0]==b[0]?0:1;}else{minDist[i][j] = Integer.MAX_VALUE;if(i>0 && j>0){minDist[i][j] = Math.min(minDist[i][j],minDist[i-1][j-1]+(a[i]==b[j]?0:1));}if(i==0 && j>0){minDist[i][j] = Math.min(minDist[i][j],minDist[i][j-1]+1);}if(i>0 && j==0){minDist[i][j] = Math.min(minDist[i][j],minDist[i-1][j]+1);}}}}return minDist[n-1][m-1];}

總結(jié)

以上是生活随笔為你收集整理的动态规划——莱文斯坦距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。