Längsta vanliga undersekvensproblem - Longest common subsequence problem

Jämförelse av två versioner av en exempelfil, baserat på deras längsta gemensamma undersekvens (svart)

Den längsta gemensamma delsekvens ( LCS ) problem är problemet att hitta den längsta delsekvensen gemensam för alla sekvenser i en uppsättning av sekvenser (ofta bara två sekvenser). Det skiljer sig från det längsta vanliga delsträngsproblemet : till skillnad från substrat krävs inte delsekvenser för att inta på varandra följande positioner inom de ursprungliga sekvenserna. Det längsta vanliga undersekvensproblemet är ett klassiskt datavetenskapsproblem , grunden för dataparametrar som diff -verktyget , och har tillämpningar inom beräkningsspråkig lingvistik och bioinformatik . Det används också i stor utsträckning avrevisionskontrollsystem som Git för att förena flera ändringar som gjorts i en revisionsstyrd samling filer.

Tänk till exempel på sekvenserna (ABCD) och (ACBAD). De har 5 längd-2 vanliga undersekvenser: (AB), (AC), (AD), (BD) och (CD); 2 längd-3 vanliga undersekvenser: (ABD) och (ACD); och inte längre vanliga undersekvenser. Så (ABD) och (ACD) är deras längsta vanliga undersekvenser.

Komplexitet

För det allmänna fallet med ett godtyckligt antal ingångssekvenser är problemet NP-hårt . När antalet sekvenser är konstant är problemet löst i polynomtid genom dynamisk programmering .

Med tanke på längdesekvenser skulle en naiv sökning testa var och en av undersekvenserna i den första sekvensen för att avgöra om de också är undersekvenser av de återstående sekvenserna; varje undersekvens kan testas linjärt i längden på de återstående sekvenserna, så tiden för denna algoritm skulle vara ${\ displaystyle N}$ ${\ displaystyle n_ {1}, ..., n_ {N}}$ ${\ displaystyle 2^{n_ {1}}}$

{\ displaystyle O \ vänster (2^{n_ {1}} \ sum _ {i> 1} n_ {i} \ höger).}

För två sekvenser av n- och m -element är den dynamiska programmeringsmetodens drifttid O ( n × m ). För ett godtyckligt antal ingångssekvenser ger den dynamiska programmeringsmetoden en lösning

{\ displaystyle O \ vänster (N \ prod _ {i = 1}^{N} n_ {i} \ höger).}

Det finns metoder med lägre komplexitet, som ofta beror på LCS -längden, alfabetets storlek eller båda.

LCS är inte nödvändigtvis unik; i värsta fall är antalet vanliga undersekvenser exponentiellt i ingångarnas längd, så den algoritmiska komplexiteten måste vara åtminstone exponentiell.

Lösning för två sekvenser

LCS -problemet har en optimal understruktur : problemet kan delas upp i mindre, enklare delproblem, som i sin tur kan delas upp i enklare delproblem, och så vidare, tills slutligen lösningen blir trivial. LCS har i synnerhet överlappande delproblem : lösningarna på delproblem på hög nivå återanvänder ofta lösningar till lägre nivåproblem. Problem med dessa två egenskaper är mottagliga för dynamiska programmeringsmetoder , där delproblemlösningar memoreras , det vill säga lösningarna för delproblem sparas för återanvändning.

Prefix

Prefixet S _n av S definieras som de första n tecknen i S . Till exempel är prefixen för S = (AGCA)

S ₀ = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA).

Låt LCS ( X , Y ) vara en funktion som beräknar en längsta delsekvens gemensam för X och Y . En sådan funktion har två intressanta egenskaper.

Första egendomen

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y ) ^ A , för alla strängar X , Y och alla symboler A , där ^ betecknar stränganslutning. Detta gör att man kan förenkla LCS -beräkningen för två sekvenser som slutar med samma symbol. Till exempel LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN")^"A", fortsätter för de återstående vanliga symbolerna, LCS ("BANANA", "ATANA") = LCS (" BAN "," AT ")^" ANA ".

Andra fastigheten

