Myers 位向量编辑距离

数值很大，相邻差却只有三种 ​

单位编辑操作保证相邻两行、相邻两列的值相差至多一。多一个模式字符，至多多付一次删除；反过来删掉这个字符也至多改变一次费用。文本多一个字符时同理。自由前缀模式取所有后缀的最小值：非空最优后缀去掉最后字符仍是上一边界的候选；若最优后缀为空，其费用为 $i$，而上一边界也可选空后缀。两个方向的界仍成立。

所以垂直、水平差分都属于 $\{-1,0,1\}$。从第零行的已知值出发累加垂直差分，可以重建整列。扫描不必每步实际累加它们，因为末行分数只需加上新一列最下面的水平差分。这也是必须在移位前检查第 $m-1$ 位的原因。

从一个格子推到整列 ​

取一个格子的左上角值为 $a$，左下角为 $a+v$，右上角为 $a+h$，相等标记为 $e\in \{0,1\}$。令 $t=min\{-e,v,h\}$，右下角按网格递推等于 $a+1+t$。因此输出差分为

输入只有 $3\times 3\times 2=18$ 种。把正、负差分分别编码成两个布尔量，逐项代入上式，可以得到：令 $x_v=e\vee [v=-1]$，则

交换横竖角色，就得到 $P_h,M_h$ 的对应公式。参考程序把全部18种输入逐一与数值递推核对。整列先由旧垂直差分求出水平差分，再把水平差分向下一行移动，转成新垂直差分。第零行的水平差分恰是 $\beta$，所以移入 ${\hat{P}}_h$ 最低位的是 $\beta$，而不是一条不问边界的固定常数。

一次加法为何能解决行间依赖 ​

难点在于第 $i$ 位所需的 $X_h$ 还依赖前一行的负水平差分。用从零开始的位下标，记旧 $P_v$ 的位为 $p_i$、相等位为 $e_i$，则需要的传播规则是

这恰好是一条二进制进位链。把 $P_v$ 与 $E\mathrm{\&}{P}_v$ 相加：第二个加数的位 $e_i{p}_i$ 不会在 $p_i=0$ 处产生进位，故加法输出进位就是上式的 $c_{i+1}$。该位和为 $p_i\oplus (e_i{p}_i)\oplus c_i$；再异或 $p_i$ 并或上 $e_i$，当 $e_i=1$ 时得到一，当 $e_i=0$ 时得到 $c_i$，结果正是 $x_i$。

于是算术加法同时完成了这条有限状态传播。这里需要进位沿连续正差分传播；不能套用“并行字段之间总要隔离进位”的直觉把它截断。最高位之外的进位可以丢弃，因为它不再影响任何有效行。

这三个层次连成归纳证明：初始差分正确；逐格布尔式等价于网格递推；进位链一次算出所有需要的横向条件；移位注入正确边界后得到下一列，末行分数也同步更新。因而每一步返回的都是所声明模式的精确费用。

先看一个确实跨字的加法 ​

取 $P=\mathtt{\text{abbb}}$、$w=3$，初始 $P_v=[111,001]$、$M_v=[000,000]$、$S=4$。读 a 时 $E=[001,000]$，字数组按低字在前排列。

低字加法是 $001+111=1000$：保存低三位 000，向高字传一。高字于是算 $000+001+1=010$。异或旧 $P_v$ 并或上 $E$，清掉第四行以外的填充位后得到 $X_h=[111,001]$。末行的负水平差分为一，分数从 $4$ 降到 $3$，对应保留 a、删除三个 b。

若在每个字都把输入进位重置为零，高字会算成 $000+001=001$，其 $X_h$ 有效位变为零，错误地返回 $4$。这不是“大例子才有”的整数溢出问题，而是在第四个模式位置就能复现的依赖丢失。

同一文本，两种边界 ​

令 $P=\mathtt{\text{ababa}}$，流入文本 zzababa，仍用 $w=3$。两个字的有效掩码是 [111,011]；末行对应高字的第二位，不是三位字的最高位。

global 必须为前面的两个 z 付费，最终距离为二；infix 可以从边界二开始，最终后缀 ababa 完全匹配。若允许至多一次编辑，infix 的合格端点是 $6,7$，global 没有合格端点。

