编辑距离：误差测量者

算法背后的故事：拼写错误

想象你是一位老师，正在批改拼写测试。

• 学生写了：“KITTEN”
• 正确单词是：“SITTING”

你应该扣多少分？

1. 把 ‘K’ 替换为 ‘S’ -> SITTEN
2. 在 ‘S’ 后面插入 ‘I’ -> SIITTEN (等等，这不对…)
3. 让我们再试一次：
   • K -> S (替换)
   • I -> I (匹配)
   • T -> T (匹配)
   • T -> T (匹配)
   • E -> I (替换)
   • N -> N (匹配)
   • 结尾 -> 添加 G (插入)

总操作数：3。 这个数字 3 就是 Levenshtein 距离 (编辑距离)。它是将一个字符串转换为另一个字符串所需的 插入、删除 或 替换 的最小次数。

为什么需要它？

• 拼写检查器： “您是不是要找…？”如果你输入 “Gogle”，它到 “Google” 的距离是 1，到 “Apple” 的距离是 4。计算机建议 “Google”。
• DNA 对齐： 比较两个基因序列，看两个物种的亲缘关系有多近。
• 查重检测： 测量两篇文章的相似度，即使学生修改了几个词。

算法是如何“思考”的

该算法使用 动态规划 (Dynamic Programming)。它构建一个网格（矩阵），其中 cell[i][j] 表示 Word A 的前 i 个字符和 Word B 的前 j 个字符之间的距离。

网格规则：

• 如果字符匹配：没有成本。cell[i][j] = cell[i-1][j-1]
• 如果不匹配：取三个选项中的最小值 + 1 成本：
  1. 插入： 看左边 (cell[i][j-1])
  2. 删除： 看上面 (cell[i-1][j])
  3. 替换： 看对角线 (cell[i-1][j-1])

工程决策：复杂度

• 时间： $O(N imes M)$，其中 N 和 M 是字符串长度。
• 空间： $O(N imes M)$ 用于完整矩阵。
• 优化： 你只需要上一行就能计算当前行。所以空间可以降低到 $O(min(N, M))$。

实现参考 (Python)

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    
    # 创建大小为 (m+1) x (n+1) 的矩阵
    # 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 # 将 s1[:i] 变为空字符串需要 i 次删除
    for j in range(n + 1):
        dp[0][j] = j # 将空字符串变为 s2[: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][j - 1],    # 插入
                    dp[i - 1][j],    # 删除
                    dp[i - 1][j - 1] # 替换
                )
    
    return dp[m][n]

# 使用示例
print(f"距离: {levenshtein_distance('kitten', 'sitting')}") # 输出: 3

小结

编辑距离教会我们：差异是可以量化的。通过将“相似性”这样模糊的概念分解为具体的原子动作（插入、删除、替换），我们可以教计算机理解人类的错误。它提醒我们，在一个充满噪音的世界里，测量预期与现实之间差距的能力，是弥合差距的第一步。