Вопрос по string, c++ – Расстояние Дамерау – Левенштейна (Редактировать расстояние с транспозицией) c реализация

статья в Википедии этот алгоритм определяется как оптимальное расстояние выравнивания строк.

Java-реализацию алгоритма расстояния DL можно найти в другом ТАК.

Чтобы получить правильные значения расстояния OSA, измените линии, отмеченные- ниже с линиями, помеченными+

 int  editdist(string s,string t,int n,int m) 
 {
     int d1,d2,d3,cost;
     int i,j;
     for(i=0;i<=n;i++) 
     {
         for(j=0;j<=m;j++)
         {
-          if(s[i+1]==t[j+1]) 
+          if(s[i+1]==t[j+1]) 
              cost=0;
           else
              cost=1;
           d1=d[i][j+1]+1;
           d2=d[i+1][j]+1;
           d3=d[i][j]+cost;
           d[i+1][j+1]=minimum(d1,d2,d3);
-          if(i>0 && j>0 && s[i+1]==t[j] && s[i]==t[j+1] )   //transposition
+          if(i>0 && j>0 && s[i]==t[j-1] && s[i-1]==t[j] )   //transposition
           {
               d[i+1][j+1]=min(d[i+1][j+1],d[i-1][j-1]+cost);
           }
         }
     }
     return d[n+1][m+1]; 
 }

Похоже, что код был скопирован из программы, написанной на языке программирования, где индексы массива начинаются с 1 по умолчанию. Поэтому все ссылки на элементы массива расстоянийd были увеличены. Однако ссылки на символы в строках являются ссылками на массивы на основе 0, поэтому их не следует обновлять.

Чтобы вычислить расстояние, массив расстояний должен быть правильно инициализирован:

for( i = 0; i < n + 1; i++)
      d[i][0] = i;
for( j = 1; j < m + 1; j++)
      d[0][j] = j;

Так как у вас есть ответ 5, возможно, ваш массив расстояний уже правильно инициализирован.

Так как вышеупомянутый алгоритм не вычисляет расстояние DL, вот набросок реализации алгоритма DL на языке C (полученной из публикации SO с включенным Java, полученной из ссылки ActionScript в статье Википедии).

#define d(i,j) dd[(i) * (m+2) + (j) ]
#define min(x,y) ((x) < (y) ? (x) : (y))
#define min3(a,b,c) ((a)< (b) ? min((a),(c)) : min((b),(c)))
#define min4(a,b,c,d) ((a)< (b) ? min3((a),(c),(d)) : min3((b),(c),(d)))

int dprint(int* dd, int n,int m){
 int i,j;
 for (i=0; i < n+2;i++){
    for (j=0;j < m+2; j++){
        printf("%02d ",d(i,j));
    }
    printf("\n");
 }
 printf("\n");
 return 0;
}

int dldist2(char *s, char* t, int n, int m) {
    int *dd;
    int i, j, cost, i1,j1,DB;
    int INFINITY = n + m;
    int DA[256 * sizeof(int)];

    memset(DA, 0, sizeof(DA));

    if (!(dd = (int*) malloc((n+2)*(m+2)*sizeof(int)))) {
      return -1;
    }

    d(0,0) = INFINITY;
    for(i = 0; i < n+1; i++) {
      d(i+1,1) = i ;
      d(i+1,0) = INFINITY;
    }
    for(j = 0; j<m+1; j++) {
      d(1,j+1) = j ;
      d(0,j+1) = INFINITY;
    }      
    dprint(dd,n,m);

    for(i = 1; i< n+1; i++) {
      DB = 0;
      for(j = 1; j< m+1; j++) {
        i1 = DA[t[j-1]];
        j1 = DB;
        cost = ((s[i-1]==t[j-1])?0:1);
        if(cost==0) DB = j;
        d(i+1,j+1) =
          min4(d(i,j)+cost,
              d(i+1,j) + 1,
              d(i,j+1)+1, 
              d(i1,j1) + (i-i1-1) + 1 + (j-j1-1));
      }
      DA[s[i-1]] = i;
      dprint(dd,n,m);
    }
    cost = d(n+1,m+1);
    free(dd);
    return cost;
}

