iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 23
2
Software Development

舌尖上的演算法系列 第 23

Day23 -- Dynamic Programming - Edit Distance

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

前言

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


Edit Distance

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

Edit Distance-1

  • 字串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。

Edit Distance-2

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

  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要填入什麼值,過程如下:

Edit Distance-3

這個過程很冗長,但我希望透過這樣的方式可以讓大家確保自己了解過程是怎麼進展;基本上,每次進行兩個字符的比較時,若字符相同,則填入斜對角的值,若字符不相同,則是比較周圍的三個值,取最小值後再加1;透過這樣一連串的過程,到最後的結果就是這兩個字串的Edit Distance。

而從這個表格上也是可以看出要如何更改,方式是從結果的Cell(最右下)透過Backtracking一路返回到最初的Cell(最左上),過程如下:

Edit Distance-4

在進行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

上一篇
Day22 -- Dynamic Programming - Coin-row Problem
下一篇
Day24 -- Dynamic Programming - Knapsack
系列文
舌尖上的演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言