介紹

Levenshtein distance(Edit Distance)，可以稱為編輯距離，編輯距離可以用來比較兩個字串並求出相似度，所以可以用來做到模糊搜尋。

Edit Distance是這樣來比較兩個字串的，假設我有兩個字串A, B。

1
2
A = 'AFEDC'
B = 'ABDECG'

編輯距離可以想成我要把A變成B需要花幾步驟來完成，圍繞在以下3種動作:

Insert插入，插入一個字元
Delete刪除，刪除一個字元
Replace替換，替換一個字元

作法是這樣的，開始逐一比較字元並修改，得出A變成B需要的步驟數。

箭頭代表字元指針

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
移動指針
    ↓
A = AFEDC
B = ABDECG
    ↑
A[0] == B[0]，此時的cost = 0

移動指針
     ↓
A = AFEDC
B = ABDECG
     ↑
A[1] != B[1]，我們可以把F換成B，此時的cost + 1 = 1

移動指針
      ↓
A = AFEDC
B = ABDECG
      ↑
A[2] != B[2]，我們可以把E換成D，此時的cost + 1 = 2

省略部分...

移動指針
        ↓
A = AFEDC
B = ABDECG
        ↑
A[4] == B[4]，不用修改，此時cost = 3

移動指針
         ↓
A = AFEDC
B = ABDECG
         ↑
A[5] == B[5]，A缺少一個字元，所以我們插入一個G，此時cost + 1 = 4


把A變成B的cost是4，所以EditDistance(A, B) = 4

如果當字串長度不一樣的時候就會出現需要刪除或是插入的動作，如果都是B > A就只會出現插入不會有刪除，如果B < A反之。

實作

知道原理之後就來產Code吧!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int EditDistance(const char *s, int len_s, const char *t, int len_t){ 
  int cost;

  /* 終止條件，當兩字串都為空 */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* 檢查字元是否一樣，不一樣的話cost = 1 */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return 最小編輯次數(刪除, 插入, 替換)*/
  return std::min(EditDistance(s, len_s - 1, t, len_t    ) + 1,
                 EditDistance(s, len_s    , t, len_t - 1) + 1,
                 EditDistance(s, len_s - 1, t, len_t - 1) + cost);
}

這裡有個比較特別的小地方，EditDistance(s, len_s + 1, t, len_t) 代表的是插入一個字元，但是這行其實不對，因為他不會終止遞迴，在這邊len_s + 1是改變後的字串(未來)，可是程式判斷的時候是以送進來的字串為主(過去)。

在這裡可以透過一個方法把len_s + 1 改成 len_t - 1，在這裡可以花一點時間思考為什麼。

其實原因是插入代表我把一個原字串沒有的字元加進字串(len_s + 1)，相當於我跟相比較的字串少了一個不相同的地方(len_t - 1)，所以其實這兩者是表達一樣的東西。

這個演算法還可以透過Dynamic Programming來完成，改天再補上Code吧~

Algorithm:: (Edit Distance)

單調列隊 Monotone-Queue/Stack 的學習筆記。

介紹

實作