Table of Contents
前言
有些時候就是有一些無聊的問題想要解決,才會發展出一些簡單的演算法,然後才會進展出更厲害的演算法,今天要講的就是一個很無聊的問題,但是也可以說是很常見的問題,那就讓我們開始吧,
Edit Distance
今天要講的是字串改變的距離 – Edit Distance,也就是現在有一個字串A,然後要把它改成字串B,最少需要做幾次調整;這是一個很經典的Dynamic Programming的問題,而要改變一個字串的動作有三:Change, Insert, Delete
,舉個例來說:
- 字串A:Spotify
- 字串B:Shopify
- Edit Distance:2
按照上面的GIF來說,一個一個去比對,這麼短的字串基本上自己判斷也可以,但是如果是一組很長或很複雜的兩個字串要做比較,那就不知道要自己判斷到何年何月了。
因此Edit Distance的演算法就此誕生,正式進行Edit Distance之前,我們會先將兩個字串轉變成一個2-D Array,並且會多一行一列,這一行一列表示的是從空字串改成當前字串的Edit Distance數值
,如下紅框,當從空字串要變成Spotify的話,Edit Distance為7,而綠框也是從空字串變成Shopify的Edit Distance也是7。
在進行比較的時候,基本上會有兩種可能:
- 兩個值相等 ➜ 其
M[x, y] = M[x-1, y-1]
- 兩個值不相等 ➜ 需要進行Edit ➜
M[x, y] = 1 + min(M[x-1, y], M[x, y-1], M[x-1, y-1])
從三個值當中尋找最小值,是因為最小值表示的是改變的最少次數,然後再加1是因為要把值改變成目標值會需要多加一次Edit。
因此在執行Edit Distance的時候就是依照上面這兩種可能去決定當前Cell要填入什麼值,過程如下:
這個過程很冗長,但我希望透過這樣的方式可以讓大家確保自己了解過程是怎麼進展;基本上,每次進行兩個字符的比較時,若字符相同,則填入斜對角
的值,若字符不相同,則是比較周圍的三個值,取最小值後再加1;透過這樣一連串的過程,到最後的結果就是這兩個字串的Edit Distance。
而從這個表格上也是可以看出要如何更改,方式是從結果的Cell(最右下)透過Backtracking
一路返回到最初的Cell(最左上),過程如下:
在進行Backtracking的時候,會去尋找當前的值的來源
,找到來源後會有四種情況,透過這四種情況就可以判斷我們到底要怎麼將兩個字串改的一樣:
- 當前的值 = 來源的值 ➜ 沒有改變
- 來源的值是斜對角,且來源的值 < 當前的值 ➜ 字符的改變(Change)
- 來源的值是左邊,且來源的值 < 當前的值 ➜ 字符的刪除(Delete)
- 來源的值是上面,且來源的值 < 當前的值 ➜ 字符的新增(Insert)
小結
- Edit Distance就是將兩個字串改成一樣需要動幾次。
- Edit Distance的過程很長,但可以透過Backtracking來知道怎麼改字串。
預告
明天我們將會再介紹另一種Dynamic Programming的演算法 - Knapsack Problem