莱文斯坦距离

莱文斯坦距离是什么？

莱文斯坦距离，又被称为编辑距离，是衡量两个字符串之间相似度的一种度量方法。它定义了将一个字符串A转换成另一个字符串B所需的最少单字符编辑操作的次数

这些允许的单字符编辑操作有三种：

1. 插入（Insertion）：在字符串中插入一个字符
2. 删除（Deletion）：从字符串中删除一个字符
3. 替换（Substitution）：将字符串中的一个字符替换成另一个字符

莱文斯坦距离越小，说明两个字符串越相似。反之，距离越大，相似度越低

一个简单的例子

让我们用一个例子来直观地理解它

计算字符串 "kitten" 和 "sitting" 的莱文斯坦距离

1. "kitten" -> "sitten"（将 'k' 替换为 's'）
2. "sitten" -> "sittin"（将 'e' 替换为 'i'）
3. "sittin" -> "sitting"（在末尾插入 'g'）

总共需要 3 次编辑操作，所以 "kitten" 和 "sitting" 的莱文斯坦距离是 3

如何计算？

莱文斯坦距离通常使用动态规划（Dynamic Programming）算法来计算。这个方法的核心思想是构建一个二维矩阵，其中 dp[i][j] 存储的是字符串 A 的前 i 个字符与字符串 B 的前 j 个字符之间的编辑距离

矩阵的填充规则如下：

• 初始化：

  • dp[i][0] 等于 i（将 A 的前 i 个字符全部删除）
  • dp[0][j] 等于 j（将 B 的前 j 个字符全部插入）

• 递推关系：对于矩阵中的每一个 (i, j)，我们比较 A 的第 i 个字符和 B 的第 j 个字符：

  • 如果 A[i-1] 等于 B[j-1]，说明这两个字符相同，不需要编辑。此时 dp[i][j] = dp[i-1][j-1]
  • 如果 A[i-1] 不等于 B[j-1]，我们需要考虑三种操作的最小代价：
    • 插入：dp[i][j-1] + 1
    • 删除：dp[i-1][j] + 1
    • 替换：dp[i-1][j-1] + 1

  最终，dp[i][j] 取这三个值的最小值：dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 1)

最终，矩阵右下角的 dp[len(A)][len(B)] 就是两个字符串的莱文斯坦距离