Problema di sottosequenza comune più lungo - Longest common subsequence problem

Confronto di due revisioni di un file di esempio, in base alla loro sottosequenza comune più lunga (nero)

La più lunga sottosequenza comune ( LCS ) problema è il problema di trovare la più lunga sottosequenza comune a tutte le sequenze in una serie di sequenze (spesso solo due sequenze). Differisce dal più lungo problema di sottostringa comune : a differenza delle sottostringhe, non è necessario che le sottosequenze occupino posizioni consecutive all'interno delle sequenze originali. Il problema di sottosequenza comune più lungo è un classico problema di informatica , la base dei programmi di confronto dei dati come l' utilità diff e ha applicazioni nella linguistica computazionale e nella bioinformatica . È anche ampiamente utilizzato dai sistemi di controllo delle revisioni come Git per riconciliare più modifiche apportate a una raccolta di file controllata dalla revisione.

Consideriamo ad esempio le sequenze (ABCD) e (ACBAD). Hanno 5 sottosequenze comuni di lunghezza 2: (AB), (AC), (AD), (BD) e (CD); 2 sottosequenze comuni di lunghezza-3: (ABD) e (ACD); e non più comuni sottosequenze. Quindi (ABD) e (ACD) sono le loro sottosequenze comuni più lunghe.

Complessità

Per il caso generale di un numero arbitrario di sequenze di input, il problema è NP-difficile . Quando il numero di sequenze è costante, il problema è risolvibile in tempo polinomiale mediante programmazione dinamica .

Date sequenze di lunghezze , una ricerca ingenua metterebbe alla prova ciascuna delle sottosequenze della prima sequenza per determinare se sono anche sottosequenze delle restanti sequenze; ogni sottosequenza può essere testata in tempo lineare nelle lunghezze delle sequenze rimanenti, quindi il tempo per questo algoritmo sarebbe $N$ $n_{1},...,n_{N}$ $2^{n_{1}}$

O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).

Per il caso di due sequenze di n e m elementi, il tempo di esecuzione dell'approccio di programmazione dinamica è O ( n × m ). Per un numero arbitrario di sequenze di input, l'approccio di programmazione dinamica fornisce una soluzione in

O\left(N\prod _{i=1}^{N}n_{i}\right).

Esistono metodi con complessità inferiore, che spesso dipendono dalla lunghezza dell'LCS, dalla dimensione dell'alfabeto o da entrambi.

La LCS non è necessariamente unica; nel peggiore dei casi, il numero di sottosequenze comuni è esponenziale nelle lunghezze degli ingressi, quindi la complessità algoritmica deve essere almeno esponenziale.

Soluzione per due sequenze

Il problema LCS ha una sottostruttura ottima : il problema può essere scomposto in sottoproblemi più piccoli e più semplici, che possono, a loro volta, essere scomposti in sottoproblemi più semplici, e così via, finché, alla fine, la soluzione diventa banale. LCS in particolare ha sottoproblemi sovrapposti : le soluzioni a sottoproblemi di alto livello spesso riutilizzano soluzioni a sottoproblemi di livello inferiore. Problemi con queste due proprietà sono suscettibili di programmazione dinamica approcci, in cui sono soluzioni sottoproblemi memoized , vale a dire, le soluzioni di sottoproblemi vengono salvate per il riutilizzo.

prefissi

Il prefisso S _n di S è definito come i primi n caratteri di S . Ad esempio, i prefissi di S = (AGCA) sono

S ₀ = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA).

Sia LCS ( X , Y ) una funzione che calcola una sottosequenza più lunga comune a X e Y . Tale funzione ha due proprietà interessanti.

Prima proprietà

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y )^ A , per tutte le stringhe X , Y e tutti i simboli A , dove ^ indica la concatenazione di stringhe. Ciò consente di semplificare il calcolo LCS per due sequenze che terminano con lo stesso simbolo. Ad esempio, LCS ("BANANA","ATANA") = LCS ("BANAN","ATAN")^"A", Continuando per i restanti simboli comuni, LCS ("BANANA","ATANA") = LCS (" BAN","AT")^"ANA".

Seconda proprietà

Se A e B sono simboli distinti ( A ≠ B ), allora LCS (X^A,Y^B) è una delle stringhe di lunghezza massima nell'insieme { LCS ( X ^ A , Y ), LCS ( X , Y ^ B ) }, per tutte le stringhe X , Y .

