莱文斯坦问题

Question

在 Levenshtein Distance 算法中，以下这行代码是做什么的？

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

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

- csharpdev

---

你需要提供更多的信息，因为我们熟知的命名算法并没有标准的伪代码实现，而维基百科是最接近的参考。维基百科上的Levenshtein距离条目(http://en.wikipedia.org/wiki/Levenshtein_distance)没有“+ cost”的内容，所以如果不知道具体的实现方式，我们无法帮助你。 - David Thornley

Answer 1

这里有一个公式：

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，则为零，在另一种情况下为一

- Valentin Golev

Answer 2

从文章中：

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

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

- James Kolpack

Answer 3

如果你继续阅读，你会知道：我们可以给插入、删除和替换不同的惩罚成本。我们还可以给出依赖于插入、删除或替换哪些字符的惩罚成本。 例如，如果你认为删除一个字母比替换一个字母更有影响力，那么在公式的删除部分中，你可以包含一些大于0的成本值。

- mykhal