Myers 最短插删脚本算法

完整编辑网格公理库编辑距离的网格动态规划Levenshtein distance dynamic programming · Wagner–Fischer algorithm把插入、删除与替换写成前缀网格的三类边，求出最小改写费用并重建逐条可执行的脚本。按前缀大小推进。这里改用“已经付了多少次插删”作层号：如果两个长版本只差几处，算法先在主对角线附近探索，很早就能结束。

最远前沿的核心不是“更靠右看起来更好”，而是编辑图的单调性。同一 $d,k$ 上若有较短和较长的两条路径，当两条路径都允许追加同一种插删时，较长路径的候选起点仍不会落在较短候选后面。若较短候选的匹配段能越过较长候选所在点，这条连续对角段也经过那个点；较长候选从那里继续匹配，至少到达同样远处。若越不过，较长候选已不差。因此保留最远点不会损失这些合法转移所能达到的最远位置。

这是按 $d$ 推进的动态规划公理库动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。，但边界剪枝需要补充论证。维护的性质是：每个保留状态都由一条合法的 $d$ 次编辑路径得到，且舍弃较短代表及越界转移不会丢掉首次到达终点所需的最优路径。内部状态由上述最远延伸论证控制；触及边界的情况如下。

假设同一上一层对角线上，较短路径到 $(x,y)$，保留路径到 $(x+t,y+t)$，$t\ge 1$。若后者已达 $x+t=m$，便不能再删除；较短路径却还可能删除一次。设 $r=n-(y+t)\ge 0$。保留路径直接插入余下 $r$ 个字符即可结束；较短路径若坚持先删，之后还剩 $t-1$ 个源字符、$t+r$ 个目标字符，光长度差就要求至少 $r+1$ 次额外编辑，加上这次删除，共至少 $r+2$ 次。它比保留路径的边界完成方案至少多花两次，不可能属于最短终点路径。已到目标串边界、不能再插入的情况完全对称。

因此越界候选可以剪去，即使这样不再保留每个恰 $d$ 编辑可达的对角线。每个更小费用的最优终点可能性仍被保留，首次找到的合法终点路径便给出最短费用。

退役规则也有完整费用证书。若第 $d_0$ 层在对角线 $k$ 到达 $(x,n)$，继续删除余下源字符就能以总费用 $d_0+m-x$ 结束。以后第 $d>d_0$ 层的同对角线状态只能是 $(x-t,n-t)$，$t\ge 0$；其剩余两串的长度差仍是 $m-x$，任何完成方式的总费用至少为 $d+m-x$，严格更大。因此这种后来状态不可能出现在最短脚本中；$x=m$ 的情形对称。

直接完成的路径也不会被退役标记无故阻断：从 $(x,n)$ 再删除一次会到下一条对角线上的 $(x+1,n)$。若那条对角线此前已经退役，其端点就是同一个边界点，却由更少编辑到达，接上余下删除会给出更便宜的完整脚本。沿剩余字符归纳，一条最优的边界完成路径不可能遭到这种阻断。保留当前触边端点及其下一层出边，因而足以继续构造最优终点和回溯脚本。

三次修改怎样从前沿中出现 ​

令 $A=\mathtt{\text{ABCDA}}$，$B=\mathtt{\text{BACDEA}}$。第一字符不同，故 $V_0[0]=0$。第一层有两个方向：

• 插入 B 后到 $(0,1)$，随后 A 匹配到 $(1,2)$，所以 $V_1[-1]=1$。
• 删除源串首个 A 后到 $(1,0)$，随后 B 匹配到 $(2,1)$，所以 $V_1[1]=2$。

完整保留的前沿为

第二层的 $k=0$ 特别重要。两个候选都从 $x=2$ 开始，本页选删除分支；随后 C,D 连续匹配，到达 $(4,4)$。第三层从这里插入 E，再匹配最后一个 A，到达 $(5,6)$，其对角线为 $-1$。

回溯得到操作流：插入 B，匹配 A，删除原来的 B，匹配 C,D，插入 E，匹配 A。实际执行是