Ad esempio, LCS ("ABCDEFG","BCDGK") è la stringa più lunga tra LCS ("ABCDEFG","BCDG") e LCS ("ABCDEF","BCDGK"); se entrambi erano di uguale lunghezza, uno di loro poteva essere scelto arbitrariamente.

Per realizzare l'immobile distinguere due casi:

Se LCS ("ABCDEFG","BCDGK") termina con una "G", allora la "K" finale non può essere nella LCS, quindi LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEFG","BCDG ").
Se LCS ("ABCDEFG","BCDGK") non termina con una "G", allora la "G" finale non può essere nella LCS, quindi LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEF", "BCDGK").

Funzione LCS definita

Si definiscano due sequenze come segue: e . I prefissi di sono ; i prefissi di sono . Lasciate che rappresentano l'insieme di più lunga sottosequenza comune di prefissi e . Questo insieme di sequenze è dato da quanto segue. $X=(x_{1}x_{2}\cdots x_{m})$ $Y=(y_{1}y_{2}\cdots y_{n})$ $X$ $X_{1,2,\dots ,m}$ $Y$ $Y_{1,2,\dots ,n}$ ${\mathit {LCS}}(X_{i},Y_{j})$ $X_{i}$ $Y_{j}$

{\mathit {LCS}}(X_{i},Y_{j})={\begin{casi}\emptyset &{\mbox{se }}i=0{\mbox{ o }}j= 0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{if }}i,j>0{\ mbox{ e }}x_{i}=y_{j}\\\nomeoperatore {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS }}(X_{i-1},Y_{j})\}&{\mbox{se }}i,j>0{\mbox{ e }}x_{i}\neq y_{j}.\end {casi}}

Per trovare l'LCS di e , confrontare e . Se sono uguali, la sequenza viene estesa da quell'elemento, . Se non sono uguali , viene conservata la più lunga tra le due sequenze, , e . (Se sono della stessa lunghezza, ma non identici, vengono mantenuti entrambi.) $X_{i}$ $Y_{j}$ $x_{i}$ $y_{j}$ ${\mathit {LCS}}(X_{i-1},Y_{j-1})$ $x_{i}$ ${\mathit {LCS}}(X_{i},Y_{j-1})$ ${\mathit {LCS}}(X_{i-1},Y_{j})$

Esempio funzionante

Verrà trovata la sottosequenza più lunga comune a R = (GAC) e C = (AGCAT). Poiché la funzione LCS utilizza un elemento "zeroth", è conveniente definire prefissi zero vuoti per queste sequenze: R ₀ = Ø; e C ₀ = Ø. Tutti i prefissi sono collocati in una tabella con C nella prima riga (rendendolo un c olumn intestazione) e R nella prima colonna (rendendolo un r ow intestazione).

Stringhe LCS
	Ø	UN	G	C	UN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
UN	Ø
C	Ø

Questa tabella viene utilizzata per memorizzare la sequenza LCS per ogni fase del calcolo. La seconda colonna e la seconda riga sono state riempite con Ø, perché quando una sequenza vuota viene confrontata con una sequenza non vuota, la sottosequenza comune più lunga è sempre una sequenza vuota.

LCS ( R ₁ , C ₁ ) è determinato confrontando i primi elementi in ciascuna sequenza. G e A non sono la stessa cosa, quindi questa LCS ottiene (usando la "seconda proprietà") la più lunga delle due sequenze, LCS ( R ₁ , C ₀ ) e LCS ( R ₀ , C ₁ ). Secondo la tabella, entrambi sono vuoti, quindi anche LCS ( R ₁ , C ₁ ) è vuoto, come mostrato nella tabella seguente. Le frecce indicano che la sequenza proviene sia dalla cella sopra, LCS ( R ₀ , C ₁ ) che dalla cella a sinistra, LCS ( R ₁ , C ₀ ).

LCS ( R ₁ , C ₂ ) è determinato confrontando G e G. Corrispondono, quindi G viene aggiunto alla sequenza in alto a sinistra, LCS ( R ₀ , C ₁ ), che è (Ø), dando (ØG), che è (G).

