第 55 课 - 编辑距离 (Levenshtein Distance)

1. 学习目标

完成本课学习后，你应该能够：

理解编辑距离的定义：明确编辑距离是衡量两个字符串之间差异的最小操作次数。
掌握动态规划解法：理解如何通过构建二维数组来分解和解决这个子问题。
实现编辑距离算法：能够独立编写计算两个字符串编辑距离的代码。
分析算法复杂度：理解该算法的时间复杂度和空间复杂度。
认识实际应用：了解编辑距离在拼写检查、DNA序列比对、差异比较等领域的应用。

2. 核心概念

编辑距离，也称为Levenshtein 距离，是指将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。允许的编辑操作有三种：

插入：在字符串中插入一个字符。
删除：从字符串中删除一个字符。
替换：将字符串中的一个字符替换为另一个字符。

问题定义：给定两个字符串 str1 (长度为 m) 和 str2 (长度为 n)，计算 str1 转换为 str2 所需的最小编辑距离。

动态规划思路：这是动态规划的经典问题，因为原问题的解可以由子问题的解组合而成，并且子问题之间存在大量重叠。

我们定义一个二维数组 dp，其中 dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最小编辑距离。

状态 i：表示考虑了 str1 的前 i 个字符。
状态 j：表示考虑了 str2 的前 j 个字符。
dp[m][n]：就是最终答案。

状态转移方程：要计算 dp[i][j]，我们考虑 str1 的第 i 个字符（记为 c1）和 str2 的第 j 个字符（记为 c2）：

如果 c1 == c2，那么这两个字符已经匹配，无需操作。dp[i][j] = dp[i-1][j-1]。
如果 c1 != c2，我们需要进行一次编辑操作（插入、删除或替换），并选择使总操作数最小的那一种。
- 插入：在 str1 的 c1 后插入 c2。这等价于 str1[0..i] 和 str2[0..j-1] 已匹配，然后再插入 c2。dp[i][j] = dp[i][j-1] + 1。
- 删除：删除 str1 的 c1。这等价于 str1[0..i-1] 和 str2[0..j] 已匹配，然后再删除 c1。dp[i][j] = dp[i-1][j] + 1。
- 替换：将 c1 替换为 c2。这等价于 str1[0..i-1] 和 str2[0..j-1] 已匹配，然后再进行一次替换。dp[i][j] = dp[i-1][j-1] + 1。综上，当 c1 != c2 时：dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1。

初始化：

dp[i][0] = i：将 str1 的前 i 个字符转换为空串，需要删除 i 次。
dp[0][j] = j：将空串转换为 str2 的前 j 个字符，需要插入 j 次。

3. 代码示例

以下是一个完整、可运行的 Python 实现，用于计算两个字符串的最小编辑距离。

def min_edit_distance(str1, str2):
    """
    计算两个字符串之间的最小编辑距离 (Levenshtein Distance)
    :param str1: 源字符串
    :param str2: 目标字符串
    :return: 最小编辑操作次数
    """
    m = len(str1)
    n = len(str2)
    
    # 创建一个 (m+1) x (n+1) 的二维数组 dp，初始化为 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化边界条件
    # dp[i][0] 表示将 str1[0..i-1] 转换为空串的操作数，显然是 i (删除 i 个字符)
    for i in range(m + 1):
        dp[i][0] = i
    # dp[0][j] 表示将空串转换为 str2[0..j-1] 的操作数，显然是 j (插入 j 个字符)
    for j in range(n + 1):
        dp[0][j] = j
    
    # 填充 dp 表
    # i 从 1 到 m，j 从 1 到 n
    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:
                # 如果字符不同，则取左、上、左上三个方向的最小值，并 +1
                # dp[i-1][j-1] 对应替换操作
                # dp[i][j-1]   对应插入操作 (在 str1 末尾插入 str2 的字符)
                # dp[i-1][j]   对应删除操作 (删除 str1 的当前字符)
                dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
    
    # dp[m][n] 即为最终结果
    return dp[m][n]

