jump to navigation

Programmazione dinamica – Distanza di Levenshtein 13 gennaio 2008

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

La Distanza di Levenshtein è la distanza tra due stringhe S1 ed S2, dove per distanza intendiamo il numero minimo di operazioni elementari che occorre fare per trasformare la stringa S1 nella stringa S2.

Queste operazioni elementari includono:

  • cancellazione di un carattere
  • sostituzione di un carattere con un altro
  • inserimento di un carattere

L’algoritmo di Levenshtein consente di calcolare la distanza tra una stringa di lunghezza m e una stringa di lunghezza n in tempo O(nm)

Per la definizione formale dell’algoritmo, potete consultare questa pagina.

In questi giorni ho implementato sia la versione “classica”, che fa uso di una matrice di ordine (m+1) \cdot (n+1), sia una versione più ottimizzata, che si limita ad usare due vettori di lunghezza m.

Ecco la prima versione:

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

register int i,j;

int **d=malloc((m+1)*sizeof(int));

for(i=0;i<=m;i++) d[i]=malloc((n+1)*sizeof(int)) for(i=0;i<=m;i++) d[i][0]=i; for(j=1;j<=n;j++) d[0][j]=j; for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(x[i-1]!=y[j-1]){ int k=min(d[i][j-1],d[i-1][j],d[i-1][j-1]); d[i][j]=k+1; }else{ d[i][j]=d[i-1][j-1]; } } } int distanza=d[m][n]; for(i=0;i<=m;i++) free(d[i]); free(d); return distanza; } [/sourcecode]

Annunci

Commenti»

1. Ordeal - 5 febbraio 2009

Ho implementato la versione ottimizzata usanso solo un vettore e una variabile temporanea per salvare D[i-1][j-1].
L’ho messa nella wiki


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: