La distanza di Levenshtein

La distanza di Levenshtein, introdotta dal matematico russo Vladimir Levenshtein nel 1965, è una metrica di modifica tra due stringhe: conta il numero minimo di operazioni elementari di inserzione, cancellazione o sostituzione di singoli caratteri necessarie per trasformare una stringa nell'altra. È una delle metriche di similarità tra testi più usate al mondo, fondamentale per:

• Correzione ortografica: quando digiti «kitten» e il correttore propone «kitchen» perché hanno distanza 3.
• Autocomplete e ricerca fuzzy: Google, Bing, motori di ricerca interni.
• Bioinformatica: allineamento di sequenze DNA o proteiche.
• Record linkage: unione di dati da fonti diverse con nomi e indirizzi scritti in modi lievemente diversi.
• Traduzione automatica: valutazione dell'output (TER — Translation Edit Rate).

Le tre operazioni elementari

Le operazioni permesse da Levenshtein, ciascuna con costo 1:

1. Inserzione: aggiungi un carattere. Esempio: «kiten» → «kitten» (inserisce 't').
2. Cancellazione: rimuovi un carattere. Esempio: «kittten» → «kitten» (cancella 't').
3. Sostituzione: cambia un carattere con un altro. Esempio: «kiiten» → «kitten» (sostituisce 'i' con 't').

La distanza tra «kitten» e «sitting» è 3: k→s (sostituzione), e→i (sostituzione), inserisci «g» alla fine. Nessuna sequenza di operazioni richiede meno passaggi.

Le quattro modalità del calcolatore

1. Distanza classica: calcola la distanza e mostra la matrice DP (programmazione dinamica) con cui è stata ottenuta, oltre alla sequenza ottimale di operazioni.
2. Similarità normalizzata: converte la distanza in percentuale (0-100%) usando sim = 1 − d/max(|s1|, |s2|). Valori > 80% indicano similarità alta (fuzzy match).
3. Damerau-Levenshtein: variante che aggiunge una quarta operazione, la trasposizione di due caratteri adiacenti (costo 1). Cattura errori di battitura come «teh» invece di «the» con costo 1 invece di 2.
4. Parola più vicina: dato un vocabolario di parole, trova quella a distanza minima da una parola target. È il cuore degli algoritmi di correzione ortografica.

L'algoritmo di programmazione dinamica

L'approccio classico, proposto da Levenshtein stesso e perfezionato da Wagner-Fischer (1974), usa programmazione dinamica: costruisce una matrice d[i][j] di dimensione (|s1|+1) × (|s2|+1), dove d[i][j] è la distanza tra i primi i caratteri di s1 e i primi j caratteri di s2. La ricorrenza è:

d[i][j] = min(d[i−1][j] + 1, d[i][j−1] + 1, d[i−1][j−1] + c)

dove c = 0 se s1[i−1] = s2[j−1], altrimenti c = 1. I tre termini rappresentano rispettivamente cancellazione, inserzione e sostituzione. La base della ricorsione è d[i][0] = i e d[0][j] = j (servono i cancellazioni o j inserzioni per svuotare o riempire una stringa). La complessità è O(|s1|·|s2|) in tempo e memoria.

Damerau-Levenshtein

Frederick Damerau (1964) osservò che l'80% degli errori di battitura umani cadono in quattro categorie: inserimento, cancellazione, sostituzione e trasposizione (scambio di due caratteri adiacenti). La distanza di Damerau-Levenshtein aggiunge quindi una quarta operazione con costo 1:

d[i][j] ≤ d[i−2][j−2] + 1 se s1[i−1] = s2[j−2] e s1[i−2] = s2[j−1]

Con Damerau, «teh» → «the» ha distanza 1 (una trasposizione); con Levenshtein classico è 2 (sostituzione e→h, sostituzione h→e). La variante di Damerau produce risultati più allineati all'intuizione umana dell'errore di battitura.

Varianti e alternative

• Distanza di Hamming: conta le posizioni in cui due stringhe di lunghezza uguale differiscono. Più semplice ma restrittiva (solo sostituzioni).
• Distanza di Jaro / Jaro-Winkler: enfatizza prefissi comuni, utile per confrontare nomi propri.
• N-gram / Jaccard: basate su sottoinsiemi di k caratteri consecutivi. Efficaci per stringhe lunghe.
• Needleman-Wunsch: generalizzazione con pesi diversi per ogni operazione. Standard in bioinformatica.
• Smith-Waterman: variante locale di Needleman-Wunsch per allineamenti parziali.

Applicazioni pratiche

• Spell-checker: Aspell, Hunspell, Google Search suggeriscono correzioni minimizzando la distanza da un vocabolario.
• Fuzzy search: Elasticsearch, Solr implementano ricerca approssimata con soglia di distanza max.
• Diff/merge: il comando diff di Unix e Git usano varianti ottimizzate (algoritmo di Myers 1986).
• DNA: BLAST e FASTA allineano sequenze biologiche con varianti pesate di Levenshtein.
• Deduplicazione: in database con dati disordinati (importazioni CSV), si uniscono record con distanza di Levenshtein < soglia.
• OCR: correzione di errori di riconoscimento caratteri basata sul dizionario della lingua.

Ottimizzazioni avanzate

Per applicazioni di produzione, l'algoritmo di Levenshtein può essere ottimizzato:

• Memoria O(min(m, n)): poiché il calcolo di una riga richiede solo la precedente, serve solo 2 array 1D.
• Ukkonen's cutoff: se sappiamo che cerchiamo distanza ≤ k, possiamo limitare il calcolo a una «banda» di larghezza 2k+1 attorno alla diagonale, riducendo la complessità a O(k·max(m, n)).
• Bit-parallel (Myers 1999): usando SIMD e operazioni bitwise, si ottiene O(⌈n/w⌉·m) con w = 64 bit di parola macchina — circa 60× più veloce per stringhe fino a 64 caratteri.
• Heuristic pruning: approximate filtering di candidati con q-gram o tabelle hash prima di calcolare Levenshtein esatto.

Aggiornato a luglio 2026