编辑距离递归算法 - 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

在本书的第287页:

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

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

Answer 2

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

Answer 3

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

这里给出了问题的递归结构,其中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如果i ,j个字符不一样])

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

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

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

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

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