0

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

编辑：对不起，研究不足的问题；d[i-1][j-1]+0/1算法的任何标准运行都会显示>的实例d[i-1][j]+1：

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

（考虑第二行）。

4

1 回答 1

1

参考维基百科的文章，在“删除”的情况下必须取最后一种情况下的最小值。

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

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

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 (*)

标有 (*) 的行是出现第二种情况的情况，但在最后一项中没有取最小值。可以在此处找到还显示动态规划表的在线计算器。

于 2014-07-14T19:09:17.197 回答