编辑距离（Levenshtein Distance）
一、定义
编辑距离是指将一个字符串变换为另一个字符串所需的最少单字符编辑操作次数。允许的三种操作：
| 操作 | 含义 | 示例（s→t） |
|---|---|---|
| 插入（Insertion） | 在 s 中插入一个字符 | “kitten” → “kittens”（插入 ‘s’） |
| 删除（Deletion） | 从 s 中删除一个字符 | “kitten” → “kittn”（删除 ‘e’） |
| 替换（Substitution） | 将 s 中一个字符替换为另一个字符 | “kitten” → “kitten”（‘k’→’s’，得 “sitten”） |
每次操作代价为 1。距离越小，两字符串越相似。
二、动态规划计算
状态定义
dp[i][j]= 将s[0..i-1]（前 i 个字符）变换为t[0..j-1]（前 j 个字符）的最小编辑次数。
状态转移方程
若 s[i-1] == t[j-1]: dp[i][j] = dp[i-1][j-1] # 字符相同，无需操作 否则: dp[i][j] = 1 + min( dp[i-1][j], # 删除 s[i-1] dp[i][j-1], # 插入 t[j-1] dp[i-1][j-1] # 替换 s[i-1] 为 t[j-1] )边界条件
dp[i][0] = i # s 的前 i 个字符全部删除变为空串 dp[0][j] = j # 空串插入 j 个字符变为 t 的前 j 个字符计算示例：s = “kitten”, t = “sitting”
填充 DP 表（行= s，列= t）：
"" s i t t i n g "" 0 1 2 3 4 5 6 7 k 1 1 2 3 4 5 6 7 i 2 2 1 2 3 4 5 6 t 3 3 2 1 2 3 4 5 t 4 4 3 2 1 2 3 4 e 5 5 4 3 2 2 3 4 n 6 6 5 4 3 3 2 3dp[6][7] = 3，即 “kitten” → “sitting” 的编辑距离为3。
操作路径：
kitten → sitten (替换 k→s) sitten → sittin (替换 e→i) sittin → sitting (插入 g)复杂度
- 时间：
O(m·n)（m、n 为两串长度） - 空间：
O(m·n)，可优化为O(min(m,n))（滚动数组）
三、主要应用
1. 拼写纠错 / 输入纠错
计算用户输入与词典中候选词的编辑距离，取距离最小的作为纠正建议。
用户输入："recive" 词典候选：receive(d=2)、recite(d=3)、recipe(d=3) → 推荐 "receive"2. 模糊字符串匹配 / 搜索
- 数据库脏数据清洗：合并同一实体的不同写法（“北京天安门” vs “天安门北京”）
- 搜索引擎容错查询：用户输错一两个字符仍能命中
3. 生物信息学：DNA/蛋白质序列比对
编辑距离是序列对齐的基础，用于衡量基因序列相似度（替换/插入/删除对应突变/缺失/插入）。扩展为 Needleman-Wunsch、Smith-Waterman 等带权对齐算法。
4. 自然语言处理
- 词形归并：比较词干相似度
- OCR 纠错：识别结果与候选词对比
- 机器翻译评估：早期 MT 评价指标 WER（Word Error Rate）本质是词级编辑距离
5. 数据去重 / 实体匹配
记录链接场景中，比较姓名、地址等字段的相似度，判断是否为同一实体。
6. 语音识别评估
字错率（CER）/ 词错率（WER）= 编辑距离 / 参考文本长度，是语音识别的标准评测指标。
四、常见变体
| 变体 | 说明 |
|---|---|
| Damerau-Levenshtein | 额外允许相邻字符交换（transposition），更贴合键盘输入错误 |
| 加权编辑距离 | 不同操作赋予不同代价（如替换代价 2，插入/删除代价 1） |
| Jaro-Winkler | 强调前缀匹配，适合人名/短字符串相似度 |
| 最长公共子序列（LCS） | 仅允许插入/删除，无替换，等价于一种特殊编辑距离 |
五、一句话总结
编辑距离通过动态规划计算两字符串间最少单字符编辑操作数，时间复杂度O(m·n)；其核心价值是提供一种字符级相似度度量，广泛应用于拼写纠错、模糊匹配、序列比对、OCR/ASR 评测等需要"容错比较"的场景。
