about 4 years ago

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.costc.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
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] 

其中, smsn 分別為輸入的字串,而 D[i][j] 為 最小編輯距離
python interactive mode 載入模組

>>> from minEditDist import minEditDist

接著,用此程式計算 AGCCTATCT 的最小編輯距離,方法如下:

>>> 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

← R -- Data Splitting 自然語言處理 -- Brown Clustering →
 
comments powered by Disqus