Om A och B är distinkta symboler ( A ≠ B ) är LCS (X^A, Y^B) en av strängarna med maximal längd i uppsättningen { LCS ( X ^ A , Y ), LCS ( X , Y ^ B )}, för alla strängar X , Y .

Till exempel är LCS ("ABCDEFG", "BCDGK") den längsta strängen bland LCS ("ABCDEFG", "BCDG") och LCS ("ABCDEF", "BCDGK"); om båda råkade vara lika långa, kunde en av dem väljas godtyckligt.

För att realisera egendomen, särskilja två fall:

Om LCS ("ABCDEFG", "BCDGK") slutar med ett "G", kan det sista "K" inte vara i LCS, därför LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEFG", "BCDG ").
Om LCS ("ABCDEFG", "BCDGK") inte slutar med ett "G", kan det sista "G" inte vara i LCS, därför LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEF", "BCDGK").

LCS -funktion definierad

Låt två sekvenser definieras enligt följande: och . Prefixen för är ; prefixen till är . Låt representera uppsättningen av längsta vanliga undersekvens av prefix och . Denna uppsättning sekvenser ges av följande. ${\ 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 {eller}} j = 0 \\ {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1}) {\ hat {}} x_ {i} & {\ mbox {if}} i, j> 0 {\ mbox {och}} x_ {i} = y_ {j} \\\ operatorname {\ max} \ {{\ mathit {LCS}} (X_ {i}, Y_ {j-1}), {\ mathit {LCS }} (X_ {i-1}, Y_ {j}) \} & {\ mbox {if}} i, j> 0 {\ mbox {och}} x_ {i} \ neq y_ {j}. \ End {case}}}

För att hitta LCS för och , jämföra och . Om de är lika, då sekvensen förlängs med det elementet, . Om de inte är lika, behålls den längsta bland de två sekvenserna,, och ,. (Om de är lika långa, men inte identiska, behålls båda.) ${\ 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})}$

Utarbetat exempel

Den längsta undersekvensen som är vanlig för R = (GAC) och C = (AGCAT) kommer att hittas. Eftersom LCS -funktionen använder ett "zeroth" -element är det bekvämt att definiera nollprefix som är tomma för dessa sekvenser: R ₀ = Ø; och C ₀ = Ø. Alla prefix placeras i en tabell med C i den första raden (vilket gör det en c olumn header) och R i den första spalten (vilket gör det en r ow header).

LCS -strängar
	O	A	G	C	A	T
O	O	O	O	O	O	O
G	O
A	O
C	O

Denna tabell används för att lagra LCS -sekvensen för varje steg i beräkningen. Den andra kolumnen och den andra raden har fyllts i med Ø, för när en tom sekvens jämförs med en icke-tom sekvens är den längsta vanliga undersekvensen alltid en tom sekvens.

LCS ( R ₁ , C ₁ ) bestäms genom att jämföra de första elementen i varje sekvens. G och A är inte desamma, så denna LCS får (med hjälp av den "andra egenskapen") den längsta av de två sekvenserna, LCS ( R ₁ , C ₀ ) och LCS ( R ₀ , C ₁ ). Enligt tabellen är båda dessa tomma, så LCS ( R ₁ , C ₁ ) är också tom, som visas i tabellen nedan. Pilarna indikerar att sekvensen kommer från både cellen ovan, LCS ( R ₀ , C ₁ ) och cellen till vänster, LCS ( R ₁ , C ₀ ).

LCS ( R ₁ , C ₂ ) bestäms genom att jämföra G och G. De matchar, så G läggs till i den övre vänstra sekvensen, LCS ( R ₀ , C ₁ ), vilket är (Ø), vilket ger (ØG), vilket är (G).

För LCS ( R ₁ , C ₃ ) matchar inte G och C. Sekvensen ovan är tom; den till vänster innehåller ett element, G. Om du väljer den längsta av dessa är LCS ( R ₁ , C ₃ ) (G). Pilen pekar till vänster, eftersom det är den längsta av de två sekvenserna.

LCS ( R ₁ , C ₄ ), likaledes, är (G).

LCS ( R ₁ , C ₅ ), likaså är (G).

"G" rad slutförd
	O	A	G	C	A	T
O	O	O	O	O	O	O
G	O	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ O	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
A	O
C	O