最少确为三次：长度差为一，所以插删总数必须是奇数；若只做一次，只能插入，而 ABCDA 并不是 BACDEA 的子序列。因此 $D\ge 3$，构造达到下界。

最远端点不等于完整路径 ​

为了输出脚本，本页实现为每层每个保留状态另记：来自哪条上一层对角线、用了插入还是删除、snake 的起点和终点。到终点后沿这些前驱逆行，再倒序输出匹配段与收费边。只保存最后一层 $V$ 无法知道前面选择过哪些分支。

删除候选要求上一状态尚未消耗完源串，插入候选要求尚未生成完目标串。一个能区分“最优终点充分性”与“全部恰层可达性”的例子是 $A=\mathtt{\text{ab}},B=\mathtt{\text{baaa}}$：第 $1$ 层的 $k=1$ 保留 $(2,1)$；第 $2$ 层再向 $k=2$ 删除会越界，因此该项不保存。但直接删除源串两个字符确实可达 $(2,0)$。这个较短端点被省略并不妨碍最优解：它还需插入四个字符，而保留的 $(2,1)$ 只需再插入三个，总费用少两次。

空串对非空串会依次沿边界插入或删除；两串全相等则在 $d=0$ 的第一次 snake 扫描中结束。原论文也可在扩展网格上保留越界前沿、规定网格外没有匹配边；本页采用显式合法性检查，因而不沿用扩展网格的全部端点表述。

对 A 与 B 两个单字符，插删模型距离为 $2$，允许替换的 Levenshtein 距离为 $1$。这不是算法精度的区别，而是允许操作不同。Myers 的这一算法也不同于把状态打包进机器字的位并行加速公理库四俄罗斯方法与字级并行Four Russians method · bit parallelism · broadword programming把状态切成可查表微块，或在一个机器字内并行处理多位，从而省去对数因子。，它利用的是最小编辑数 $D$。

每层至多考虑 $d+1$ 条对角线，候选检查和退役标记共花 $O((D+1{)}^2)$ 时间。成功的匹配比较则按对角线计费：在某线退役前，设第 $d$ 层端点为内部点 $(x,y)$，删除和插入分别可到相邻线上的 $(x+1,y)$、$(x,y+1)$。下一层未退役的相邻线会保留至少这么远的端点；再转回原线时，合法候选的 $x$ 至少为 $x+1$，严格超过旧端点。

若两条返回路线都不可用，两条相邻线必已退役：未退役者本可由上述合法出边生成，只有触边才能阻止返回。因此原线此后也不会重新出现。由此，同一条线的各段匹配扫描互不重叠，总长为 $O(N)$；全部只涉及 $O(D+1)$ 条线。结合 $D\le N$，总时间为 $O((N+1)(D+1))$，包括 $D=0$ 的相等串扫描以及两串均空的常数工作。

这里不能省掉退役条件。若只剪去越界出边，对 abbaaa 与 bba，$k=1$ 在第 $1$ 层已从 $(1,0)$ 匹配到 $(4,3)$，第 $3$ 层却会从 $(3,2)$ 再扫描同一尾段；更晚的起点也可能倒退。退役规则正是让上述不重复扫描的论证适用于本页的边界处理方式。

仅求距离时，可以使用 $O(D+1)$ 个动态前沿状态，或预分配 $O(N)$ 数组。退役标记另占 $O(D+1)$ 空间。本页为回溯保存第 $0$ 至第 $D$ 层，状态总数是 $1+2+\cdots +(D+1)=O((D+1{)}^2)$，另有 $O(N)$ 输出空间。原论文还有用中间 snake 分治的线性空间重建变体；不能把那个变体的存储界直接套给保存全部历史的实现。

当 $D$ 很小，$ND$ 明显小于 $mn$，这解释了算法适合文本版本差异；当两串几乎没有共同部分，$D$ 接近 $N$，优势可能消失。算法也可以设置费用上限 $K$：完整算完第 $K$ 层还不可达，就严格得到“插删距离大于 $K$”，而不是一个未经证明的近似脚本。