algorithm - 通过递归理解编辑距离

Question

我正在阅读 Skiena 的《算法设计手册》一书中的“8.2.1 通过回避编辑距离”部分。在这一节中，我无法理解以下两点。

• D[i,j-1]+1。这意味着文本中有一个额外的字符需要考虑，因此我们不推进模式指针并支付插入成本。
• D[i-1,j]+1。这意味着模式中有一个额外的字符要删除，因此我们不推进文本指针并支付删除成本。

以上两点提到了计算插入和删除距离。我无法理解这种逻辑是如何工作的。似乎对于每一对，它都假设需要插入和删除。我对吗？为什么每次插入和删除都要加1？请解释这个逻辑是如何工作的。

算法如下

    //we will pass two strings and lengths of those strings
    int string_compare(char *s, char *t, int i, int j)
    {
      int k; /* counter */
      int opt[3]; /* cost of the three options */
      int lowest_cost; /* lowest cost */
      if (i == 0) return(j * indel(’ ’));
      if (j == 0) return(i * indel(’ ’));

      opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);

    // *** I could not able to understand below two lines.   ***
      opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]); 
      opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);


      return( min(opt[Match],opt[INSERT],opt[DELETE])); //min function will return min of all three values
    }

    int match(char c, char d)
    {
        if (c == d) return(0);
        else return(MAXLEN);
    }
    int indel(char c)
    {
        return(1);
    }

请举例说明。

这不是一个重复的问题。我做了研究，但找不到任何东西。

Answer 1

这个算法花了我一段时间才真正理解。请注意，我面前没有那本教科书，但我会尽力提供我所知道的帮助。

解释

假设我们正在评估 string1 和 string2。我也会详细说明 MATCH。

您的陈述，“似乎对于每一对，它都假设需要插入和删除” 只需要一点澄清。该算法不一定假设需要插入和删除，它只是检查所有可能性。在检查递归插入/删除/匹配调用的结果后，它返回所有 3 种方法中的最小值——将 string1 更改为 string2 的 3 种可能方法中的最佳选择。

“为什么每次插入和删除都添加 1？” - 您为字符串的每次更改添加 1。因此，需要更改的每个递归级别都意味着将编辑距离“加 1”。但是，如果字母相同，则不需要更改，您添加 0。这在 match 中显示。* 每个递归调用表示对字符串的一次更改.

一个愚蠢的例子

如果您查看本文底部的引用资料，您会发现一些关于该算法如何工作的措辞优美、深思熟虑的解释。有时那不是你需要的。这有点奇怪，但我偶尔会发现如果我能将代码拟人化会很有帮助。考虑到这一点，我希望这会有所帮助。

举个例子，string_compare("he", "her", 2, 3)。我们分别从每个字符串的第二个和第三个位置(末端)开始。以下是函数在第一次发出递归调用时“说”的一些声音表达:

• MATCH - 我来处理“e”和“r”。我会加 1，因为它们不同，你只需得到 'h' 和 'he' 的结果。
• INSERT - 让我们看看如果将一个字符插入到 string1 中需要多少更改。我们当然会插入一个匹配字符，所以我们真的可以跳过 string2 中的 'r'。你评估“他”和“他”，我会给你得到的任何东西加 1。
• DELETE - 如果我们跳过 string1 中的“e”，让我们看看需要进行多少更改。这是一个变化，所以当你比较“h”和“her”时，我会为你得到的任何东西加 1。

分支太多(这是指数时间复杂度)，很难把每一个场景都画出来。但是，您可以看到 INSERT 对话正在比较“他”和“他”。在以下递归中，将测试每种可能性。但是，MATCH 总是最优的，因为每个字符都匹配并加 0。

每个递归调用都贯穿该对话。比较当前字符递归，在string1中插入一个字符递归，从string1中删除一个字符递归。在每个递归级别中，这 3 个中的最小值是变化最少的路径。这将携带堆栈给你你的答案。

我知道这是一个奇怪的解释，但我希望它能有所帮助。

除了已经提供的可能重复项之外，还有关于该算法的相当可靠的文章(带代码)here .

*话虽如此，老实说，我不确定为什么您的 match 函数会返回 MAXLEN。我希望它返回 1，如 possible duplicate link from the comments 中所示.