编辑距离(Levenshtein’s)算法实例详解

目标

72. 编辑距离

给你两个单词 word1word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

说实话,我看不懂 LC 上的题解 —— 虽然看完能照猫画虎代码,但是对于原理还是不清不楚。不给实例分析的题解都是耍流氓(暴论)。

概念铺垫

代表串:假设有字符串 w,则下标 i 处的字符为 w [i],其代表串为 w [i] 之前的子串(切片) w [0:i-1](也即 w 从头算起长度为 i 的子串)。

举个例子,现有字符串 pluveto,则 w [3] 代表串为 pluw [0] 代表串为 $\varepsilon$ (空串)。

【定义】 $f (i,j)$ 表示将 w [i] 代表串,变成 w [j] 代表串所需的最小步骤数。

这里的步骤,就是执行操作的个数,允许的操作已经在题目中给出。

DP 表的解释

以下面的表为例,从上到下是 i 增加的方向,从左到右是 j 增加的方向。坐标从 0 起(对应轴上的空白),比如下面写着 0 的格子,其坐标是 $(0,0)$.

image-20211116130103287

初始化 DP 数组,尝试寻找规律

$f (0,0)$ ,将 (空串) 变成 (空串) 需要 0 步,无脑填 0.

image-20211116130103287

$f (0,1)$,将空串变 a 需要一步插入,填 1.

image-20211116130248455

f (0,2),将空串变 ab 需要两步插入,填 2. 相当于 $f (0,1) + 1$。

image-20211116130311488

同理:

image-20211116130339793

接下来,将 f (1) 所代表的串 a 变成空串,需要 1 步删除。

image-20211116130454338

同理,将 (2,0) 代表的串 ab 变成空串,需要 2 步删除。相当于 $f (1,0)+1$。

image-20211116130544923

其余同理。

image-20211116130624884

归纳:如何利用历史状态计算新状态?

重点来了。下面我们填写 $f (1,1)$。即w1 [1] 的代表串 a 变成 w2 [1] 的代表串 a(本次求值目标)

image-20211116142625573

(请时刻关注上面这个求职目标的位置)

我们有三种操作的方法,插入,删除,替换,对应三种情况:

插入的情况

第一种情况,先将 w1 [i-1] 代表串变成即 w2 [i] 代表串。需要 f (0,1)=1 次操作:

image-20211116131028633

这种操作之后,再将 w1 [i-1] 代表串之后插入一个 a,即可得到本次求值目标。这种情况下 $f (1,1) = f (0,1) + 1 = 1+1=2$。

其中 f (1,1) 表示本次求值目标,

f (0,1) 表示 w1 [i-1] 代表串变成 w2 [i] 代表串 所需次数,查表得到 $1$。

1 表示 w1 [i-1] 代表串 之后再插入一个 a 这一次动作的计数。

替换的情况

第二种情况,先将 w1 [i-1] 代表串(空串)变成 w2 [i-1] 代表串(空串)。需要 f (0,0)=0 次操作。

image-20211116131612384

然后再把 w2 [i] 代表串替换为 w1 [i] 即可得到本次求值目标,实现两串相同。由于替换的字符恰好等于 w2 [i] 的字符,即不需要替换,即代价为 0。这种情况下,$f (1,1)=f (0,0)+0=0$.

删除的情况(等价于插入)

第三种情况,先将 w1 [i] 代表串 a 经过变成 w2 [j-1] 代表串(空串)。查表需要 f (1,0)=1 次操作。

image-20211116131612384

然后再在 w2 [j-1] 代表串(空串)之后插入一个 a 即可得到本次求值目标,这种情况下,进行了一次操作,代价为 1,$f (1,1)=f (1,0)+0=1+0=1$.

也可以理解为在 w1 [i] 最后删除一个 a,对 w2 插入和对 w1 删除就代价和效果而言是等价的

image-20211116132110812

上面三种操作,代价最小的是第二种,所以我们取 $f (1,1)=\min (1,0,1) = 0$:

image-20211116132252326

发现,实际上求 $f (i,j)$,就是求左上角、正上方、正左方的(单元格的值各自与其对应后续操作的开销的和)的最小值: $\min\{f (i-1,j) + c_1,f (i-1,j-1)+c_2,f (i,j-1)+c_3\} = \min (C_1,C_2,C_3)$

有个细节在于 $c_1,c_2,c_3$ 的计算。$c_1,c_3$ 是插入和删除操作(或者可以都看成插入),开销固定是 1.

$c_2$ 是替换操作,w1 [i] == w2 [i] 即字符相同时不用替换,开销是 0,不同时替换,开销是 1.

至于为啥?

为了读者更好地理解,我们不糊弄过去,下面看个例子。求值目标是 $f (i,j) = f (3,2)$:

image-20211116140338877

在这一步发现。周围开销最小的是上方,即 $f (i-1,j)=f (2,2)=0$,即意味着,只要经过 0 步,就可以把 w1 [i-1] 代表串 ab,变成 $w2 [j]$ 代表串 ab. 这没问题。此时 w1 [i]==w2 [j]=='b',我们怎么办?

