3

在Levenshtein 距离算法中，这条线做了什么？：

    d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

尽管它获得了所有这些值中的最小值，但为什么将成本添加到末尾，为什么我们在每个数组索引器（前两个参数）的末尾都有 + 1？

4

3 回答 3

2

这是一个公式：

替代文字

m(a,b) = if a==b then 0 else 1

带有“min”的行是递归公式本身，其他是递归导致的非递归情况。

您的行正在使用“缓存”数组中的结果。试着看看它：

 d(i, j) = Minimum (d(i-1, j)+1, d(i, j-1)+1, d(i-1, j-1) + cost);

cost是, 如果是 ,则m(a,b)为零a==b

于 2010-01-05T17:37:42.210 回答
1

来自文章：

                (
                  d[i-1, j] + 1,  // deletion
                  d[i, j-1] + 1,  // insertion
                  d[i-1, j-1] + 1 // substitution
                )

该算法的目的是找到将一个字符串（或列表）转换为另一个字符串的最便宜的路径。在您引用的行中考虑了任何给定操作的“成本”。在您的情况下，“删除”被认为是 1 的成本，“插入”也是 1，而“替换”的成本是可变的。

于 2010-01-05T17:37:15.863 回答
0

如果您进一步阅读，您会知道：我们可以对插入、删除和替换给予不同的惩罚成本。我们还可以根据插入、删除或替换的字符给出惩罚成本。

例如，如果您认为删除字母比替换字母产生更大的差异，您会在公式的删除部分中包含一些 >0 的成本值

于 2010-01-05T17:36:14.100 回答