在自然语言处理、拼写纠错、模糊搜索等场景中，我们经常需要衡量两个字符串之间的相似度。编辑距离（Edit Distance） 就是一个经典的衡量方式，它描述了将一个字符串转换为另一个字符串所需的最少操作次数。
一、问题定义：什么是编辑距离？
编辑距离，也称为 Levenshtein Distance，指的是将字符串 A 转换成字符串 B 所需的最少操作次数。操作允许：
- • 插入一个字符（Insert）
- • 删除一个字符（Delete）
- • 替换一个字符（Replace）
示例：
A = "kitten" B = "sitting" 编辑距离 = 3 解释： kitten → sitten（k → s） → sittin（e → i）→ sitting（插入 g）
二、应用场景
编辑距离广泛应用于：
- • 搜索引擎模糊匹配（例如：“gooogle” 应该匹配 “google”）
- • 拼写检查和自动纠正
- • 语音识别、OCR纠错
- • DNA序列比对
三、解决思路：动态规划（DP）
1. 状态定义
设 dp[i][j] 表示将字符串 A 的前 i 个字符转换成字符串 B 的前 j 个字符所需的最小操作数。
2. 状态转移方程
我们可以从三个方向转移过来：
- • 插入：
dp[i][j-1] + 1（B 多了个字符） - • 删除：
dp[i-1][j] + 1（A 多了个字符） - • 替换或匹配：
dp[i-1][j-1] + cost
- • 如果
A[i-1] == B[j-1]，cost = 0 - • 否则
cost = 1
最终状态转移为：
dp[i][j] = min( dp[i-1][j] + 1, // 删除 dp[i][j-1] + 1, // 插入 dp[i-1][j-1] + cost // 替换/匹配 )
3. 初始化
- •
dp[0][j] = j：将空串变成 B 前 j 个字符需要插入 j 次； - •
dp[i][0] = i：将 A 前 i 个字符变成空串需要删除 i 次。
四、Go语言实现
动态规划二维实现：
package main import ( "fmt" "math" ) func MinDistance(a, b string) int { m, n := len(a), len(b) dp := make([][]int, m+1) // 初始化二维数组 for i := range dp { dp[i] = make([]int, n+1) } // 初始化第一列和第一行 for i := 0; i <= m; i++ { dp[i][0] = i } for j := 0; j <= n; j++ { dp[0][j] = j } // 状态转移 for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { cost := 0 if a[i-1] != b[j-1] { cost = 1 } dp[i][j] = min( dp[i-1][j]+1, // 删除 dp[i][j-1]+1, // 插入 dp[i-1][j-1]+cost, // 替换/匹配 ) } } return dp[m][n] } func min(a, b, c int) int { return int(math.Min(float64(a), math.Min(float64(b), float64(c)))) } func main() { a := "kitten" b := "sitting" fmt.Printf("编辑距离 between '%s' and '%s' is: %d\n", a, b, MinDistance(a, b)) }
五、运行示例
输入： a = "kitten" b = "sitting" 输出： 编辑距离 between 'kitten' and 'sitting' is: 3
六、时间与空间复杂度分析
- • 时间复杂度：O(m * n)
因为我们遍历了大小为 m x n 的二维数组； - • 空间复杂度：O(m * n)
用于存储状态的二维数组。
七、空间优化版本（滚动数组）
可以优化为一维数组来降低空间：
func MinDistanceOptimized(a, b string) int { m, n := len(a), len(b) prev := make([]int, n+1) curr := make([]int, n+1) // 初始化第一行 for j := 0; j <= n; j++ { prev[j] = j } for i := 1; i <= m; i++ { curr[0] = i for j := 1; j <= n; j++ { cost := 0 if a[i-1] != b[j-1] { cost = 1 } curr[j] = min( curr[j-1]+1, // 插入 prev[j]+1, // 删除 prev[j-1]+cost, // 替换 ) } prev, curr = curr, prev } return prev[n] }
八、拓展：支持更多操作的变种编辑距离
- • Damerau-Levenshtein 距离：除了插入、删除、替换，还支持交换相邻字符；
- • 带权重的编辑距离：不同操作赋予不同代价；
- • 相似度计算：将编辑距离转为百分比相似度，比如：
similarity := 1 - float64(distance) / float64(max(len(a), len(b)))
九、实战应用场景举例
| 场景 | 作用描述 |
| 搜索引擎 | 用户输入有误时自动推荐相似关键词 |
| 拼写检查 | IDE、文本编辑器纠正英文单词 |
| 语音/图像识别后处理 | 自动修正识别错误的单词序列 |
| 文件比对工具 | 如 Git diff、文本比较器 |
| 生物信息学 | DNA/RNA 序列比对、蛋白质比对 |
十、总结
| 点位 | 内容 |
| 算法思想 | 动态规划 |
| 实现结构 | dp[i][j] 表示 A 的前 i 个字符转换为 B 的前 j 个字符的最小编辑距离 |
| 时间复杂度 | O(m * n) |
| 空间优化 | 支持优化为滚动数组，空间降为 O(n) |
| 实战价值 | 应用场景极广，从 NLP 到搜索再到生物信息学 |
