【动态规划】求解编辑距离问题

问题描述

编辑距离问题是求解将⼀个字符串转换为另⼀个字符串所需的插⼊、删除、替换的最小次数。$$\mathbb{COMMOM}\stackrel{sub}{\to }\mathbb{COMMUM}\stackrel{sub}{\to }\mathbb{COMMUN}\stackrel{ins}{\to }\mathbb{COMMUNE}$$上述将单词 COMMOM 变为 COMMUNE 共需要经过至少3次操作。

对编辑距离进行可视化，可以得到序列比对

• 第一行的空格表示插入
• 第二行的空格表示删除
• 具有不同字符的列表示替换

编辑距离 = 序列比对中具有不同字符的列数

最小编辑距离 = 最优序列比对中具有不同字符的列数

编辑距离问题也可以这么表述：
对于给定字符串$A[\mathrm{1...}m]$ 和 $B[\mathrm{1...}n]$ 求解他们的最小编辑距离 $D(m,n)$

---

递推关系

假设对 $\forall i<m,\forall j<n$，可以计算 $A[\mathrm{1...}i]$ 和 $B[\mathrm{1...}j]$的最小编辑距离 $D(i,j)$。

考虑 $A[\mathrm{1...}m]$ 和 $B[\mathrm{1...}n]$ 的最优比对，可以发现如下规律：

1. 最后⼀列不可能是两个空格
2. 某个串为空串时，最小编辑距离是另⼀个串的长度
3. $A[m]$ 和 $B[n]$ 都存在：$D(m,n)=D(m-1,n-1)+(A[m]=B[n]?0:1)$
4. $A[m]$ 和 $B[n]$ 有一方为空，删除不为空的那一个： D ( m , n ) = { D ( m − 1 , n ) + 1 A [ m ] a n d − D ( m , n − 1 ) + 1 B [ n ] a n d − D(m,n) =
   {D(m−1,n)+1A[m]and−D(m,n−1)+1B[n]and−" role="presentation" style="position: relative;">{D(m−1,n)+1D(m,n−1)+1A[m]and−B[n]and−$$\{\begin{array}{ll}D(m-1,n)+1& A[m]and-\\ D(m,n-1)+1& B[n]and-\end{array}$$
   D(m,n)={D(m−1,n)+1D(m,n−1)+1​A[m]and−B[n]and−​
5. 综上，只需要沿着三条路径递归得到最小的那条 D ( m , n ) = { i i f j = 0 j i f i = 0 min ⁡ { D ( m − 1 , n ) + 1 D ( m , n − 1 ) + 1 D ( m − 1 , n − 1 ) + ( A [ m ] = B [ n ] ? 0 : 1 ) o t h e r w i s e D(m,n) =
   \begin{cases} i &if\quad j=0\\ j &if\quad i=0 \\ \min \begin{cases} D(m − 1,n) + 1 \\ D(m, n − 1) + 1 \\ D(m − 1,n − 1) + (A[m] = B[n]?0 : 1) \end{cases}" role="presentation" style="position: relative;">\begin{cases} i &if\quad j=0\\ j &if\quad i=0 \\ \min \begin{cases} D(m − 1,n) + 1 \\ D(m, n − 1) + 1 \\ D(m − 1,n − 1) + (A[m] = B[n]?0 : 1) \end{cases}$$\text{begin{cases} i \&ifquad j=0 j \&ifquad i=0 min begin{cases} D(m − 1,n) + 1 D(m, n − 1) + 1 D(m − 1,n − 1) + (A[m] = B[n]?0 : 1) end{cases}}$$
   &otherwise \end{cases} D(m,n)=⎩ ⎨ ⎧​ijmin⎩ ⎨ ⎧​D(m−1,n)+1D(m,n−1)+1D(m−1,n−1)+(A[m]=B[n]?0:1)​​ifj=0ifi=0otherwise​
6. 时间复杂度：$O(mn)$ ； 空间复杂度：$O(mn)$。

---

运行实例

对于每个 $D[i,j]$, 都可以通过 $D[i-1,j-1]$; $D[i-1,j]$; $D[i,j-1]$这三个点得到而这三个点又分别对应 替换；删除；插入三种操作。

通过上述递推关系，我们可以自上而下，自左向右构造记录表。在填完记录表后右下角的那个值即为最小编辑距离。接着就是使用回溯的方式，构造满足最小编辑距离的最优比对（如下图右侧所示）

#include 
#include 
#include 
#include 

using namespace std;

// 计算最小编辑距离，并返回最小编辑距离的值，计算编辑距离表dp
int minEditDistance(const string& word1, const string& word2, vector<vector<int>>& dp) {
    int m = word1.length();
    int n = word2.length();

    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == 0) {
                dp[i][j] = j;
            }
            else if (j == 0) {
                dp[i][j] = i;
            }
            else if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else {
                dp[i][j] = 1 + min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] });
            }
        }
    }

    return dp[m][n];
}

