經動態規劃:編輯距離
摘要:def dp(i, j) -> int # 返回 s1[0..i] 和 s2[0..j] 的最小編輯距離。if s1[i] == s2[j]: return dp(i - 1, j - 1) # 啥都不做 # 解釋: # 本來就相等,不需要任何操作 # s1[0..i] 和 s2[0..j] 的最小編輯距離等於 # s1[0..i-1] 和 s2[0..j-1] 的最小編輯距離 # 也就是說 dp(i, j) 等於 dp(i-1, j-1)。
預計閱讀時間:8 分鐘
前幾天在網上看到一份鵝場的面試題,算法部分大半是動態規劃,最後一題就是寫一個計算編輯距離的函數,今天就專門寫一篇文章來探討一下這個經典問題。
我個人很喜歡編輯距離這個問題,因爲它看起來十分困難,解法卻出奇得簡單漂亮,而且它是少有的比較實用的算法(是的,我承認很多算法問題都不太實用)。下面先來看下題目:
爲什麼說這個問題難呢,因爲顯而易見,它就是難,讓人手足無措,望而生畏。
爲什麼說它實用呢,因爲前幾天我就在日常生活中用到了這個算法。之前有一篇公衆號文章由於疏忽,寫錯位了一段內容,我決定修改這部分內容讓邏輯通順。但是公衆號文章最多隻能修改 20 個字,且只支持增、刪、替換操作(跟編輯距離問題一模一樣),於是我就用算法求出了一個最優方案,只用了 16 步就完成了修改。
再比如高大上一點的應用,DNA 序列是由 A,G,C,T 組成的序列,可以類比成字符串。編輯距離可以衡量兩個 DNA 序列的相似度,編輯距離越小,說明這兩段 DNA 越相似,說不定這倆 DNA 的主人是遠古近親啥的。
下面言歸正傳,詳細講解一下編輯距離該怎麼算,相信本文會讓你有收穫。
一、思路
編輯距離問題就是給我們兩個字符串 s1
和 s2
,只能用三種操作,讓我們把 s1
變成 s2
,求最少的操作數。需要明確的是,不管是把 s1
變成 s2
還是反過來,結果都是一樣的,所以後文就以 s1
變成 s2
舉例。
前文最長公共子序列說過, 解決兩個字符串的動態規劃問題,一般都是用兩個指針 i,j
分別指向兩個字符串的最後,然後一步步往前走,縮小問題的規模 。
設兩個字符串分別爲 "rad" 和 "apple",爲了把 s1
變成 s2
,算法會這樣進行:
根據上面的 GIF,可以發現操作不只有三個,其實還有第四個操作,就是什麼都不要做(skip)。比如這個情況:
因爲這兩個字符本來就相同,爲了使編輯距離最小,顯然不應該對它們有任何操作,直接往前移動 i,j
即可。
還有一個很容易處理的情況,就是 j
走完 s2
時,如果 i
還沒走完 s1
,那麼只能用刪除操作把 s1
縮短爲 s2
。比如這個情況:
類似的,如果 i
走完 s1
時 j
還沒走完了 s2
,那就只能用插入操作把 s2
剩下的字符全部插入 s1
。 等會會看到,這兩種情況就是算法的 base case 。
下面詳解一下如何將這個思路轉化成代碼,坐穩,準備發車了。
二、代碼詳解
先梳理一下之前的思路:
base case 是 i
走完 s1
或 j
走完 s2
,可以直接返回另一個字符串剩下的長度。
對於每對兒字符 s1[i]
和 s2[j]
,可以有四種操作:
if s1[i] == s2[j]: 啥都別做(skip) i, j 同時向前移動 else: 三選一: 插入(insert) 刪除(delete) 替換(replace)
有這個框架,問題就已經解決了。讀者也許會問,這個「三選一」到底該怎麼選擇呢?很簡單,全試一遍,哪個操作最後得到的編輯距離最小,就選誰。這裏需要遞歸技巧,理解需要點技巧,先看下代碼:
下面來詳細解釋一下這段遞歸代碼,base case 應該不用解釋了,主要解釋一下遞歸部分。
都說遞歸代碼的可解釋性很好,這是有道理的,只要理解函數的定義,就能很清楚地理解算法的邏輯。我們這裏 dp(i, j) 函數的定義是這樣的:
def dp(i, j) -> int # 返回 s1[0..i] 和 s2[0..j] 的最小編輯距離
記住這個定義之後,先來看這段代碼:
if s1[i] == s2[j]: return dp(i - 1, j - 1) # 啥都不做 # 解釋: # 本來就相等,不需要任何操作 # s1[0..i] 和 s2[0..j] 的最小編輯距離等於 # s1[0..i-1] 和 s2[0..j-1] 的最小編輯距離 # 也就是說 dp(i, j) 等於 dp(i-1, j-1)
如果 s1[i]!=s2[j]
,就要對三個操作遞歸了,稍微需要點思考:
dp(i, j - 1) + 1, # 插入 # 解釋: # 我直接在 s1[i] 插入一個和 s2[j] 一樣的字符 # 那麼 s2[j] 就被匹配了,前移 j,繼續跟 i 對比 # 別忘了操作數加一
dp(i - 1, j) + 1, # 刪除 # 解釋: # 我直接把 s[i] 這個字符刪掉 # 前移 i,繼續跟 j 對比 # 操作數加一
dp(i - 1, j - 1) + 1 # 替換 # 解釋: # 我直接把 s1[i] 替換成 s2[j],這樣它倆就匹配了 # 同時前移 i,j 繼續對比 # 操作數加一
現在,你應該完全理解這段短小精悍的代碼了。還有點小問題就是,這個解法是暴力解法,存在重疊子問題,需要用動態規劃技巧來優化。
怎麼能一眼看出存在重疊子問題呢?前文 動態規劃之正則表達式 有提過,這裏再簡單提一下,需要抽象出本文算法的遞歸框架:
def dp(i, j): dp(i - 1, j - 1) #1 dp(i, j - 1) #2 dp(i - 1, j) #3
對於子問題 dp(i-1,j-1)
,如何通過原問題 dp(i,j)
得到呢?有不止一條路徑,比如 dp(i,j)->#1
和 dp(i,j)->#2->#3
。一旦發現一條重複路徑,就說明存在巨量重複路徑,也就是重疊子問題。
三、動態規劃優化
對於重疊子問題呢,前文動態規劃詳解 介紹過,優化方法無非是備忘錄或者 DP table。
備忘錄很好加,原來的代碼稍加修改即可:
def minDistance(s1, s2) -> int: memo = dict() # 備忘錄 def dp(i, j): if (i, j) in memo: return memo[(i, j)] ... if s1[i] == s2[j]: memo[(i, j)] = ... else: memo[(i, j)] = ... return memo[(i, j)] return dp(len(s1) - 1, len(s2) - 1)
主要說下 DP table 的解法:
首先明確 dp 數組的含義,dp 數組是一個二維數組,長這樣:
dp[i][j]
的含義和之前的 dp 函數類似:
def dp(i, j) -> int # 返回 s1[0..i] 和 s2[0..j] 的最小編輯距離 dp[i-1][j-1] # 存儲 s1[0..i] 和 s2[0..j] 的最小編輯距離
有了之前遞歸解法的鋪墊,應該很容易理解。 dp 函數的 base case 是 i,j
等於 -1,而數組索引至少是 0,所以 dp 數組會偏移一位, dp[..][0]
和 dp[0][..]
對應 base case。 。
既然 dp 數組和遞歸 dp 函數含義一樣,也就可以直接套用之前的思路寫代碼, 唯一不同的是,DP table 是自底向上求解,遞歸解法是自頂向下求解 :
三、擴展延伸
一般來說,處理兩個字符串的動態規劃問題,都是按本文的思路處理,建立 DP table。爲什麼呢,因爲易於找出狀態轉移的關係,比如編輯距離的 DP table:
還有一個細節,既然每個 dp[i][j]
只和它附近的三個狀態有關,空間複雜度是可以壓縮成 O ( m i n ( M , N ) ) 的(M,N 是兩個字符串的長度)。不難,但是可解釋性大大降低,讀者可以自己嘗試優化一下。
你可能還會問, 這裏只求出了最小的編輯距離,那具體的操作是什麼 ?之前舉的修改公衆號文章的例子,只有一個最小編輯距離肯定不夠,還得知道具體怎麼修改纔行。
這個其實很簡單,代碼稍加修改,給 dp 數組增加額外的信息即可:
// int[][] dp; Node[][] dp; class Node { int val; int choice; // 0 代表啥都不做 // 1 代表插入 // 2 代表刪除 // 3 代表替換 }
val
屬性就是之前的 dp 數組的數值, choice
屬性代表操作。在做最優選擇時,順便把操作記錄下來,然後就從結果反推具體操作。
我們的最終結果不是 dp[m][n]
嗎,這裏的 val
存着最小編輯距離, choice
存着最後一個操作,比如說是插入操作,那麼就可以左移一格:
重複此過程,可以一步步回到起點 dp[0][0]
,形成一條路徑,按這條路徑上的操作編輯對應索引的字符,就是最佳方案:
這就是編輯距離算法的全部內容,希望本文對你有幫助。