本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

有些時候就是有一些無聊的問題想要解決，才會發展出一些簡單的演算法，然後才會進展出更厲害的演算法，今天要講的就是一個很無聊的問題，但是也可以說是很常見的問題，那就讓我們開始吧，

Edit Distance

今天要講的是字串改變的距離 -- Edit Distance，也就是現在有一個字串Ａ，然後要把它改成字串Ｂ，最少需要做幾次調整；這是一個很經典的Dynamic Programming的問題，而要改變一個字串的動作有三：Change, Insert, Delete，舉個例來說：

• 字串Ａ：Spotify
• 字串Ｂ：Shopify
• Edit Distance：2

按照上面的GIF來說，一個一個去比對，這麼短的字串基本上自己判斷也可以，但是如果是一組很長或很複雜的兩個字串要做比較，那就不知道要自己判斷到何年何月了。

因此Edit Distance的演算法就此誕生，正式進行Edit Distance之前，我們會先將兩個字串轉變成一個2-D Array，並且會多一行一列，這一行一列表示的是從空字串改成當前字串的Edit Distance數值，如下紅框，當從空字串要變成Spotify的話，Edit Distance為7，而綠框也是從空字串變成Shopify的Edit Distance也是7。

在進行比較的時候，基本上會有兩種可能：

1. 兩個值相等 ➜ 其M[x, y] = M[x-1, y-1]
2. 兩個值不相等 ➜ 需要進行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的時候，會去尋找當前的值的來源，找到來源後會有四種情況，透過這四種情況就可以判斷我們到底要怎麼將兩個字串改的一樣：

1. 當前的值 ＝ 來源的值 ➜ 沒有改變
2. 來源的值是斜對角，且來源的值 < 當前的值 ➜ 字符的改變(Change)
3. 來源的值是左邊，且來源的值 < 當前的值 ➜ 字符的刪除(Delete)
4. 來源的值是上面，且來源的值 < 當前的值 ➜ 字符的新增(Insert)

小結

1. Edit Distance就是將兩個字串改成一樣需要動幾次。
2. Edit Distance的過程很長，但可以透過Backtracking來知道怎麼改字串。

預告

明天我們將會再介紹另一種Dynamic Programming的演算法 - Knapsack Problem

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin