Questa particolare definizione di distanza di edit usa solo tre operazioni: copia, inserimento ed eliminazione (quattro se si include l'operazione "nessuna operazione", che non ha costo) attraverso le quali si calcola il costo necessario per trasformare una sequenza di caratteri in un altra. Tanto più piccolo è il costo tanto maggiore è la somiglianza delle due sequenze. Al contrario, tanto maggiore è il costo tanto minore è la somiglianza delle sequenze.
Ad esempio, per trasformare la sequenza di caratteri Mantello in Minerva è necessario un certo numero di copie, inserimenti o eliminazione che, sommate tutte insieme danno il costo necessario per la trasformazione (si faccia riferimento all'immagine sotto). Per semplificare le cose il costo sarà uguale per tutte le operazioni ma, volendo generalizzare, può avere un valore diverso che dipende dall'operazione e dall'architettura sulla quale viene eseguito l'algoritmo.
Invertendo l'input delle stringhe (volendo cioè trasformare la sequenza di caratteri Minerva in Mantello) il costo sarebbe stato comunque 5 ma con un operazione di inserimento al posto di quella di eliminazione. Da notare anche che la cella vuota in direzione dell'operazione di eliminazione non indica uno spazio nella sequenza finale. E' solo necessaria (a livello visivo) per allineare le operazioni applicate ai caratteri successivi ma può confondere le idee pertanto nel prosieguo della lettura non si faccia più riferimento a questa immagine ma solo a quella successiva che mostra la matrice del costo delle operazioni.
Una implementazione efficiente dell'algoritmo che calcola la distanza di edit è, ad esempio, quella che sfrutta la programmazione dinamica attraverso la formula
$D[i, 0]:= i \quad\text{ for $1 \le i \ge n$.}$
$D[0, j]:= j \quad\text{ for $1\le j \ge m$.}$
$D[i, j]:= \begin{cases} MIN(D[i, j-1] + 1, D[i-1, j] + 1, D[i-1, j-1] + K), & \quad\text{for $1\le i \ge n, 1 \le j \ge m$.} \end{cases}$
con $D[i, j]$ distanza di edit delle sottosequenze composte, rispettivamente, dai primi $i$ caratteri della prima sequenza e dai primi $j$ caratteri della seconda sequenza. Con $n$ ed $m$ si indicano il numero di caratteri delle due sequenze. Con $a_i$ si indica l'$i$-esimo carattere della prima sequenza e con $b_j$ il $j$-esimo carattere della seconda sequenza. Infine, $K$ è definita come
$K:= \begin{cases} 1, & \text{if $a_i \ne b_j$.} \\ 0, & \text{if $a_i = b_j$.} \end{cases}$
Quello che si ottiene è una matrice che conserva i risultati parziali delle distanze di edit delle sottosequenze delle due stringhe.
Nello specifico, se nell'iterazione corrente si verifica che $a_i = b_j$, $D[i, j]$ sarà uguale a quello calcolato per $D[i-1, j-1]$ dato che non è necessario effettuare operazioni e il costo è già stato calcolato per le due sottosequenze precedenti entrambe con un carattere in meno. Al contrario ($a_i \ne b_j$) sarà uguale a $D[i-1, j-1] + 1$ per via della copia necessaria del carattere della prima sottosequenza nella seconda.
Se invece il carattere è da inserire, $D[i, j]$ sarà uguale a $D[i, j-1] + 1$ dato che è necessario solo aumentare il costo (già calcolato) che prendeva in esame la seconda sottostringa con un carattere in meno. Ad esempio (guardando l'immagine sotto), se si volesse trasformare "M" in "MAN" si ha prima $D[1,1]=0$ (dato che i primi caratteri sono uguali; 'M' per entrambe le stringhe) e poi $D[1,2]=1$ (per via dell'inserimento di 'A'), che è uguale a $D[1,1]+1$. Infine si ha $D[1,3]=2$ (per l'inserimento di 'N'), che è uguale a $D[1,2]+1$.
Infine, se il carattere è da eliminare $D[i, j]$ sarà uguale a $D[i-1, j] + 1$ dato che è necessario solo aumentare il costo (già calcolato) che prendeva in esame la prima sottostringa con un carattere in meno.
Alla fine, l'essenza dell'algoritmo è quella di effettuare un cammino minimo tra le varie distanze delle sottosequenze che vengono calcolate ad ogni iterazione per arrivare alla trasformazione finale con il costo minore.
L'implementazione in codice, se si segue la formula, in effetti è abbastanza semplice.
/*Per facilitare la stesura, la lettura e la comprensione del codice si è volutamente deciso di utilizzare un mix di C/C++ cercando di restare il più possibile all'interno del sottoinsieme C del C++ e di utilizzare solo quei costrutti e funzionalità di base del C++ che permettono una maggiore semplificazione.*/ #include <stdio.h> #include <stdlib.h> #include <string.h> int levenshtein_distance(char*, char*); void print_matrix(unsigned int*, int, int); unsigned int min_3(unsigned int a, unsigned int b, unsigned int c) { return ((a < b) ? ((a < c) ? a : c) : (b < c) ? b : c); } int main(int argc, char *argv[], char *envp[]) { char s1[] = { "Mantello" }; char s2[] = { "Minerva" }; printf("La distanza di edit tra %s e %s: %d", s1, s2, levenshtein_distance(s1, s2)); return 0; } int levenshtein_distance(char *s1, char *s2) { unsigned int i, j, s1len, s2len, cost; s1len = strlen(s1); s2len = strlen(s2); unsigned int *matrix = (unsigned int*)malloc((s2len + 1) * (s1len + 1) * sizeof(unsigned int)); matrix[0] = 0; for (j = 1; j <= s1len; j++) matrix[0 * (s1len + 1) + j] = j; for (i = 1; i <= s2len; i++) matrix[i * (s1len + 1) + 0] = i; for (i = 1; i <= s2len; i++) { for (j = 1; j <= s1len; j++) matrix[i * (s1len + 1) + j] = min_3( matrix[(i - 1) * (s1len + 1) + j] + 1, matrix[i * (s1len + 1) + (j - 1)] + 1, matrix[(i - 1) * (s1len + 1) + (j - 1)] + (s1[j - 1] == s2[i - 1] ? 0 : 1) ); } print_matrix(matrix, s2len + 1, s1len + 1); cost = (matrix[(s2len + 1) * (s1len + 1) - 1]); free(matrix); return cost; } void print_matrix(unsigned int *a, int n, int m) { for (unsigned int i = 0; i < n; i++) { for (unsigned int j = 0; j < m; j++) { printf("%d ", a[m*i + j]); } printf("\n"); } printf("\n"); }
Riferimenti:
[1] https://en.wikipedia.org/wiki/Edit_distance
[2] http://www.di.univaq.it/adimarco/teaching/bioinfo15/DistanzaEdit01.04.15.pdf
[3] https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance
[4] http://www.levenshtein.net/
Nessun commento:
Posta un commento