19

我正在阅读 Steven Skiena 的《算法设计手册》，我正在阅读动态编程章节。他有一些编辑距离的示例代码，并使用了一些既没有在书中也没有在互联网上解释的功能。所以我想知道

a) 这个算法是如何工作的？

b) indel 和 match 函数有什么作用？

#define MATCH     0       /* enumerated type symbol for match */
#define INSERT    1       /* enumerated type symbol for insert */
#define DELETE    2       /* enumerated type symbol for delete */

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]);
        opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
        opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

        lowest_cost = opt[MATCH];
        for (k=INSERT; k<=DELETE; k++)
                if (opt[k] < lowest_cost) lowest_cost = opt[k];

        return( lowest_cost );
}
4

6 回答 6

30

在书中第 287 页：

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

int indel(char c)
{
  return(1);
}
于 2014-01-26T14:50:08.533 回答
8

书中对它们进行了解释。请阅读第8.2.4 节编辑距离的种类

于 2013-10-07T06:22:03.213 回答
6

基本上，它利用动态规划方法解决问题，其中问题的解决方案构建为子问题的解决方案，以避免自下而上或自上而下的重新计算。

问题的递归结构如下所示，其中i,j两个字符串中的开始（或结束）索引分别是。

在此处输入图像描述

这是此页面的摘录，很好地解释了该算法。

问题：给定两个大小为 m、n 的字符串和一组操作替换 (R)、插入 (I) 和删除 (D)，所有这些都以相同的成本进行。查找将一个字符串转换为另一个字符串所需的最小编辑（操作）数。

识别递归方法：

在这种情况下会有什么子问题？考虑查找部分字符串的编辑距离，比如小前缀。对于某些 1< i < m 和 1 < j < n，我们将它们表示为 [1...i] 和 [1...j]。显然它正在解决最终问题的较小实例，将其表示为 E(i, j)。我们的目标是找到 E(m, n) 并最小化成本。

在前缀中，我们可以通过三种方式（i，-），（-，j）和（i，j）对字符串进行右对齐。连字符 (-) 表示无字符。一个例子可以更清楚地说明。

给定字符串 SUNDAY 和 SATURDAY。我们希望以最少的编辑将 SUNDAY 转换为 SATURDAY。让我们选择 i = 2 和 j = 4，即前缀字符串分别是 SUN 和 SATU（假设字符串索引从 1 开始）。最右边的字符可以以三种不同的方式对齐。

案例1：对齐字符U和U。它们是相等的，不需要编辑。我们仍然留下了 i = 1 和 j = 3, E(i-1, j-1) 的问题。

情况 2：从第一个字符串中对齐右字符，而第二个字符串中没有字符。我们需要在这里删除（D）。我们仍然留下了 i = 1 和 j = 4, E(i-1, j) 的问题。

情况 3：对齐第二个字符串的右字符，而不是第一个字符串的字符。我们需要在这里插入（I）。我们仍然留下了 i = 2 和 j = 3, E(i, j-1) 的问题。

结合所有子问题，对齐以 i 和 j 结尾的前缀字符串的最小成本由下式给出

E(i, j) = min( [E(i-1, j) + D], [E(i, j-1) + I], [E(i-1, j-1) + R 如果我,j 个字符不相同])

我们还没有完成。基本情况是什么？

当两个字符串的大小都为 0 时，成本为 0。当只有一个字符串为零时，我们需要像非零长度字符串那样进行编辑操作。数学上，

E(0, 0) = 0, E(i, 0) = i, E(0, j) = j

我建议通过这个讲座来获得一个很好的解释。

该函数match()返回 1，如果两个字符不匹配（以便在最终答案中增加一个动作），否则返回 0。

于 2013-10-07T17:11:35.230 回答
3

请通过此链接： https ://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/styles/pages/editdistance.html

实现上述算法的代码是：

