编辑距离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(d2)、recite(d3)、recipe(d3) → 推荐 receive2. 模糊字符串匹配 / 搜索数据库脏数据清洗合并同一实体的不同写法“北京天安门” vs “天安门北京”搜索引擎容错查询用户输错一两个字符仍能命中3. 生物信息学DNA/蛋白质序列比对编辑距离是序列对齐的基础用于衡量基因序列相似度替换/插入/删除对应突变/缺失/插入。扩展为 Needleman-Wunsch、Smith-Waterman 等带权对齐算法。4. 自然语言处理词形归并比较词干相似度OCR 纠错识别结果与候选词对比机器翻译评估早期 MT 评价指标 WERWord Error Rate本质是词级编辑距离5. 数据去重 / 实体匹配记录链接场景中比较姓名、地址等字段的相似度判断是否为同一实体。6. 语音识别评估字错率CER/ 词错率WER 编辑距离 / 参考文本长度是语音识别的标准评测指标。四、常见变体变体说明Damerau-Levenshtein额外允许相邻字符交换transposition更贴合键盘输入错误加权编辑距离不同操作赋予不同代价如替换代价 2插入/删除代价 1Jaro-Winkler强调前缀匹配适合人名/短字符串相似度最长公共子序列LCS仅允许插入/删除无替换等价于一种特殊编辑距离五、一句话总结编辑距离通过动态规划计算两字符串间最少单字符编辑操作数时间复杂度O(m·n)其核心价值是提供一种字符级相似度度量广泛应用于拼写纠错、模糊匹配、序列比对、OCR/ASR 评测等需要容错比较的场景。
)
