Quando un motore di ricerca propone «forse cercavi…», quando un correttore ortografico suggerisce la parola giusta o quando uno strumento di versionamento mostra le righe cambiate tra due versioni di un file, dietro c'è la stessa domanda: quanto sono diverse due sequenze, e qual è il modo più economico di trasformare l'una nell'altra? La risposta classica è la distanza di edit, e il modo per calcolarla è uno degli esempi più eleganti di programmazione dinamica.
La distanza di Levenshtein
La distanza di Levenshtein tra due stringhe è il numero minimo di operazioni elementari per trasformare la prima nella seconda. Le operazioni ammesse sono tre, ciascuna di costo 1:
- inserimento di un carattere;
- cancellazione di un carattere;
- sostituzione di un carattere con un altro.
Da «gatto» a «matto» basta una sostituzione: distanza 1. Da «casa» a «cassa» basta un inserimento: distanza 1. Da «kitten» a «sitting» servono tre operazioni: due sostituzioni (k → s, e → i) e un inserimento (g finale).
La ricorrenza
Sia D(i, j) la distanza tra i primi i caratteri di A e i primi j caratteri di B. Guardiamo gli ultimi caratteri dei due prefissi:
- se sono uguali, non serve fare nulla: D(i, j) = D(i − 1, j − 1);
- altrimenti si sceglie la migliore tra tre opzioni:
- sostituire: 1 + D(i − 1, j − 1);
- cancellare l'ultimo carattere di A: 1 + D(i − 1, j);
- inserire l'ultimo carattere di B: 1 + D(i, j − 1).
I casi base sono intuitivi: D(i, 0) = i, perché per arrivare alla stringa vuota bisogna cancellare tutto; D(0, j) = j, perché partendo dal vuoto bisogna inserire tutto.
Un esempio con la tabella
Confrontiamo «sole» e «sale». La tabella ha una riga per ogni prefisso di «sole» e una colonna per ogni prefisso di «sale»:
| ε | s | a | l | e | |
|---|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 | 4 |
| s | 1 | 0 | 1 | 2 | 3 |
| o | 2 | 1 | 1 | 2 | 3 |
| l | 3 | 2 | 2 | 1 | 2 |
| e | 4 | 3 | 3 | 2 | 1 |
La cella in basso a destra vale 1: basta sostituire la «o» con la «a». Seguendo all'indietro le scelte che hanno prodotto ogni cella si ricostruisce anche la sequenza di operazioni, cioè l'allineamento tra le due stringhe.
Il codice
def levenshtein(a, b):
prec = list(range(len(b) + 1))
for i, ca in enumerate(a, 1):
corr = [i]
for j, cb in enumerate(b, 1):
if ca == cb:
corr.append(prec[j - 1])
else:
corr.append(1 + min(prec[j - 1], prec[j], corr[j - 1]))
prec = corr
return prec[-1]
Il tempo è proporzionale al prodotto delle lunghezze, |A| · |B|. Poiché ogni riga dipende solo dalla precedente, la memoria si riduce a due righe. Se però serve ricostruire l'allineamento, bisogna tenere l'intera tabella oppure usare tecniche più sofisticate come quella di Hirschberg, che recupera l'allineamento in memoria lineare dividendo il problema a metà.
Varianti utili
- Pesi diversi: in un correttore per tastiera, sostituire una lettera con una adiacente può costare meno che con una lontana. Basta cambiare i costi nella ricorrenza.
- Trasposizioni: la distanza di Damerau-Levenshtein conta come una sola operazione lo scambio di due caratteri adiacenti, l'errore di battitura più comune («teh» al posto di «the»).
- Soglia massima: se interessa solo sapere se la distanza è al massimo k, basta calcolare una fascia diagonale larga 2k + 1 della tabella. È così che si cerca velocemente tra molti candidati.
- Allineamento di sequenze biologiche: gli algoritmi di Needleman-Wunsch (allineamento globale) e Smith-Waterman (allineamento locale) sono la stessa idea con punteggi per corrispondenze, differenze e lacune.
La sottosequenza comune più lunga
Un problema parente è la sottosequenza comune più lunga (LCS): la sequenza più lunga di elementi che compaiono in entrambe le stringhe nello stesso ordine, anche non consecutivi. Per «ABCBDAB» e «BDCABA» una LCS ha lunghezza 4, per esempio «BCBA».
La ricorrenza è simile: se gli ultimi elementi coincidono si aggiunge 1 alla soluzione dei prefissi più corti, altrimenti si prende il massimo tra togliere un elemento da una sequenza o dall'altra. Se si ammettono solo inserimenti e cancellazioni, la distanza di edit è uguale a |A| + |B| − 2 · LCS.
Come funziona un diff
Gli strumenti che confrontano file di testo applicano la stessa logica considerando come elementi le righe invece dei caratteri: le righe della LCS sono quelle invariate, le altre sono marcate come aggiunte o rimosse. Per file lunghi la tabella completa sarebbe troppo grande, e gli strumenti reali usano algoritmi più efficienti, come quello di Myers, che lavorano bene quando le differenze sono poche rispetto alla lunghezza dei file. È il caso tipico delle modifiche al codice sorgente.
Nell'analisi di documenti, confrontare due versioni di un contratto o di una pagina web con un diff per righe e poi per parole rende evidenti modifiche che a occhio sfuggirebbero.
In sintesi
- La distanza di Levenshtein conta inserimenti, cancellazioni e sostituzioni minime tra due stringhe.
- Si calcola con una tabella di programmazione dinamica in tempo |A| · |B|.
- Ripercorrendo la tabella si ottiene l'allineamento, cioè la sequenza di modifiche.
- Pesi, trasposizioni e soglie adattano l'algoritmo a correttori e ricerche approssimate.
- La sottosequenza comune più lunga è alla base degli strumenti di diff tra file.
