无需删除操作的编辑距离算法

Question

我使用完整矩阵修改了 Levenshtein 距离算法形式 geeksforgeeks。我删除了删除操作 (prevRow[j])，现在它仅适用于输入字符串的特定顺序。

cout << levenshteinFullMatrix("hellox", "xhello"); // 5 correct 
cout <<levenshteinFullMatrix("xhello", "hellox"); // 2 wrong

有人可以告诉我应该如何修改下面的函数才能正确工作，并向我解释为什么它现在对函数参数的顺序敏感吗？

非常感谢

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;

int levenshteinFullMatrix(const string &str1, const string &str2) {
        int m = str1.length();
        int n = str2.length();

        // Initialize the DP table
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
        // Fill the first row and column (only insertions allowed)
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // Insertions to match str1 to an empty str2
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // Insertions to match an empty str1 to str2
        }
    
        // Compute the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1]; // No cost for matching characters
                } else {
                    // Minimum cost between insertion or replacement
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1]) + 1;
                }
            }
        }

}

// Drivers code
int main()
{
    // Function Call
    cout << levenshteinFullMatrix("hellox", "xhello"); // 5 correct 
    cout << levenshteinFullMatrix("xhello", "hellox"); // 2 wrong
    return 0;
}

我尝试编辑索引，在 google 和 StackOverflow 上搜索解决方案。

Answer 1

让我们首先看看您允许哪些编辑操作以及与它们关联的成本：
案例：匹配字符：

dp[i][j] = dp[i - 1][j - 1];

-> 成本为 0（操作 1）
案例：字符不匹配：我们取之间的最小值

dp[i - 1][j - 1]

-> 字符不匹配，替换成本为 1（操作 2）

dp[i][j - 1]

-> 在第二个字符串上追加一个字符，成本 1（操作 3）

我们已经可以看到您的编辑操作不是对称的，因此当我们交换字符串时结果可能会有所不同是有道理的。

现在让我们看看您提供的示例：

cout << levenshteinFullMatrix("hellox", "xhello"); // 5 correct 

"", "" -> 初始情况，总成本为 0
"h", "x" -> op2, 成本 1, 总成本为 1
"he", "xh" -> op2, 成本 1, 总成本为 2
"hel", "xhe" -> op2, 成本 1, 总成本为 3
"hell", "xhel" -> op1, 成本 0, 总成本为 3
"hello", "xhell" -> op2, 成本 1, 总成本为 4
"hellox", "xhello" -> op2, 成本 1, 总成本为 5

cout <<levenshteinFullMatrix("xhello", "hellox"); // 2 wrong

"x", "" -> 初始情况，总成本为 1
"xh", "h" -> op1, cost , 总成本为 1
"xhel", "hel" -> op1, 成本 0, 总成本为 1
"xhell", "hell" -> op1, 成本 0, 总成本为 1
"xhello", "hello" -> op1, 成本 0, 总成本为 1
"xhello", "hellox" -> op3, 成本 1, 总成本为 2

最终，您的方法的问题在于您选择了非对称操作。您允许在所有 DP 过程中在第二个字符串上添加字母，但仅允许在初始化阶段在第一个字符串上添加字母。
如果编辑操作是对称的，您将得到相同的结果：如果您允许在所有 DP 过程中以 1 的成本在任何字符串上添加/删除字母，则为 2 ；如果您只允许更换，则为 5。

Answer 2

两个参数字符串是对称的。从左侧参数中删除一个字符和向右侧参数中插入一个字符是同一件事。从右侧参数中删除一个字符和向左侧参数中插入一个字符是同一件事。如果您不允许从右删除和从左删除，那么您同时也不允许这两种插入，并且您只能比较相同长度的字符串，并且不需要 DP。只需比较相同位置的字符，然后将不等对的数量相加即可。

如果您只想禁止从左删除（与从右插入相同），则需要修改第一个

for

循环：

      for (int i = 0; i <= m; i++) {
          dp[i][0] = n+m+1; // A large value means editing is impossible
                            // Insertions to match str1 to an empty str2 
                            // ARE NOT ALLOWED
      }