Damerau-Levenshtein Entfernung (Edit Entfernung mit Transposition) c Implementierung

Question

Ich implementiert die Damerau-Levenshtein Abstand in C++ aber es gibt keine korrekte O/P für die Eingabe (PANTERA, Aorta) die richtige O/P ist 4, aber meine Code gibt 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]; 
} 

Ich sehe keine Fehler. Kann jemand ein Problem mit dem Code finden?

Answer 1

Der Algorithmus in der Post berechnet Damerau-Levenshtein Entfernung nicht. In einer wikipedia article ist dieser Algorithmus definiert als die optimale String Alignment Distance.

Eine Java-Implementierung des DL-Distanzalgorithmus kann in einem anderen SO post gefunden werden.

Um die richtigen Werte von OSA Abstand nehmen Sie bitte die Linien markiert mit - unten mit den Linien mit +

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

markiert ändern Es sieht aus, als ob der Code aus einem Programm in einer Programmiersprache kopiert wurde, in dem Array-Indizes beginnen standardmäßig bei 1. Daher wurden alle Verweise auf die Elemente des Distanzfeldes d inkrementiert. Die Verweise auf die Zeichen in den Zeichenfolgen sind jedoch Verweise auf 0-basierte Arrays, daher sollten sie nicht aktualisiert werden.

Um den Abstand der Abstand Array richtig initialisiert hat berechnet werden:

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

Da Sie die 5 Antwort erhalten haben, haben Sie wahrscheinlich bereits Ihre Entfernung Array korrekt initialisiert.

Da der obige Algorithmus den DL-Abstand nicht berechnet, hier eine Skizze einer C-Implementierung des DL-Algorithmus (abgeleitet aus dem SO-Post mit einem Java-Impl. Abgeleitet aus einem ActionScript-Impl. Im Wikipedia-Artikel).

#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

Hier ist meine C++ Version dieses Algorithmus:

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

Ihr Beispiel pantera sollte Aorta 5 geben, könnten Sie hier testen https://code.hackerearth.com/0356acE

mehr als das Kompilieren des Codes tut, hier ist eine Version, die kompilieren

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

auch für diejenigen, die wi implementieren möchten kipedia Version, [Wikiepadia Link] wiki seien Sie vorsichtig.

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] 

und hier ist meine eigene Version 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]; 
}