Mark Chang's Blog

Machine Learning, Deep Learning and Python

Minimum Edit Distance

Minimum Edit Distance

Minimum Edit Distance （最小編輯距離），是用來計算兩個字串的相似程度。

可應用於拼字校正、或是計算兩個DNA序列的相似程度。

例如，假設有三個DNA序列：

1. AGCCT

2. AACCT

3. ATCT

直覺上，會認為，DNA序列 2. 和 1. 的相似程度比 3. 和 1. 的相似程度還要高。

但為何是 2. 和 1. 較相似？相似程度又是多少？

若要把兩序列的相似程度量化成數值，就要計算「最小編輯距離」，最小編輯距離越小，就表示兩序列越相似。

Defining of Minimum Edit Distance

我們採用 Levenshtein 的最小編輯距離的定義，這是一種最簡單的定義方式。依此定義，若一個字串，編輯成另外一個字串，可以進行下面三種動作。

其中，定義 a. 和 b. 的 cost 為 ， c. 的 cost 為 （因為「替換」相當於「刪除」後再「插入」）。

例如， 1. 和 2. 的最小編輯距離，可以這樣計算，如下：

上圖中，將兩字串對齊，發現要把 1. 編輯成 2. ，需要對第二個字 G 進行替換（ s ），把 G 替換成 A ，而替換的 cost 為 ，故 1. 和 2. 的最小編輯距離為 。

再來，把 1. 編輯成 3. 的最小編輯距離，如下：

上圖中， 表示該處沒字元， 而要把 1. 編輯成 3. ，需要把第二個字 G 刪除（ d ），並替換（ s ）第三個字 C ，這兩個動作的 cost 分別為 和 ，故最小編輯距離為

Computing Minimum Edit Distance

接著來看，要用什麼演算法，來計算最小編輯距離？可以用 Dynamic Programming 的方式來計算。

所謂的 Dynamic Programming 簡而言之，就是把一個問題，一層一層分解下去，分成許多子問題，再算出這些子問題，用這些子問題的解答，求出原本問題的答案。

首先，定義字串長度為 的兩字串，最小編輯距離為

在分解過程中，需要計算長度為 的兩個子字串，最小編輯距離為 ，其中 。

接著，定義起始狀態，就是把兩個給定的字串，各自編輯成空字串的距離，分別為 和 。

由於，把字串長度為 的字串，編輯成空字串長度為 ，即 , 同理，

演算法如下：從起始狀態開始，由 及 ，依序去計算長度為 字串的最小編輯距離。

其中， 為第一個字串中第 個字元， 為第二個字串中第 個字元。

用以上演算法，舉個例子來計算，若兩字串分別為：

  1. AGCCT

  2. ATCT

輸入字串長度分別為 和 ，故 。

演算法開始的第一步，先建立以下表格，右下方空格部份即為 的值。

接著，填入初始狀態的值，即

再來，計算 的值，用演算法的公式，如下：

其中，可從表格中得知 ，又因為 ，故 的最小編輯距離為 。將算出來的 結果，填入表格，如下：

用此公式，依序算出表格中其他空格的值。

全部算完以後，表格中最右下方的數字，即為 AGCCT 和 ATCT 兩序列的最小編輯距離，其值為3。

Implementation

再來是實作的部份，建立一個python程式檔 minEditDist.py ，並將以下程式複製貼上。

minEditDist.py
1
2
3
4
5
6
7
8
9
10
11

def minEditDist(sm,sn):
  m,n = len(sm),len(sn)
  D = map(lambda y: map(lambda x,y : y if x==0 else x if y==0 else 0,
    range(n+1),[y]*(n+1)), range(m+1))
  for i in range(1,m+1):
    for j in range(1,n+1):
      D[i][j] = min( D[i-1][j]+1, D[i][j-1]+1,
        D[i-1][j-1] + apply(lambda: 0 if sm[i-1] == sn[j-1] else 2))
  for i in range(0,m+1):
    print D[i]
  return D[m][n]

其中， sm 和 sn 分別為輸入的字串，而 D[i][j] 為 最小編輯距離 。

到 python interactive mode 載入模組

1

>>> from minEditDist import minEditDist

接著，用此程式計算 AGCCT 和 ATCT 的最小編輯距離，方法如下：

1
2
3
4
5
6
7
8

>>> minEditDist("AGCCT","ATCT")
[0, 1, 2, 3, 4]
[1, 0, 1, 2, 3]
[2, 1, 2, 3, 4]
[3, 2, 3, 2, 3]
[4, 3, 4, 3, 4]
[5, 4, 3, 4, 3]
3

程式印出 表格中的數值，並回傳最後結果，結果為 。

Reference

本文參考至coursera線上課程

Dan Jurafsky & Christopher Manning. Natural Language Processing

https://www.coursera.org/course/nlp

Comments