// 通过回溯法找到所有满足最小编辑距离的操作序列。
void findAllSequences(const string& word1, const string& word2, int i, int j, const string& sequence, vector<string>& sequences, vector<vector<int>>& dp) {
    if (i == 0 && j == 0) {
        sequences.push_back(sequence);
        return;
    }

    if (i > 0 && j > 0 && word1[i - 1] == word2[j - 1]) {
        findAllSequences(word1, word2, i - 1, j - 1, "No operation: " + string(1, word1[i - 1]) + " -> " + string(1, word2[j - 1]) + "\n" + sequence, sequences, dp);
    }

    if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + 1) {
        findAllSequences(word1, word2, i - 1, j - 1, "Replace: " + string(1, word1[i - 1]) + " -> " + string(1, word2[j - 1]) + "\n" + sequence, sequences, dp);
    }

    if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
        findAllSequences(word1, word2, i - 1, j, "Delete: " + string(1, word1[i - 1]) + " \n" + sequence, sequences, dp);
    }

    if (j > 0 && dp[i][j] == dp[i][j - 1] + 1) {
        findAllSequences(word1, word2, i, j - 1, "Insert: " + string(1, word2[j - 1]) + " \n" + sequence, sequences, dp);
    }
}

int main() {
    string word1 = "ALTRUISTIC";
    string word2 = "ALGORITHM";

    vector<vector<int>> dp(word1.length() + 1, vector<int>(word2.length() + 1, 0));

    int minDistance = minEditDistance(word1, word2, dp);

    cout << "Minimum Edit Distance between " << word1 << " and " << word2 << " is: " << minDistance << endl;

    vector<string> sequences;
    findAllSequences(word1, word2, word1.length(), word2.length(), "", sequences, dp);

    cout << "Operations to convert " << word1 << " to " << word2 << " are: " << endl;
    for (const string& seq : sequences) {
        cout << seq << "----------"<< endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

运行结果：

---

时空复杂度优化

现在我们已经可以计算最小编辑距离，同时构造出最优比对。他们的时空复杂度总结如下：

从实际情况来看，$O(mn)$ 的空间比 $O(mn)$ 的时间更难满足，比如当 $m=n=10^5$ 时

• 时间上：执行$10^{10}$次指令大约需要10秒（假设CPU每秒执行$10^9$条指令）
• 空间上：需要$10^{10}$bits，大约 40 GB

那么能否使用 $O(m+n)$ 的空间来构造最优比对呢？

答：可以使用 Hirschberg 算法。

---

Hirschberg 算法

Hirschberg 算法是一种高效的线性空间动态规划算法。它通过使用分治策略来降低空间复杂度，从而在线性空间内计算最优比对。

该算法的思想基于以下洞察力：

• 在动态规划算法中，通常使用二维矩阵来存储中间状态，这导致了 $O(mn)$ 的空间复杂度。
• 但实际上，可以通过观察计算过程中的对称性，将动态规划的空间复杂度降低到 $O(m+n)$。

在计算动态规划的过程中，我们观察到 $D(i,j)$ 的计算仅依赖于 $D(i-1,j)$、$D(i,j-1)$ 和 $D(i-1,j-1)$。基于此，我们可以利用两个长度为 n 的一维数组来存储中间状态，每次只需要保留上一行和当前行的信息。