För LCS ( R ₂ , C ₁ ) jämförs A med A. De två elementen matchar, så A läggs till Ø, vilket ger (A).

För LCS ( R ₂ , C ₂ ) stämmer inte A och G, så den längsta av LCS ( R ₁ , C ₂ ), som är (G) och LCS ( R ₂ , C ₁ ), vilket är (A ), är använd. I detta fall innehåller de var och en ett element, så detta LCS ges två undersekvenser: (A) och (G).

För LCS ( R ₂ , C ₃ ), inte A matchar inte C. LCS ( R ₂ , C ₂ ) innehåller sekvenser (A) och (G); LCS ( R ₁ , C ₃ ) är (G), som redan finns i LCS ( R ₂ , C ₂ ). Resultatet är att LCS ( R ₂ , C ₃ ) innehåller också de två undersekvenser, (A) och (G).

För LCS ( R ₂ , C ₄ ), överensstämmer med A A, vilken är fäst till den övre vänstra cellen, vilket ger (GA).

För LCS ( R ₂ , C ₅ ), betyder A inte matchar T. Jämföra de två sekvenserna, (GA) och (G), är den längsta (GA), så LCS ( R ₂ , C ₅ ) är (GA).

"G" & "A" rader slutförda
	O	A	G	C	A	T
O	O	O	O	O	O	O
G	O	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ O	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
A	O	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (A)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	O

För LCS ( R ₃ , C ₁ ) stämmer inte C och A, så LCS ( R ₃ , C ₁ ) får den längsta av de två sekvenserna, (A).

För LCS ( R ₃ , C ₂ ) matchar inte C och G. Båda LCS ( R ₃ , C ₁ ) och LCS ( R ₂ , C ₂ ) har ett element. Resultatet är att LCS ( R ₃ , C ₂ ) innehåller de två undersekvenserna, (A) och (G).

För LCS ( R ₃ , C ₃ ) matchar C och C, så C läggs till LCS ( R ₂ , C ₂ ), som innehåller de två undersekvenserna, (A) och (G), vilket ger (AC) och (GC ).

För LCS ( R ₃ , C ₄ ) matchar inte C och A. Att kombinera LCS ( R ₃ , C ₃ ), som innehåller (AC) och (GC), och LCS ( R ₂ , C ₄ ), som innehåller (GA), ger totalt tre sekvenser: (AC), (GC) och (GA).

Slutligen, för LCS ( R ₃ , C ₅ ), matchar inte C och T. Resultatet är att LCS ( R ₃ , C ₅ ) innehåller även de tre sekvenserna, (AC), (GC), och (GA).

Fullbordad LCS -tabell
	O	A	G	C	A	T
O	O	O	O	O	O	O
G	O	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ O	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
A	O	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (A)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	O	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ (A)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (AC) och (GC)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) & (GC) & (GA)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) & (GC) & (GA)

Slutresultatet är att den sista cellen innehåller alla de längsta undersekvenserna som är gemensamma för (AGCAT) och (GAC); dessa är (AC), (GC) och (GA). Tabellen visar också de längsta gemensamma undersekvenserna för alla möjliga prefix. Till exempel för (AGC) och (GA) är den längsta vanliga undersekvensen (A) och (G).

Traceback -tillvägagångssätt

Att beräkna LCS för en rad i LCS -tabellen kräver endast lösningarna för den aktuella raden och den föregående raden. Men för långa sekvenser kan dessa sekvenser bli många och långa, vilket kräver mycket lagringsutrymme. Lagringsutrymme kan sparas genom att inte spara de faktiska undersekvenserna, utan längden på undersekvensen och pilarnas riktning, som i tabellen nedan.

Lagrar längd, snarare än sekvenser
	A	G	C	A	T
O	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

De faktiska undersekvenserna härleds i ett "spår tillbaka" -förfarande som följer pilarna bakåt, med början från den sista cellen i tabellen. När längden minskar måste sekvenserna ha haft ett gemensamt element. Flera vägar är möjliga när två pilar visas i en cell. Nedan är tabellen för en sådan analys, med siffror färgade i celler där längden är på väg att minska. De djärva siffrorna spårar sekvensen, (GA).

