Distanza di edit (distanza di Levenshtein)
Scrivi recieve e il telefono ti suggerisce receive. Sa che ci eri andato vicino perché le due parole distano solo un paio di modifiche. Misurare questa vicinanza, la distanza di edit, è un classico compito per la programmazione dinamica.
Il problema
Una modifica cambia una parola di una lettera: inserire una lettera, cancellare una lettera o sostituire una lettera con un'altra. La distanza di edit tra due parole è il numero minimo di modifiche che trasformano l'una nell'altra. Tra cat e cut la distanza è 1, tra cat e cast anche 1, e tra cat e act 2. Si chiama anche distanza di Levenshtein, dal nome del matematico sovietico Vladimir Levenshtein, che la studiò nel 1965.
La tabella
Sia d[i][j] la distanza di edit tra le prime i lettere di una parola e le prime j lettere dell'altra. Trasformare una parola nel nulla richiede una cancellazione per lettera, quindi d[i][0] = i, e costruire una parola dal nulla richiede un inserimento per lettera, quindi d[0][j] = j. Se la lettera i è uguale alla lettera j, d[i][j] = d[i − 1][j − 1]. Altrimenti d[i][j] = 1 + il minimo tra d[i − 1][j − 1] (sostituzione), d[i − 1][j] (cancellazione) e d[i][j − 1] (inserimento).
Un esempio
Per kitten e sitting la tabella ha 7 righe e 8 colonne. La cella in basso a destra vale 3, e rileggendo da lì si ottiene: sostituire k con s, mantenere i, t e t, sostituire e con i, mantenere n e inserire g. Da kitten a sitten, poi sittin, poi sitting: tre modifiche, e la tabella dimostra che non esiste una lista più corta.
Rileggere le modifiche
Parti dalla cella in basso a destra e chiediti da quale vicino viene il suo valore. Se le lettere coincidono e la cella è uguale al vicino in alto a sinistra, la lettera è stata mantenuta: spostati in diagonale. Se vale uno in più del vicino in alto a sinistra, era una sostituzione; uno in più della cella sopra, una cancellazione; uno in più della cella a sinistra, un inserimento. Più percorsi possono essere alla pari, e ognuno dà una lista di modifiche più corta possibile.
Storia e applicazioni
Levenshtein introdusse la distanza nel 1965 mentre lavorava sui codici a correzione d'errore. Il metodo della tabella fu pubblicato da diverse persone, in particolare da Robert Wagner e Michael Fischer nel 1974, per questo è spesso chiamato algoritmo di Wagner–Fischer. Oggi le distanze di edit ordinano i suggerimenti ortografici, trovano nei database nomi scritti con errori, confrontano sequenze di DNA e di proteine e valutano il riconoscimento vocale.
Provala tu
Apri l'app e premi Passo. Le due lettere confrontate si illuminano nelle intestazioni; se sono uguali si copia la cella blu in alto a sinistra, se sono diverse si leggono tutti e tre i vicini blu e si aggiunge uno al minimo. Alla fine il percorso arancione torna indietro dall'angolo, e le modifiche compaiono sotto la tabella.
Domande frequenti
La distanza di edit è una metrica?
Sì. Non è mai negativa, vale 0 solo per parole uguali, è la stessa nei due versi, e passare per una terza parola non può mai accorciarla: d(a, c) ≤ d(a, b) + d(b, c). Per questo è utile per cercare corrispondenze simili.
Che cos'è la distanza di Damerau–Levenshtein?
È la distanza di edit con una modifica in più: lo scambio di due lettere vicine. Nel 1964 Frederick Damerau scoprì che inserimento, cancellazione, sostituzione e scambio insieme coprono più dell'80% degli errori di ortografia. Con gli scambi, recieve e receive distano 1 invece di 2.
Si può calcolare la distanza di edit più velocemente di O(m·n)?
Non di molto. Nel 2015 Arturs Backurs e Piotr Indyk hanno dimostrato che un metodo con tempo O(n^(2 − ε)) per qualche ε > 0 smentirebbe l'ipotesi del tempo esponenziale forte, che la maggior parte dei ricercatori ritiene vera. Per parole simili, però, basta una stretta fascia attorno alla diagonale della tabella.
Come si usa la distanza di edit nel confronto del DNA?
I biologi usano la stessa tabella con punteggi al posto dei conteggi: le corrispondenze fanno guadagnare punti, mentre sostituzioni e lacune costano punti che dipendono dalle lettere. È l'algoritmo di Needleman–Wunsch del 1970 per sequenze intere, e l'algoritmo di Smith–Waterman del 1981 per i tratti che corrispondono meglio.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova la distanza di edit