Levenshtein距離，單獨跟蹤插入/刪除/替換

Question

Levenshtein distance上的維基百科文章在其possible modifications部分中指出，「[可以分別存儲插入，刪除和替換的數量」。

這是如何完成的？我在article中創建了基於矩陣的動態編程解決方案的實現，其中矩陣的每個單元格都有一個用於刪除/插入/替換的單獨值，但是對於我而言，我似乎無法解決邏輯。

直觀地看，如果我發現需要在同一步驟中進行刪除和插入操作，那麼這些應該成爲替代。

爲了使我想要的完全清楚，下面是源字符串「mat」和目標字符串「catch」的示例矩陣。我期望這需要一次替換（即將「m」改爲「c」）和兩次插入（即附加「ch」）。每個單元格都是「刪除/插入/替換」。

 
      C  A  T  C  H 
    +-----+-----+-----+-----+-----+-----+ 
    |D/I/S|0/1/0|0/2/0|0/3/0|0/4/0|0/5/0| 
    +-----+-----+-----+-----+-----+-----+ 
M |1/0/0|0/0/1|0/1/1|0/2/1|0/3/1|0/4/1| 
    +-----+-----+-----+-----+-----+-----+ 
A |2/0/0|1/0/1|0/0/1|0/1/1|0/2/1|0/3/1| 
    +-----+-----+-----+-----+-----+-----+ 
T |3/0/0|2/0/1|1/0/1|0/0/1|0/1/1|0/2/1| 
    +-----+-----+-----+-----+-----+-----+ 

有沒有人計算出這個算法？

Answer 1

對於目標小區X，我們需要找到最小的：

this + substitution | this + deletion 
--------------------+---------------- 
this + insertion |  x 

從左上角的是，當我們還沒有處理，任一值的是，所以我們必須在同一時間處理兩個，因此它是一個替代品。

從左邊是當我們還沒有處理目標值，所以它是插入。

從上面我們還沒有處理源值，所以它是刪除。

爲了單獨地存儲這些值，則需要一個三維陣列：

array[targetSize+1][inputSize+1][3] 

然後，對於每個前3個細胞，添加1所取代，缺失或插入（如上所述），然後根據替換，刪除和插入的次數計算總成本，並找出3個成本中的最小值。然後將最小值的單元格中的值複製到當前單元格中（添加了1個操作）。

所以，對於：

0/1/0|0/2/0 
-----+----- 
0/0/1| x 

假設的1對每個操作的成本。

我們計算：
0/1/0 + 1取代= 0/1/1，成本= 2
0/0/1 + 1插入= 0/1/1，成本= 2
0/2/0 + 1缺失= 1/2/0，成本= 3

然後我們挑成本2和將0/1/1放入新單元中。

我希望有幫助。