Cea mai lungă problemă comună de subsecvență - Longest common subsequence problem

Compararea a două revizuiri ale unui fișier exemplu, pe baza celei mai lungi subsecvențe comune (negru)

Cea mai lungă problemă de subsecvență comună ( LCS ) este problema găsirii celei mai lungi subsecvențe comune tuturor secvențelor dintr-un set de secvențe (adesea doar două secvențe). Acesta diferă de cea mai lungă problemă comună de șiruri : spre deosebire de șiruri, subsecvențele nu sunt necesare pentru a ocupa poziții consecutive în cadrul secvențelor originale. Cea mai lungă problemă comună de subsecvență este o problemă clasică de informatică , baza programelor de comparație a datelor , cum ar fi utilitarul diff , și are aplicații în lingvistică computațională și bioinformatică . De asemenea, este utilizat pe scară largă de sistemele de control al reviziilor, cum ar fi Git, pentru reconcilierea mai multor modificări aduse unei colecții de fișiere controlate de revizie.

De exemplu, luați în considerare secvențele (ABCD) și (ACBAD). Au 5 subsecvențe comune de lungime-2: (AB), (AC), (AD), (BD) și (CD); 2 subsecvențe comune de lungime-3: (ABD) și (ACD); și nu mai sunt subsecvențe comune. Deci (ABD) și (ACD) sunt cele mai lungi subsecvențe comune ale acestora.

Complexitate

Pentru cazul general al unui număr arbitrar de secvențe de intrare, problema este NP-hard . Când numărul de secvențe este constant, problema este rezolvabilă în timp polinomial prin programare dinamică .

Având în vedere secvențe de lungimi , o căutare naivă ar testa fiecare dintre subsecvențele primei secvențe pentru a determina dacă acestea sunt și subsecvențe ale secvențelor rămase; fiecare subsecvență poate fi testată în timp liniar în lungimile secvențelor rămase, deci timpul pentru acest algoritm ar fi ${\ displaystyle N}$ ${\ displaystyle n_ {1}, ..., n_ {N}}$ ${\ displaystyle 2 ^ {n_ {1}}}$

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

Pentru cazul a două secvențe de elemente n și m , timpul de rulare al abordării de programare dinamică este O ( n × m ). Pentru un număr arbitrar de secvențe de intrare, abordarea de programare dinamică oferă o soluție în

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

Există metode cu o complexitate mai mică, care depind adesea de lungimea LCS, de mărimea alfabetului sau de ambele.

LCS nu este neapărat unic; în cel mai rău caz, numărul de subsecvențe comune este exponențial în lungimile intrărilor, deci complexitatea algoritmică trebuie să fie cel puțin exponențială.

Soluție pentru două secvențe

Problema LCS are o substructură optimă : problema poate fi descompusă în subprobleme mai mici și mai simple, care pot fi, la rândul lor, descompuse în subprobleme mai simple și așa mai departe, până când, în cele din urmă, soluția devine banală. LCS, în special, are subprobleme suprapuse : soluțiile pentru subprobleme la nivel înalt refolosesc adesea soluții pentru subprobleme la nivel inferior. Problemele cu aceste două proprietăți sunt supuse abordărilor de programare dinamică , în care sunt memoizate soluțiile de subproblemă , adică soluțiile subproblemelor sunt salvate pentru reutilizare.

Prefixe

Prefixul S _n al S este definit ca primele n caractere ale S . De exemplu, prefixele lui S = (AGCA) sunt

S ₀ = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA).

Să LCS ( X , Y ) să fie o funcție care calculează o cea mai lunga comuna subsecventa la X și Y . O astfel de funcție are două proprietăți interesante.

Prima proprietate

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y ) ^ A , pentru toate șirurile X , Y și toate simbolurile A , unde ^ denotă concatenarea șirurilor. Acest lucru permite simplificarea calculului LCS pentru două secvențe care se termină cu același simbol. De exemplu, LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN") ^ "A", Continuând pentru simbolurile comune rămase, LCS ("BANANA", "ATANA") = LCS (" BAN "," AT ") ^" ANA ".

A doua proprietate

Dacă A și B sunt simboluri distincte ( A ≠ B ), atunci LCS (X ^ A, Y ^ B) este una dintre șirurile de lungime maximă din mulțimea { LCS ( X ^ A , Y ), LCS ( X , Y ^ B )}, pentru toate șirurile X , Y .

De exemplu, LCS ("ABCDEFG", "BCDGK") este cel mai lung șir dintre LCS ("ABCDEFG", "BCDG") și LCS ("ABCDEF", "BCDGK"); dacă ambele aveau aceeași lungime, una dintre ele ar putea fi aleasă în mod arbitrar.

