unified engine · 2×2 象限

序列对齐 DP：一张表跑出四种算法

LCS（最长公共子序列）、编辑距离（Levenshtein）、Needleman–Wunsch（全局序列比对）看着是三道题，底层却是同一个二维 DP。它们都在一张「行为序列 $A$ 、列为序列 $B$ 」的表上填格：每个格子 $F[i][j]$ 只从对角（替换或匹配）、上（删）、左（插）三个来源里，按 $\max$ 或 $\min$ 取最优。真正区分这几个算法的，只是每个方向记什么代价、以及取 $\max$ 还是 $\min$ 这一组参数。本页把它抽象成一个 spec，用同一个引擎在四者之间切换。

1 · 格子的转移来源

把 $A$ 排成行、 $B$ 排成列， $F[i][j]$ 表示 $A$ 的前 $i$ 个字符与 $B$ 的前 $j$ 个字符之间的最优值。要算它，只需看三个已经算好的邻居，各加上一步操作的代价再聚合：

F[i][j] = \mathrm{agg} \begin{cases} F[i-1][j-1] + d(a, b) & \text{对角：}a\text{ 与 }b\text{ 对位} \\ F[i-1][j] + \mathrm{up}(a) & \text{上：删去 }A\text{ 的字符 }a \\ F[i][j-1] + \mathrm{left}(b) & \text{左：插入 }B\text{ 的字符 }b \end{cases}

其中 $\mathrm{agg}$ 是 $\max$ 或 $\min$ ，而 $d$ 、 $\mathrm{up}$ 、 $\mathrm{left}$ 是三个方向各自的代价函数。边界（第一行与第一列）对应「一方为空串」，沿单一方向累积即可。填完整张表后，从终点 $F[m][n]$ 沿方向指针回溯，就能还原出完整的对齐与编辑脚本。

图 1-1 · 单个格子的三个转移来源。可切换来源观察该方向对应哪一步编辑操作。

2 · spec 与算法的对应

把四个算法按两个维度摆成一张 2×2 矩阵。纵轴是聚合方向： $\max$ 配相似度（分越高越像）对 $\min$ 配代价（代价越低越像）。横轴是代价取法：朴素的 0 与 1 对带权打分。四个格子恰好落到四个算法。

LCS（ $\max$ 加朴素）：相等才 $+1$ ，删插不计，求最长公共子序列。
Needleman–Wunsch（ $\max$ 加打分）：匹配、失配、gap 各给一个可正可负的得分，求总分最高的全局比对。
编辑距离（ $\min$ 加朴素）：增、删、改各记 $1$ ，求把 $A$ 改成 $B$ 的最少操作数。
带权编辑（ $\min$ 加带权）：增、删、改各带不同权重，求最小总代价。

图 2-1 · 同一套填表逻辑在四个 spec 下的表与回溯路径。可点矩阵切换算法、改

A

与

B

或点预设换输入，并逐帧看填表与回溯；Needleman–Wunsch 与带权编辑另有参数滑块与翻转视角按钮（见 §4）。

这个「换 spec 即换算法」的说法可以验证。给 LCS、编辑距离与 Needleman–Wunsch 各写一份不复用引擎的参考实现，在 14 个词两两组合的 196 组输入上比对，引擎的表末值与三份参考实现逐组一致，无一例外。

3 · 四种 spec 的参数对照

四个算法的差别全部浓缩在下表——同一套 solve(A, B, spec) 填表逻辑，只是喂进去的 $d$ 、 $\mathrm{up}$ 、 $\mathrm{left}$ 与 $\mathrm{agg}$ 不同。

四行只在代价函数与聚合方向上不同，填表与回溯的代码完全共用。
算法	对角 $d(a, b)$	上 $\mathrm{up}(a)$	左 $\mathrm{left}(b)$	$\mathrm{agg}$
LCS	$a = b\ ?\ 1 : -\infty$	$0$	$0$	$\max$
Needleman–Wunsch	$a = b\ ?\ \mathrm{match} : \mathrm{mismatch}$	$\mathrm{gap}$	$\mathrm{gap}$	$\max$
编辑距离	$a = b\ ?\ 0 : 1$	$1$	$1$	$\min$
带权编辑	$a = b\ ?\ 0 : W_{\mathrm{sub}}$	$W_{\mathrm{del}}$	$W_{\mathrm{ins}}$	$\min$