int damerau_levenshtein_distance(std::string p_string1, std::string p_string2)
{
    int l_string_length1 = p_string1.length();
    int l_string_length2 = p_string2.length();
    int d[l_string_length1+1][l_string_length2+1];

    int i;
    int j;
    int l_cost;,

    for (i = 0;i <= l_string_length1;i++)
    {
        d[i][0] = i;
    }
    for(j = 0; j<= l_string_length2; j++)
    {
        d[0][j] = j;
    }
    for (i = 1;i <= l_string_length1;i++)
    {
        for(j = 1; j<= l_string_length2; j++)
        {
            if( p_string1[i-1] == p_string2[j-1] )
            {
                l_cost = 0;
            }
            else
            {
                l_cost = 1;
            }
            d[i][j] = std::min(
            d[i-1][j] + 1,                  // delete
            std::min(d[i][j-1] + 1,         // insert
            d[i-1][j-1] + l_cost)           // substitution
            );
            if( (i > 1) && 
            (j > 1) && 
            (p_string1[i-1] == p_string2[j-2]) && 
            (p_string1[i-2] == p_string2[j-1])
            ) 
            {
            d[i][j] = std::min(
            d[i][j],
             d[i-2][j-2] + l_cost   // transposition
            );
            }
        }
    }
    return d[l_string_length1][l_string_length2];
}

https: //code.hackerearth.com/0356ac

Более того, ваш код не компилируется, вот версия, которая компилируется

using namespace std;
int  editdist(string s,string t,int n,int m) 
{
  int d1,d2,d3,cost;
  int i,j;
  int d[n + 1][m + 1];
  for(i=0;i<=n;i++) 
  {
    for(j=0;j<=m;j++)
    {
      if(s[i - 1]==t[j - 1]) 
        cost=0;
      else
        cost=1;
      d1=d[i][j+1]+1;
      d2=d[i+1][j]+1;
      d3=d[i][j]+cost;
      d[i+1][j+1]=min(min(d1,d2),d3);
      if(i>0 && j>0 && s[i+1]==t[j] && s[i]==t[j+1] )   //transposition
      {
        d[i+1][j+1]=min(d[i+1][j+1],d[i-1][j-1]+cost);
      }
   }
 }
 return d[n+1][m+1];  
} 

Также для тех, кто хочет реализовать версию Википедии, [ссылка на Википедию] Вики быть осторожен

for j := 1 to length(b) inclusive do
  if a[i] = b[j] then // should be replaced by if a[i - 1] = b[j - 1]

а вот моя собственная версия с ++

unsigned int lev_dam_dist(std::string s1,  std::string s2)
{
  size_t size1 = s1.size();
  size_t size2 = s2.size();
  size_t d[size1 + 1][size2 + 1];
  for (int i = 0; i <= size1; i ++)
    d[i][0] = i;
  for (int i = 0; i <= size2; i ++)
    d[0][i] = i;

  int cost = 0; 
  for (int i = 1; i <= size1; i ++)
    for (int j = 1; j <= size2; j ++)
    {      
      cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1 ;
      if ( (i > 1) && (j > 1) && (s1[i] == s2[j - 1]) && (s1[i - 1] == s2[j]))
      {
        size_t a = std::min(d[i - 1][j], d[i][j - 1] + 1);
        size_t b = std::min(d[i][j] + cost, d[i - 2][j - 2]);
        d[i][j] = std::min(a, b);
      }
      else
      {
        d[i][j] = std::min(std::min(d[i][j -1] + 1, d[i - 1][j] + 1), d[i - 1][j - 1] + cost);
      }
    }
  return d[size1][size2];
}