jump to navigation

Levenshtein distance – An optimized version 15 gennaio 2008

Posted by fripp in Algoritmi, C, Informatica, Matematica, Programmazione.
Tags:
trackback

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]

Annunci

Commenti»

1. Francesco - 25 settembre 2008

Hi,
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


Rispondi

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 )

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 )

Google+ photo

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

Connessione a %s...

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