string - 给定 a 和 b 以及 b 和 c 的成对编辑距离，我们能找到 a 和 c 的成对编辑距离吗？

Question

如果我们有三个字符串 a、b、c，并且我们知道（或已经计算）edit_distance(a,b) 和 edit_distance(b,c)，我们是否可以在不实际比较 a 和 c 的情况下有效地计算 edit_distance(a,c)。

*edit_distance(a,b) = 将 a 转换为 b 所需的字符插入、删除和替换次数。*

Answer 1

一般来说，没有。例如，取

• 一个 = 帽
• b = 猫
• c = 车

这里，edit_distance(a, b) = 1 和 edit_distance(b, c) = 1。此外，edit_distance(a, c) = 1。

然而，我们也可以有

• 一个 = 帽
• b = 猫
• c = 大鼠

这里，edit_distance(a, b) = 1 and edit_distance(b, c) = 1，但是edit_distance(a, c) = 2。因此，没有办法纯粹使用a和b的编辑距离和b和c 计算 a 和 c 的编辑距离。

但是，我们确实知道 edit_distance(a, c) ≤ edit_distance(a, b) + edit_distance(b, c)，因为您始终可以按顺序应用转换将 a 转换为 c。更一般地说，编辑距离形成了一个离散的距离度量，它构成了BK-tree 数据结构的基础。

希望这可以帮助！