Per LCS ( R ₁ , C ₃ ), G e C non corrispondono. La sequenza sopra è vuota; quello a sinistra contiene un elemento, G. Selezionando il più lungo di questi, LCS ( R ₁ , C ₃ ) è (G). La freccia punta a sinistra, poiché questa è la più lunga delle due sequenze.

LCS ( R ₁ , C ₄ ), analogamente, è (G).

LCS ( R ₁ , C ₅ ), analogamente, è (G).

Riga "G" completata
	Ø	UN	G	C	UN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
UN	Ø
C	Ø

Per LCS ( R ₂ , C ₁ ), A viene confrontato con A. I due elementi corrispondono, quindi A viene aggiunto a Ø, dando (A).

Per LCS ( R ₂ , C ₂ ), A e G non corrispondono, quindi il più lungo di LCS ( R ₁ , C ₂ ), che è (G), e LCS ( R ₂ , C ₁ ), che è (A ), viene utilizzato. In questo caso, contengono ciascuno un elemento, quindi a questa LCS vengono date due sottosequenze: (A) e (G).

Per LCS ( R ₂ , C ₃ ), A non corrisponde a C. LCS ( R ₂ , C ₂ ) contiene le sequenze (A) e (G); LCS( R ₁ , C ₃ ) è (G), che è già contenuto in LCS ( R ₂ , C ₂ ). Il risultato è che LCS ( R ₂ , C ₃ ) contiene anche le due sottosuccessioni, (A) e (G).

Per LCS ( R ₂ , C ₄ ), A corrisponde ad A, che viene aggiunto alla cella in alto a sinistra, dando (GA).

Per LCS ( R ₂ , C ₅ ), A non corrisponde a T. Confrontando le due sequenze, (GA) e (G), la più lunga è (GA), quindi LCS ( R ₂ , C ₅ ) è (GA).

Righe "G" e "A" completate
	Ø	UN	G	C	UN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
UN	Ø	${\overset {\nwarrow }{\ }}$ (UN)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) e (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) e (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	Ø

Per LCS ( R ₃ , C ₁ ), C e A non corrispondono, quindi LCS ( R ₃ , C ₁ ) ottiene la più lunga delle due sequenze, (A).

Per LCS ( R ₃ , C ₂ ), C e G non corrispondono. Sia LCS ( R ₃ , C ₁ ) che LCS ( R ₂ , C ₂ ) hanno un elemento. Il risultato è che LCS ( R ₃ , C ₂ ) contiene le due sottosuccessioni, (A) e (G).

Per LCS ( R ₃ , C ₃ ), C e C corrispondono, quindi C viene aggiunto a LCS ( R ₂ , C ₂ ), che contiene le due sottosequenze, (A) e (G), dando (AC) e (GC ).

Per LCS ( R ₃ , C ₄ ), C e A non corrispondono. Combinando LCS ( R ₃ , C ₃ ), che contiene (AC) e (GC), e LCS ( R ₂ , C ₄ ), che contiene (GA), si ottiene un totale di tre sequenze: (AC), (GC) , e (GA).

Infine, per LCS ( R ₃ , C ₅ ), C e T non corrispondono. Il risultato è che LCS ( R ₃ , C ₅ ) contiene anche le tre sequenze, (AC), (GC) e (GA).

Tabella LCS completata
	Ø	UN	G	C	UN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
UN	Ø	${\overset {\nwarrow }{\ }}$ (UN)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) e (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) e (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	Ø	${\overset {\ \uparrow }{\ }}$ (UN)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) e (G)	${\overset {\nwarrow }{\ }}$ (AC) e (GC)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) e (GC) e (GA)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) e (GC) e (GA)

Il risultato finale è che l'ultima cella contiene tutte le sottosequenze più lunghe comuni a (AGCAT) e (GAC); questi sono (AC), (GC) e (GA). La tabella mostra anche le sottosequenze comuni più lunghe per ogni possibile coppia di prefissi. Ad esempio, per (AGC) e (GA), le sottosequenze comuni più lunghe sono (A) e (G).

Approccio traceback

Il calcolo dell'LCS di una riga della tabella LCS richiede solo le soluzioni della riga corrente e della riga precedente. Tuttavia, per sequenze lunghe, queste sequenze possono diventare numerose e lunghe, richiedendo molto spazio di archiviazione. È possibile risparmiare spazio di archiviazione salvando non le sottosequenze effettive, ma la lunghezza della sottosequenza e la direzione delle frecce, come nella tabella seguente.

