在典型的动态编辑距离算法中,计算单元格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|
+-+-+
(考虑第二行)。
最佳答案
引用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 .
关于algorithm - Levenshtein 距离算法中的冗余,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24743832/