编辑距离算法

"您是要搜索 'Alber Einstien'？"

搜索引擎能识别你的拼写错误，文本编辑器能自动纠错，DNA 序列能被比对到参考基因组——这些背后都有同一个算法：编辑距离（Edit Distance），或称 Levenshtein 距离。

破除误解：最少步数不等于"实际改了什么"#

上面那三步看起来像是一份"真相"：把 kitten 改成 sitting 就是这么改的。两处都要小心。

第一，最优编辑序列通常不唯一。 编辑距离 3 是一个最小值，达到它的操作序列可能有好几条。把 AB 变成 BA，距离是 2，而两条完全不同的路都只花 2 步：

• 替换 A→B，再替换 B→A
• 删掉开头的 A，再在末尾插入 A

一个说"两个字符都改了"，一个说"一个字符搬了家"，代价却一样。把 aaaa 对齐到 aa 更夸张——保留哪两个 a 有 $\binom{4}{2} = 6$ 种选法，全都最优；串一长，最优路径的条数可以呈指数级增长。

这不是理论洁癖：这正是为什么不同 diff 工具对同一次改动会给出看起来不同的输出，尽管它们算出的距离一模一样。后文的 git --patience 一节就是在这堆等价最优解里挑一个人类更好读的。

第二，最少步数不是真实发生的步数。 DNA 比对时我们算出两个序列距离 12，绝不意味着演化过程中真的只发生了 12 次事件——真实历史可能来回突变了上百次，只是净效果等价于 12 步。编辑距离给的是"至少需要多少"，把它当成"实际发生了多少"是应用中最常见的越界解读。

第三，它测的是形状，不是意思。「猫」和「狗」编辑距离 1，「猫」和「小猫咪」编辑距离 3——按编辑距离算，猫离狗更近。这个度量对语义一无所知，后文会回到这一点。

问题定义#

编辑距离：将字符串 $s$ 变换为字符串 $t$ 所需要的最少编辑操作次数。标准操作集（Levenshtein, 1966）：

• 插入（Insertion）：在任意位置插入一个字符
• 删除（Deletion）：删除一个字符
• 替换（Substitution）：将一个字符替换为另一个字符

例：将 "kitten" 变为 "sitting"：

