编辑距离 - 随着记忆化 [英] Edit distance - With memoization

问题描述

我试图做编辑距离问题，但缓存结果，所以我不重复呼叫。它的工作之前，我想存储的子地图中，但现在它停止工作。对于呼叫我做，比较不可和你不应该，则返回1，显然不正确，但为什么呢？

 使用名字空间std;
INT计数器= 0;

INT匹配（字符C1，C2炭）{
  C1 == C2？ 0：1;
}

INT edit_distance（字符串S1，S2线，地图＆LT;对＆LT;字符串，字符串＆gt;中INT＆GT;＆安培;备忘录）{
  如果（备忘录[make_pair（S1，S2）]）
    返回备忘录[make_pair（S1，S2）];
  INT I = s1.size（）;
  INT J = s2.size（）;

  如果（s1.empty（））
    返回备忘录[make_pair（S1，S2）] = 1 + J;
  如果（s2.empty（））
    返回备忘录[make_pair（S1，S2）] = 1 + I;

  INT选择[3];

  选择[0] = edit_distance（s1.substr（1），s2.substr（1），备忘录）+匹配（S1 [Ⅰ-1]，S2 [J-1]）;
  选择[1] = edit_distance（s1.substr（1），S2，备忘录）+1;
  选择[2] = edit_distance（S1，s2.substr（1），备忘录）+1;

  INT分钟=选择[0];
  的for（int i = 1;我3;;我++）{
    如果（OPT [1]  - ;分）
      分= OPT [I]
  }
  备忘录[make_pair（S1，S2）] =分钟;
  返回分钟;
}

INT edit_distance_driver（字符串S1，S2线）{
  地图＆LT;对＆LT;字符串，字符串＆GT;，INT＆GT;备忘录;
  返回edit_distance（S1，S2，备忘录）;
}

诠释的main（）{
  COUT＆LT;＆LT; edit_distance_driver（不可，你不应该）＆LT;＆LT; ENDL;
}
 

解决方案

该问题是在这里：

 选择[0] = edit_distance（s1.substr（1），s2.substr（1），备忘录）+匹配（S1 [I-1]，S2 [J-1 ]）;
 

您没有递归在首先字符，但你检查最后字符。

您应该将检查的第一个字符，所以它应该是：

 选择[0] = edit_distance（s1.substr（1），s2.substr（1），备忘录）+匹配（S1 [0]，S2 [0]）;
 

和明显匹配应返回的东西：

  INT匹配（字符C1，C2炭）{
  返回C1 == C2？ 0：1;
}
 

然后您code打印6这些字符串的。

I'm trying to do the edit distance problem, but cache the results so I don't repeat calls. It worked before I tried to store subproblems in a map, but now it stops working. For the call I make, comparing "thou shalt not" and "you should not", it returns 1. Obviously incorrect, but why?

using namespace std;
int counter = 0;

int match(char c1, char c2){
  c1 == c2 ? 0 : 1;
}

int edit_distance(string s1, string s2,map<pair<string,string>, int>& memo){
  if(memo[make_pair(s1,s2)])
    return memo[make_pair(s1,s2)];
  int i = s1.size();
  int j = s2.size();

  if(s1.empty())
    return memo[make_pair(s1,s2)] = 1 + j;
  if(s2.empty())
    return memo[make_pair(s1,s2)] = 1 + i;

  int opt[3];

  opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[i-1],s2[j-1]);
  opt[1] = edit_distance(s1.substr(1), s2,memo) + 1;
  opt[2] = edit_distance(s1, s2.substr(1),memo) + 1;

  int min = opt[0];
  for(int i = 1; i < 3; i++){
    if(opt[i] < min)
      min = opt[i];
  }
  memo[ make_pair(s1,s2) ] = min;
  return min;
}

int edit_distance_driver(string s1, string s2){
  map<pair<string,string>,int> memo;
  return edit_distance(s1, s2, memo);
}

int main(){
  cout << edit_distance_driver("thou shalt not","you should not") << endl;
}

解决方案

The problem is here:

opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[i-1],s2[j-1]);

You recurse without the first characters, but you check the last characters.

You should instead check the first characters, so it should be:

opt[0] = edit_distance(s1.substr(1), s2.substr(1),memo) + match(s1[0],s2[0]);

And obviously match should return something:

int match(char c1, char c2){
  return c1 == c2 ? 0 : 1;
}

Then your code prints 6 for those strings.

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