Ultimo aggiornamento: 2026-07-01

Distanza di Levenshtein

La distanza di Levenshtein, detta anche distanza di edit, misura quanto due stringhe siano diverse contando il numero minimo di modifiche di un singolo carattere necessarie per trasformare l’una nell’altra. Le modifiche consentite sono l’inserimento, l’eliminazione e la sostituzione, ciascuna con costo uno. Il calcolatore riceve due stringhe e restituisce questa distanza insieme a una percentuale di somiglianza, utile per il controllo ortografico, la corrispondenza approssimata e il confronto di sequenze come il DNA.

Le tre operazioni di modifica

Ogni trasformazione tra due stringhe può essere espressa come una sequenza di tre mosse di base. Un inserimento aggiunge un carattere, un’eliminazione ne toglie uno e una sostituzione rimpiazza un carattere con un altro. La distanza di Levenshtein cerca la sequenza più economica di queste mosse, dove ognuna costa uno. Poiché la sostituzione è un singolo passo e non un’eliminazione seguita da un inserimento, cambiare una lettera conta sempre come una modifica, non due.

Prende il nome da Vladimir Levenshtein, che la definì nel 1965, e generalizza la più antica Calcolatore della distanza di Hamming: la distanza di Hamming consente solo sostituzioni e soltanto per stringhe di uguale lunghezza, mentre quella di Levenshtein ammette anche inserimenti ed eliminazioni, perciò gestisce stringhe di lunghezze diverse.

La tabella di programmazione dinamica

La distanza si calcola riempiendo una tabella $D$ con una riga per ciascun carattere della prima stringa (più una riga vuota iniziale) e una colonna per ciascun carattere della seconda (più una colonna vuota iniziale). La cella $D[i][j]$ contiene la distanza di edit tra i primi $i$ caratteri di A e i primi $j$ caratteri di B.

La prima riga e la prima colonna contano le modifiche rispetto alla stringa vuota, quindi $D[i][0] = i$ e $D[0][j] = j$. Ogni altra cella è il minimo di tre candidati:

dove il costo di sostituzione $c$ è 0 quando i caratteri coincidono e 1 quando differiscono. La risposta si trova nella cella in basso a destra. Riempire la tabella richiede un tempo proporzionale al prodotto delle due lunghezze, $m \times n$.

Esempio svolto

Prendiamo la coppia classica «kitten» e «sitting». Seguendo il percorso ottimale nella tabella si ottengono tre modifiche:

Non esiste alcuna sequenza più breve, quindi la distanza è 3. La stringa più lunga ha 7 caratteri, perciò la somiglianza è $1 - 3/7 \approx 0{,}571$, cioè circa il 57%.

La somiglianza e i suoi limiti

Il calcolatore normalizza la distanza grezza in un punteggio di somiglianza tramite

$S = 1 - \dfrac{d_L}{\max(m, n)}$

Dividere per la lunghezza della stringa più lunga mantiene il risultato tra lo 0% per stringhe del tutto diverse e il 100% per stringhe identiche; due stringhe vuote sono considerate identiche. Questa è una delle normalizzazioni più comuni — altri strumenti dividono per la somma delle lunghezze o usano misure basate su rapporti — quindi i valori di somiglianza provenienti da fonti diverse non sono direttamente confrontabili.

Dove viene usata

I correttori ortografici ordinano le correzioni candidate in base alla distanza di edit dalla parola scritta male. I sistemi di ricerca e di basi di dati la usano per la corrispondenza approssimata, tollerando i refusi nella consultazione di nomi o indirizzi. In bioinformatica, la distanza di edit è alla base dell’allineamento di sequenze per confrontare DNA, RNA e proteine, dove inserimenti ed eliminazioni corrispondono a mutazioni. Il modello di costo di Levenshtein semplice tratta tutte le modifiche allo stesso modo; le applicazioni che richiedono penalità diverse per operazioni diverse, o che devono allineare in modo efficiente sequenze molto lunghe, lo estendono con costi pesati o con algoritmi di allineamento specializzati.