Distanza di Levenshtein

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.

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.

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

$a=a_{1}a_{2}\dots a_{m}$

e

$b=b_{1}b_{2}\dots b_{n}$

due sequenze. Si definisca $D(i,j)$ come la distanza di Levenshtein tra il prefisso $a_{1}\dots a_{i}$ e il prefisso $b_{1}\dots b_{j}$.

Le condizioni al bordo sono

$D(i,0)=i,\qquad D(0,j)=j.$

Per $i>0$ e $j>0$ vale la ricorrenza

$D(i,j)=\min {\begin{cases}D(i-1,j)+1,\\D(i,j-1)+1,\\D(i-1,j-1)+\delta (a_{i},b_{j}),\end{cases}}$

dove

$\delta (a_{i},b_{j})={\begin{cases}0,&a_{i}=b_{j},\\1,&a_{i}\neq b_{j}.\end{cases}}$

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.

La distanza fra le due sequenze complete è quindi $D(m,n)$.

Esempi

Per trasformare «bar» in «biro» bastano due operazioni:

1. bar → bir, sostituendo a con i;
2. 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 $m$ e $n$ vale

$|m-n|\leq d_{L}(a,b)\leq \max(m,n).$

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:

$d_{L}(a,b)\leq d_{H}(a,b).$

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 $m$ e $n$ è

$m+n-2L,$

dove $L$ è 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 $(m+1)\times (n+1)$ 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 $\Theta (mn)$ e spazio $\Theta (mn)$.

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 $O(\min(m,n))$.

Ricostruzione delle operazioni

Se viene conservata l'intera matrice, si può ricostruire una sequenza ottima di operazioni risalendo da $D(m,n)$ 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 $s$ è 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 $s$.

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.

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 è

$d_{N}(a,b)={\frac {d_{L}(a,b)}{\max(|a|,|b|)}},$

da cui si può ricavare una similarità

$s(a,b)=1-d_{N}(a,b).$

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.

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.

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.

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.

La Character Error Rate può essere espressa come

$\mathrm {CER} ={\frac {S+D+I}{N}},$

dove $S$, $D$ e $I$ sono, rispettivamente, sostituzioni, cancellazioni e inserimenti, mentre $N$ è 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).

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

In bioinformatica, la distanza di edit è strettamente collegata al problema dell'allineamento di sequenze. Inserimenti, cancellazioni e sostituzioni forniscono un modello semplice delle differenze tra sequenze di DNA o proteine; gli algoritmi di allineamento utilizzati nella pratica adottano però spesso matrici di sostituzione e penalità per i gap più ricche rispetto alla distanza di Levenshtein a costo unitario.

Unicode e unità di confronto

La definizione matematica opera su sequenze di simboli e non stabilisce che cosa debba essere considerato un «carattere» in una specifica implementazione. Nel testo Unicode, il confronto può avvenire a livello di byte codificati, unità di codice, punti di codice Unicode oppure cluster di grafemi estesi. Scelte diverse possono produrre valori di distanza diversi.

Questo aspetto è rilevante anche per l'italiano e per le trascrizioni dialettali. Una vocale accentata può essere rappresentata da un singolo punto di codice precomposto oppure da una vocale di base seguita da un segno diacritico combinante. Le due rappresentazioni possono essere canonicamente equivalenti pur non essendo sequenze identiche di punti di codice.

Unicode Standard Annex #15 definisce forme di normalizzazione quali NFC e NFD per trattare l'equivalenza canonica. Unicode Standard Annex #29 definisce invece gli extended grapheme clusters, una approssimazione algoritmica dei caratteri percepiti dall'utente.

Di conseguenza, un'implementazione che confronta testo Unicode dovrebbe specificare sia l'unità di confronto sia l'eventuale normalizzazione applicata prima del calcolo. Nel caso di OCR, trascrizioni fonetiche o materiali dialettali, i diacritici possono costituire informazioni linguistiche rilevanti e non devono essere eliminati automaticamente.

Limitazioni

La distanza di Levenshtein misura un costo minimo di edit, non una similarità semantica. Due parole con significati molto diversi possono differire per un solo carattere, mentre due espressioni semanticamente equivalenti possono avere una distanza elevata.

La versione classica assegna lo stesso costo a tutte le sostituzioni e non incorpora automaticamente somiglianze fonetiche, morfologiche, etimologiche o contestuali. Quando tali informazioni sono rilevanti, possono essere introdotte mediante pesi, pre-elaborazione o altre misure.

Anche in dialettometria, l'interpretazione della distanza dipende dalla rappresentazione scelta. Una misura adatta a quantificare differenze fonetiche non è necessariamente sufficiente a rappresentare da sola differenze lessicali o genealogiche fra varietà linguistiche.

Storia

Levenshtein pubblicò nel 1965 il lavoro che introdusse la distanza nel contesto dei codici capaci di correggere cancellazioni, inserimenti e sostituzioni. L'articolo originario non presentava la forma matriciale oggi più comunemente usata a fini didattici.

Nel 1974 Wagner e Fischer pubblicarono una formulazione generale mediante programmazione dinamica del problema di trasformazione da stringa a stringa. Negli anni successivi furono sviluppati algoritmi dipendenti dalla distanza effettiva, metodi bit-paralleli e tecniche di indicizzazione e ricerca approssimata.

Bibliografia

• V. I. Levenshtein, «Binary codes capable of correcting deletions, insertions, and reversals», Soviet Physics Doklady, vol. 10, 1966, pp. 707–710.
• Robert A. Wagner, Michael J. Fischer, «The String-to-String Correction Problem», Journal of the ACM, vol. 21, n. 1, 1974, pp. 168–173.
• Esko Ukkonen, «Algorithms for approximate string matching», Information and Control, vol. 64, n. 1–3, 1985, pp. 100–118.
• 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.
• Gonzalo Navarro, «A guided tour to approximate string matching», ACM Computing Surveys, vol. 33, n. 1, 2001, pp. 31–88.

Voci correlate

• Distanza di Hamming
• Programmazione dinamica
• Allineamento di sequenze
• Algoritmo di pattern matching su stringhe
• Bioinformatica

Altri progetti

Altri progetti

• Wikiquote

• Wikiquote contiene citazioni di o su distanza di Levenshtein

Collegamenti esterni

• (EN) Levenshtein Distance – risorsa sulla definizione, gli algoritmi, la storia, la letteratura scientifica e le applicazioni della distanza di Levenshtein.
• (EN) Levenshtein distance – Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology.