Forse cercavi: distanza di Levenshtein
Spesso capita di digitare in maniera errata una chiave di ricerca e vedersela correggere non appena clicchiamo il tasto ‘Invio’. Cosa succede? Come può un computer, nella maggior parte dei casi, capire cosa volevamo veramente scrivere? La risposta, abbastanza diretta, è: distanza di Levenshtein (o se lo trovate troppo complicato da pronunciare/scrivere, distanza di edit). Considerate due stringhe sorgente e destinazione, la distanza di Levenshtein è il numero di operazioni elementari necessarie per trasformare la stringa sorgente in quella di destinazione. Essa definisce tre operazioni elementari: i) la cancellazione di un carattere; ii) la sostituzione di un carattere; iii) l’inserimento di un nuovo carattere. Due stringhe uguali hanno distanza di Levenshtein pari a 0.
L’algoritmo
Considerando s come la lunghezza della stringa sorgente e d come la lunghezza della stringa destinazione implementeremo un algoritmo che faccia uso di una matrice (s + 1) * (d + 1). In colonna scriveremo la stringa sorgente, come riga inseriremo invece la stringa di destinazione. In ogni cella della matrice è rappresentata la distanza che intercorre tra una porzione di stringa sorgente e una porzione di stringa destinazione. Nell’angolo in basso a destra le porzioni di stringa sono complete, quindi, il valore che vi è rappresentato è l’effettiva distanza tra la stringa sorgente e quella di destinazione. Un esempio: supponiamo che io voglia conoscere la distanza tra il mio vero nome mariano e una stringa ottenuta per errata digitazione, supponiamo marinao (errore comune).
| m | a | r | i | a | n | o | ||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| m | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| a | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| r | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
| i | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| n | 5 | 4 | 3 | 2 | 1 | 1 | 1 | 2 |
| a | 6 | 5 | 4 | 3 | 2 | 1 | 2 | 2 |
| o | 7 | 6 | 5 | 4 | 3 | 2 | 2 | 2 |
La matrice sopra rappresenta il calcolo che svolge l’algoritmo per arrivare al risultato finale, ossia la distanza contenuta nella cella in basso a destra, tutte le altre celle sono intermedie. Per alcune celle, (quelle tratteggiate in basso), è stata aggiunta una breve spiegazione su come è stata calcolata la distanza, basterà tenere il puntatore fermo per qualche secondo e leggerne l’etichetta. In questa pagina c’è un’applet Java che prende in ingresso una stringa di destinazione e una di origine e ci mostra la matrice, risultante da provare. Ovviamente quest’algoritmo si trova in numerose versioni, sia per quello che riguarda il linguaggio in cui è stato sviluppato sia per il modo in cui è stato sviluppato. Il seguente algoritmo, infatti, non è il più efficiente nel calcolo della distanza di Levenshtein ma in compenso ci permette di avere un codice più autoesplicativo. Per coloro che sviluppano in PHP la funzione per il calcolo della distanza è una built-in del linguaggio [link]. La versione di questo articolo è in linguaggio Java.
public class Distance {
/** Questo metodo calcola il minimo tra tre numeri interi*/
private int getMinimo(int a, int b, int c) {
int min;
// imposto il minimo uguale ad a
min = a;
// se il parametro b è minore del minimo
if (b < min) {
// il nuovo minimo sarà il parametro b
min = b;
}
// se il parametro c è minore del minimo
if (c < min) {
// il nuovo minimo sarà il parametro c
min = c;
}
// ritorno il minimo (min)
return min;
}
/** Funzione per il calcolo effettivo della distanza di Levenshtein*/
private int getDistanza(String s, String t) {
int d[][]; // matrice
int n; // lunghezza di s
int m; // lunghezza di t
int i; // iterazioni su s
int j; // iterazioni su t
char s_i; // i-esimo carattere di s
char t_j; // j-esimo carattere di t
int costo;
n = s.length(); // n conterrà il num di caratteri di s
m = t.length(); // m conterrà il num di caratteri di t
// se la stringa sorgente è vuota
if (n == 0) {
// la distanza è il num di chr della dest.
return m;
}
// se la stringa destinazione è vuota
if (m == 0) {
// la distanza è il num di chr della sorg.
return n;
}
// creo la matrice (n+1)*(m+1)
d = new int[n + 1][m + 1];
// la prima riga della mat. conterrà le distanze da 0 a n
// la distanza 1 è associata al primo chr della stringa, 0 al vuoto
// Nel caso del nostro esempio:
// 0 1 2 3 4 5 6 7
// - M A R I A N O
for (i = 0; i <= n; i++) {
d[i][0] = i;
}
// la prima colonna della mat. conterrà le distanze da 0 a m
// la distanza 1 è associato al primo chr della stringa, 0 al vuoto
// Nel caso del nostro esempio:
// - 0
// M 1
// A 2
// R 3
// I 4
// N 5
// A 6
// O 7
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// esamino ogni carattere di s (i da 1 a n)
for (i = 1; i <= n; i++) {
s_i = s.charAt(i - 1);
// Esamino ogni carattere di t (j da 1 a m)
for (j = 1; j <= m; j++) {
t_j = t.charAt(j - 1);
// Se l'i-esimo elemento di s
// è uguale al j-esimo elemento di t
if (s_i == t_j) {
// il costo è 0
costo = 0;
} else { // altrimenti
// il costo è 1
costo = 1;
}
// imposto la cella d[i][j] scegliendo il valore minimo tra:
// - la cella immediatamente superiore + 1
// - la cella immediatamente a sinistra + 1
// - la cella diagonalmente in alto a sinistra più il costo
d[i][j] = getMinimo(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + costo);
}
}
// una volta completate tutte le iterazioni la cella
// d[n][m] contiene la distanza finale tra la stringa
// sorgente e quella di destianzione
return d[n][m];
}
}
Eseguendo come da esempio il metodo getDistanza() e passando come parametri le stringhe mariano e marinao avremo come risultato la distanza di Levenshtein tra le due stringhe, ossia: 2. Il lettore più ansioso di arrivare alla soluzione si starà chiedendo cosa farsene di questo numero, d’altronde Google (ad esempio) accetta una stringa e se questa non esiste tenta di fornire la stringa corretta, fin qui invece la nostra funzione necessita come argomenti sia della stringa corretta che di quella errata. Che senso ha? Bene! Il solito lettore ansioso sappia di non aver perso tempo fino ad ora. Siamo infatti arrivati solo a metà dell’articolo.
Come sfruttare la distanza
Ora che abbiamo un metodo in grado di fornirci la distanza tra due stringhe possiamo passare alla parte più interessante, ovvero, come “indovinare” la parola che avrebbe voluto scrivere in realtà l’utente. L’idea di base è concettualmente molto semplice, restringiamo il campo alla ricerca in un array in modo da non essere troppo dispersivi. Vogliamo verificare se nell’array dizionario è presente la parola x. Se tale parola non è presente allora si cerca in dizionario qual’è la parola che più somiglia alla parola x, ovvero, quella con la minore distanza di Levenshtein rispetto a x. In pratica calcoleremo la distanza di Levenshtein tra x ed ogni parola di dizionario, la parola con distanza minore potrebbe essere quella che l’utente cercava. La classe precedente sarà quindi completata con l’aggiunta di un nuovo metodo.
/** Calcolo una parola alt alternativa alla parola input s*/
public String getAlternativa(String s, String d[]) {
int i, // iteratore ciclo for
min = 100; // iniziallizzo il minimo a 100
int rit; // distanza di hamming
String alt = ""; // stringa da ritornare
// per ogni elemento dell'array d
for (i = 0; i < d.length; i++) {
// calcolo della distanza tra s e l'i-esimo elemento d
rit = getDistanza(s, d[i]);
// se la distanza è minore del minimo
if (rit < min) {
// la distanza rit sarà il nuovo minimo
min = rit;
// e l'i-esimo elemento di d sarà l'alternativa
alt = d[i];
}
}
// ritorno l'alternativa
return alt;
}
Ora abbiamo la nostra classe Distance che ci fornisce tutti i mezzi per realizzare il nostro scopo, basterà creare un’istanza di tale classe quando serve per poter trovare un alternativa valida ad una parola digitata in maniera errata. L’approccio scelto utilizza un dizionario di parole al cui interno sono memorizzate le parole esatte. Ovviamente quanto più è grande il dizionario maggiore sarà la precisione con cui l’algoritmo “indovinerà” la parola esatta e di conseguenza maggiore sarà il carico. che la macchina dovrà sopportare Questo che segue è l’esempio di una classe che implementa la distanza di Levenshtein per trovare la giusta alternativa alla parola marinao, avendo un dizionario limitato a solo 3 parole:
public class Main {
public static void main(String[] args) {
String parole[];
parole = new String[3];
parole[0] = "mariano";
parole[1] = "marziano";
parole[2] = "martino";
Distance d = new Distance();
System.out.println("Forse cercavi: "+d.getAlternativa("marinao", parole));
// Forse cercavi: mariano
}
}
Limiti matematici
L’algoritmo per la distanza di Levenshtein è caratterizzato da dei limiti strettamente matematici e sono i seguenti:
- il limite superiore è pari alla lunghezza della stringa più lunga;
- il limite inferiore è pari alla differenza fra le lunghezze delle due stringhe;
- se le stringhe sono identiche la distanza è 0 (e la distanza di Levenshtein non supera la distanza di Hamming)
Conclusioni
Sebbene funzionale, tale algoritmo, se usato con grandi moli di dati mostrerebbe subito i suoi limiti. E’ possibile ridurre l’occupazione di memoria del precendente algoritmo osservando che ad ogni passo dell’iterazione è sufficiente mantenere due righe della matrice, quella corrente e qualle precedente. Usando questo accorgimento è possibile ridurre l’occupazione di memoria da O(mn) a O(m). Inoltre potrebbe essere interessante relegare al database il calcolo della distanza, visto che sarebbe molto più conveniente mantenere il nostro dizionario di parole direttamente in una base di dati, insomma, ci sono ancora sperimentazioni da fare. C’è da ricordare che l’algoritmo è case-sensitive per cui la stringa “Mariano” è diversa da “mariano”, quindi prima di un confronto sarebbe opportuno portare le stringhe completamente toUpperCase() o toLowerCase(). Un buon tool di supporto per comprendere bene come funziona il calcolo della distanza di Levenshtein lo trovate qui.