Memorizzazione della lunghezza, piuttosto che delle sequenze
	UN	G	C	UN	T
Ø	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
UN	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

Le effettive sottosequenze vengono dedotte in una procedura di "traceback" che segue le frecce a ritroso, partendo dall'ultima cella della tabella. Quando la lunghezza diminuisce, le sequenze devono avere avuto un elemento comune. Sono possibili diversi percorsi quando vengono visualizzate due frecce in una cella. Di seguito è riportata la tabella per tale analisi, con i numeri colorati nelle celle in cui la lunghezza sta per diminuire. I numeri in grassetto tracciano la sequenza, (GA).

Esempio di traceback
	UN	G	C	UN	T
Ø	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
UN	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

Relazione con altri problemi

Per due stringhe e , la lunghezza della supersequenza comune più breve è correlata alla lunghezza della LCS da $X_{1\dots m}$ $Y_{1\dots n}$

\left|SCS(X,Y)\right|=n+m-\left|LCS(X,Y)\right|.

La distanza di modifica quando è consentito solo l'inserimento e la cancellazione (nessuna sostituzione), o quando il costo della sostituzione è il doppio del costo di un inserimento o cancellazione, è:

d'(X,Y)=n+m-2\cdot \left|LCS(X,Y)\right|.

Codice per la soluzione di programmazione dinamica

Calcolo della lunghezza della LCS

La funzione seguente prende come input le sequenze X[1..m]e Y[1..n], calcola il LCS tra X[1..i]e Y[1..j]per tutti 1 ≤ i ≤ me 1 ≤ j ≤ n, e lo memorizza in C[i,j]. C[m,n]conterrà la lunghezza della LCS di Xe Y.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
        C[i,0] = 0
    for j := 0..n
        C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

In alternativa, potrebbe essere utilizzata la memorizzazione .

Esempio in C#

static int[,] LcsLength(string a, string b)
{
    int[,] C = new int[a.Length + 1, b.Length + 1]; // (a, b).Length + 1
    for (int i = 0; i < a.Length; i++)
        C[i, 0] = 0;
    for (int j = 0; j < b.Length; j++)
        C[0, j] = 0;
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
        {
            if (a[i - 1] == b[j - 1])//i-1,j-1
                C[i, j] = C[i - 1, j - 1] + 1;
            else
                C[i, j] = Math.Max(C[i, j - 1], C[i - 1, j]);
        }
    return C;
}

Lettura di un LCS

La seguente funzione ripercorre le scelte effettuate durante il calcolo della Ctabella. Se gli ultimi caratteri nei prefissi sono uguali, devono essere in un LCS. In caso contrario, controlla cosa ha fornito la LCS più grande di mantenimento e , e fai la stessa scelta. Scegline uno solo se erano ugualmente lunghi. Chiama la funzione con e . $x_{i}$ $y_{j}$ i=mj=n

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    if C[i,j-1] > C[i-1,j]
        return backtrack(C, X, Y, i, j-1)
    return backtrack(C, X, Y, i-1, j)

Esempio in C#

string Backtrack(int[,] C, char[] aStr, char[] bStr, int x, int y)
{
    if (x == 0 | y == 0)
        return "";
    if (aStr[x - 1] == bStr[y - 1]) // x-1, y-1
        return backtrack(C, aStr, bStr, x - 1, y - 1) + aStr[x - 1]; // x-1
    if (C[x, y - 1] > C[x - 1, y])
        return backtrack(C, aStr, bStr, x, y - 1);
    return backtrack(C, aStr, bStr, x - 1, y);
}

Lettura di tutte le LCS

Se scegli e darebbe un risultato ugualmente lungo, leggi entrambe le sottosequenze risultanti. Questo viene restituito come set da questa funzione. Nota che questa funzione non è polinomiale, poiché potrebbe ramificarsi in quasi tutti i passaggi se le stringhe sono simili. $x_{i}$ $y_{j}$

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    R := {}
    if C[i,j-1] ≥ C[i-1,j]
        R := backtrackAll(C, X, Y, i, j-1)
    if C[i-1,j] ≥ C[i,j-1]
        R := R ∪ backtrackAll(C, X, Y, i-1, j)
    return R

Stampa la differenza

