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

其中 lev 对应于已经存在的 levenshtein 矩阵元素。lev(i, j-1) 只是我们要确定的 lev(i, j-1) 左侧的矩阵分量。 lev(i-1, j) 是上面的分量，lev(i-1, j-1) 是左边和上面的元素。这里1_(a_i != b_i)的意思是，如果这个空格上的字母不等于1就加1，否则加0。

如果我们直接跳到对应于字母 (s, k) 的矩阵元素 (1, 1):我们确定 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 矩阵。