字符串编辑距离

字符串编辑距离（Edit Distance），又称莱文斯坦距离（Levenshtein Distance），是衡量两个字符串之间相似程度的经典动态规划问题。它定义为将一个字符串转换为另一个字符串所需的最少单字符编辑操作次数（插入、删除或替换）。

定义与基本概念

给定两个字符串 $A$ 和 $B$，编辑距离 $d(A,B)$ 的计算基于以下操作：

• 插入（Insert）：在字符串中插入一个字符。
• 删除（Delete）：删除字符串中的一个字符。
• 替换（Replace）：将字符串中的一个字符替换为另一个字符。

例如，将 "kitten" 转换为 "sitting" 的编辑距离为 3：

1. kitten → sitten（替换 'k' 为 's'）
2. sitten → sittin（替换 'e' 为 'i'）
3. sittin → sitting（插入 'g'）

动态规划解法

编辑距离问题可以通过动态规划高效解决。定义 $dp[i][j]$ 表示字符串 $A[0..i-1]$ 和 $B[0..j-1]$ 之间的编辑距离。状态转移方程如下：

$dp[i][j]=\{\begin{array}{ll}i& \text{if }j=0,\\ j& \text{if }i=0,\\ dp[i-1][j-1]& \text{if }A[i-1]=B[j-1],\\ 1+\min (dp[i-1][j],dp[i][j-1],dp[i-1][j-1])& \text{otherwise.}\end{array}$

代码实现

以下是 Python 实现示例：

def edit_distance(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # 删除
                                   dp[i][j - 1],      # 插入
                                   dp[i - 1][j - 1])  # 替换
    return dp[m][n]

# 示例
print(edit_distance("kitten", "sitting"))  # 输出: 3

动态规划表解析

以 "kitten" 和 "sitting" 为例，动态规划表如下：

flowchart LR subgraph DP Table A[0,1,2,3,4,5,6,7] B[1,1,2,3,4,5,6,7] C[2,2,1,2,3,4,5,6] D[3,3,2,1,2,3,4,5] E[4,4,3,2,1,2,3,4] F[5,5,4,3,2,2,3,4] G[6,6,5,4,3,3,2,3] end

优化空间复杂度

上述算法空间复杂度为 $O(mn)$。可优化至 $O(\min (m,n))$，仅保留前一行的数据：

def edit_distance_optimized(str1, str2):
    m, n = len(str1), len(str2)
    if m < n:
        return edit_distance_optimized(str2, str1)
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr
    return prev[n]

实际应用案例

1. 拼写检查：如输入法建议最接近的正确单词。 2. 生物信息学：比较DNA序列的相似性。 3. 自然语言处理：模糊字符串匹配，如搜索引擎纠错。

案例：拼写纠正

假设用户输入 "helo"，候选词为 ["hello", "help", "hole"]。计算编辑距离：

• helo → hello: 1（插入 'l'）
• helo → help: 2（替换 'o' 为 'p'，插入 'p'）
• helo → hole: 1（替换 'e' 为 'o'）

优先推荐 "hello" 和 "hole"。

变种与扩展

• Damerau-Levenshtein 距离：增加相邻字符交换操作。
• 加权编辑距离：为不同操作分配不同权重。
• 最长公共子序列（LCS）：仅允许插入和删除操作。

总结

字符串编辑距离是动态规划的经典应用，通过分解子问题并存储中间结果，高效解决了字符串相似度计算问题。理解其原理有助于掌握更复杂的序列比对算法。