莱文斯坦问题

Question

在Levenshtein Distance算法，这是什么做的线？：

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

虽然它得到了最低所有这些值的，为什么成本加入到结束，为什么我们还要+ 1在每个数组索引器的末尾（前两个参数）？

Answer 1

如果你进一步研究，你会知道：我们可以给插入，删除和替换赋予不同的惩罚成本。我们还可以根据哪些字符被插入，删除或替换来给予罚金。

例如，包括在公式的删除部分有些> 0成本值，如果你想比的一封信缺失使得除字母替代

Answer 2

从文章较大的差异：

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

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

Answer 3

这里是一个式：

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，一个在其他情况下