编辑距离递归算法 - Skiena

Question

我正在阅读由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); 
} 

Answer 1

他们在书中解释。请阅读章节8.2.4编辑距离

Answer 2

基本上，它利用动态规划方法来解决问题的解决方案，以解决子问题，避免重新计算，自下而上或顶部-下。

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

下面是从this page，说明该算法很好的摘录。

问题：给定的大小为m两个字符串，n和一组操作替换 （R），插入（I）和删除（d）所有在等价。查找将一个字符串转换为另一个字符串所需编辑（操作）的最小编号 。

确定递归方法：

会是怎样子的问题在这种情况下？考虑找到部分字符串的编辑距离 ，比如说小字头。让我们将它们表示为 [1 ... i]和[1 ... j]对于某些1 < i < m和1 < j < n。显然它是 解决最终问题的较小实例，表示它为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和由

E（I，J）=分钟（[E（I-1，J）+ d]，[E给出Ĵ结束的最小成本（i，j-1）+ I]，[E（i-1，j-1）+ R if i，j字符不相同]）

我们还没有完成。什么是基础案例？

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

E（0,0）= 0，E（I，0）= I，E（0，J）= j的

我建议通过this lecture去一个很好的解释。

功能match()返回1，如果两个角色不匹配（这样一个更此举是在最后的答案添加），否则为0。

Answer 3

在287页的书：

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

int indel(char c) 
{ 
    return(1); 
} 

Answer 4

请通过这个链接： 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 :) 

     } 
    } 

Answer 5

这是一个递归算法，不是动态编程。请注意，当算法开始时，两个指针都分别指向s的最后一个字符t & t。

插入缺失返回1 匹配（A，B）返回0，如果A = B（匹配）否则返回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); 
} 

该算法是不难理解的，你只需要阅读它几次。总是让我感到有趣的是发明它的人和相信递归会做正确的事情。