Questa funzione ripercorrerà la matrice C e stamperà la differenza tra le due sequenze. Nota che otterrai una risposta diversa se scambi ≥e <, con >e ≤sotto.

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i >= 0 and j >= 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

Esempio

Sia “ ” e sia “ ”. La sottosequenza comune più lunga tra e è “ ”. La tabella mostrata di seguito, generata dalla funzione , mostra le lunghezze delle sottosequenze comuni più lunghe tra i prefissi di e . La th riga e th colonna mostra la lunghezza dell'LCS tra e . $X$ XMJYAUZ $Y$ MZJAWXU $X$ $Y$ MJAUCLCSLength $X$ $Y$ $i$ $j$ $X_{1..i}$ $Y_{1..j}$

		0	1	2	3	4	5	6	7
		Ø	m	Z	J	UN	W	X	tu
0	Ø	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	m	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	sì	0	1	1	2	2	2	2	2
5	UN	0	1	1	2	3	3	3	3
6	tu	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

I numeri evidenziati mostrano il percorso che la funzione backtrackseguirebbe dall'angolo in basso a destra all'angolo in alto a sinistra, durante la lettura di un LCS. Se i simboli attuali in e sono uguali, fanno parte dell'LCS e andiamo sia in alto che a sinistra (mostrati in grassetto ). In caso contrario, saliamo o andiamo a sinistra, a seconda di quale cella ha un numero più alto. Ciò corrisponde a prendere l'LCS tra e , o e . $X$ $Y$ $X_{1..i-1}$ $Y_{1..j}$ $X_{1..i}$ $Y_{1..j-1}$

Ottimizzazione del codice

È possibile apportare diverse ottimizzazioni all'algoritmo sopra per velocizzarlo per i casi del mondo reale.

Riduci il set di problemi

La matrice C nell'algoritmo ingenuo cresce quadraticamente con le lunghezze delle sequenze. Per due sequenze di 100 elementi, sarebbe necessaria una matrice di 10.000 elementi e sarebbe necessario eseguire 10.000 confronti. Nella maggior parte dei casi reali, in particolare le differenze e le patch del codice sorgente, l'inizio e la fine dei file cambiano raramente e quasi certamente non entrambi contemporaneamente. Se solo pochi elementi sono cambiati nel mezzo della sequenza, l'inizio e la fine possono essere eliminati. Ciò riduce non solo i requisiti di memoria per la matrice, ma anche il numero di confronti che devono essere eseguiti.

function LCS(X[1..m], Y[1..n])
    start := 1
    m_end := m
    n_end := n
    trim off the matching items at the beginning
    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
        start := start + 1
    trim off the matching items at the end
    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    C = array(start-1..m_end, start-1..n_end)
    only loop over the items that have changed
    for i := start..m_end
        for j := start..n_end
            the algorithm continues as before ...

Nel migliore dei casi, una sequenza senza modifiche, questa ottimizzazione eliminerebbe completamente la necessità della matrice C. Nello scenario peggiore, una modifica al primo e all'ultimo elemento della sequenza, vengono eseguiti solo due confronti aggiuntivi.

Riduci il tempo di confronto

La maggior parte del tempo impiegato dall'algoritmo ingenuo viene impiegato per eseguire confronti tra gli elementi nelle sequenze. Per le sequenze testuali come il codice sorgente, si desidera visualizzare le righe come elementi della sequenza anziché come singoli caratteri. Ciò può significare confronti di stringhe relativamente lunghe per ogni passaggio dell'algoritmo. È possibile effettuare due ottimizzazioni che possono aiutare a ridurre il tempo che consumano questi confronti.

Riduci le stringhe in hash

Una funzione hash o checksum può essere utilizzata per ridurre la dimensione delle stringhe nelle sequenze. Cioè, per il codice sorgente in cui la riga media è lunga 60 o più caratteri, l'hash o il checksum per quella riga potrebbe essere lungo solo da 8 a 40 caratteri. Inoltre, la natura casuale di hash e checksum garantirebbe che i confronti si cortocircuitino più velocemente, poiché le righe del codice sorgente raramente verranno modificate all'inizio.