Pentru a realiza proprietatea, distingeți două cazuri:

Dacă LCS ("ABCDEFG", "BCDGK") se termină cu un "G", atunci "K" final nu poate fi în LCS, deci LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEFG", "BCDG ").
Dacă LCS ("ABCDEFG", "BCDGK") nu se termină cu un "G", atunci "G" final nu poate fi în LCS, deci LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEF", „BCDGK”).

Funcția LCS definită

Să fie definite două secvențe după cum urmează: și . Prefixele lui sunt ; prefixele lui sunt . Să reprezinte mulțimea celei mai lungi subsecvențe comune de prefixe și . Acest set de secvențe este dat de următoarele. ${\ displaystyle X = (x_ {1} x_ {2} \ cdots x_ {m})}$ ${\ displaystyle Y = (y_ {1} y_ {2} \ cdots y_ {n})}$ ${\ displaystyle X}$ ${\ displaystyle X_ {1,2, \ dots, m}}$ ${\ displaystyle Y}$ ${\ displaystyle Y_ {1,2, \ dots, n}}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j})}$ ${\ displaystyle X_ {i}}$ ${\ displaystyle Y_ {j}}$

{\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j}) = {\ begin {cases} \ emptyset & {\ mbox {if}} i = 0 {\ mbox {or}} j = 0 \\ {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1}) {\ hat {}} x_ {i} și {\ mbox {if}} i, j> 0 {\ mbox {și}} x_ {i} = y_ {j} \\\ operatorname {\ max} \ {{\ mathit {LCS}} (X_ {i}, Y_ {j-1}), {\ mathit {LCS }} (X_ {i-1}, Y_ {j}) \} și {\ mbox {if}} i, j> 0 {\ mbox {și}} x_ {i} \ neq y_ {j}. \ End {cazuri}}}

Pentru a găsi LCS de și , comparați și . Dacă sunt egale, atunci secvența este extinsă de acel element ,. Dacă acestea nu sunt egale, atunci cea mai lungă dintre cele două secvențe , și , este păstrată. (Dacă au aceeași lungime, dar nu identice, atunci ambele sunt păstrate.) ${\ displaystyle X_ {i}}$ ${\ displaystyle Y_ {j}}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle y_ {j}}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1})}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j-1})}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j})}$

Exemplu lucrat

Cea mai lungă subsecvență comună pentru R = (GAC) și C = (AGCAT) va fi găsită. Deoarece funcția LCS utilizează un element "zero", este convenabil să se definească zero prefixe care sunt goale pentru aceste secvențe: R ₀ = Ø; și C ₀ = Ø. Toate prefixele sunt plasate într - un tabel cu C , în primul rând (făcând o c olumn antet) și R în prima coloană (ceea ce face un r um antet).

Corzi LCS
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
A	Ø
C	Ø

Acest tabel este utilizat pentru a stoca secvența LCS pentru fiecare etapă a calculului. Cea de-a doua coloană și al doilea rând au fost completate cu Ø, deoarece atunci când o secvență goală este comparată cu o secvență ne-goală, cea mai lungă subsecvență comună este întotdeauna o secvență goală.

LCS ( R ₁ , C ₁ ) este determinat prin compararea primelor elemente din fiecare secvență. G și A nu sunt la fel, deci acest LCS obține (folosind „a doua proprietate”) cea mai lungă dintre cele două secvențe, LCS ( R ₁ , C ₀ ) și LCS ( R ₀ , C ₁ ). Conform tabelului, ambele sunt goale, deci LCS ( R ₁ , C ₁ ) este de asemenea gol, așa cum se arată în tabelul de mai jos. Săgețile indică faptul că secvența provine atât din celula de mai sus, LCS ( R ₀ , C ₁ ), cât și din celula din stânga, LCS ( R ₁ , C ₀ ).

LCS ( R ₁ , C ₂ ) este determinat prin compararea lui G și G. Se potrivesc, deci G este atașat la secvența din stânga sus, LCS ( R ₀ , C ₁ ), care este (Ø), dând (ØG), care este (G).

Pentru LCS ( R ₁ , C ₃ ), G și C nu se potrivesc. Secvența de mai sus este goală; cel din stânga conține un element, G. Selectând cel mai lung dintre acestea, LCS ( R ₁ , C ₃ ) este (G). Săgeata arată spre stânga, deoarece aceasta este cea mai lungă dintre cele două secvențe.

LCS ( R ₁ , C ₄ ), de asemenea, este (G).

LCS ( R ₁ , C ₅ ), de asemenea, este (G).

