编辑距离的网格动态规划

格点 $(i,j)$ 的含义是：源串前 $i$ 个字符已经消耗，目标串前 $j$ 个字符已经生成。向下走只消耗源字符，是删除；向右走只生成目标字符，是插入；沿对角走同时消耗和生成，是配对或替换。所有边都增加 $i+j$，所以网格是一个有向无环图公理库有向无环图Directed acyclic graph · DAG不含有向环的有向图。，可以按拓扑次序求最短路。

为什么只看最后一步就够了？一条对齐路径到达 $(i,j)$，最后必然来自这三个前驱之一。若到那个前驱的部分并非最优，换成更便宜的部分不会影响最后一步，整条路径就还能变好。因此每个格子都由已经正确的较小前缀推出。归纳开始于空串边界，结束于右下角。

“脚本”最好用消耗与生成的方式保存，而不是把每条命令都写成对当前字符串的绝对下标。前面的删除会移动后面的下标；对齐操作流则只维护两个游标。配对或替换读一个源字符并写一个目标字符，删除只读，插入只写，含义不会随执行进度漂移。

同样最优的两种解释 ​

取 $A=\mathtt{\text{CACTUS}}$、$B=\mathtt{\text{CATCUS}}$。完整表如下，行、列标题中的空字符表示长度为零的前缀。

在 $D[3,3]$，前缀 CAC 对 CAT 的最后字符不同。对角候选为 $D[2,2]+1=1$，删除、插入候选都为 $2$，所以此格取 $1$。到 $D[4,4]$ 时，三种候选都为 $2$，出现真正的解释歧义。

按本页的回溯顺序，保留前两个字符，把第三位 C 换成 T、第四位 T 换成 C，再保留 US，得到费用 $2$ 的脚本。另一个同费脚本是删除第三位 C，得到 CATUS，再在 T 后插入 C。两条路径告诉我们：编辑距离认证最少操作数，不会自动判断现实中作者究竟做了哪一种修改。

为什么不是 $1$？两串长度相同，一次插入或删除无法保持长度；一次替换只能改变一个位置，而第三、第四位都不同。这给出下界 $2$，与脚本上界相遇。

先固定操作，再谈“距离” ​

若加入“相邻转置费用 $1$”，此例就会变成 $1$，需要另一套递推或状态；不能仍用三向公式然后把结果称作含转置的距离。若只允许等长逐位替换，得到的是Hamming 距离公理库Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。；它无法解释一次插入引起的后续错位。精确字符串匹配公理库字符串匹配String matching · Exact pattern matching在文本中定位模式串全部出现位置的问题。又是在文本里找原样出现的位置，目标不是把两个整串改成相同。

带权对齐可以把三种边的 $1$ 换成相应费用，空串边界改成累计插删费用。此时计算的是规定网格模型下的最小对齐费用。若还希望它等于允许任意连续改写的费用，要排除“先把一个字符换成第三种字符，再换成目标字符更便宜”等捷径，或先对字符操作费用做最短路闭包；对称性、正定性也不能由非负费用自动得到。

填表需要 $O((m+1)(n+1))$ 时间、$O((m+1)(n+1))$ 存储；常写的 $O(mn)$ 默认两串都非空。回溯至多走 $m+n$ 步。只求距离时，每格只依赖当前行左邻与上一行，交换两串让短串作为列维后，可把工作数组压到 $O(min(m,n)+1)$。但覆盖旧行也会丢掉回溯所需的前驱，不能直接宣称同样空间里还保有整份脚本。

Hirschberg 分解公理库Hirschberg 线性空间序列比对Hirschberg algorithm · Linear-space sequence alignment用前向与反向滚动行认证最优路径的中线穿越点，释放分数数组后递归重建完整对齐。用前向、反向滚动行找出最优路径的中间穿越点，再递归恢复脚本。若应用规定只有插入和删除，并且差异很少，Myers 算法公理库Myers 最短插删脚本算法Myers O(ND) algorithm · Shortest edit script按插删次数扩展编辑图的最远对角前沿，在差异较小时避免填满网格，并记录蛇形匹配段重建脚本。则按修改数扩展前沿，避免填满网格。前者主要节省重建存储，后者利用小差异参数；两者解决的问题条件不同。

比较两个实现时，先检查脚本实际生成了目标串，再检查费用最优。相同距离而脚本不同常常只是平局规则不同，不能仅据此判错。包含空串、重复字符、全相等、全不同以及插删优于替换的例子，才能覆盖边界和回溯分支。