Home > programming > Edit distance, DP

Edit distance, DP


edit distance btw:victor and vector is 1
0       1       2       3       4       5       6
1       1       2       3       4       5       6
2       2       1       2       3       4       5
3       3       2       1       2       3       4
4       4       3       2       1       2       3
5       5       4       3       2       1       2
6       6       5       4       3       2       1

edit distance btw:victor and vtor is 2
0       1       2       3       4       5       6
1       1       2       2       3       4       5
2       2       2       3       2       3       4
3       3       3       3       3       2       3
4       4       4       4       4       3       2

edit distance btw:victor and vicfangtor is 4
0       1       2       3       4       5       6
1       0       1       2       3       4       5
2       1       0       1       2       3       4
3       2       1       1       2       3       4
4       3       2       2       2       3       4
5       4       3       3       3       3       4
6       5       4       4       4       4       4
7       6       5       4       5       5       5
8       7       6       5       4       5       6
9       8       7       6       5       4       5
10      9       8       7       6       5       4

 

#include <iostream>
using namespace std;

int min(int a, int b, int c){

int m=9999;

m = (a<=b && a<=c)?a:m;
m = (b<=a && b<=c)?b:m;
m = (c<=a && c<=b)?c:m;
return m;

}

int main(){
//cout<<min(99,1,4)<<endl;

char s[] = “victor”;
char t[] = “vicfangtor”;

int m = sizeof(s)/sizeof(char)-1;
int n = sizeof(t)/sizeof(char)-1;

int d[m+1][n+1];

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

for(int j = 1; j<n+1; j++){
for(int i = 1; i<m+1; i++){
if(s[i] == t[j]){
d[i][j] = d[i-1][j-1];
}else{

d[i][j]=min(d[i-1][j]+1, d[i-1][j-1]+1, d[i][j-1]+1);

}

}

}

cout<<“edit distance btw:”<<s<<” and “<<t<<” is “<<d[m][n]<<endl;

for(int j=0; j<n+1; j++){
for(int i=0; i<m+1; i++){
cout<<d[i][j]<<“\t”;
}
cout<<endl;
}

return 0;

Advertisements
Categories: programming
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: