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

做搜索纠错的时候，最绕不开的一个基础算法就是最小编辑距离（Minimum Edit Distance，也叫 Levenshtein Distance）。它的核心作用很简单：算两个字符串之间有多“像”。比如用户输入了“kitten”，系统要猜到他想找的是“sitting”，靠的就是这两个词之间的距离足够近。这个算法的应用范围比大多数人想象的要广：拼写纠错、代码查重、DNA 序列比对、机器翻译评测指标 WER、语音识别结果修正，甚至你在编辑器里看到的 diff 提示，底层都跟它有关。

这篇文章我会把最小编辑距离从定义、动态规划原理到 Python 实现完整拆开来讲，包含我实际写代码时踩过的坑和工程优化思路。无论你是刚开始学算法的学生，还是要做模糊匹配的工程师，照着这篇文章的逻辑走一遍，基本能把这套东西吃透。

1. 编辑距离到底在算什么

1.1 从一个例子体会“距离”

先看一个最经典的例子：把字符串kitten变成sitting，最少需要几步？

我来手动演示一遍：

• kitten→sitten：把k替换成s
• sitten→sittin：把e替换成i
• sittin→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^(m+n))，因为每个字符位置都可能分叉出三种情况，指数爆炸。我拿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] = i：s1的前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的每个前缀。

表里最右下角的数字 3，就是kitten和sitting的编辑距离。

我建议读者自己手动填一遍这个表，填的时候你会直观地看到每个格子怎么从上一行和左边推出来。尤其注意第二行第二列那个 1：k和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 列 = i（s1 前 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 复杂度与边界情况

时间复杂度和空间复杂度如下：

边界情况主要是空字符串：

• 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 相关距离算法怎么选

编辑距离这几个字在不同的上下文里可能有不同含义，工程上需要区分清楚。我把常见的几个放到一个表里对比：

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 很小（比如纠错场景 k=2），不需要填满整个 DP 表。因为距离超过 k 的路径不会再回到 k 以内，所以只需要计算对角线附近宽度约 2k+1 的带状区域。时间复杂度从 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，要么边界条件完全错掉。

一个自查技巧：先画表，再写代码。你在纸上画出表格后就会发现，行数是m+1，列数是n+1，因为第一行第一列是空串对应的边界。写代码时把表格尺寸先确认好，后面基本不会错。

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 树。算法只是工具，真正值钱的是你对自己的数据有多了解。