编辑距离

拼写检查怎么知道你想打的是哪个词？

你手一抖打成了 recieve，输入法立刻在下面提示 receive；你搜 kitten 打成了 sitting，引擎也能猜个八九不离十。它凭什么认定这两个词"很接近"，而不是别的词？

背后有一把专门量"词与词差多远"的尺子——编辑距离。它问的是一个很朴素的问题：把一个词改成另一个，最少要动几次手？

三种基本操作

允许的"动手"只有三种，每种算一步：

• 增：插入一个字符（cat → cart）
• 删：删掉一个字符（cart → car）
• 改：替换一个字符（cat → cut）

把一个词变成另一个，用掉的最少步数，就是它们的编辑距离（也叫 Levenshtein 距离）。

比如 kitten → sitting：把 k 改成 s、e 改成 i、末尾加一个 g——三步，一步都不能少。所以它们的编辑距离是 3。

怎么保证"最少"？——填一张表

难点在于"最少"。挨个去试组合会爆炸。聪明的办法是动态规划：把大问题拆成小问题，结果填进一张表里。

把两个词分别摆在表格的行和列。格子 $D_{i,j}$ 表示：第一个词的前 $i$ 个字母，变成第二个词的前 $j$ 个字母，最少要几步。

关键洞察是——每个格子，只取决于它的三个邻居：

想算 $D_{i,j}$，看它上面、左边、左上三个已经算好的格子，挑一条最省的路走过来。

• 从上面来 = 删一个字符，$D_{i-1,j}+1$
• 从左边来 = 增一个字符，$D_{i,j-1}+1$
• 从左上来 = 改一个字符；若这两个字符本来就相同，则不花钱（+0），否则 +1

于是递推式就是：

第一行、第一列先填好（从空串出发，只能一路插入或删除：$D_{i,0}=i$、$D_{0,j}=j$）。然后一格格往右下推，右下角那个数，就是答案。

回溯：看清它到底怎么改的

填完表还能"倒着走回去"：从右下角出发，每步回到那个给出最小值的邻居，一路退到左上角。这条路径就还原了最优的对齐方式——哪里匹配、哪里增、哪里删、哪里改，一目了然。动画里红线画的就是这条路。

它藏在哪些地方

• 拼写检查 / 自动纠错 / 搜索"你是不是要找"：找编辑距离最小的候选词。
• 生物信息：DNA、蛋白质的序列比对，本质就是带权的编辑距离。
• 版本对比：git diff、文档 diff 找最小改动，思路同源。

下次输入法替你纠错时，别小看它——那是一张表格，悄悄帮你算了几百条改法里最省的一条。