Damerau-Levenshtein distancia (Editar distancia con transposición) c implementación

Question

Implementé la distancia Damerau-Levenshtein en C++ pero no da la o/p correcta para la entrada (pantera, aorta) la o/p correcta es 4 pero mi código da 5 .....

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]) 
       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 
      { 
       d[i+1][j+1]=min(d[i+1][j+1],d[i-1][j-1]+cost); 
      } 
     } 
    } 
    return d[n+1][m+1]; 
} 

no veo ningún error. ¿Alguien puede encontrar un problema con el código?

Answer 1

El algoritmo en la publicación no calcula la distancia Damerau-Levenshtein. En un wikipedia article este algoritmo se define como la distancia óptima de alineación de cadenas.

Una implementación de java del algoritmo de distancia DL se puede encontrar en otro SO post.

para obtener los valores correctos de distancia OSA favor cambian las líneas marcadas con - a continuación con las líneas marcadas con +

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]; 
} 

Parece como si el código fue copiado de un programa escrito en un lenguaje de programación, donde los índices de matriz comienzan en 1 por defecto. Por lo tanto, todas las referencias a los elementos de la matriz de distancia d se incrementaron. Sin embargo, las referencias a los caracteres dentro de las cadenas son referencias a matrices basadas en 0, por lo tanto, no deberían actualizarse.

para calcular la distancia de la matriz de distancia tiene que ser inicializado correctamente:

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

Dado que usted tiene la respuesta 5, es probable que la matriz de distancia ya se ha inicializado correctamente.

Dado que el algoritmo anterior no calcular la distancia DL, aquí es un esquema de una implementación de C del algoritmo DL (derivado del SO poste con un impl java. Derivado de una impl ActionScript. En el artículo de Wikipedia).

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

Answer 2

aquí está mi versión de C++ de este algoritmo:

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]; 
} 

Answer 3

tu ejemplo pantera, la aorta se debe dar 5, se puede probar aquí https://code.hackerearth.com/0356acE

más de que su código duerma compilar, aquí wich es una versión de compilación

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]; 
} 

también para aquellos que quieren poner en práctica wi versión de kipedia, [enlace de Wikiepadia] wiki tenga cuidado.

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] 

y aquí es mi propia versión C++

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]; 
}