给定a和b以及b和c的成对编辑距离,我们可以找到a和c的成对编辑距离吗？

Question

如果我们有三个字符串a,b,c并且我们知道(或已经计算过)edit_distance(a,b)和edit_distance(b,c),我们是否可以有效地计算edit_distance(a,c)而无需实际比较a和c.

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

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),因为你总是可以应用变换顺序把一个成C.更一般地,编辑距离形成离散距离度量,其形成BK树数据结构的基础.

希望这可以帮助!