LCS 的对角取 $-\infty$ 是因为它不允许替换：两个字符不相等时绝不能走对角占一个匹配位，只能从上或左绕过（即删或插）。把失配的对角代价设成 $-\infty$ ，在 $\max$ 聚合下它永远不会被选中，等于禁掉了替换。编辑距离则相反，替换是合法的一步，失配对角记 $1$ 。

4 · 相似度与代价的同构

有的算法求 $\max$ 、有的求 $\min$ ，根源是相似度等于代价取负。把一个 spec 的全部代价取负、并把 $\max$ 翻成 $\min$ （反之亦然），得到的是同一个问题的另一种说法：最优路径完全不变，只是表里每个数字镜像取负。同样在那 196 组输入上实测，翻转前后的表末值严格互为相反数，回溯出的操作序列一字不差。

警示 · 这解释了为什么生物信息学惯用 Needleman–Wunsch 的得分（ $\max$ ）语言，而编辑距离用代价（ $\min$ ）语言。两者并非不同算法，只是同一个 DP 在符号上的两种约定。

5 · LCS 与编辑距离的化归

当编辑距离只允许增、删而不允许替换时，它与 LCS 之间有一个精确等式：

\mathrm{indel}(A, B) = m + n - 2 \cdot \mathrm{LCS}(A, B)

直觉是：两串各长 $m$ 与 $n$ ，公共子序列里的那 $\mathrm{LCS}$ 个字符两边都保留，其余 $m - \mathrm{LCS}$ 个要删、 $n - \mathrm{LCS}$ 个要插。这个等式同样在 196 组输入上逐组核过，无一例外。以 kitten 与 sitting 为例： $\mathrm{LCS} = 4$ ，仅增删的编辑距离是 $6 + 7 - 2 \times 4 = 5$ ，而允许替换的编辑距离只有 $3$ ——替换省下的正是那两步「删一个再插一个」。

6 · DTW 与时间轴对齐

前面四个算法比的是字符序列。把序列换成数值（音频帧、笔迹坐标、传感器采样），问题就从「怎么改」变成「两条随时间变化、但快慢不同的信号怎么对齐、有多像」，这就是 DTW（dynamic time warping，动态时间规整）。它和编辑距离是近亲：同样一张二维表、同样三方向、同样取 $\min$ 。但有三处关键不同，不能当成第五个 spec 并进上面的引擎。

格子代价是距离：每格付 $\mathrm{dist}(a, b) = |a - b|$ ，是实数，不是 0 与 1 或操作权重。

三方向付同一份代价： $D[i][j] = \mathrm{dist}(a, b) + \min(\nwarrow, \uparrow, \leftarrow)$ ，三个前驱都加同一个 $\mathrm{dist}$ 再取最优；编辑距离则是三方向各付各的。

边界是无穷、产物是 warping 路径： $D[i][0] = D[0][j] = \infty$ 逼对齐从 $(1,1)$ 起；回溯得到的是「一个点对多个点」的时间轴伸缩关系，不是增删改的编辑脚本。

图 6-1 · 两条数值序列的 DTW 对齐，柱高为信号幅度、连线为对齐关系。可选「同峰 · 不同速」预设，看两条形状相同快慢不同的信号如何把峰值拉伸对齐到一起。

建议 · 这是字幕对齐（forced alignment）的内核：已知一段音频与对应文本，把音频特征帧序列与文本音素序列用 DTW 或 HMM 对齐，就能算出「第几个字落在哪个时间区间」，生成逐字高亮的字幕。手势识别同理，把用户画的轨迹与模板轨迹对齐，快慢与点数不同也不影响判定。这类功能在前端通常藏在媒体或手势库内部。

7 · 参考文献

Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8), 707–710.
Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443–453.
Sakoe, H., & Chiba, S. (1978). Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, 26(1), 43–49.