Ci sono tre principali svantaggi di questa ottimizzazione. Innanzitutto, è necessario spendere in anticipo una quantità di tempo per precalcolare gli hash per le due sequenze. In secondo luogo, è necessario allocare memoria aggiuntiva per le nuove sequenze hash. Tuttavia, rispetto all'algoritmo ingenuo qui utilizzato, entrambi questi inconvenienti sono relativamente minimi.

Il terzo inconveniente è quello delle collisioni . Poiché non è garantito che il checksum o l'hash siano univoci, c'è una piccola possibilità che due elementi diversi possano essere ridotti allo stesso hash. Questo è improbabile nel codice sorgente, ma è possibile. Un hash crittografico sarebbe quindi molto più adatto per questa ottimizzazione, poiché la sua entropia sarà significativamente maggiore di quella di un semplice checksum. Tuttavia, i vantaggi potrebbero non valere la configurazione e i requisiti di calcolo di un hash crittografico per sequenze di lunghezza ridotta.

Riduci lo spazio richiesto

Se è richiesta solo la lunghezza dell'LCS, la matrice può essere ridotta facilmente a una matrice oa un vettore (più intelligente) poiché l'approccio di programmazione dinamica richiede solo le colonne attuali e precedenti della matrice. L'algoritmo di Hirschberg permette la costruzione della stessa sequenza ottima nello stesso tempo quadratico e nei limiti dello spazio lineare. $2\times \min(n,m)$ $\min(m,n)+1$

Algoritmi ulteriormente ottimizzati

Esistono diversi algoritmi che funzionano più velocemente dell'approccio di programmazione dinamico presentato. Uno di questi è l' algoritmo di Hunt-Szymanski , che in genere viene eseguito nel tempo (per ), dove è il numero di corrispondenze tra le due sequenze. Per problemi con una dimensione alfabetica limitata, il metodo dei quattro russi può essere utilizzato per ridurre il tempo di esecuzione dell'algoritmo di programmazione dinamica di un fattore logaritmico. $O((n+r)\log(n))$ $n>m$ $r$

Comportamento su stringhe casuali

A partire da Chvátal & Sankoff (1975) , un certo numero di ricercatori ha studiato il comportamento della lunghezza della sottosequenza comune più lunga quando le due stringhe date sono estratte casualmente dallo stesso alfabeto. Quando la dimensione dell'alfabeto è costante, la lunghezza prevista dell'LCS è proporzionale alla lunghezza delle due stringhe e le costanti di proporzionalità (a seconda della dimensione dell'alfabeto) sono note come costanti di Chvátal-Sankoff . I loro valori esatti non sono noti, ma sono stati dimostrati i limiti superiore e inferiore dei loro valori ed è noto che crescono in modo inversamente proporzionale alla radice quadrata della dimensione dell'alfabeto. È stato dimostrato che modelli matematici semplificati del problema di sottosequenza comune più lungo sono controllati dalla distribuzione di Tracy-Widom .

Languages

In other projects

Problema di sottosequenza comune più lungo - Longest common subsequence problem

Contenuti

Complessità

Soluzione per due sequenze

prefissi

Prima proprietà

Seconda proprietà

Funzione LCS definita

Esempio funzionante

Approccio traceback

Relazione con altri problemi

Codice per la soluzione di programmazione dinamica

Calcolo della lunghezza della LCS

Esempio in C#

Lettura di un LCS

Esempio in C#

Lettura di tutte le LCS

Stampa la differenza

Esempio

Ottimizzazione del codice

Riduci il set di problemi

Riduci il tempo di confronto

Riduci le stringhe in hash

Riduci lo spazio richiesto

Algoritmi ulteriormente ottimizzati

Comportamento su stringhe casuali

Guarda anche

Riferimenti

link esterno

		0	1	2	3	4	5	6	7
		Ø	m	Z	J	UN	W	X	tu
0	Ø	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	m	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	sì	0	1	1	2	2	2	2	2
5	UN	0	1	1	2	3	3	3	3
6	tu	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

		0	1	2	3	4	5	6	7
		Ø	m	Z	J	UN	W	X	tu
0	Ø	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	m	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	sì	0	1	1	2	2	2	2	2
5	UN	0	1	1	2	3	3	3	3
6	tu	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

		0	1	2	3	4	5	6	7
		Ø	m	Z	J	UN	W	X	tu
0	Ø	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	m	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	sì	0	1	1	2	2	2	2	2
5	UN	0	1	1	2	3	3	3	3
6	tu	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4