Nella teoria dell'informazione, nell'informatica e nella linguistica computazionale, la distanza di Levenshtein è una metrica che misura la differenza tra due stringhe o, più in generale, tra due sequenze finite di simboli. Nella definizione classica, essa è pari al numero minimo di operazioni elementari di inserimento, cancellazione e sostituzione necessarie per trasformare una sequenza nell'altra, assegnando costo 1 a ciascuna operazione.V. I. Levenshtein, «Binary codes capable of correcting deletions, insertions, and reversals», Doklady Akademii Nauk SSSR, vol. 163, n. 4, 1965, pp. 845–848. Traduzione inglese in Soviet Physics Doklady, vol. 10, n. 8, 1966, pp. 707–710. Math-Net.
La distanza prende il nome dal matematico sovietico Vladimir Levenshtein, che la introdusse nel 1965 nel contesto dei codici in grado di correggere errori di inserimento e cancellazione. È una forma classica di distanza di edit (edit distance); quest'ultima espressione viene però usata anche in senso più generale per famiglie di misure nelle quali cambiano l'insieme delle operazioni ammesse o i relativi costi.Gonzalo Navarro, «A guided tour to approximate string matching», ACM Computing Surveys, vol. 33, n. 1, 2001, pp. 31–88, doi:10.1145/375360.375365.
La distanza di Levenshtein è impiegata, tra l'altro, nella correzione ortografica, nella ricerca approssimata, nella dialettometria, nella valutazione del riconoscimento automatico del parlato e dell'OCR, nel confronto di record e nella comparazione di sequenze biologiche.
Definizione
Siano
e
due sequenze. Si definisca come la distanza di Levenshtein tra il prefisso e il prefisso .
Le condizioni al bordo sono
Per e vale la ricorrenza
dove
I tre termini corrispondono, rispettivamente, alla cancellazione di un simbolo dalla sequenza di origine, all'inserimento di un simbolo della sequenza di destinazione e alla corrispondenza o sostituzione dell'ultimo simbolo dei due prefissi.Robert A. Wagner, Michael J. Fischer, «The String-to-String Correction Problem», Journal of the ACM, vol. 21, n. 1, 1974, pp. 168–173, doi:10.1145/321796.321811.
La distanza fra le due sequenze complete è quindi .
Esempi
Per trasformare «bar» in «biro» bastano due operazioni:
bar → bir, sostituendo a con i; bir → biro, inserendo o alla fine.
Non esiste una sequenza di una sola operazione che realizzi la trasformazione, quindi la distanza è 2.
Un altro esempio classico è kitten → sitting, che richiede due sostituzioni e un inserimento, per una distanza complessiva pari a 3.
Proprietà e limiti
Con costi unitari di inserimento, cancellazione e sostituzione, la distanza di Levenshtein è una metrica: è non negativa, vale zero se e solo se le due sequenze coincidono, è simmetrica e soddisfa la disuguaglianza triangolare.
Per due sequenze di lunghezze e vale
Il limite inferiore segue dal fatto che una singola inserzione o cancellazione modifica la lunghezza soltanto di un'unità. Il limite superiore si ottiene sostituendo i simboli nella parte di lunghezza comune e inserendo o cancellando quelli rimanenti.
Quando le due sequenze hanno la stessa lunghezza, la distanza di Hamming è un limite superiore:
La distanza di Hamming conta soltanto le sostituzioni e si applica direttamente a sequenze di uguale lunghezza.
Se non si consentono sostituzioni e sono permesse soltanto inserzioni e cancellazioni, la distanza di edit risultante tra due sequenze di lunghezze e è
dove è la lunghezza di una sottosequenza comune più lunga. Questa relazione non vale senza modifiche per la distanza di Levenshtein classica, perché una sostituzione costa 1 mentre una cancellazione seguita da un inserimento costa 2.
Calcolo
Programmazione dinamica
L'algoritmo classico usa la programmazione dinamica. Una matrice di dimensioni memorizza le distanze fra tutte le coppie di prefissi.
funzione DistanzaLevenshtein(s[1..m], t[1..n]): crea d[0..m, 0..n]
per i da 0 a m: d[i,0] = i
per j da 0 a n: d[0,j] = j
per i da 1 a m: per j da 1 a n: se s[i] = t[j]: costo = 0 altrimenti: costo = 1
d[i,j] = minimo( d[i-1,j] + 1, // cancellazione di s[i] d[i,j-1] + 1, // inserimento di t[j] d[i-1,j-1] + costo // corrispondenza o sostituzione )
restituisci d[m,n]
L'invariante è che d[i,j] rappresenta il numero minimo di operazioni necessarie per trasformare i primi i simboli di s nei primi j simboli di t.
Il riempimento dell'intera matrice richiede tempo e spazio .
Riduzione della memoria
Se è necessario conoscere soltanto il valore della distanza, ogni riga dipende dalla riga precedente e da quella corrente. Usando la sequenza più corta come dimensione memorizzata, lo spazio di lavoro può essere ridotto a .Esko Ukkonen, «Algorithms for approximate string matching», Information and Control, vol. 64, n. 1–3, 1985, pp. 100–118, doi:10.1016/S0019-9958(85)80046-2.
Ricostruzione delle operazioni
Se viene conservata l'intera matrice, si può ricostruire una sequenza ottima di operazioni risalendo da alle celle predecessore che giustificano il valore corrente. Possono esistere più cammini ottimi con lo stesso costo totale, quindi una stessa distanza non implica necessariamente un'unica sequenza di edit.
Algoritmi dipendenti dalla distanza
Quando la distanza effettiva è piccola rispetto alle lunghezze delle sequenze, non è sempre necessario calcolare l'intera matrice. Ukkonen sviluppò algoritmi esatti che limitano il calcolo alla regione rilevante della matrice e il cui costo dipende da .
In questo contesto l'espressione «ricerca approssimata» indica che si ammettono differenze tra le stringhe, non che il valore della distanza venga necessariamente approssimato.
Metodi bit-paralleli
Myers propose nel 1999 un algoritmo basato su vettori di bit per la ricerca approssimata, nel quale più stati della programmazione dinamica sono rappresentati simultaneamente nei bit di una parola macchina e aggiornati mediante operazioni bit a bit.Gene Myers, «A fast bit-vector algorithm for approximate string matching based on dynamic programming», Journal of the ACM, vol. 46, n. 3, 1999, pp. 395–415, doi:10.1145/316542.316550.
Varianti e distanze correlate
Distanza di edit ponderata
Nella distanza di edit ponderata, inserimenti, cancellazioni e sostituzioni possono avere costi differenti, eventualmente dipendenti dai simboli coinvolti. Una scelta arbitraria dei costi non conserva automaticamente tutte le proprietà metriche: per esempio, costi asimmetrici possono violare la simmetria.
La distanza di Damerau-Levenshtein aggiunge alle tre operazioni classiche la trasposizione di due simboli adiacenti.
Normalizzazione
La distanza grezza tende ad assumere valori potenzialmente maggiori per sequenze più lunghe. Per questo motivo alcune applicazioni usano forme normalizzate. Non esiste tuttavia un'unica definizione universale di «distanza di Levenshtein normalizzata».
Una scelta comune è
da cui si può ricavare una similarità
La normalizzazione è usata anche nella dialettometria quantitativa. Un'analisi recente delle varietà romanze documentate dall'Atlante Linguistico ed Etnografico dell'Italia e della Svizzera Meridionale impiega la distanza di Levenshtein normalizzata per costruire una matrice di distanze poi analizzata mediante clustering gerarchico.Giorgio Nagy, Varietà linguistiche romanze in Italia e Svizzera: un'analisi statistica, tesi di laurea magistrale, Università degli Studi di Padova, 2024/2025. Archivio dell'Università di Padova.
Applicazioni
Correzione ortografica e ricerca approssimata
La distanza di Levenshtein è una misura di base nella ricerca approssimata di stringhe e può essere usata per generare o ordinare candidati in un correttore ortografico. In raccolte di grandi dimensioni, il calcolo della distanza viene spesso combinato con filtri, indici, q-grammi o altre tecniche che riducono il numero di confronti completi da eseguire.
Dialettometria e varietà linguistiche italiane
In Italia la distanza di Levenshtein è stata impiegata in studi di dialettometria e geografia linguistica. Nei materiali dell'Atlante Lessicale Toscano, Simonetta Montemagni ha utilizzato la misura per calcolare la distanza linguistica tra varietà dialettali toscane e italiano standard, distinguendo diversi insiemi di risposte e criteri di selezione.Simonetta Montemagni, contributo sull'analisi quantitativa dei dati dell'Atlante Lessicale Toscano, Istituto di Linguistica Computazionale del CNR. testo completo.
Un ulteriore studio sulle varietà venete del Friuli-Venezia Giulia, basato sui dati del progetto VALTA, usa l'algoritmo di Levenshtein per calcolare distanze fonetiche successivamente analizzate con strumenti dialettometrici.Antonio Chianese, «Approccio dialettometrico alle varietà venete in Friuli-Venezia Giulia: la distanza fonetica nei dati del VALTA», Atti e Memorie della Società Dalmata di Storia Patria, vol. XLVI, 2024. Università Ca' Foscari Venezia.
L'uso in dialettometria non implica che una distanza di edit grezza rappresenti da sola ogni dimensione della distanza linguistica: la scelta dell'unità di confronto, della normalizzazione e degli eventuali pesi influisce sull'interpretazione dei risultati.
OCR e digitalizzazione del patrimonio linguistico
La distanza di Levenshtein è impiegata anche nella valutazione dell'OCR. Nel progetto di acquisizione digitale dell'Atlante Linguistico ed Etnografico dell'Italia e della Svizzera Meridionale (AIS), un test su circa 100.000 caratteri provenienti da 14 tavole ha calcolato un tasso medio di errore dei caratteri (CER) del 3,65%, includendo inserimenti, omissioni, sostituzioni e diacritici nel conteggio basato sulla distanza di Levenshtein.Graziano Tisato, «Acquisition of the whole AIS, the Linguistic and Ethnographic Atlas of Italy and Southern Switzerland», Studi AISV, vol. 6, 2019, doi:10.17469/O2106AISV000008. AISV.
La Character Error Rate può essere espressa come
dove , e sono, rispettivamente, sostituzioni, cancellazioni e inserimenti, mentre è il numero di simboli nella trascrizione di riferimento. La CER è quindi una misura normalizzata derivata da un allineamento di edit, non la stessa funzione matematica della distanza di Levenshtein grezza.
Riconoscimento automatico del parlato italiano
Un principio analogo è usato nella valutazione del riconoscimento automatico del parlato. In uno studio AItLA sull'italiano non standard, trascrizioni manuali e trascrizioni prodotte da Google-IT sono state allineate mediante programmazione dinamica per calcolare la distanza di Levenshtein; gli errori sono stati classificati come cancellazioni, sostituzioni e inserimenti e impiegati per il calcolo del Word Error Rate (WER).Giovina Angela Del Rosso, Silvia Brambilla, «L'accuratezza della trascrizione ASR sul parlato non-standard. L'italiano nell'OH Portal», in Jacopo Saturno e Lorenzo Spreafico (a cura di), Fare linguistica applicata con le digital humanities, Studi AItLA 14, 2022, pp. 99–116. AItLA.
Lo studio considera, tra gli altri, parlato italiano standard, italiano regionale di Bari e parlato di apprendenti L2, mostrando come l'errore dipenda anche dalle condizioni acustiche e dalla varietà linguistica considerata.
Corrispondenza di dati
In attività di integrazione e pulizia dei dati, la distanza di Levenshtein può essere impiegata come una delle caratteristiche per confrontare campi testuali che contengono errori di digitazione, abbreviazioni o grafie differenti. In questi casi viene spesso combinata con normalizzazione, regole specifiche del dominio o altre misure di similarità, poiché una bassa distanza di edit non equivale necessariamente all'identità dell'entità rappresentata.
Bioinformatica