int dpEdit(char *s1, char *s2 ,int len1,int len2)
{
if(len1==0)  /// Base Case
return len2;
else if(len2==0)
return len1;
else
{
    int add, remove,replace;
    int table[len1+1][len2+2];
    for(int i=0;i<=len2;i++)
    table[0][i]=i;
    for(int i=0;i<=len1;i++)
    table[i][0]=i;
    for(int i=1;i<=len1;i++)
    {
        for(int j=1;j<=len2;j++)
        {
          // Add 
          //
          add = table[i][j-1]+1;  
          remove = table[i-1][j]+1;
          if(s1[i-1]!=s2[j-1])
          replace = table[i-1][j-1]+1;
          else
          replace =table[i-1][j-1];
          table[i][j]= min(min(add,remove),replace); // Done :)

        }
    }
于 2014-08-23T03:53:52.580 回答
1

到目前为止，这对于 OP 来说可能不是问题，但我会写下我对文本的理解。

/**
 * Returns the cost of a substitution(match) operation
 */
int match(char c, char d)
{
  if (c == d) return 0
  else return 1
}

/**
 * Returns the cost of an insert/delete operation(assumed to be a constant operation)
 */
int indel(char c)
{
  return 1
}

编辑距离本质上是将给定字符串转换为另一个参考字符串所需的最小修改次数。如您所知，修改可以如下。

  1. 替换（替换单个字符）
  2. 插入（在字符串中插入单个字符）
  3. 删除（从字符串中删除单个字符）

现在，

正确提出字符串相似性问题需要我们设置每个字符串转换操作的成本。为每个操作分配相等的成本 1 定义了两个字符串之间的编辑距离。

这样就确定了我们已知的三个修改中的每一个都具有恒定的成本 O(1)。

但是我们怎么知道在哪里修改呢？

相反，我们从字符串的末尾逐个字符地查找可能需要或不需要的修改。所以，

  1. 我们计算所有替换操作，从字符串的末尾开始
  2. 我们统计所有删除操作，从字符串末尾开始
  3. 我们统计所有的插入操作，从字符串的末尾开始

最后，一旦我们有了这些数据，我们就会返回上述三个总和中的最小值。

于 2019-08-24T14:08:11.203 回答
1

这是一种递归算法，不是动态规划。请注意，当算法开始时，i & j 分别指向 s & t 的最后一个字符。

indel 返回 1。如果 a = b（匹配），match(a, b) 返回 0，否则返回 1（替换）

#define MATCH     0       /* enumerated type symbol for match */
#define INSERT    1       /* enumerated type symbol for insert */
#define DELETE    2       /* enumerated type symbol for delete */

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 */

    // base case, if i is 0, then we reached start of s and 
    // now it's empty, so there would be j * 1 edit distance between s & t
    // think of it if s is initially empty and t is not, how many
    // edits we need to perform on s to be similar to t? answer is where
    // we are at t right now which is j
    if (i == 0) return(j * indel(' '));
    // same reasoning as above but for s instead of t
    if (j == 0) return(i * indel(' '));

    // calculate opt[match] by checking if s[i] = t[j] which = 0 if true or 1 if not
    // then recursively do the same for s[i-1] & t[j-1]
    opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
    // calculate opt[insert] which is how many chars we need to insert 
    // in s to make it looks like t, or look at it from the other way,
    // how many chars we need to delete from t to make it similar to s?
    // since we're deleting from t, we decrease j by 1 and leave i (pointer
    // in s) as is + indel(t[j]) which we deleted (always returns 1)
    opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
    // same reasoning as before but deleting from s or inserting into t
    opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

    // these lines are just to pick the min of opt[match], opt[insert], and
    // opt[delete]
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
            if (opt[k] < lowest_cost) lowest_cost = opt[k];

    return( lowest_cost );
}

该算法并不难理解，您只需阅读几次即可。总是让我感到有趣的是发明它的人以及递归会做正确事情的信任。

于 2016-10-23T18:32:12.963 回答