Khoảng cách Damerau – Levenshtein (Chỉnh sửa khoảng cách với chuyển vị trí) c thực hiện

Question

Tôi đã thực hiện khoảng cách Damerau – Levenshtein bằng C++ nhưng không cung cấp cho o/p chính xác cho đầu vào (pantera, aorta) o/p chính xác là 4 nhưng mã cho 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]; 
} 

Tôi không thấy lỗi nào. Ai đó có thể tìm thấy một vấn đề với mã?

Answer 1

Thuật toán trong bài viết không tính toán khoảng cách Damerau-Levenshtein. Trong một wikipedia article thuật toán này được định nghĩa là Khoảng cách chuỗi liên kết tối ưu.

Việc triển khai java thuật toán khoảng cách DL có thể được tìm thấy trong một số SO post khác.

Để có được giá trị đúng đắn về khoảng cách OSA hãy thay đổi các dòng được đánh dấu bằng - dưới đây với các dòng được đánh dấu bằng +

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

Có vẻ như nếu mã đã được sao chép từ một chương trình viết bằng ngôn ngữ lập trình ở đâu chỉ số mảng bắt đầu ở mức 1 theo mặc định. Do đó tất cả các tham chiếu đến các phần tử của mảng khoảng cách d được tăng lên. Tuy nhiên, các tham chiếu đến các ký tự trong các chuỗi là tham chiếu đến các mảng dựa trên 0, do đó chúng không được cập nhật.

Để tính toán khoảng cách mảng khoảng cách phải được khởi tạo đúng cách:

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

Vì bạn đã có câu trả lời 5, bạn có thể có mảng khoảng cách của bạn đã khởi tạo một cách chính xác.

Vì thuật toán trên không tính toán khoảng cách DL, đây là bản phác thảo về triển khai C của thuật toán DL (bắt nguồn từ bài SO với java impl. Xuất phát từ một đoạn mã ActionScript trong bài viết trên 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

Dưới đây là C++ phiên bản của tôi về thuật toán này:

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

dụ Pantera của bạn, động mạch chủ nên cung cấp cho 5, bạn có thể kiểm tra ở đây https://code.hackerearth.com/0356acE

hơn rằng mã của bạn doesnt biên dịch, đây là phiên bản biên dịch

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

cũng dành cho những ai muốn triển khai wi phiên bản kipedia, [liên kết Wikiepadia] wiki cẩn thận.

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] 

và đây là phiên bản của riêng tôi 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]; 
}