levenshtein矩陣單元格計算

Question

我不明白如何計算levenshtein矩陣中的值According to this article。我知道我們是如何到達編輯距離爲3的。有人可以用平信徒的語言解釋我們如何在每個單元中得到每個值？

Answer 1

您好我剛剛看了一下維基百科文章的您共享的鏈接：

的矩陣中的「定義」中描述構建方式。 現在我將把它翻譯成它意味着什麼，你需要做什麼來自己構建矩陣：

只是爲了確保沒有缺少基本信息：i表示行號，j表示列數。

所以讓我們從矩陣的第一個定義行開始吧： 它說矩陣是max（i，j），如果min（i，j）= 0 條件將只滿足第0行和第0列。 （然後min（0，j）是0並且min（i，0）是0）。因此，對於第0行和第0列，輸入max（i，j）的值，它對應於第0列的行號和第0行的列號。 到目前爲止好：

k i t t e n 
    0 1 2 3 4 5 6 
s 1 
i 2 
t 3 
t 4 
i 5 
n 6 
g 7 

所有其他值都建爲最小這三個值中的一個：

lev(i-1, j) + 1 
lev(i, j-1) + 1 
lev(i-1, j-1) + 1_(a_i != b_i) 

凡列弗對應於已經存在的萊文斯坦矩陣元素。 012vlev（i，j-1）只是我們想要確定的左邊的矩陣組件。 lev（i-1，j）是上面的分量，lev（i-1，j-1）是左邊和上面的元素。這裏，1_（a_i！= b_i）表示如果這個空間上的字母不等於1，則加0，否則爲0.

如果我們直接跳到矩陣元素（1,1） （S，K）：我們確定的3個組成部分：

lev(i-1, j) + 1 = 2  [1 + 1 = 2] 
lev(i, j-1) + 1 = 2  [1 + 1 = 2] 
lev(i-1, j-1) + 1 = 1 [0 + 1 = 1] + 1 because k is clearly not s 

現在，我們取最小值這三個值中，我們發現了萊文斯坦矩陣的下一個條目。

對每個單元行或列進行此評估，結果是完整的Levenshtein矩陣。

Answer 2

將鼠標懸停與點的每個值以上之下在wikipedia article該矩陣，它通俗地說了每個值的裝置描述。

例如使用(x,y)符號

• 元件(0,0)比較None到None。 (0,0) = 0因爲它們相等
• 元件(0,1)比較'k'到None。 (0,1) = 1因爲：
  1. insert 'k'轉化None到'k'所以+1
• 元件(3,2)比較'kit'到'si'。因爲== None這樣+0的``
  1. None(3,2) = 2 - Lev = 0看到元素(0,0)
  2. swap 's','k'所以+1 - Lev = 1看到元素(1,1)
  3. 'i' == 'i'所以+0 - Lev = 1看到元素(2,2)
  4. insert 't'所以+1 - Lev = 2見元素(3,2)