Spår tillbaka exempel
	A	G	C	A	T
O	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

Förhållande till andra problem

För två strängar och är längden på den kortaste vanliga supersekvensen relaterad till längden på LCS med ${\ displaystyle X_ {1 \ punkter m}}$ ${\ displaystyle Y_ {1 \ punkter n}}$

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

Den redigeringsdistansen när endast insättning och deletion är tillåtet (ingen substitution), eller när kostnaden för substitutionen är den dubbla av kostnaden för en insertion eller deletion, är:

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

Kod för den dynamiska programmeringslösningen

Beräkna längden på LCS

Funktionen nedan tar som inmatningssekvenser X[1..m]och Y[1..n]beräknar LCS mellan X[1..i]och Y[1..j]för alla 1 ≤ i ≤ moch 1 ≤ j ≤ n, och lagrar den i C[i,j]. C[m,n]kommer att innehålla längden på LCS för Xoch 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]

Alternativt kan memoization användas.

Exempel i 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;
}

Läser upp en LCS

Följande funktion spårar de val som tas vid beräkningen av Ctabellen. Om de sista tecknen i prefixen är lika måste de vara i en LCS. Om inte, kolla vad som gav den största LCS för att behålla och , och gör samma val. Välj bara en om de var lika långa. Ring funktionen med och . ${\ 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)

Exempel i 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);
}

Läser upp alla LCS

