python - levenshtein 矩阵单元计算

Question

我不明白如何根据这篇文章计算 levenshtein 矩阵中的值。我确实知道我们如何达到 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-1, j) 是上面的组件，lev(i-1, j-1) 是左边和上面的元素。这里，1_(a_i != 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

将鼠标悬停在每个值上方，维基百科文章中该矩阵下方的点，它用外行术语描述了每个值的含义。

例如使用(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)