在 infix 的第 $3$ 步，初始正差分仍全为一，$E=[101,010]$。低字算 $101+111=1100$，把进位传到高字，最终 $X_h=[111,011]$；$P_h=[000,000]$、$M_h=[111,011]$。分数减一后，把 $M_h$ 左移得到 [110,011]，把 $P_h$ 左移并注入零仍是 [000,000]。新 $P_v=[110,011],M_v=0$，重建列为

最终 infix 列为 $[0,0,1,0,1,0]$，两个差分向量是 $P_v=[010,001]$、$M_v=[100,010]$。global 最终列则为 $[7,6,5,4,3,2]$，全部有效垂直差分为负。下载结果逐列保存完整核对值。

端点不是起点，费用不是脚本 ​

模式 ab 对文本 acb，在末边界 $3$ 的 infix 分数为一。后缀 acb 可以插入 c 得到，后缀 cb 可以替换首字母得到；两个不同起点都达到最小值。一个分数不能决定选哪一条解释。本页也没有保存历史列的前驱，不能把这些输出称作已重建的编辑脚本。

$m=0$ 时 global 返回 $j$，infix 返回零，直接按边界处理，不读取不存在的最高位。任意 $m$ 下，初始 $j=0$ 分数都是 $m$。阈值 $k\ge m$ 时 infix 每个边界都合格，因为空后缀总是候选；因此“报告一个合格端点”也不保证找到了非空片段。

边界的一位之差可以用 $P=\mathtt{\text{a}},T=\mathtt{\text{ba}}$ 验证：global 最终为一，infix 为零。如果把两种模式都固定注入一，后者就悄悄变成前者。

时间按实际字数计，输出另算 ​

设字母表大小为 $\sigma$，$q=\lceil m/w\rceil$。参考程序先建立 $\sigma$ 行的掩码表，再逐位置置位，编译时间为 $O(m+\sigma (q+1)+1)$。每个非空模式的扫描步骤包含常数趟长度 $q$ 的布尔、加法和移位循环，因此是 $O(q)$ 个字操作。扫描全文并保存每个新边界的分数，统一耗时

掩码表、当前差分、临时数组与单步诊断记录共占 $O(\sigma (q+1)+q+1)$ 个字；feed 返回的 $n$ 项分数另占 $O(n)$。step 不保存旧文本或全部历史。column() 是额外的 $O(m+1)$ 时间与空间诊断操作，不能在每字节都调用它后仍声称扫描仅用 $O(nq)$。

实现把向量拆成宽度1至63的字，加法中间数至多多一位；小宽度用于测试跨字传递。位置和分数不超过63位非负整数，模式最多4096字节。参数、字节、块类型和位置上限均在改动状态前检查。理论模型要求地址与计数器可放入机器字，不能把调试用的一位逻辑块宽当成整台机器的地址宽度。

它利用的不是小编辑数 ​

本算法的扫描成本不乘阈值 $k$，也不依赖实际最小费用很小：无论最终分数是多少，每个符号都推进整列差分。它与Myers 1986 最短插删前沿理路Myers 最短插删脚本算法Myers O(ND) algorithm · Shortest edit script按插删次数扩展编辑图的最远对角前沿，在差异较小时避免填满网格，并记录蛇形匹配段重建脚本。同属一个作者的工作，却是不同算法。1986方案按编辑次数扩展最远对角位置，允许插入和删除；本页1999方案打包相邻差分，包含费用一的替换。例如 a 到 b 在本页费用一，在仅插删模型中费用二。

改变费用或加入转置，需要重新推导差分范围与格子逻辑。删除费用二时，初始垂直差分已经是二，两个仅编码 $-1,0,1$ 的向量无法原样表示。把阈值检查换一个数不能修复这种状态不充分。带状算法、期望时间剪枝和脚本重建也不包含在这份全列接口里。

参考程序另用普通标量网格逐列比较全部数值，覆盖两种边界、空模式、跨字长度与分块输入；结果文件保留上述轨迹和被击穿的快捷写法。终点任务要求从位向量重建一列，再用独立网格验证分数，而不只接受一个最终整数。