Om du väljer och skulle ge ett lika långt resultat, läs upp båda resulterande undersekvenserna. Detta returneras som en uppsättning av denna funktion. Lägg märke till att denna funktion inte är polynom, eftersom den kan förgrena sig i nästan varje steg om strängarna är lika. ${\ 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

Skriv ut diff

Denna funktion går tillbaka genom C -matrisen och skriver ut skillnaden mellan de två sekvenserna. Lägg märke till att du får ett annat svar om du byter ≥och <, med >och ≤nedan.

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

Exempel

Låt vara " " och " ". Den längsta vanliga undersekvensen mellan och är “ ”. Tabellen som visas nedan, som genereras av funktionen , visar längden på de längsta gemensamma undersekvenserna mellan prefixen för och . Den th raden och th kolumnen visar längden på LCS mellan och . ${\ 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
		O	M	Z	J	A	W	X	U
0	O	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	Y	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

De markerade siffrorna visar den väg som funktionen backtrackskulle följa från nedre högra till övre vänstra hörnet när man läser upp en LCS. Om de nuvarande symbolerna i och är lika är de en del av LCS, och vi går både upp och åt vänster (visas med fet stil ). Om inte, går vi upp eller åt vänster, beroende på vilken cell som har ett högre tal. Detta motsvarar antingen att ta LCS mellan och , eller och . ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X_ {1..i-1}}$ ${\ displaystyle Y_ {1..j}}$ ${\ displaystyle X_ {1..i}}$ ${\ displaystyle Y_ {1..j-1}}$

Kodoptimering

Flera optimeringar kan göras till algoritmen ovan för att påskynda den för verkliga fall.

Minska problemuppsättningen

C -matrisen i den naiva algoritmen växer kvadratiskt med sekvensernas längd. För två sekvenser med 100 artiklar skulle en matris på 10 000 artiklar behövas och 10 000 jämförelser skulle behöva göras. I de flesta verkliga fall, särskilt källkoddifferenser och patchar, ändras början och slutet av filer sällan, och nästan säkert inte båda samtidigt. Om bara några få objekt har ändrats i mitten av sekvensen kan början och slutet elimineras. Detta minskar inte bara minneskraven för matrisen, utan också antalet jämförelser som måste göras.

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

I bästa fall, en sekvens utan förändringar, skulle denna optimering helt eliminera behovet av C-matrisen. I värsta fall, en ändring av de allra första och sista objekten i sekvensen, görs bara ytterligare två jämförelser.

Minska jämförelsetiden

Det mesta av den tid som den naiva algoritmen tar tar åt att utföra jämförelser mellan objekt i sekvenserna. För textsekvenser som källkod vill du se rader som sekvenselement istället för enstaka tecken. Detta kan innebära jämförelser av relativt långa strängar för varje steg i algoritmen. Två optimeringar kan göras som kan bidra till att minska tiden som dessa jämförelser tar.

Minska strängarna till hash

En hash -funktion eller kontrollsumma kan användas för att minska storleken på strängarna i sekvenserna. Det vill säga, för källkod där den genomsnittliga raden är 60 eller fler tecken lång, kan hash eller kontrollsumma för den raden vara endast 8 till 40 tecken lång. Dessutom skulle haschers och kontrollsummars randomiserade karaktär garantera att jämförelser skulle kortsluta snabbare, eftersom rader med källkod sällan kommer att ändras i början.

Det finns tre primära nackdelar med denna optimering. Först måste en tid läggas ned i förväg för att beräkna hasharna för de två sekvenserna. För det andra måste ytterligare minne tilldelas för de nya hashade sekvenserna. I jämförelse med den naiva algoritmen som används här är emellertid båda dessa nackdelar relativt minimala.

Den tredje nackdelen är kollisioner . Eftersom kontrollsumman eller hash inte garanteras vara unik är det en liten chans att två olika objekt kan reduceras till samma hash. Detta är osannolikt i källkoden, men det är möjligt. En kryptografisk hash skulle därför vara mycket bättre lämpad för denna optimering, eftersom dess entropi kommer att bli betydligt större än för en enkel kontrollsumma. Fördelarna kanske dock inte är värda installationen och beräkningskraven för en kryptografisk hash för små sekvenslängder.

Minska det nödvändiga utrymmet

Om bara längden på LCS krävs kan matrisen enkelt reduceras till en matris eller till en vektor (smartare) eftersom den dynamiska programmeringsmetoden bara behöver matrisens nuvarande och tidigare kolumner. Hirschbergs algoritm gör det möjligt att konstruera själva den optimala sekvensen i samma kvadratiska tid och linjära rymdgränser. ${\ displaystyle 2 \ times \ min (n, m)}$ ${\ displaystyle \ min (m, n) +1}$

Ytterligare optimerade algoritmer

Det finns flera algoritmer som körs snabbare än den presenterade dynamiska programmeringsmetoden. En av dem är Hunt – Szymanski -algoritmen , som vanligtvis körs i tid (för ), där är antalet matchningar mellan de två sekvenserna. För problem med en begränsad alfabetstorlek kan metoden för fyra ryssar användas för att minska den dynamiska programmeringsalgoritmens drifttid med en logaritmisk faktor. ${\ displaystyle O ((n+r) \ log (n))}$ ${\ displaystyle n> m}$ ${\ displaystyle r}$

Beteende på slumpmässiga strängar

Från och med Chvátal & Sankoff (1975) har ett antal forskare undersökt beteendet hos den längsta vanliga undersekvenslängden när de två givna strängarna slumpmässigt dras från samma alfabet. När alfabetets storlek är konstant är LCS: s förväntade längd proportionell mot längden på de två strängarna, och proportionalitetskonstanterna (beroende på alfabetets storlek) är kända som Chvátal – Sankoff -konstanterna . Deras exakta värden är inte kända, men övre och nedre gränser för deras värden har bevisats, och det är känt att de växer omvänt proportionellt mot kvadratroten i alfabetets storlek. Förenklade matematiska modeller av det längsta vanliga undersekvensproblemet har visat sig styras av Tracy -Widom -distributionen .

Languages

In other projects

Längsta vanliga undersekvensproblem - Longest common subsequence problem

Innehåll

Komplexitet

Lösning för två sekvenser

Prefix

Första egendomen

Andra fastigheten

LCS -funktion definierad

Utarbetat exempel

Traceback -tillvägagångssätt

Förhållande till andra problem

Kod för den dynamiska programmeringslösningen

Beräkna längden på LCS

Exempel i C#

Läser upp en LCS

Exempel i C#

Läser upp alla LCS

Skriv ut diff

Exempel

Kodoptimering

Minska problemuppsättningen

Minska jämförelsetiden

Minska strängarna till hash

Minska det nödvändiga utrymmet

Ytterligare optimerade algoritmer

Beteende på slumpmässiga strängar

Se även

Referenser

externa länkar

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