jump to navigation

Levenshtein distance – An optimized version 15 gennaio 2008

Posted by fripp in Algoritmi, C, Informatica, Matematica, Programmazione.

We can adapt the algorithm to use less space, O(m) instead of O(mn), since it only requires that the previous row and current row be stored at any one time.
This is the second version of the algorithm

int levenshtein_distance(char *x, char *y){
int m=strlen(x);
int n=strlen(y);

register int i,j;
int distance;
int *prev=malloc((n+1)*sizeof(int));
int *curr=malloc((n+1)*sizeof(int));
int *tmp=0;

for(i=0;i<=n;i++) prev[i]=i; for(i=1;i<=m;i++){ curr[0]=i; for(j=1;j<=n;j++){ if(x[i-1]!=y[j-1]){ int k=min(curr[j-1],prev[j-1],prev[j]); curr[j]=k+1; }else{ curr[j]=prev[j-1]; } } tmp=prev; prev=curr; curr=tmp; memset((void*)curr,0,sizeof(int)*(n+1)); } distance=prev[n]; free(curr); free(prev); return distance; } [/sourcecode]



1. Francesco - 25 settembre 2008

I have tried to make to depart the program of the distance of Levenshtein in Dev-C++ but it doesn’t depart because me from some errors as for instance in the line” int * curr=malloc((n+1)*sizeof(int)); ” writing ” invalid conversion from goes out ` void * to ` int * ‘”.
and then MIN thing is? the least one?but it needs to make the function of the least one?
Thanks for the availability.
PS Scusa the errors but I am Italian


Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )


Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: