levenshtein矩阵单元格计算

Question

我不明白 levenshtein 矩阵中的值是如何计算的 According to this article。我知道我们是如何得出 3 的编辑距离的。有人可以通俗易懂地解释一下我们是如何得出每个单元格中的每个值的吗？

Answer 1

将鼠标悬停在 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' 进行比较。 (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)

Answer 2

您好，我刚刚看了您分享的维基百科文章的 link：

"Definition" 中描述了构建矩阵的方式。现在我将把它翻译成它的意思以及你需要做些什么来自己构建矩阵：

为了确保没有遗漏任何基本信息：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) 的意思是，如果这个 space 上的字母不等于 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 矩阵。

levenshtein矩阵单元格计算

levenshtein matrix cell calculation

python

matrix

levenshtein-distance

hamming-distance

edit-distance