Sottosequenza comune più lunga (LCS)

Quando confronti due versioni di un file, le righe che non sono cambiate sono una sottosequenza comune a entrambe. Trovare la più lunga ti dice esattamente che cosa è stato aggiunto e che cosa è stato tolto. La stessa idea allinea filamenti di DNA e suggerisce correzioni ortografiche, e si risolve con una delle tabelle più eleganti dell'informatica.

Una tabella con una parola in alto e un'altra lungo il lato, numeri nelle celle e un percorso di celle arancioni che risale dall'angolo in basso a destra
Una tabella con una parola in alto e un'altra lungo il lato, numeri nelle celle e un percorso di celle arancioni che risale dall'angolo in basso a destra

Il problema

Una sottosequenza di una parola mantiene alcune delle sue lettere nel loro ordine originale: ACE è una sottosequenza di ABCDE, ma EA no. Una sottosequenza comune di due parole è una sottosequenza di entrambe, e il problema è trovare la più lunga. Una parola di lunghezza n ha 2ⁿ sottosequenze, quindi provarle tutte è senza speranza appena le lettere sono più di poche.

La tabella

Sia len[i][j] la lunghezza della sottosequenza comune più lunga tra le prime i lettere di una parola e le prime j lettere dell'altra. Una parola vuota non ha niente in comune con nessuna, quindi la prima riga e la prima colonna valgono 0. Se la lettera i è uguale alla lettera j, len[i][j] = len[i − 1][j − 1] + 1: la corrispondenza allunga ciò che c'era prima. Altrimenti len[i][j] è il più grande tra len[i − 1][j] e len[i][j − 1]: si scarta una delle due lettere e si tiene il risultato migliore.

Un esempio

Confronta ABCBDAB con BDCABA. La prima lettera della seconda parola, B, coincide con la B della riga 2; la C nella terza colonna coincide con la riga 3, e così via, e ogni corrispondenza aggiunge uno alla cella in alto a sinistra. La cella in basso a destra arriva a 4. Rileggendo da lì si ottiene BCBA, ma BCAB e BDAB sono altrettanto lunghe: una sottosequenza comune più lunga non è per forza unica.

Rileggere la risposta

Parti dalla cella in basso a destra. Se le lettere della sua riga e della sua colonna coincidono, quella lettera fa parte della risposta: annotala e spostati in diagonale in alto a sinistra. Altrimenti spostati sulla cella vicina, sopra o a sinistra, con il valore più grande, perché è da lì che la cella ha preso il suo valore. Fermati alla prima riga o colonna. Le lettere annotate, in ordine inverso, sono la sottosequenza.

Storia e applicazioni

Il metodo della tabella fu scoperto in modo indipendente da diverse persone intorno al 1970, tra cui Robert Wagner e Michael Fischer, il cui articolo del 1974 risolveva il problema strettamente legato della distanza di edit. Nel 1975 Dan Hirschberg mostrò come trovare la sottosequenza con molta meno memoria, e nel 1976 James Hunt e Douglas McIlroy costruirono il programma Unix diff sulle sottosequenze comuni più lunghe di righe. I biologi usano la stessa idea, con dei punteggi, per allineare sequenze di DNA e di proteine.

Douglas McIlroy, fotografato da Peter Adams per Faces of Open Source. Nel 1976 lui e James Hunt basarono il programma Unix diff sulle più lunghe sottosequenze comuni di righe.
Douglas McIlroy, fotografato da Peter Adams per Faces of Open Source. Nel 1976 lui e James Hunt basarono il programma Unix diff sulle più lunghe sottosequenze comuni di righe.

Esploralo

Apri l'app e premi Passo. Le due lettere confrontate si illuminano nelle intestazioni; una corrispondenza legge la cella blu in alto a sinistra, una differenza legge le due celle blu sopra e a sinistra. Quando la tabella è piena, il percorso arancione risale dall'angolo e le lettere della risposta compaiono sotto la tabella.

Domande frequenti

Di quanto tempo e quanta memoria ha bisogno l'algoritmo LCS?

Tempo O(m·n) per parole di lunghezza m e n. Anche la tabella completa richiede memoria O(m·n) per rileggere la risposta; nel 1975 Dan Hirschberg mostrò come trovare la sottosequenza stessa con solo O(min(m, n)) di memoria.

Come usa diff la sottosequenza comune più lunga?

Tratta ogni riga di un file come un unico simbolo e trova una sottosequenza comune più lunga delle righe dei due file. Le righe in quella sottosequenza sono invariate; le altre righe del vecchio file sono state cancellate, e le altre righe del nuovo file sono state aggiunte.

E con tre o più parole?

La tabella ha una dimensione per ogni parola, quindi tre parole di lunghezza n richiedono n³ celle. Per un numero arbitrario di parole il problema è NP-difficile.

Che legame c'è tra la LCS e la distanza di edit?

Se sono ammessi solo inserimenti e cancellazioni, la distanza di edit di due parole è la loro lunghezza totale meno il doppio della lunghezza della loro sottosequenza comune più lunga. Ammettendo anche le sostituzioni si ottiene la distanza di Levenshtein, calcolata con una tabella molto simile.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Prova la sottosequenza comune più lunga