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)