我们令 $C_1 = f (i-1,j) + c_1$ $C_2 = f (i-1,j-1) + c_2$ $C_3 = f (i,j-1) + c_3$

  • 怎么求 $C_1$ ?让 w1 [i-1] 代表串 ab 变成 w2 [j] 代表串 ab 的开销是 0,要经过一步插入,所以 $c_1 =1$,$C_1 = 1+1=2$
  • 同理让 w1 [i] 代表串 abb 变成 w2 [j-1] 代表串 a 的开销是 2(上表 $f (i,j-1)$),然后要经过一步删除,所以 $c_3 =1 $,$C_3 = 2+1=3$
  • 再看 $C_2$,由于 $f (i-1,j-1)$ 即让 w1 [i-1] 代表串(ab)变成 w2 [j-1] 代表串(a)的开销是 $f (i-1,j-1) = 1$,而 w1 [i]==w2 [j],所以 $c_2 = 0$,故 $C_2 = 1+0 = 1$

所以 $f (i,j) = \min \{C_1,C_2,C_3\} = \min\{2,1,3\} = 1$:

image-20211116141024276

重复此过程,得到:

image-20211116141126811

最右下角就是答案:

image-20211116141223357

用代码表达出来

掌握了手算的方法,剩下的就是代码实现。

参考代码:

inline int min3(int a, int b, int c) {
  return a < b ? (c < a ? c : a) : (b > c ? c : b);
}

class Solution {
public:
  int minDistance(string w1, string w2) {
    int n = w1.size();
    int m = w2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    //-- 初始化基本情况
    // +-------> y
    // |
    // x
    //
    // 第一列的各行
    for (int i = 1; i <= n; i++) {
      dp[i][0] = i;
    }
    // 第一行的各列
    for (int j = 1; j <= m; j++) {
      dp[0][j] = j;
    }
    //-- 开始 DP
    for (int i = 1; i <= n; i++) {   // 各行
      for (int j = 1; j <= m; j++) { // 各列
        auto c1 = dp [i - 1][j] + 1;  // 上
        auto cc2 = w1[i - 1] == w2[j - 1] ? 0 : 1;
        auto c2 = dp [i - 1][j - 1] + cc2; // 左上
        auto c3 = dp [i][j - 1] + 1;   // 左
        dp[i][j] = min3(c1, c2, c3);
      }
    }

    return dp[n][m];
  }
};

空间优化

$f (i,j)$ 只依赖当前行和前一行。但是初始化的时候却要初始化最左列全部。如果优化为 $O (m)$ 空间,势必要破坏最左列的初始化。但是注意到初始化的结构和遍历的结构很像,只要把 “第一列的各行” 初始化放到后面就行:

class Solution {
public:
  int minDistance(string w1, string w2) {
    int n = w1.size();
    int m = w2.size();
    int d = 2;
    vector<vector<int>> dp(d, vector<int>(m + 1, 0));
    // 第一行的各列
    for (int j = 1; j <= m; j++) {
      dp[0][j] = j;
    }
    //-- 开始 DP
    for (int i = 1; i <= n; i++) { // 各行
      dp [i % d][0] = i; // 初始化移动到这儿了
      for (int j = 1; j <= m; j++) {      // 各列
        auto c1 = dp [(i - 1) % d][j] + 1; // 上
        auto cc2 = w1[i - 1] == w2[j - 1] ? 0 : 1;
        auto c2 = dp [(i - 1) % 2][j - 1] + cc2; // 左上
        auto c3 = dp[i % d][j - 1] + 1;
        dp[i % d][j] = min3(c1, c2, c3);
        // print_vec_2d(dp);
      }
    }

    // print_vec_2d(dp);

    return dp[n % 2][m];
  }
};

优化后的空间复杂度变成 $O (2m)$,有所进步。

image-20211116151354731

进一步空间优化

我们还可以进一步优化为 $O (m)$,即只用一个额外数组。画个图就懂了:

image-20211116153132242

可以注意到,每一步所依赖的范围,只有这一行的元素个数 + 1,即 $m+1$。其余左上角前面的值、问号后面的值是什么,我们并不关心。据此,可以滚动这个 m+1 的空间求值。

image-20211116153053355

下面是进一步优化的结果:

class Solution {
public:
  int minDistance(string w1, string w2) {
    int n = w1.size();
    int m = w2.size();
    if (n == 0)
      return m;
    if (m == 0)
      return n;
    std::vector<int> dp(m + 1);
    for (int c = 0; c < m + 1; c++) {
      dp[c] = c;
    }
    for (int r = 1; r < n + 1; r++) {
      int pre = r;
      for (int c = 1; c < m + 1; c++) {
        int cur = min(dp[c], pre) + 1;
        if (w1[r - 1] == w2[c - 1]) {
          cur = min(cur, dp[c - 1]);
        } else {
          cur = min(cur, dp[c - 1] + 1);
        }
        dp[c - 1] = pre;
        pre = cur;
        if (c == m)
          dp[c] = cur;
      }
    }
    return dp[m];
  }
};