Edit Distance与Alignment Distance等价性反向证明及资源咨询

首先明确前提：我们讨论的是标准Levenshtein编辑距离（允许插入、删除、替换三种操作，单步操作代价为1），对齐距离的gap代价和错配代价均为1。
证明步骤如下：

1. 设两个字符串$x$、$y$的最短编辑操作序列长度为$k = d_{edit}(x,y)$，则存在转换序列 $x = s_0 \to s_1 \to s_2 \to ... \to s_k = y$，其中任意相邻的$s_{i-1}$与$s_i$之间仅相差一次单步编辑操作。
2. 先证任意仅差一次单步编辑操作的字符串对$a,b$，满足$d_{align}(a,b) = 1$：
   • 若为替换操作：两字符串长度相同，仅单个位置字符不同，对齐时该位置记为错配（代价1），其余位置匹配（代价0），总对齐代价为1，没有更优方案。
   • 若为删除/插入操作：两字符串长度差1，对齐时多出来的单个字符与空位配对（gap代价1），其余位置匹配，总对齐代价为1，没有更优方案。
3. 利用对齐距离的三角不等式（对任意三个字符串$a,b,c$，有$d_{align}(a,c) \le d_{align}(a,b) + d_{align}(b,c)$），对上述转换序列迭代应用三角不等式可得：
   $$d_{align}(x,y) = d_{align}(s_0, s_k) \le \sum_{i=1}^k d_{align}(s_{i-1}, s_i) = k = d_{edit}(x,y)$$
   综上反向不等式得证，结合你已经掌握的$d_{edit} \le d_{align}$，可推出两种距离完全等价。

• 《算法导论》：动态规划章节的字符串编辑距离部分，包含两种距离等价性的完整推导，以及编辑距离满足度量空间四大公理（非负性、同一性、对称性、三角不等式）的完整证明。
• 《生物序列分析：蛋白质和核酸的概率论模型》：从生物序列对齐的应用场景出发，系统论证了对齐距离的度量性质，以及和编辑距离的等价关系，推导过程严谨且覆盖多种代价权重的变体情况。
• 《字符串算法》：专门设置字符串距离度量章节，除了基础等价性证明外，还包含多种扩展编辑操作下的距离性质推导，适合需要深入研究的场景。

内容的提问来源于stack exchange，提问作者datoad