最小编辑距离算法详解：动态规划与Python实现工程实践

做搜索纠错的时候最绕不开的一个基础算法就是最小编辑距离Minimum Edit Distance也叫 Levenshtein Distance。它的核心作用很简单算两个字符串之间有多“像”。比如用户输入了“kitten”系统要猜到他想找的是“sitting”靠的就是这两个词之间的距离足够近。这个算法的应用范围比大多数人想象的要广拼写纠错、代码查重、DNA 序列比对、机器翻译评测指标 WER、语音识别结果修正甚至你在编辑器里看到的 diff 提示底层都跟它有关。这篇文章我会把最小编辑距离从定义、动态规划原理到 Python 实现完整拆开来讲包含我实际写代码时踩过的坑和工程优化思路。无论你是刚开始学算法的学生还是要做模糊匹配的工程师照着这篇文章的逻辑走一遍基本能把这套东西吃透。1. 编辑距离到底在算什么1.1 从一个例子体会“距离”先看一个最经典的例子把字符串kitten变成sitting最少需要几步我来手动演示一遍kitten→sitten把k替换成ssitten→sittin把e替换成isittin→sitting在末尾插入一个g一共 3 次操作所以这两个字符串的编辑距离就是 3。你可以把编辑距离理解成“两个字符串之间的物理距离”距离越小意味着它们越相似。kitten和sitting这种 6 个字符里 4 个相同、只有 3 处差异的串距离是 3而abc和abc这种完全一样的串距离是 0。1.2 三种操作与数学定义标准 Levenshtein 距离允许的操作只有三种每种操作的代价默认为 1插入Insert在源字符串的任意位置插入一个字符删除Delete从源字符串中删除一个字符替换Replace把源字符串中的某个字符替换成另一个字符注意一点这里的“插入”和“删除”是成对出现的。从abc变成ab你可以说是删掉了c反过来从ab变成abc就是插入了c。所以编辑距离是天然对称的distance(a, b)等于distance(b, a)。替换操作单独占一种是因为现实中“改一个字”往往比“删掉再加一个”更贴近真实场景。比如把k换成s一次操作就完成了如果只允许插入和删除那就得先删再插需要两次。大多数情况下替换的代价设成 1但某些特殊业务里也可以调整比如键盘上相邻键的误触替换代价就可以设得比 1 更低。1.3 编辑距离和相似度的关系编辑距离本身是一个绝对差值它并不能直接当“相似度”用。一个 100 字符的文本和另一个 100 字符的文本距离是 20跟两个 10 字符的短词距离是 20显然前者相似度更高。所以工程上做相似度计算时通常会做归一化similarity 1 - edit_distance / max(len(a), len(b))分母用max(len(a), len(b))是最常见的做法因为编辑距离不可能超过最长字符串的长度最坏情况就是先全删掉再全插入。也有用两个字符串平均长度做分母的效果差不多但要记住同一套系统里必须统一标准否则不同接口返回的相似度没有可比性。基于常见实践的补充如果你做的是中文场景的模糊匹配直接对整句算编辑距离通常效果不好因为中文的最小语义单位是“词”不是“字”。更实用的做法是先用分词把句子切碎再对分词序列算编辑距离或者配合向量相似度做二次过滤。2. 动态规划思路状态、转移与决策2.1 递归是最直观的但代价太高很多人第一次接触编辑距离第一反应就是递归。思路很自然从两个字符串的末尾开始比较如果最后一个字符相同就继续比较前面的子串如果不同就分别尝试“删除”“插入”“替换”三种操作的成本。我先把这段朴实无华的代码写出来def edit_distance_recursive(s1: str, s2: str) - int: if len(s1) 0: return len(s2) if len(s2) 0: return len(s1) if s1[-1] s2[-1]: return edit_distance_recursive(s1[:-1], s2[:-1]) delete_cost edit_distance_recursive(s1[:-1], s2) insert_cost edit_distance_recursive(s1, s2[:-1]) replace_cost edit_distance_recursive(s1[:-1], s2[:-1]) return 1 min(delete_cost, insert_cost, replace_cost)代码逻辑完全正确但跑起来就很痛苦复杂度是 O(3^(mn))因为每个字符位置都可能分叉出三种情况指数爆炸。我拿kitten和sitting这种长度的串试过虽然结果能出但已经能感受到明显的卡顿如果换成几百个字符的文本直接卡死。递归慢的根本原因是存在大量重叠子问题。s1[:-1]和s2[:-1]这个组合会被不同的递归路径反复计算上百次每一次都是从头再算一遍。2.2 状态定义与转移方程动态规划的思路是把子问题的结果存起来避免重复计算。定义dp[i][j]表示s1的前i个字符编辑成s2的前j个字符所需的最小操作次数。注意这里的i和j是“长度”不是“下标”。dp[3][2]代表s1的前 3 个字符和s2的前 2 个字符之间的距离。这是一个很容易弄混的细节后面讲实现的时候我会再强调。初始化dp[0][j] j空字符串变成s2的前j个字符只能一路插入插几次就是几次dp[i][0] is1的前i个字符变成空字符串只能一路删除转移方程分两种情况第一种s1[i-1] s2[j-1]最后一个字符相同dp[i][j] dp[i-1][j-1]既然最后一个字符已经一样了那就别动它距离跟两个字符串各自去掉最后一个字符之后的状态一致。第二种s1[i-1] ! s2[j-1]最后一个字符不同dp[i][j] 1 min( dp[i-1][j], # 删除 s1 的最后一个字符 dp[i][j-1], # 在 s1 末尾插入一个跟 s2 最后一个字符相同的字符 dp[i-1][j-1] # 把 s1 的最后一个字符替换成 s2 的最后一个字符 )这里要理解一件事这三种操作本质上是在处理“最后一个字符不匹配”时的三种补救策略。删除s1的前 i 个字符要变成s2的前 j 个字符但s1多出来最后一个字符删掉它然后让s1的前 i-1 个字符去对齐s2的前 j 个字符插入s1的前 i 个字符要变成s2的前 j 个字符但少了一个字符那就在末尾插入一个等于s2[j-1]的字符问题退化成让s1的前 i 个字符对齐s2的前 j-1 个字符替换s1的最后一个字符跟s2的最后一个字符不一样直接替换掉然后让s1的前 i-1 个字符对齐s2的前 j-1 个字符每个转移方向都对应一个真实世界的编辑动作这也是编辑距离的 DP 表可以被用来回溯编辑路径的原因。2.3 手把手把 DP 表填完纸上得来终觉浅我拿kitten→sitting完整推一遍。注意表格里的行是kitten的每个前缀包括空串列是sitting的每个前缀。sitting01234567k11234567i22123456t33212345t44321234e55432234n66543323表里最右下角的数字 3就是kitten和sitting的编辑距离。我建议读者自己手动填一遍这个表填的时候你会直观地看到每个格子怎么从上一行和左边推出来。尤其注意第二行第二列那个 1k和s不同取的是左上角dp[0][0] 1也就是把k替换成s的一次操作。从我带过的新人经验来看能把 DP 表画明白的人代码基本不会写错反过来代码写不对的十有八九是心里根本没有这张表。3. Python 实现从二维到一维3.1 二维 DP 实现思路最清晰的一版先把最标准的二维实现写出来。def min_distance(s1: str, s2: str) - int: m, n len(s1), len(s2) # dp[i][j] 表示 s1 前 i 个字符变成 s2 前 j 个字符的最小编辑距离 dp [[0] * (n 1) for _ in range(m 1)] # 初始化边界空串到非空串只能靠插入/删除 for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j # 逐个填充 DP 表 for i in range(1, m 1): for j in range(1, n 1): if s1[i - 1] s2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] 1 min( dp[i - 1][j], # 删除 s1[i-1] dp[i][j - 1], # 插入 s2[j-1] dp[i - 1][j - 1] # 替换 s1[i-1] 为 s2[j-1] ) return dp[m][n]测试一下print(min_distance(kitten, sitting)) # 3 print(min_distance(, abcd)) # 4 print(min_distance(abc, abc)) # 0 print(min_distance(abc, yabd)) # 2最后一个abc→yabd距离是 2把a替换成y再在末尾插入d。你可以自己填一下表验证。注意代码里的s1[i - 1]不是s1[i]。因为i是长度第 i 个字符的下标是i - 1。这个错位问题我见过太多次了新手写到这里几乎必踩一次。3.2 滚动数组优化把空间降到 O(n)二维 DP 的空间复杂度是 O(m×n)如果两个字符串都是几千字符内存占用会到千万级别很浪费。观察一下转移方程就会发现计算dp[i][j]时只用到了当前行的前一列dp[i][j-1]上一行的同一列dp[i-1][j]上一行的前一列dp[i-1][j-1]这意味着我们根本不需要保留整个二维表只需要一维数组加上一个临时变量就能搞定。这就是滚动数组。def min_distance_rolling(s1: str, s2: str) - int: m, n len(s1), len(s2) # dp[j] 表示“当前行”第 j 列的值 # 初始化时是第 0 行空串到 s2 的每个前缀的编辑距离 dp list(range(n 1)) for i in range(1, m 1): prev dp[0] # prev 保存 dp[i-1][j-1] dp[0] i # 当前行第 0 列 is1 前 i 个字符变成空串 for j in range(1, n 1): temp dp[j] # temp 保存 dp[i-1][j] if s1[i - 1] s2[j - 1]: dp[j] prev else: dp[j] min(temp 1, dp[j - 1] 1, prev 1) prev temp return dp[n]这里最关键的变量是prev。它在每轮j循环开始之前保存的是“上一行第 j-1 列”的值即dp[i-1][j-1]。如果你去掉prev直接写dp[j-1]那就用了当前行刚更新过的值结果就会错。这个坑我在 5.2 节会专门演示一个翻车现场。空间从 O(m×n) 降到了 O(n)时间仍然是 O(m×n)。如果还想进一步压到 O(min(m, n))可以在函数开头判断一下哪个字符串短把短字符串放到s2的位置上因为dp数组长度跟着n走。代码很容易改我就不重复贴了。3.3 回溯具体操作路径很多时候只算距离不够业务上还需要知道“到底是怎么变的”。比如我要在界面上展示给用户看“你输入的kitten和目标sitting之间差了哪几个字符”。这时候需要回溯 DP 表找出完整的编辑路径。def edit_distance_with_ops(s1: str, s2: str): m, n len(s1), len(s2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if s1[i - 1] s2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] 1 min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) ops [] i, j m, n while i 0 or j 0: if i 0 and j 0 and s1[i - 1] s2[j - 1]: ops.append((keep, s1[i - 1])) i - 1 j - 1 elif i 0 and j 0 and dp[i][j] dp[i - 1][j - 1] 1: ops.append((replace, s1[i - 1], s2[j - 1])) i - 1 j - 1 elif i 0 and dp[i][j] dp[i - 1][j] 1: ops.append((delete, s1[i - 1])) i - 1 elif j 0 and dp[i][j] dp[i][j - 1] 1: ops.append((insert, s2[j - 1])) j - 1 ops.reverse() return dp[m][n], ops回溯的规则是从右下角往左上角走当前两个字符相同优先走“保持”当前格子是由左上角加 1 来的说明走了“替换”当前格子是由上方加 1 来的说明走了“删除”当前格子是由左方加 1 来的说明走了“插入”注意如果存在多条最优路径回溯只会给出其中一条。这在大多数业务场景下已经够用了但如果你要做“差异高亮”需要知道的是路径本身而不是“唯一最优解”所以不必纠结。运行一下dist, ops edit_distance_with_ops(kitten, sitting) print(dist) for op in ops: print(op)输出结果会是替换两次、插入一次。仔细看的话你会发现回溯给出的路径不一定是我第 1 节手动演示的那条顺序但次数同样是 3。这就是动态规划表的特性多条路径等价取差异结果而不纠结过程。3.4 复杂度与边界情况时间复杂度和空间复杂度如下版本时间复杂度空间复杂度朴素递归O(3^(mn))O(mn) 递归栈二维 DPO(mn)O(mn)滚动数组 DPO(mn)O(n)带回溯的 DPO(mn)O(mn)边界情况主要是空字符串s1为空s2任意距离就是len(s2)纯插入s2为空s1任意距离就是len(s1)纯删除两个都为空距离 0这些在初始化阶段直接处理掉了不需要单独写额外逻辑。4. 工程场景下的选型与变通4.1 拼写纠错和模糊匹配怎么用编辑距离最典型的落地场景是拼写纠错。比如一个搜索服务用户输入“pythob”系统想提示“python”。做法一般是维护一个高频词表把用户输入跟候选词逐个算编辑距离选出距离最小的几个词作为纠错建议。做这类功能时有几个实用经验别全表扫描如果词表有几十万条每条都跑一遍完整的 O(mn) DP延迟会非常难看。正确姿势是先粗筛比如只比较长度差在 2 以内的候选或者用 BK 树Burkhard-Keller Tree这种专门为编辑距离设计的索引结构把查询复杂度从线性降到对数级别。设置阈值拼写纠错一般只看距离 ≤ 2 的候选超过 2 的改动太大基本不可能是误输。结合词频距离相同的情况下优先展示高频词。很多搜索引擎的纠错结果并不是“距离最近”而是“距离最近×词频最高”。模糊匹配场景也类似。比如知识库问答系统里用户问的问题和库里标准问题的说法有细微差别用编辑距离做一遍初筛再用更重的语义模型精排是性价比很高的组合方式。4.2 相关距离算法怎么选编辑距离这几个字在不同的上下文里可能有不同含义工程上需要区分清楚。我把常见的几个放到一个表里对比算法核心操作适用场景复杂度Levenshtein 距离插入、删除、替换通用字符串相似度、拼写纠错O(mn)Damerau-Levenshtein 距离上述三种 相邻字符交换键盘误触场景如ab打成baO(mn)Hamming 距离等长字符串逐位比较DNA 片段、定长编码校验O(n)Jaro-Winkler 相似度字符匹配 顺序 前缀加分人名、地名短字符串匹配O(n)Needleman-Wunsch带得分矩阵的全局比对生物信息学序列比对O(mn)Smith-Waterman带局部匹配的局部比对找序列中的相似片段O(mn)Damerau-Levenshtein 在拼写纠错里特别值得留意。用户打字最常见的错误之一是把两个相邻字符打反比如“hlelo”应该是“hello”。标准 Levenshtein 距离会认为这需要两次操作删除l再插入l距离是 2但 Damerau 距离把相邻交换算成一次操作距离就是 1。如果你的业务是键盘输入纠错基本无脑选 Damerau 变体。它的 DP 递推公式比标准版多一个分支代码稍长一点但原理完全一致。4.3 超长字符串的工程优化思路两个几万字的文本算编辑距离O(mn) 的复杂度会直接让人崩溃。这时候有几个思路思路一砍掉公共前缀和后缀这是最简单也最有效的一招。如果两个字符串开头有一段完全相同的字符这段无论如何都不会被编辑。同样结尾相同的一段也不会。把两端相同部分直接裁掉再对中间区域算编辑距离m 和 n 都显著变小。比如两段只有中间一小段不同的长文本裁完中间可能只剩几十个字符。思路二长度差剪枝编辑距离有一个绝对下界两个字符串的长度差。|len(a) - len(b)|就是无论如何都不可能低于的编辑次数。如果你只需要判断距离是否小于某个阈值 k可以先算长度差一旦超过 k 直接返回失败连 DP 都不用跑。思路三阈值限制 带状 DP如果 k 很小比如纠错场景 k2不需要填满整个 DP 表。因为距离超过 k 的路径不会再回到 k 以内所以只需要计算对角线附近宽度约 2k1 的带状区域。时间复杂度从 O(mn) 降为 O(k×min(m,n))收益极其可观。这个优化在拼写纠错词库里几乎是标配。思路四近似算法兜底有些场景不要求精确距离只要能区分“明显不同”就行。这时候可以用 SimHash、MinHash 或者字符 n-gram 重叠率做近似判断速度比编辑距离快几个数量级。我的个人建议是精确距离用在候选量小的场景近似算法用在海量粗筛场景两者配合而不是互斥。5. 踩坑记录与排查技巧5.1 索引错位是新手重灾区我前面提过DP 表里的i和j是长度不是下标所以比较字符时要用s1[i-1]和s2[j-1]。很多人把初始化写成dp [[0] * n for _ in range(m)]然后在循环里用s1[i]比较结果要么报IndexError要么边界条件完全错掉。一个自查技巧先画表再写代码。你在纸上画出表格后就会发现行数是m1列数是n1因为第一行第一列是空串对应的边界。写代码时把表格尺寸先确认好后面基本不会错。5.2 滚动数组丢状态滚动数组最容易犯的错误就是没保存左上角旧值。我写一个错误版本# 错误示范没有保存左上角的旧值 def min_distance_wrong(s1: str, s2: str) - int: m, n len(s1), len(s2) dp list(range(n 1)) for i in range(1, m 1): dp[0] i for j in range(1, n 1): if s1[i - 1] s2[j - 1]: dp[j] dp[j - 1] # 错这里应该用左上角 dp[i-1][j-1] else: dp[j] min(dp[j] 1, dp[j - 1] 1, dp[j - 1] 1) # 全是当前行的值递推关系失效 return dp[n]这个版本的问题很明显当s1[i-1] s2[j-1]时dp[j]应该继承dp[i-1][j-1]也就是“上一行前一列”。但一维数组里当前行的dp[j-1]已经被覆盖成新值了再用它就相当于偷看了未来。正确写法必须用一个prev变量在每轮循环前把旧值暂存。排查这个问题的技巧是拿一个短例子手动跑一遍对比滚动数组输出和二维 DP 输出。如果前几行结果一致、后面开始不一致八成就是prev的更新时机出了问题。5.3 打印 DP 表调试法我强烈建议在调试 DP 代码时写一个小工具函数把表完整打印出来。这比盯着代码空想高效得多def print_dp_table(s1: str, s2: str, dp): m, n len(s1), len(s2) header [ ] [] list(s2) print( .join(f{x:2} for x in header)) for i in range(m 1): row_label if i 0 else s1[i - 1] row [row_label] [dp[i][j] for j in range(n 1)] print( .join(f{x:2} for x in row))每次调完一行转移逻辑就把表打出来跟手算的期望表对比。一旦某个格子跟预期不一致立刻就能定位是哪一行、哪一列、哪一次转移出了问题。这个方法我用了很多年比打日志好用得多。5.4 中文字符串的特殊情况Python 的len()对字符串计数是按 Unicode 码点所以len(你好)是 2中文场景的编辑距离天然按“字”计算这是符合直觉的。但要小心的是组合字符。比如é在 Unicode 里可以表示成单个码点\u00e9也可以拆成e 组合重音符号\u0301。这两种表示如果分别出现在两个字符串里视觉上一样但编辑距离可能大于 0。处理这类文本时需要用unicodedata.normalize先做归一化把字符串统一成同一种形式再算距离。Emoji 更麻烦。‍‍这种家庭组合 Emoji 在 Python 里由多个码点组成len()会算成好几个字符。如果你的业务按“用户视觉上的一个字符”来算距离普通的编辑距离就不够用了得用 grapheme 分割库如第三方库grapheme先把用户感知的字符切出来再对切分后的序列算编辑距离。这块经验来自我之前处理一个用户昵称去重需求最初直接对原始字符串算距离结果‍‍和‍‍这种明明是“换了一个孩子性别”的情况距离被算得很大完全不符合人工判断。后来切成 grapheme 序列再算结果才合理。最后分享一个实际心得编辑距离本身不难难的是把它放到合适的场景里用对。我见过不少项目一上来就对全量数据跑精确编辑距离遇到性能瓶颈后又盲目换成近似算法最后精度掉得厉害。更好的路径是先分析业务里字符串的特征——长度分布、差异类型、可容忍的误差——再决定用哪种距离变体、要不要剪枝、要不要上 BK 树。算法只是工具真正值钱的是你对自己的数据有多了解。