Rândul „G” finalizat
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
A	Ø
C	Ø

Pentru LCS ( R ₂ , C ₁ ), A este comparat cu A. Cele două elemente se potrivesc, deci A este atașat la Ø, dând (A).

Pentru LCS ( R ₂ , C ₂ ), A și G nu se potrivesc, deci cel mai lung dintre LCS ( R ₁ , C ₂ ), care este (G) și LCS ( R ₂ , C ₁ ), care este (A ), este folosit. În acest caz, fiecare conține câte un element, deci acestui LCS i se dau două subsecvențe: (A) și (G).

Pentru LCS ( R ₂ , C ₃ ), A nu se potrivește C. LCS ( R ₂ , C ₂ ) conține secvențe (A) și (G); LCS ( R ₁ , C ₃ ) este (G), care este deja conținut în LCS ( R ₂ , C ₂ ). Rezultatul este că LCS ( R ₂ , C ₃ ) conține și cele două subsecvențe, (A) și (G).

Pentru LCS ( R ₂ , C ₄ ), A se potrivește cu A, care este atașat la celula din stânga sus, dând (GA).

Pentru LCS ( R ₂ , C ₅ ), A nu se potrivește cu T. Comparând cele două secvențe, (GA) și (G), cea mai lungă este (GA), deci LCS ( R ₂ , C ₅ ) este (GA).

Rândurile „G” și „A” s-au finalizat
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
A	Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (A)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) și (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) și (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	Ø

Pentru LCS ( R ₃ , C ₁ ), C și A nu se potrivesc, deci LCS ( R ₃ , C ₁ ) obține cea mai lungă dintre cele două secvențe, (A).

Pentru LCS ( R ₃ , C ₂ ), C și G nu se potrivesc. Atât LCS ( R ₃ , C ₁ ), cât și LCS ( R ₂ , C ₂ ) au un singur element. Rezultatul este că LCS ( R ₃ , C ₂ ) conține cele două subsecvențe, (A) și (G).

Pentru LCS ( R ₃ , C ₃ ), C și C se potrivesc, deci C este anexat la LCS ( R ₂ , C ₂ ), care conține cele două subsecvențe, (A) și (G), dând (AC) și (GC ).

Pentru LCS ( R ₃ , C ₄ ), C și A nu se potrivesc. Combinarea LCS ( R ₃ , C ₃ ), care conține (AC) și (GC), și LCS ( R ₂ , C ₄ ), care conține (GA), dă un total de trei secvențe: (AC), (GC) și (GA).

În cele din urmă, pentru LCS ( R ₃ , C ₅ ), C și T nu se potrivesc. Rezultatul este că LCS ( R ₃ , C ₅ ) conține, de asemenea, cele trei secvențe, (AC), (GC) și (GA).

Tabel LCS completat
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
A	Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (A)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) și (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) și (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	Ø	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ (A)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) și (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (AC) și (GC)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) & (GC) & (GA)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) & (GC) & (GA)

Rezultatul final este că ultima celulă conține toate cele mai lungi subsecvențe comune (AGCAT) și (GAC); acestea sunt (AC), (GC) și (GA). Tabelul arată, de asemenea, cele mai lungi subsecvențe comune pentru fiecare pereche posibilă de prefixe. De exemplu, pentru (AGC) și (GA), cele mai lungi subsecvențe comune sunt (A) și (G).

Abordarea Traceback

Calculul LCS al unui rând al tabelului LCS necesită doar soluțiile pentru rândul curent și rândul anterior. Totuși, pentru secvențe lungi, aceste secvențe pot deveni numeroase și lungi, necesitând mult spațiu de stocare. Spațiul de stocare poate fi salvat prin salvarea nu a subsecvențelor reale, ci a lungimii subsecvenței și a direcției săgeților, ca în tabelul de mai jos.

Stocarea lungimii, mai degrabă decât a secvențelor
	A	G	C	A	T
Ø	0	0	0	0	0
G	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 0	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1
A	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 2
C	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2

Subsecvențele reale sunt deduse printr-o procedură de "traceback" care urmează săgețile înapoi, începând de la ultima celulă din tabel. Când lungimea scade, secvențele trebuie să fi avut un element comun. Sunt posibile mai multe căi atunci când sunt afișate două săgeți într-o celulă. Mai jos este tabelul pentru o astfel de analiză, cu numere colorate în celule unde lungimea este pe cale să scadă. Numerele aldine trasează secvența, (GA).

Exemplu de traceback
	A	G	C	A	T
Ø	0	0	0	0	0
G	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 0	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1
A	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 2
C	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2

Relația cu alte probleme

