编辑距离递归算法 – Skiena

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

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

在本书的第287页：

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

Answer 2

基本上，它利用动态编程方法解决问题，将问题的解决方案构建为子问题的解决方案，以避免重新计算，无论是自下而上还是自上而下。

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

以下是此页面的摘录，可以很好地解释算法。

问题：给定两个大小为m，n和一组操作的字符串替换（R），插入（I）和删除（D）都是以相同的代价。 查找将一个字符串转换为另一个字符串所需的最少编辑次数（操作）。

识别递归方法：

在这种情况下会出现什么问题？ 考虑找到部分字符串的编辑距离，比如小前缀。 让我们将它们表示为[1 … i]和[1 … j]，其中1

在前缀中，我们可以通过三种方式（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如果i ，j个字符不一样]）

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

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

E（0,0）= 0，E（i，0）= i，E（0，j）= j

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

如果两个字符不匹配（在最终答案中添加了一个移动match() ，则函数match()返回1，否则返回0。

Answer 3

他们在书中解释了。 请阅读8.2.4编辑距离的变化部分

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

这是一种递归算法，而不是动态编程。 注意，当算法启动时，i＆j分别指向s＆t的最后一个char。

indel返回1. match（a，b）如果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 ); } 

算法不难理解，你只需要阅读几次。 总是让我感到愉快的是发明它的人以及递归会做正确事情的信任。