kitten → sitten（k→s，替换）
sitten → sittin（e→i，替换）
sittin → sitting（插入 g）
```

编辑距离 = 3。

变体：不同应用场景用不同操作集：

动态规划求解#

编辑距离是动态规划（DP）的经典应用。定义：

$dp[i][j]$ 表示 $s[0..i-1]$ 与 $t[0..j-1]$ 的编辑距离。

递推关系：

$$dp[i][j] = \begin{cases} i & \text{if } j = 0 \\ j & \text{if } i = 0 \\ dp[i-1][j-1] & \text{if } s[i-1] = t[j-1] \\ 1 + \min\begin{cases} dp[i-1][j] & \text{(delete } s[i-1]\text{)} \\ dp[i][j-1] & \text{(insert } t[j-1]\text{)} \\ dp[i-1][j-1] & \text{(replace)} \end{cases} & \text{otherwise} \end{cases}$$

示例：$s = \text{"kitten"}$，$t = \text{"sitting"}$（$m=6$，$n=7$）

右下角 $dp[6][7] = 3$，即编辑距离为 3。

一个格子怎么来的。挑中间那格看：行 e、列 i，即 $dp[5][5]$——把 kitte 变成 sitti 要几步？

$s[4] = $ e，$t[4] = $ i，不相等，所以要在三条路里选最省的，再 $+1$：

$\min(2, 2, 1) + 1 = 2$。左上角赢了——替换比"删一个再插一个"便宜，这就是替换操作存在的全部理由。整张表就是这一个判断重复 $m \times n$ 次。

倒着走回去，就得到具体怎么改。DP 表不只给距离，还藏着编辑脚本：从右下角出发，每次退回刚才选中的那个来源格：

$$dp[6][7] \xrightarrow{\text{插入 g}} dp[6][6] \xrightarrow{\text{n 匹配}} dp[5][5] \xrightarrow{\text{e→i 替换}} dp[4][4] \xrightarrow{\text{t 匹配}} dp[3][3] \xrightarrow{\text{t 匹配}} dp[2][2] \xrightarrow{\text{i 匹配}} dp[1][1] \xrightarrow{\text{k→s 替换}} dp[0][0]$$

翻转过来读：替换 k→s，替换 e→i，插入 g——正是本文开头列的那三步。距离和路径是同一张表的两种读法，这也是所有 diff 工具能打印出"具体改了哪几行"而不只是"改了 3 处"的原因。

时间复杂度 $O(mn)$，空间复杂度 $O(mn)$。若只要距离不要脚本，可以只存两行，空间降到 $O(\min(m,n))$——但回溯路径就丢了。这是个真实的工程取舍：git diff 要输出补丁，所以不能用这个优化；拼写检查只要距离，就可以用。

加速技巧#

Unicode 小字母表：若字符集小（如仅 26 个英文字母），可以预计算每行的位向量，利用 SIMD 指令并行处理，将常数因子减小到约 1/64。

Bit-Parallel 算法（Myers, 1999）：将 DP 表编码为位向量，用位运算批量计算，时间复杂度 $O(mn/w)$（$w$ 为机器字长，通常 64），适合字符串不太长的场景。

Ukkonen 的 $O(kn)$ 算法（1985）：若事先知道编辑距离上界为 $k$，只需计算 DP 表的对角带，时间 $O(kn)$，大幅加速拼写检查（通常 $k \leq 3$）。

近似编辑距离（LSH）：对超大规模字符串集合（如数十亿 DNA 序列），精确计算两两编辑距离不可行。局部敏感哈希（Locality-Sensitive Hashing）能近似找到编辑距离小于 $k$ 的对，是基因组学中的重要工具。

应用版图#

拼写检查与自动纠错：

Peter Norvig 的著名拼写纠错器（2007 年发布，约 21 行 Python 代码）的核心就是枚举编辑距离为 1 和 2 的候选词，选概率最高者。现代输入法的候选词提示也基于类似原理。

DNA 序列比对：

将一段 DNA 测序读段比对到参考基因组，本质是找编辑距离最小的位置。Needleman-Wunsch 算法（1970，全局比对）和 Smith-Waterman 算法（1981，局部比对）是编辑距离 DP 的生物信息学定制版，是现代基因组学工具链的基础。

diff 与版本控制：

Unix diff 命令计算两个文件的最小差异（基于 LCS），git diff 的输出就是两个文件 LCS 意义下的最小编辑序列——只是"字符"换成了"行"。Myers（1986）的算法是 git diff 的默认后端，它的巧妙之处在于不填整张 DP 表：编辑脚本长度为 $d$ 时只需沿着表的 $O(d)$ 条对角线搜索，代价 $O((m+n)d)$。而代码提交通常只改几行，$d$ 很小，所以它在实践中远快于 $O(mn)$。

这里有一件很能说明问题的事：git 至今提供四种 diff 算法（myers、minimal、patience、histogram），因为"最小编辑距离"和"人类看得懂的 diff"并不是一回事。移动一整个函数时，最小编辑序列可能把它拆成一堆交错的增删行；patience 算法（Bram Cohen 提出）反其道而行，先只匹配两边各自唯一出现的行作为锚点，再递归处理锚点之间的区块，牺牲最优性换取可读性。Linux 内核等项目的开发者常显式配置 --histogram（patience 的改进版）。算法给出的最优解未必是人要的解——这在编辑距离的应用史里反复出现。

自然语言处理：

候选词生成（OCR 纠错、语音识别后处理）、词语相似性计算，都用编辑距离作为基本度量。

光学字符识别（OCR）：

OCR 输出的文本经常有字符替换、漏识别等错误，后处理阶段用编辑距离将可疑词语纠正为词典中编辑距离最近的词。

当每步代价不再是 1#

标准编辑距离给三种操作都记 1 分。这个假设一旦放开，同一套 DP 就能表达远为丰富的领域知识——而且真实应用几乎全都放开了它。

替换代价按生物学定不同。蛋白质比对里，把亮氨酸换成异亮氨酸（两个性质相近的疏水氨基酸）在演化上很常见，把它换成带电的天冬氨酸则罕见得多。所以生物信息学不用"替换 = 1"，而用打分矩阵：PAM（Dayhoff, 1978）与 BLOSUM（Henikoff & Henikoff, 1992）从真实的同源序列比对中统计出每对氨基酸互换的频率，取对数几率作为分数。BLOSUM62 是 BLAST 的默认矩阵。此时"距离"变成了"最高得分"，DP 递推的 $\min$ 换成 $\max$，骨架不变。

空位代价不该线性累加。基因组里一次插入/缺失事件常常一口气涉及好几个碱基，所以"连续缺失 5 个"应该比"分散缺失 5 个"便宜。于是引入仿射空位罚分：开一个空位罚 $d$，每延长一位再罚 $e$（通常 $e \ll d$），总代价 $d + (k-1)e$。这一改动破坏了原递推的无后效性——现在必须记住"上一步是否已经在空位中"。Gotoh（1982）给出的解法是维护三张 DP 表（当前位置分别处于匹配态、$s$ 空位态、$t$ 空位态），仍是 $O(mn)$。

键盘距离也能进代价函数。输入法纠错里，把 s 打成 a（相邻键）的代价应低于打成 p。现代拼写纠错的打分函数通常混合了键盘布局、字符频率与语言模型概率——编辑距离退化成一个特征，而不是最终判据。

这条线索的普遍意义是：编辑距离的价值不在那三种操作，而在"最小代价变换"这个框架。领域知识全部编码进代价函数，算法骨架一行不动。

代价与争议#

$O(mn)$ 难以突破——但只对"精确"而言：这是本题最值得讲清的一段，因为它常被讲成一个绝望的结论。

2015 年，巴克斯特罗姆（Backurs）与印德尔（Indyk）在 STOC 证明：在强指数时间假设（SETH）下，编辑距离不存在 $O(n^{2-\epsilon})$ 的算法。SETH 是复杂度理论中一条被广泛采信但未获证明的猜想（大意是 $k$-SAT 无法显著优于穷举）。所以这不是无条件下界，而是一条条件下界：要么编辑距离确实需要平方时间，要么 SETH 是假的——而后者会推翻大量已有结果。这类"细粒度复杂度"（fine-grained complexity）论证是近十年算法理论最活跃的方向之一。

但故事在这里转弯：下界只管精确计算。

• 2018 年，Chakraborty、Das、Goldenberg、Koucký 与 Saks 在 FOCS 给出第一个真正次平方时间的常数因子近似算法，运行时间 $\tilde{O}(n^{2-2/7})$。
• 2020 年，Andoni 与 Nosatzki 在 FOCS 把它推到近线性：对任意 $\varepsilon > 0$，在 $n^{1+\varepsilon}$ 时间内给出常数因子近似。

也就是说，如果你能接受"距离是 3 还是 7 之间某个常数倍的答案"，那么平方时间的墙根本不在那里。这对实际系统意义重大：拼写检查、去重、粗筛比对本来就只需要"够近还是不够近"，精确值是奢侈品。

一个通用教训：面对一条难以逾越的下界，正确的反应通常不是硬撞，而是问"我真的需要精确解吗"。近似、参数化（如 Ukkonen 的 $O(kn)$，把 $k$ 当参数）、随机化——都是绕过下界的合法路径，因为下界针对的是它证明的那个问题，而不是你真正要解决的那个问题。

相似性与语义：编辑距离是表面（Surface-Level）的相似性度量，完全基于字符操作，不理解语义。"猫"和"狗"的编辑距离是 1，"猫"和"小猫咪"的编辑距离是 3，但后者语义更近。现代 NLP 用词嵌入（Word Embedding）距离衡量语义相似性，与编辑距离互补。

跨域连接#

• 贝叶斯定理：把它接进噪声信道模型，"最近的词"就变成"后验概率最大的词"——先验来自词频，似然来自打错的概率。代价函数由此获得含义：它是负对数似然，而不是随手指定的整数。这解释了为什么把键盘布局与字符频率并入代价能提升纠错，也解释了候选很多时纯距离为何输给带语言模型的方案。
• 医学遗传学与基因组学：序列比对不用"替换记一分"，而用从同源序列统计出的对数几率打分矩阵，于是最小距离变成最高得分，取小换成取大而骨架不变。空位罚分更能说明问题：一次插入缺失常涉及连续多个碱基，所以连续空位应比分散空位便宜；而这条改动破坏了无后效性，必须把"是否已在空位中"加成一维状态。
• 语言的变化：历史语言学判定同源不靠形近。距离小可能只是偶然相似或借词，真正的证据是规则的音对应——同一音位在成批词汇里系统性地对应，这种规律性无法由巧合产生。基于词表距离的分类法屡遭批评，正因为它把"少数几步就能改过去"当成了亲缘证据，而距离对哪一步在语言学上可能发生一无所知。
• 柯尔莫哥洛夫复杂度：把编辑脚本看成一段把源串变成目标串的程序，距离就是这段程序长度的上界估计，对应条件复杂度的朴素版本。差别在允许的程序类：柯氏复杂度允许任意图灵机因而不可计算，这里把程序限制成三种操作的序列因而可算。用受限的操作集换来可计算性，是这个类比最有价值的一课。
• 后缀树与后缀数组：两者在序列检索里分工明确——后缀结构回答"这个子串在不在、在哪里"，距离回答"两条串有多像"。流水线通常是先用前者做精确种子匹配，再只在种子附近做代价高的对齐。分工的依据是复杂度：精确匹配可做到近线性，而精确距离在合理的复杂度假设下无法做到真正次平方。

参考文献#

• Levenshtein, V. I. Binary Codes Capable of Correcting Deletions, Insertions, and Reversals. Soviet Physics Doklady 10(8), 707–710 (1966).
• Wagner, R. A. & Fischer, M. J. The String-to-String Correction Problem. JACM 21(1), 168–173 (1974).（首个完整的 DP 解法）
• Needleman, S. B. & Wunsch, C. D. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins. J. Mol. Biol. 48(3), 443–453 (1970).
• Gotoh, O. An Improved Algorithm for Matching Biological Sequences. J. Mol. Biol. 162(3), 705–708 (1982).（仿射空位罚分的三表 DP）
• Henikoff, S. & Henikoff, J. G. Amino Acid Substitution Matrices from Protein Blocks. PNAS 89(22), 10915–10919 (1992).（BLOSUM 矩阵）
• Myers, E. W. An O(ND) Difference Algorithm and Its Variations. Algorithmica 1(2), 251–266 (1986).（git diff 默认后端）
• Ukkonen, E. Algorithms for Approximate String Matching. Information and Control 64(1–3), 100–118 (1985).（$O(kn)$ 对角带算法）
• Backurs, A. & Indyk, P. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). STOC 2015, pp. 51–58.
• Chakraborty, D., Das, D., Goldenberg, E., Koucký, M. & Saks, M. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. FOCS 2018, 979–990；JACM 67(6), 2020. DOI: 10.1145/3422823.
• Andoni, A. & Nosatzki, N. S. Edit Distance in Near-Linear Time: It's a Constant Factor. FOCS 2020, 990–1001. arXiv:2005.07678.

延伸阅读#

• Gusfield, D. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.（字符串算法与生物序列比对的标准参考书）
• Jurafsky, D. & Martin, J. H. Speech and Language Processing. 3rd ed. draft.（拼写纠错与噪声信道模型如何把编辑距离接入概率框架）
• Git 文档：git diff --diff-algorithm= 说明（myers / minimal / patience / histogram 的差异）。