Pentru două șiruri și , lungimea celei mai scurte suprasecvențe comune este legată de lungimea LCS de ${\ displaystyle X_ {1 \ dots m}}$ ${\ displaystyle Y_ {1 \ dots n}}$

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

Distanța de editare atunci când este permisă doar inserarea și ștergerea (fără înlocuire) sau când costul înlocuirii este dublul costului unei inserții sau ștergeri este:

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

Cod pentru soluția de programare dinamică

Calculând lungimea LCS

Funcția de mai jos ia ca secvențe de intrare X[1..m]și Y[1..n]calculează LCS între X[1..i]și Y[1..j]pentru toți 1 ≤ i ≤ mși 1 ≤ j ≤ no stochează în C[i,j]. C[m,n]va conține lungimea LCS a Xși 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]

Alternativ, se poate utiliza memoizarea .

Exemplu în 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;
}

Citirea unui LCS

Funcția următoare backtracks opțiunile luate atunci când se calculează Cmasa. Dacă ultimele caractere din prefixe sunt egale, acestea trebuie să fie într-un LCS. Dacă nu, verificați ce a dat cel mai mare LCS de păstrare și , și faceți aceeași alegere. Alegeți una dacă au fost la fel de lungi. Apelați funcția cu și . ${\ displaystyle x_ {i}}$ ${\ displaystyle 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)

Exemplu în 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);
}

Citirea tuturor LCS-urilor

Dacă alegeți și ar da un rezultat la fel de lung, citiți ambele subsecvențe rezultate. Aceasta este returnată ca set de această funcție. Observați că această funcție nu este polinomială, deoarece s-ar putea ramifica în aproape fiecare pas dacă șirurile sunt similare. ${\ displaystyle x_ {i}}$ ${\ displaystyle 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

Imprimați dif

Această funcție va urmări înapoi prin matricea C și va imprima diferența dintre cele două secvențe. Observați că veți obține un răspuns diferit dacă faceți schimb ≥și <, cu >și ≤mai jos.

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 ""

Exemplu

Să fie „ ” și să fie „ ”. Cea mai lungă subsecvență comună între și este „ ”. Tabelul de mai jos, generat de funcție , arată lungimile celor mai lungi subsecvențe comune dintre prefixele lui și . Rândul lea și lea arată coloana lungimea LCS între și . ${\ displaystyle X}$ XMJYAUZ ${\ displaystyle Y}$ MZJAWXU ${\ displaystyle X}$ ${\ displaystyle Y}$ MJAUCLCSLength ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle X_ {1..i}}$ ${\ displaystyle Y_ {1..j}}$

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	A	W	X	U
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	Da	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

Cele evidențiate Numerele arată calea funcției backtrackar reieși din dreapta jos în colțul din stânga sus, atunci când citirea unui LCS. Dacă simbolurile curente din și sunt egale, fac parte din LCS și mergem atât în sus, cât și în stânga (afișat cu caractere aldine ). Dacă nu, mergem în sus sau la stânga, în funcție de ce celulă are un număr mai mare. Aceasta corespunde fie luării LCS între și , fie și . ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X_ {1..i-1}}$ ${\ displaystyle Y_ {1..j}}$ ${\ displaystyle X_ {1..i}}$ ${\ displaystyle Y_ {1..j-1}}$

Optimizarea codului

Mai multe optimizări pot fi făcute algoritmului de mai sus pentru a-l accelera pentru cazurile din lumea reală.

Reduceți setul de probleme

Matricea C din algoritmul naiv crește cvadrat cu lungimile secvențelor. Pentru două secvențe de 100 de elemente, ar fi necesară o matrice de 10.000 de elemente și ar trebui făcute 10.000 de comparații. În majoritatea cazurilor din lumea reală, în special diferențele și patch-urile din codul sursă, începutul și sfârșitul fișierelor se schimbă rar și aproape sigur nu ambele în același timp. Dacă doar câteva elemente s-au schimbat la mijlocul secvenței, începutul și sfârșitul pot fi eliminate. Acest lucru reduce nu numai cerințele de memorie pentru matrice, ci și numărul de comparații care trebuie făcute.

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 ...

În cel mai bun caz, o secvență fără modificări, această optimizare ar elimina complet necesitatea matricei C. În cel mai rău caz, o modificare a primului și ultimului element din secvență, se efectuează doar două comparații suplimentare.

Reduceți timpul de comparație

Majoritatea timpului luat de algoritmul naiv este petrecut efectuând comparații între elementele din secvențe. Pentru secvențe textuale, cum ar fi codul sursă, doriți să vizualizați liniile ca elemente de secvență în loc de caractere unice. Aceasta poate însemna comparații de șiruri relativ lungi pentru fiecare pas din algoritm. Se pot face două optimizări care pot ajuta la reducerea timpului consumat de aceste comparații.

