【动态规划】求解编辑距离问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】求解编辑距离问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

问题描述

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

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

C	O	M	M	O	M	-
C	O	M	M	U	N	E

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

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

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

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

递推关系

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

C	O	M	M	O	M	-
C	O	M	M	U	N	E

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

最后⼀列不可能是两个空格
某个串为空串时，最小编辑距离是另⼀个串的长度
$A [m]$ 和 $B [n]$ 都存在： $D (m, n) = D (m - 1, n - 1) + (A [m] = B [n]? 0 : 1)$
$A [m]$ 和 $B [n]$ 有一方为空，删除不为空的那一个： $\begin{cases} D(m − 1,n) + 1 & A[m]\quad and \quad- \\ D(m, n − 1) + 1 & B[n]\quad and \quad- \\ \end{cases}$
综上，只需要沿着三条路径递归得到最小的那条 $\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} &otherwise \end{cases}$
时间复杂度： $O (mn)$ ；空间复杂度： $O (mn)$ 。

运行实例

字符串编辑动态规划求解的,算法学习,动态规划,算法,editDistance
对于每个 $D [i, j]$ , 都可以通过 $D [i - 1, j - 1]$ ; $D [i - 1, j]$ ; $D [i, j - 1]$ 这三个点得到而这三个点又分别对应替换；删除；插入三种操作。

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

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;
}

运行结果：

字符串编辑动态规划求解的,算法学习,动态规划,算法,editDistance

时空复杂度优化

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

	计算最小编辑距离	构造最优比对
时间	$O (mn)$	$O (m + n)$
空间	$O (mn)$	$O (mn)$

从实际情况来看， $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)$ 。

字符串编辑动态规划求解的,算法学习,动态规划,算法,editDistance
在计算动态规划的过程中，我们观察到 $D (i, j)$ 的计算仅依赖于 $D (i - 1, j)$ 、 $D (i, j - 1)$ 和 $D (i - 1, j - 1)$ 。基于此，我们可以利用两个长度为 n 的一维数组来存储中间状态，每次只需要保留上一行和当前行的信息。文章来源地址https://www.toymoban.com/news/detail-781563.html