algorithm - Levenshtein 距离算法中的冗余

Question

在典型的动态编辑距离算法中，计算单元格d[i][j]的值，其中i和j分别是行号和列号，我们取d[i-1][j-1]+0/1中的最小值，d[i-1][j]+ 1 和 d[i][j-1]+1。但是，在我看来，d[i-1][j-1]+0/1 和 d[i-1][j]+1 中的最小值> 总是 d[i-1][j-1]+0/1，在这种情况下包括 d[i-1][j]+1 在计算中似乎是多余的。 Levenshtein 中的 d[i-1][j-1]+0/1 > d[i-1][j]+1 是否曾经是这种情况距离算法，如果不是，省略这个比较不是更有效吗？

编辑:对于研究不足的问题深表歉意；该算法的任何标准运行都会显示 d[i-1][j-1]+0/1 > d[i-1][j]+1 的实例:

    A
 +-+-+
 |0|1|
 +-+-+
A|1|0|
 +-+-+

(考虑第二行)。

Answer 1

引用Wikipedia Article ，最后一种情况下的最小值必须在“删除”情况下取。

假设我们要计算 abc 和 ab 之间的 Levenshtein 距离(从现在开始固定并从符号中省略)。

迭代评估产生以下中间结果。

lev(0,0) = 0 (1st case applies)
lev(0,1) = 1 (1st case applies)
lev(0,2) = 2 (1st case applies)

lev(1,0) = 1 (1st case applies)
lev(1,1) = min(2,2,0) (2nd case, minimum taken in last term) = 0
lev(1,2) = min(1,2,1) (2nd case, minumum taken in last term) = 1

lev(2,0) = 2 (1st case applies)
lev(2,1) = min(3,1,2) (2nd case, minimum taken in second term) = 1 (*)
lev(2,2) = min(2,2,0) (2nd case, minimum taken in the last term) = 0

lev(3,0) = 3 (1st case applies)
lev(3,1) = min(4,2,2) (2nd case, minimum taken in the second and third term) = 2
lev(3,2) = min(3,1,2) (2nd case, minimum taken in the second term) = 1 (*)

标有 (*) 的行是出现第二种情况的情况，但最小值未在上学期被采用。可以找到还显示动态规划表的在线计算器 here .