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

所有其他值均为以下三个值中的最小值：

^{pr2}$

其中lev对应于已经存在的levenshtein矩阵元素。 lev（i，j-1）就是我们要确定的，左边的矩阵分量。lev（i-1，j）是上面的组件，lev（i-1，j-1）是左边和上面的元素。给你，我！=b_i）表示，如果此空格上的字母不等于1，则加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矩阵的下一个条目。在

对每个元素行或列进行此计算，结果就是完整的Levenshtein矩阵。在

Answer 2

将鼠标悬停在每个值的上方，在wikipedia article中的矩阵下面有点，它用通俗的术语描述每个值的含义。在

例如，使用(x,y)符号

• 元素(0,0)将None与{}进行比较。(0,0) = 0因为它们是相等的
• 元素(0,1)比较'k'和{}。(0,1) = 1因为：
  1. insert 'k'将None转换为'k'所以+1
• 元素(3,2)比较'kit'和{}。(3,2) = 2因为``
  1. None==None所以+0-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)