跳到主要内容

字符串编辑距离

字符串编辑距离（Edit Distance），也称为 Levenshtein 距离，是衡量两个字符串之间相似度的一种方法。它表示将一个字符串转换为另一个字符串所需的最少操作次数。这些操作包括插入、删除和替换字符。

什么是字符串编辑距离？​

假设我们有两个字符串 str1 和 str2，我们希望将 str1 转换成 str2。为了实现这一目标，我们可以执行以下三种操作：

  1. 插入：在 str1 中插入一个字符。
  2. 删除：从 str1 中删除一个字符。
  3. 替换：将 str1 中的一个字符替换为另一个字符。

字符串编辑距离就是通过上述操作将 str1 转换成 str2 所需的最少操作次数。

示例​

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

  1. 替换 k 为 s："sitten"。
  2. 替换 e 为 i："sittin"。
  3. 插入 g："sitting"。

因此，"kitten" 和 "sitting" 之间的编辑距离为 3。

动态规划解决方案​

字符串编辑距离问题可以通过动态规划（Dynamic Programming, DP）高效解决。动态规划的核心思想是将问题分解为子问题，并存储子问题的解以避免重复计算。

定义状态​

我们定义一个二维数组 dp，其中 dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最少操作次数。

状态转移方程​

  1. 如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1]，因为不需要任何操作。
  2. 如果 str1[i-1] != str2[j-1]，则 dp[i][j] 可以通过以下三种操作之一得到：
    • 插入：dp[i][j-1] + 1
    • 删除：dp[i-1][j] + 1
    • 替换：dp[i-1][j-1] + 1
    我们需要取这三种操作中的最小值。

初始化​

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

代码实现​

以下是 Python 实现：

python
def minDistance(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] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    
    return dp[m][n]

示例输入和输出​

python
str1 = "kitten"
str2 = "sitting"
print(minDistance(str1, str2))  # 输出: 3

实际应用场景​

字符串编辑距离在许多领域都有广泛应用，例如：

  1. 拼写检查：计算用户输入的单词与字典中单词的编辑距离，以提供拼写建议。
  2. 生物信息学：比较 DNA 序列或蛋白质序列的相似性。
  3. 自然语言处理：用于文本相似度计算、机器翻译等任务。

总结​

字符串编辑距离是一个经典的动态规划问题，通过定义状态和状态转移方程，我们可以高效地解决它。掌握这一算法不仅有助于理解动态规划的核心思想，还能在实际应用中解决许多与字符串相关的问题。

附加资源与练习​

  • 练习：尝试实现一个函数，计算两个字符串的编辑距离，并输出具体的操作步骤。
  • 扩展阅读：了解其他字符串相似度算法，如 Jaro-Winkler 距离 和 Hamming 距离。
提示

如果你对动态规划的其他应用感兴趣，可以继续学习背包问题、最长公共子序列等经典问题。