编辑距离算法解释

根据维基百科，计算两个字符串 a 和 b 之间的编辑距离的递归公式的定义如下：

我不明白为什么我们不考虑删除的情况a[j]，或者我们插入b[i]。另外，如果我错了，请纠正我，插入的情况和删除的情况不一样吗？我的意思是，我们可以在第二个字符串中插入相同的字符，而不是从一个字符串中删除一个字符，反之亦然。那么为什么不将插入/删除操作合并为一个操作，其成本等于min{cost_insert, cost_delete}?

未完成此操作，因为不允许您编辑这两个字符串。编辑距离的定义（来自维基百科）是：

将 a 转换为 b 的最小权重系列编辑操作。

因此，您专门寻找要在字符串上执行的操作序列（的权重）a将其转换为字符串b.

此外，编辑距离不一定是对称的。如果插入和删除的成本相同，则距离是对称的：d(a,b) = d(b,a)

考虑维基百科的例子，但成本不同：

• 插入成本：w_ins = 1
• 删除成本：w_del = 2
• 替换成本：w_sub = 1

的距离为kitten and sitting仍然是3，

kitten -> sitten  (substitution k->s, cost 1)
sitten -> sittin  (substitution e->i, cost 1)
sittin -> sitting (insertion of g, cost 1)
=> d(kitten, sitting) = 3

但距离sitting and kitten is not:

sitting -> kitting  (substitution s->k, cost 1)
kitting -> kitteng  (substitution i->e, cost 1)
kitteng -> kitten (deletion of g, cost 2)
=> d(kitten, sitting) = 4

你看到了d(kitten, sitting) != d(kitten, sitting).

另一方面，如果您确实使用对称成本，就像编辑距离（具有单位成本的编​​辑距离）一样，您可以假设：d(a,b) = d(b,a)成立。那么，即使考虑相反的情况，你也不会赢得任何东西。您丢失的是哪个字符在哪个字符串中被替换的信息，这使得之后提取操作序列变得更加困难。

The 瓦格纳-费舍尔算法 https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm您在问题中显示的内容可以通过以最小成本回溯路径来从 DP 矩阵中提取此内容。考虑这两个编辑矩阵to and foo单位成本：

  t o       f o o
f 1 2     t 1 2 3
o 2 1     o 2 1 2
o 3 2

请注意，如果将矩阵转置为d(to, foo)你得到的矩阵d(foo, to)。请注意，通过这种方式，第一个矩阵中的插入将成为第二个矩阵中的删除，反之亦然。所以这就是你所寻找的对称性再次出现的地方。

我希望这有帮助 ：）