为什么从 "abcd" 到 "badc" 的 Levenshtein 距离是 3？

Question

从"abcd"开始，我想去"badc":

• 我删除了 "a" -> "bcd";
• 我在正确的位置插入"a" -> "bacd";
• 我删除了 "c" -> "bad";
• 我在正确的位置插入"c" -> "badc".

这是4次手术。我找不到更短的方法来做到这一点。但是，Levenshtein 距离 returns 我的成本是 3。这是为什么？

感谢您的回复。

Answer 1

您可以在 3 次操作中从 abcd 变为 badc。请记住，您可以进行插入、删除和替换：

1. 删除 a -> bcd.
2. 用 a 替换 c -> bad.
3. 在末尾添加c -> badc.

更一般地说，如果插入和删除操作相邻，则插入 + 删除操作对可以合并为替换。