编辑距离递归算法 - Skiena [英] Edit distance recursive algorithm -- Skiena

问题描述

我读的算法设计手册由史蒂芬Skiena，我对动态规划章节。他有一些例如code代表编辑距离，并使用它们既不在书也不在互联网上解释了一些功能。所以我不知道

一）请问这是怎么算法的工作？

二）什么功能的插入缺失和匹配呢？

 ＃定义匹配0 / *枚举类型匹配*符号/
对于插入*的#define INSERT 1 / *枚举类型符号/
＃定义DELETE 2 / *枚举类型符号删除* /INT string_compare（字符* S，字符* T，INT I，诠释J）
{
        时int k; / *计数器/
        INT选择[3]; / *的三个选项的成本* /
        INT lowest_cost; / *成本最低* /        如果（我== 0）返回（J *插入缺失（''））;
        如果（J == 0）返回（我*插入缺失（''））;        选择[赛事] = string_compare（S，T，I-1，J-1）+匹配（S [I]，T [J]）;
        选择[插入] = string_compare（S，T，I，J-1）+插入缺失（T [J]）;
        选择[删除] = string_compare（S，T，I-1，J）+插入缺失（S [I]）;        lowest_cost =选择[赛事];
        对于（K = INSERT; K＆LT; =删除; k ++）
                如果（选择[​​K]＆LT; lowest_cost）lowest_cost =选择[K];        回报（lowest_cost）;
}
 

解决方案

本书

在287页

  INT匹配（字符C，焦四）
{
  如果（C = D）回报（0）;
  否则返回（1）;
}INT插入缺失（焦三）
{
  返回（1）;
}
 

I'm reading The Algorithm Design Manual by Steven Skiena, and I'm on the dynamic programming chapter. He has some example code for edit distance and uses some functions which are explained neither in the book nor on the internet. So I'm wondering

a) how does this algorithm work?

b) what do the functions indel and match do?

#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 );
}

解决方案

On page 287 in the book:

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

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

这篇关于编辑距离递归算法 - Skiena的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！