编辑距离（Edit Distance）也被称为 Levenshtein 距离，是衡量两个字符串之间差异的一种方法。它通过将一个字符串转换成另一个字符串所需的最少编辑操作数来计算。这些编辑操作包括插入、删除和替换。

基本概念

编辑距离算法的核心思想是：通过计算两个字符串之间的最小编辑操作次数，来衡量它们之间的相似度。

计算方法

编辑距离算法通常使用动态规划的方法来计算。以下是动态规划解法的基本步骤：

  1. 创建一个二维数组 dp，大小为 (m+1) x (n+1)，其中 m 和 n 分别为两个字符串的长度。
  2. 初始化 dp[0][j] 和 dp[i][0] 为 i 或 j，因为将空字符串转换为另一个字符串的长度即为另一个字符串的长度。
  3. 遍历 dp 数组，对于每个位置 (i, j)，根据以下规则进行计算：
    • 如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1]；
    • 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

示例

假设我们有两个字符串 s1 = "kitten" 和 s2 = "sitting"，我们可以使用编辑距离算法来计算它们之间的距离。

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

    for i in range(m+1):
        for j in range(n+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif s1[i-1] == s2[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]

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

相关资源

如果你对编辑距离算法感兴趣，可以阅读以下文章进行深入学习：

图片展示

下面展示一些编辑距离算法的应用示例：

Levenshtein Distance
Edit Distance Example