编辑距离（Edit Distance）——从字符串相似度到动态规划经典模型

引言

在自然语言处理（NLP）、搜索引擎纠错、DNA序列比对、拼写检查系统等领域，经常需要衡量两个字符串之间的相似程度。

例如：

kitten
sitting

显然两个单词非常接近，但究竟有多接近？

如何用数学方法描述这种“接近程度”？

为了解决这一问题，俄罗斯科学家 Vladimir Levenshtein 于 1965 年提出了著名的 Levenshtein Distance（编辑距离）。

编辑距离定义为：

将一个字符串转换为另一个字符串所需要执行的最少编辑操作次数。

允许的操作包括：

• 插入（Insert）

• 删除（Delete）

• 替换（Replace）

问题描述

给定两个字符串：

word1
word2

求将 word1 转换为 word2 所需的最少操作次数。

例如：

horse → ros

转换过程：

horse
↓ replace(h,r)
rorse
↓ delete(r)
rose
↓ delete(e)
ros

答案：

3

编辑距离的本质

假设：

word1 = horse
word2 = ros

我们关注的是：

horse前i个字符
与
ros前j个字符

之间的最优转换方案。

因此可以发现：

一个大问题可以分解为若干个更小的子问题。

这正是动态规划的典型特征。

动态规划状态定义

设：

dp[i][j]

表示：

word1前i个字符
转换成
word2前j个字符

所需的最少操作次数

例如：

dp[3][2]

表示：

"hor"
→
"ro"

的最小编辑距离。

状态转移推导

这是整道题最核心的部分。

情况一：字符相同

假设：

word1[i-1] == word2[j-1]

例如：

abc
abc

最后一个字符已经匹配：

c == c

无需额外操作。

因此：

dp[i][j] = dp[i-1][j-1]

情况二：字符不同

假设：

word1[i-1] != word2[j-1]

例如：

horse
ros

最后一个字符不同。

此时有三种选择。

1. 删除

删除 word1 的最后一个字符：

horse
↓
hors

问题变成：

dp[i-1][j]

再加一次删除操作：

dp[i-1][j] + 1

2. 插入

向 word1 末尾插入一个字符：

hors
↓
horse

对应：

dp[i][j-1]

再执行一次插入：

dp[i][j-1] + 1

3. 替换

直接修改最后一个字符：

horse
↓
rorse

对应：

dp[i-1][j-1]

加一次替换：

dp[i-1][j-1] + 1

综合状态转移方程

因此得到：

dp[i][j]=\\min\\left(dp[i-1][j]+1,\\ dp[i][j-1]+1,\\ dp[i-1][j-1]+cost\\right)

其中：

cost =
0 (字符相同)
1 (字符不同)

或者写成：

if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] =
min({
dp[i-1][j], // 删除
dp[i][j-1], // 插入
dp[i-1][j-1] // 替换
}) + 1;

初始化分析

动态规划中最容易忽略的部分就是边界条件。

第一列

dp[i][0]

表示：

word1前i个字符
→
空串

唯一办法：

全部删除

因此：

dp[i][0] = i;

第一行

dp[0][j]

表示：

空串
→
word2前j个字符

只能不断插入：

dp[0][j] = j;

DP表格演示

以：

word1 = horse
word2 = ros

为例：

最终：

dp[5][3]

即：

3

代码实现

class Solution {
public:
int minDistance(string word1, string word2) {

int m = word1.size();
int n = word2.size();

vector<vector<int>> dp(
m + 1,
vector<int>(n + 1, 0)
);

// 初始化
for(int i = 0; i <= m; i++)
dp[i][0] = i;

for(int j = 0; j <= n; j++)
dp[0][j] = j;

// 状态转移
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if(word1[i-1] == word2[j-1])
{
dp[i][j] = dp[i-1][j-1];
}
else
{
dp[i][j] =
min({
dp[i-1][j], // 删除
dp[i][j-1], // 插入
dp[i-1][j-1] // 替换
}) + 1;
}
}
}

return dp[m][n];
}
};

空间优化

观察状态转移：

dp[i][j]

仅依赖于：

dp[i-1][j]
dp[i][j-1]
dp[i-1][j-1]

即：

• 当前行

• 上一行

因此可以压缩成：

O(n)

空间复杂度。

优化后：

时间复杂度：O(mn)

空间复杂度：O(n)

编辑距离的现实应用

编辑距离远不止是一道算法题。

它广泛应用于工业系统。

搜索引擎纠错

用户输入：

googel

系统自动纠正：

google

因为：

EditDistance(googel, google)=2

拼写检查器

例如：

• Microsoft Word

• VSCode

• IntelliJ IDEA

都会计算候选词的编辑距离。

DNA序列比对

生物信息学中：

ACTGCA
ACTACA

可以通过编辑距离衡量基因序列相似度。

OCR文字识别

识别结果：

ChatGP7

真实结果：

ChatGPT

编辑距离：

1

系统可以自动修正。

动态规划思想总结

编辑距离是动态规划中的经典代表问题，其核心思想可以概括为：

最终建立最优子结构关系。

从算法体系角度看，编辑距离与：

• 最长公共子序列（LCS）

• 最长公共子串

• 不同的子序列

• 正则表达式匹配

共同构成了字符串动态规划（String DP）的重要基础，其思想在自然语言处理、生物信息学以及搜索推荐系统中均具有广泛应用价值。