# 测试用例
if __name__ == "__main__":
    word1 = "kitten"
    word2 = "sitting"
    distance = min_edit_distance(word1, word2)
    print(f"‘{word1}’ 和 ‘{word2}’ 的编辑距离是: {distance}")
    # 预期输出: 3 (kitten -> sitten (替换 'k'->'s'), sitten -> sittin (替换 'e'->'i'), sittin -> sitting (插入 'g'))

4. 实践练习

练习题 1 (基础)

题目：编写一个函数，接收两个单词作为输入，返回它们之间的编辑距离，并使用上面的测试用例验证你的函数。

word1 = "horse"
word2 = "ros"
# 你的代码
# 预期输出: 3 (horse -> rorse (替换 'h'->'r'), rorse -> rose (删除 'r'), rose -> ros (删除 'e'))

练习题 2 (进阶 - 不同代价)

题目：假设插入、删除和替换操作的代价分别为 insert_cost, delete_cost, replace_cost (通常 replace_cost 可能更高)。修改上面的函数，接受这三个代价参数，计算加权编辑距离。

def min_weighted_edit_distance(str1, str2, insert_cost=1, delete_cost=1, replace_cost=1):
    # 你的实现
    pass

# 测试
word1 = "intention"
word2 = "execution"
# 默认代价为1，预期输出: 5
# 如果替换代价为2，预期输出会更高，请你推导一下。

练习题 3 (挑战 - 空间优化)

题目：上面的实现使用了 O(m*n) 的空间。注意到状态 dp[i][j] 只依赖于 dp[i-1][...] 和 dp[i][...]。请尝试将算法优化到 O(min(m, n)) 的空间复杂度。（提示：可以使用两个一维数组滚动更新）。

5. 常见错误

索引混淆：dp 数组的维度是 (m+1) x (n+1)，但遍历字符串 str1 和 str2 时，使用的是索引 i-1 和 j-1。初学者容易搞错，导致 IndexError 或逻辑错误。
- 错误写法：if str1[i] == str2[j]:
- 正确写法：if str1[i-1] == str2[j-1]: (因为 i 和 j 从 1 开始，对应原字符串索引 0)
边界条件初始化遗漏：忘记初始化第一行 (dp[0][j]) 和第一列 (dp[i][0])。这会导致后续计算引用未初始化的值。
- 错误：只初始化 dp[0][0]=0。
- 正确：必须初始化 for i: dp[i][0] = i 和 for j: dp[0][j] = j。
状态转移方程理解错误：在字符不相等时，误以为只能进行替换操作，或者错误地理解了插入和删除操作对应的子问题。
- 关键：插入操作对应 dp[i][j-1]，删除操作对应 dp[i-1][j]，替换操作对应 dp[i-1][j-1]。可以结合子问题的含义进行记忆。
未考虑三种操作：在 min 函数中遗漏了某一个方向的值，导致结果不正确。
- 错误：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + 1 (遗漏了插入操作 dp[i][j-1])。

6. 小结

本课我们学习了编辑距离这一经典问题。

核心：编辑距离是衡量两个字符串差异的度量，通过插入、删除、替换三种操作计算最小代价。
解法：动态规划是求解此问题的标准方法。通过定义 dp[i][j] 表示子问题的解，并建立状态转移方程 dp[i][j] = dp[i-1][j-1] (if chars equal) else 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])，我们可以自底向上地填满整个表格。
复杂度：
- 时间复杂度：O(m * n)，需要填充整个 dp 表。
- 空间复杂度：O(m * n) (标准实现) 或 O(min(m, n)) (空间优化版本)。
应用：编辑距离在计算机科学中有广泛应用，如拼写检查、模糊搜索、生物信息学中的序列比对、版本控制中的差异比较算法等。掌握编辑距离，不仅学会了一个实用算法，更深化了对动态规划解决字符串问题思路的理解，为后续学习更复杂的序列问题打下坚实基础。

练习编辑器

rust