给定字符串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所需的字符插入、删除和替换次数。*

- Cerberuz

Answer 1

一般情况下是不行的。例如，考虑以下内容：

• a = CAP
• b = CAT
• c = CAR

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

但是，我们也可以有以下内容：

• a = CAP
• b = CAT
• c = RAT

在这里，edit_distance(a, b) = 1，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树数据结构的基础。

希望这可以帮到您！

- templatetypedef

---

我们也知道 edit_distance(a, c) ≥ abs(edit_distance(a, b) - edit_distance(b, c))；换句话说，一个转换中的每个插入/删除/替换可能会抵消另一个转换中的单个插入/删除/替换，但不能超过这个范围。 - Kyle Strand

@KyleStrand 实际上，通过一些代数运算可以从三角不等式推导出d(a,c)>=|d(a,b)-d(b,c)|。d(a,b) <= d(a,c) + d(b,c) 意味着d(a,c) >= d(a,b) - d(b,c)； 以及 d(b,c) <= d(a,c) + d(a,b) 意味着d(a,c) >= d(b,c) - d(a,b)。以上两个陈述意味着d(a,c) >= |d(a,b) - d(b,c)|。 - Narut Sereewattanawoot

另一个很好的例子是 a = CAT，b = CAP，c = CAT 的情况。仅从距离度量无法确定 d(a,c) == 0。 - Jim Mischel