Reduceți șirurile la hashuri

O funcție hash sau suma de control poate fi utilizată pentru a reduce dimensiunea șirurilor din secvențe. Adică, pentru codul sursă în care linia medie are o lungime de 60 sau mai multe caractere, hash-ul sau suma de control pentru acea linie ar putea avea doar 8 până la 40 de caractere. În plus, natura randomizată a hash-urilor și sumelor de verificare ar garanta că comparațiile vor face scurtcircuit mai rapid, deoarece liniile codului sursă vor fi rareori modificate la început.

Există trei dezavantaje principale ale acestei optimizări. În primul rând, trebuie petrecut un timp în prealabil pentru a precomputa hashurile pentru cele două secvențe. În al doilea rând, trebuie alocată memorie suplimentară pentru noile secvențe hash. Cu toate acestea, în comparație cu algoritmul naiv folosit aici, ambele dezavantaje sunt relativ minime.

Al treilea dezavantaj este cel al coliziunilor . Deoarece suma de control sau hash nu este garantată ca fiind unică, există o mică șansă ca două elemente diferite să poată fi reduse la același hash. Acest lucru este puțin probabil în codul sursă, dar este posibil. Prin urmare, un hash criptografic ar fi mult mai potrivit pentru această optimizare, deoarece entropia sa va fi semnificativ mai mare decât cea a unei simple sume de control. Cu toate acestea, este posibil ca beneficiile să nu merite setările și cerințele de calcul ale unui hash criptografic pentru lungimi de secvență mici.

Reduceți spațiul necesar

Dacă este necesară doar lungimea LCS, matricea poate fi redusă cu ușurință la o matrice sau la un vector (mai inteligent), deoarece abordarea de programare dinamică are nevoie doar de coloanele curente și anterioare ale matricei. Algoritmul lui Hirschberg permite construirea propriu-zisă a secvenței optime în același timp pătratic și limite spațiale liniare. ${\ displaystyle 2 \ times \ min (n, m)}$ ${\ displaystyle \ min (m, n) +1}$

Algoritmi optimizați în continuare

Există mai mulți algoritmi care rulează mai repede decât abordarea de programare dinamică prezentată. Unul dintre ele este algoritmul Hunt – Szymanski , care rulează de obicei în timp (pentru ), unde este numărul de potriviri dintre cele două secvențe. Pentru probleme cu dimensiunea alfabetului delimitat, Metoda celor patru ruși poate fi utilizată pentru a reduce timpul de rulare al algoritmului de programare dinamică cu un factor logaritmic. ${\ displaystyle O ((n + r) \ log (n))}$ ${\ displaystyle n> m}$ ${\ displaystyle r}$

Comportament pe șiruri aleatorii

Începând cu Chvátal & Sankoff (1975) , un număr de cercetători au investigat comportamentul celei mai lungi lungimi comune de subsecvență atunci când cele două șiruri date sunt trase aleatoriu din același alfabet. Când dimensiunea alfabetului este constantă, lungimea așteptată a LCS este proporțională cu lungimea celor două șiruri, iar constantele de proporționalitate (în funcție de mărimea alfabetului) sunt cunoscute ca constantele Chvátal – Sankoff . Valorile lor exacte nu sunt cunoscute, dar limitele superioare și inferioare ale valorilor lor au fost dovedite și se știe că cresc invers proporțional cu rădăcina pătrată a dimensiunii alfabetului. Modelele matematice simplificate ale celei mai lungi probleme comune de subsecvență s-au dovedit a fi controlate de distribuția Tracy-Widom .

Languages

In other projects

Cea mai lungă problemă comună de subsecvență - Longest common subsequence problem

Cuprins

Complexitate

Soluție pentru două secvențe

Prefixe

Prima proprietate

A doua proprietate

Funcția LCS definită

Exemplu lucrat

Abordarea Traceback

Relația cu alte probleme

Cod pentru soluția de programare dinamică

Calculând lungimea LCS

Exemplu în C #

Citirea unui LCS

Exemplu în C #

Citirea tuturor LCS-urilor

Imprimați dif

Exemplu

Optimizarea codului

Reduceți setul de probleme

Reduceți timpul de comparație

Reduceți șirurile la hashuri

Reduceți spațiul necesar

Algoritmi optimizați în continuare

Comportament pe șiruri aleatorii

Vezi si

Referințe

linkuri externe

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	A	W	X	U
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	Da	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	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	A	W	X	U
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	Da	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	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	A	W	X	U
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	Da	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4