Nejdelší běžný problém s posloupností - Longest common subsequence problem

Porovnání dvou revizí ukázkového souboru na základě jejich nejdelší společné posloupnosti (černá)

The nejdelší společná posloupnost (LCS) problém je problém najít nejdelší subsekvence společné pro všechny sekvence v sadě sekvencí (často jen dvě sekvence). Liší se od nejdelší běžný problém s podřetězcem: na rozdíl od podřetězců nejsou subsekvence nutné k obsazení po sobě jdoucích pozic v původních sekvencích. Nejdelší běžný problém s posloupností je klasický počítačová věda problém, základ porovnání dat programy jako rozdíl nástroj a má aplikace v výpočetní lingvistika a bioinformatika. To je také široce používán systémy kontroly revizí jako Git pro usmíření několik změn provedených v kolekci souborů řízených revizemi.

Zvažte například sekvence (ABCD) a (ACBAD). Mají 5 společných subsekvencí délky 2: (AB), (AC), (AD), (BD) a (CD); 2 společné délky a 3 společné subsekvence: (ABD) a (ACD); a již běžné posloupnosti. Takže (ABD) a (ACD) jsou jejich nejdelší společné subsekvence.

Složitost

Problém je v obecném případě libovolného počtu vstupních sekvencí NP-tvrdé.^[1] Když je počet sekvencí konstantní, problém je řešitelný v polynomiálním čase pomocí dynamické programování.

Dáno ${ displaystyle N}$ sekvence délek ${ displaystyle n_ {1}, ..., n_ {N}}$, naivní hledání by otestovalo každou z ${ displaystyle 2 ^ {n_ {1}}}$ subsekvence první sekvence k určení, zda jsou také subsekvencemi zbývajících sekvencí; každá subsekvence může být testována v čase lineárně v délkách zbývajících sekvencí, takže čas pro tento algoritmus bude

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

Pro případ dvou sekvencí n a m prvků, doba běhu přístupu dynamického programování je Ó (n × m).^[2] Pro libovolný počet vstupních sekvencí poskytuje řešení dynamický programovací přístup

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

Existují metody s nižší složitostí,^[3]které často závisí na délce LCS, velikosti abecedy nebo na obou.

LCS není nutně jedinečný; v nejhorším případě je počet běžných subsekvencí v délkách vstupů exponenciální, takže algoritmická složitost musí být alespoň exponenciální.^[4]

Řešení pro dvě sekvence

Problém LCS má optimální spodní konstrukce: problém lze rozdělit na menší, jednodušší dílčí problémy, které lze následně rozdělit na jednodušší dílčí problémy atd., dokud nakonec nebude řešení triviální. Zejména LCS má překrývající se dílčí problémy: řešení dílčích problémů na vysoké úrovni často znovu používají řešení dílčích problémů na nižší úrovni. Problémy s těmito dvěma vlastnostmi lze vyřešit dynamické programování přístupy, ve kterých jsou dílčí řešení memoized, to znamená, že řešení dílčích problémů jsou uložena pro opětovné použití.

Předpony

Předpona S_n z S je definován jako první n znaky S.^[5] Například předpony S = (AGCA) jsou

S₀ = ()

S₁ = (A)

S₂ = (AG)

S₃ = (AGC)

S₄ = (AGCA).

Definujte funkci LCS(X, Y) jako nejdelší společné posloupnosti X a Y. Tato funkce má dvě zajímavé vlastnosti.

První vlastnost

Předpokládejme, že obě sekvence končí ve stejném prvku. Pak je jejich LCS LCS sekvence s vyloučeným posledním prvkem, s připojeným společným posledním prvkem.

Například LCS ((BANANA), (ATANA)) = LCS ((BANAN), (ATAN)) ^ (A), kde ^ označuje zřetězení řetězců. Pokračování pro zbývající společné prvky, LCS ((BANANA), (ATANA)) = LCS ((BAN), (AT)) ^ (ANA).

Obecně platí, že pro jakékoli sekvence X a Y délky n a m, pokud označíme jejich prvky X₁ na X_n a y₁ na y_m a jejich předpony X₁ na X_n-1 a Y₁ na Y_m-1, pak:

Li: X_n=y_m

pak: LCS(X_n, Y_m) = LCS( X_n-1, Y_m-1) ^ X_n. Všimněte si, že LCS pro X_n a Y_m zahrnuje stanovení LCS kratších sekvencí, X_n-1 a Y_m-1.

Druhá vlastnost

Předpokládejme, že dvě sekvence X a Y nekončí stejným symbolem. LCS X a Y je tedy delší LCS (X_n, Y_m-1) a LCS (X_n-1, Y_m).

Chcete-li porozumět této vlastnosti, zvažte dvě následující sekvence:

posloupnost X: (ABCDEFG) (n prvků)
posloupnost Y: (BCDGK) (m prvků)

LCS těchto dvou sekvencí končí buď G (poslední prvek sekvence X), nebo nekončí.

Případ 1: LCS končí písmenem G
Pak to nemůže skončit K. Takže to neuškodí odstranit K ze sekvence Y: pokud by K byly v LCS, byl by to jeho poslední znak; v důsledku toho K není v LCS. Takže LCS (X_n, Y_m) = LCS (X_n, Y_m-1).

Případ 2: LCS nekončí písmenem G
Poté můžeme odstranit G ze sekvence X (ze stejného důvodu jako výše). Takže LCS (X_n, Y_m) = LCS (X_n-1, Y_m).

LCS, který hledáme, je v každém případě jedním z LCS (X_n, Y_m-1) nebo LCS (X_n-1, Y_m). Tyto dvě poslední LCS jsou obě společné subsekvence X a Y. LCS (X, Y) je nejdelší. Jeho hodnota je tedy nejdelší sekvencí LCS (X_n, Y_m-1) a LCS (X_n-1, Y_m).

LCS funkce definována

Nechť jsou dvě sekvence definovány takto: ${ displaystyle X = (x_ {1} x_ {2} cdots x_ {m})}$ a ${ displaystyle Y = (y_ {1} y_ {2} cdots y_ {n})}$. Předpony ${ displaystyle X}$ jsou ${ displaystyle X_ {1,2, tečky, m}}$; předpony ${ displaystyle Y}$ jsou ${ displaystyle Y_ {1,2, tečky, n}}$. Nechat ${ displaystyle { mathit {LCS}} (X_ {i}, Y_ {j})}$ představují množinu nejdelší společné posloupnosti předpon ${ displaystyle X_ {i}}$ a ${ displaystyle Y_ {j}}$. Tato sada sekvencí je dána následujícím textem.

${ 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} & { mbox {if}} i, j> 0 { mbox {and}} 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 {a}} x_ {i} neq y_ {j}. End {případy}}}$

Chcete-li najít LCS ${ displaystyle X_ {i}}$ a ${ displaystyle Y_ {j}}$, porovnat ${ displaystyle x_ {i}}$ a ${ displaystyle y_ {j}}$. Pokud jsou stejné, pak sekvence ${ displaystyle { mathit {LCS}} (X_ {i-1}, Y_ {j-1})}$ je rozšířen o tento prvek, ${ displaystyle x_ {i}}$. Pokud nejsou stejné, pak delší ze dvou sekvencí, ${ displaystyle { mathit {LCS}} (X_ {i}, Y_ {j-1})}$, a ${ displaystyle { mathit {LCS}} (X_ {i-1}, Y_ {j})}$, je zachován. (Pokud mají stejnou délku, ale nejsou totožné, zůstanou obě zachovány.)

Pracoval příklad

Nejdelší společná posloupnost R = (GAC) a C = (AGCAT) bude nalezen. Protože LCS funkce používá prvek „nula“, je vhodné definovat nulové předpony, které jsou pro tyto sekvence prázdné: R₀ = Ø; a C₀ = Ø. Všechny předpony jsou umístěny v tabulce s C v první řadě (což je Czáhlaví sloupce) a R v prvním sloupci (což je a row header).

Tato tabulka slouží k uložení sekvence LCS pro každý krok výpočtu. Druhý sloupec a druhý řádek byly vyplněny s Ø, protože při porovnání prázdné sekvence s neprázdnou sekvencí je nejdelší společnou posloupností vždy prázdná sekvence.

LCS(R₁, C₁) je určen porovnáním prvních prvků v každé sekvenci. G a A nejsou stejné, takže tento LCS získá (pomocí „druhé vlastnosti“) nejdelší ze dvou sekvencí, LCS(R₁, C₀) a LCS(R₀, C₁). Podle tabulky jsou oba prázdné, takže LCS(R₁, C₁) je také prázdný, jak ukazuje následující tabulka. Šipky označují, že sekvence pochází z obou buněk výše, LCS(R₀, C₁) a buňka vlevo, LCS(R₁, C₀).

LCS(R₁, C₂) je určeno porovnáním G a G. Shodují se, takže G je připojeno k levé horní posloupnosti, LCS(R₀, C₁), což je (Ø), což dává (ØG), což je (G).

Pro LCS(R₁, C₃), G a C se neshodují. Sekvence výše je prázdná; ten nalevo obsahuje jeden prvek, G. Vyberte nejdelší z nich, LCS(R₁, C₃) je (G). Šipka ukazuje doleva, protože to je nejdelší ze dvou sekvencí.

LCS(R₁, C₄), podobně, je (G).

LCS(R₁, C₅), je také (G).

Řádek „G“ byl dokončen

	Ó	A	G	C	A	T
Ó	Ó	Ó	Ó	Ó	Ó	Ó
G	Ó	${ displaystyle { přesahující { uparrow} { leftarrow}}}$Ó	${ displaystyle { přesahující { nwarrow} {}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)
A	Ó
C	Ó

Pro LCS(R₂, C₁), A se porovnává s A. Dva prvky se shodují, takže A je připojeno k Ø, což dává (A).

Pro LCS(R₂, C₂), A a G se neshodují, takže nejdelší z LCS(R₁, C₂), což je (G) a LCS(R₂, C₁), což je (A), se používá. V tomto případě každý obsahuje jeden prvek, takže tomuto LCS jsou dány dvě subsekvence: (A) a (G).

Pro LCS(R₂, C₃), A neodpovídá C. LCS(R₂, C₂) obsahuje sekvence (A) a (G); LCS (R₁, C₃) je (G), který je již obsažen v LCS(R₂, C₂). Výsledkem je to LCS(R₂, C₃) obsahuje také dvě subsekvence, (A) a (G).

Pro LCS(R₂, C₄), A odpovídá A, který je připojen k levé horní buňce, což dává (GA).

Pro LCS(R₂, C₅), A neodpovídá T. Ve srovnání se dvěma sekvencemi (GA) a (G) je nejdelší (GA), takže LCS(R₂, C₅) je (GA).

Řady „G“ a „A“ byly dokončeny

	Ó	A	G	C	A	T
Ó	Ó	Ó	Ó	Ó	Ó	Ó
G	Ó	${ displaystyle { přesahující { uparrow} { leftarrow}}}$Ó	${ displaystyle { přesahující { nwarrow} {}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)
A	Ó	${ displaystyle { přesahující { nwarrow} {}}}$(A)	${ displaystyle { přesahující { uparrow} { leftarrow}}}$(A) a (G)	${ displaystyle { přesahující { uparrow} { leftarrow}}}$(A) a (G)	${ displaystyle { přesahující { nwarrow} {}}}$(GA)	${ displaystyle { přesahující {} { leftarrow}}}$(GA)
C	Ó

Pro LCS(R₃, C₁), C a A se neshodují, takže LCS(R₃, C₁) získá nejdelší ze dvou sekvencí (A).

Pro LCS(R₃, C₂), C a G se neshodují. Oba LCS(R₃, C₁) a LCS(R₂, C₂) mají jeden prvek. Výsledkem je to LCS(R₃, C₂) obsahuje dvě subsekvence, (A) a (G).

Pro LCS(R₃, C₃), C a C se shodují, takže C je připojeno LCS(R₂, C₂), který obsahuje dvě subsekvence (A) a (G), přičemž dává (AC) a (GC).

Pro LCS(R₃, C₄), C a A se neshodují. Kombinování LCS(R₃, C₃), který obsahuje (AC) a (GC) a LCS(R₂, C₄), který obsahuje (GA), poskytuje celkem tři sekvence: (AC), (GC) a (GA).

Konečně pro LCS(R₃, C₅), C a T se neshodují. Výsledkem je to LCS(R₃, C₅) obsahuje také tři sekvence (AC), (GC) a (GA).

Vyplněná tabulka LCS

	Ó	A	G	C	A	T
Ó	Ó	Ó	Ó	Ó	Ó	Ó
G	Ó	${ displaystyle { přesahující { uparrow} { leftarrow}}}$Ó	${ displaystyle { přesahující { nwarrow} {}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)	${ displaystyle { přesahující {} { leftarrow}}}$(G)
A	Ó	${ displaystyle { přesahující { nwarrow} {}}}$(A)	${ displaystyle { přesahující { uparrow} { leftarrow}}}$(A) a (G)	${ displaystyle { přesahující { uparrow} { leftarrow}}}$(A) a (G)	${ displaystyle { přesahující { nwarrow} {}}}$(GA)	${ displaystyle { přesahující {} { leftarrow}}}$(GA)
C	Ó	${ displaystyle { přesahující { uparrow} {}}}$(A)	${ displaystyle { přesahující { uparrow} { leftarrow}}}$(A) a (G)	${ displaystyle { přesahující { nwarrow} {}}}$(AC) a (GC)	${ displaystyle { přesahující { uparrow} { leftarrow}}}$(AC) & (GC) & (GA)	${ displaystyle { přesahující { uparrow} { leftarrow}}}$(AC) & (GC) & (GA)

Konečným výsledkem je, že poslední buňka obsahuje všechny nejdelší subsekvence společné pro (AGCAT) a (GAC); to jsou (AC), (GC) a (GA). Tabulka také zobrazuje nejdelší běžné subsekvence pro každou možnou dvojici předpon. Například pro (AGC) a (GA) jsou nejdelší běžnou subsekvenci (A) a (G).

Traceback přístup

Výpočet LCS řádku tabulky LCS vyžaduje pouze řešení aktuálního řádku a předchozího řádku. Přesto u dlouhých sekvencí mohou být tyto sekvence četné a dlouhé, což vyžaduje hodně úložného prostoru. Úložný prostor lze uložit tak, že neukládáte skutečné podsekvence, ale délku podsekvence a směr šipek, jak je uvedeno v tabulce níže.

Ukládání délky, spíše než sekvencí

	Ó	A	G	C	A	T
Ó	0	0	0	0	0	0
G	0	${ displaystyle { přesahující { uparrow} { leftarrow}}}$0	${ displaystyle { přesahující { nwarrow} {}}}$1	${ displaystyle { přesahující {} { leftarrow}}}$1	${ displaystyle { přesahující {} { leftarrow}}}$1	${ displaystyle { přesahující {} { leftarrow}}}$1
A	0	${ displaystyle { přesahující { nwarrow} {}}}$1	${ displaystyle { přesahující { uparrow} { leftarrow}}}$1	${ displaystyle { přesahující { uparrow} { leftarrow}}}$1	${ displaystyle { přesahující { nwarrow} {}}}$2	${ displaystyle { přesahující {} { leftarrow}}}$2
C	0	${ displaystyle { přesahující { uparrow} {}}}$1	${ displaystyle { přesahující { uparrow} { leftarrow}}}$1	${ displaystyle { přesahující { nwarrow} {}}}$2	${ displaystyle { přesahující { uparrow} { leftarrow}}}$2	${ displaystyle { přesahující { uparrow} { leftarrow}}}$2

Skutečné subsekvence jsou odvozeny v proceduře "zpětného sledování", která následuje šipky zpět, počínaje od poslední buňky v tabulce. Když se délka zmenšuje, musely mít sekvence společný prvek. Pokud jsou v buňce zobrazeny dvě šipky, je možné několik cest. Níže je tabulka pro takovou analýzu s čísly zabarvenými do buněk, kde se délka zmenší. Tučná čísla sledují sekvenci (GA).^[6]

Příklad Traceback

	Ó	A	G	C	A	T
Ó	0	0	0	0	0	0
G	0	${ displaystyle { přesahující { uparrow} { leftarrow}}}$0	${ displaystyle { přesahující { nwarrow} {}}}$1	${ displaystyle { přesahující {} { leftarrow}}}$1	${ displaystyle { přesahující {} { leftarrow}}}$1	${ displaystyle { přesahující {} { leftarrow}}}$1
A	0	${ displaystyle { přesahující { nwarrow} {}}}$1	${ displaystyle { přesahující { uparrow} { leftarrow}}}$1	${ displaystyle { přesahující { uparrow} { leftarrow}}}$1	${ displaystyle { přesahující { nwarrow} {}}}$2	${ displaystyle { přesahující {} { leftarrow}}}$2
C	0	${ displaystyle { přesahující { uparrow} {}}}$1	${ displaystyle { přesahující { uparrow} { leftarrow}}}$1	${ displaystyle { přesahující { nwarrow} {}}}$2	${ displaystyle { přesahující { uparrow} { leftarrow}}}$2	${ displaystyle { přesahující { uparrow} { leftarrow}}}$2

Vztah k dalším problémům

Pro dva struny ${ displaystyle X_ {1 tečky m}}$ a ${ displaystyle Y_ {1 tečky n}}$, délka nejkratší společná supersequence souvisí s délkou LCS o^[3]

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

The upravit vzdálenost když je povoleno pouze vložení a smazání (žádné nahrazení), nebo když je cena nahrazení dvojnásobkem ceny za vložení nebo smazání, je:

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

Kód pro řešení dynamického programování

Výpočet délky LCS

Níže uvedená funkce slouží jako vstupní sekvence X [1..m] a Y [1..n], počítá LCS mezi X [1..i] a Y [1..j] pro všechny 1 ≤ i ≤ m a 1 ≤ j ≤ na ukládá jej do C [i, j]. C [m, n] bude obsahovat délku LCS z X a Y.

funkce LCSLength (X [1..m], Y [1..n]) C = pole (0..m, 0..n) pro i: = 0..m C [i, 0] = 0 pro j: = 0..n C [0, j] = 0 pro i: = 1..m pro j: = 1..n -li X [i] = Y [j] // i-1 a j-1 při čtení X & Y z nuly C [i, j]: = C [i-1, j-1] + 1 jiný                C [i, j]: = max (C [i, j-1], C [i-1, j]) vrátit se C [m, n]

Alternativně, memorování lze použít.

Příklad v C #

statický int[,] LcsLength(tětiva A, tětiva b){    int[,] C = Nový int[A.Délka + 1, b.Délka + 1]; // (a, b). Délka + 1    pro (int i = 0; i < A.Délka; i++)        C[i, 0] = 0;    pro (int j = 0; j < b.Délka; j++)        C[0, j] = 0;    pro (int i = 1; i <= A.Délka; i++)        pro (int j = 1; j <= b.Délka; j++)        {            -li (A[i - 1] == b[j - 1])// i-1, j-1                C[i, j] = C[i - 1, j - 1] + 1;            jiný                C[i, j] = Matematika.Max(C[i, j - 1], C[i - 1, j]);        }    vrátit se C;}

Čtení LCS

Následující funkce doprovodné stopy možnosti provedené při výpočtu C stůl. Pokud jsou poslední znaky v předponách stejné, musí být v LCS. Pokud ne, zkontrolujte, co dalo největšímu LCS vedení ${ displaystyle x_ {i}}$ a ${ displaystyle y_ {j}}$, a učinit stejnou volbu. Stačí si vybrat jednu, pokud jsou stejně dlouhé. Zavolejte funkci pomocí i = m a j = n.

funkce backtrack (C [0..m, 0..n], X [1..m], Y [1..n], i, j) -li i = 0 nebo j = 0 vrátit se ""    -li  X [i] = Y [j] vrátit se ústupek (C, X, Y, i-1, j-1) + X [i] -li C [i, j-1]> C [i-1, j] vrátit se ústupek (C, X, Y, i, j-1) vrátit se ústupek (C, X, Y, i-1, j)

Příklad v C #

tětiva Backtrack(int[,] C, char[] aStr, char[] bStr, int X, int y){    -li (X == 0 | y == 0)        vrátit se "";    -li (aStr[X - 1] == bStr[y - 1]) // x-1, y-1        vrátit se ústupek(C, aStr, bStr, X - 1, y - 1) + aStr[X - 1]; // x-1    -li (C[X, y - 1] > C[X - 1, y])        vrátit se ústupek(C, aStr, bStr, X, y - 1);    vrátit se ústupek(C, aStr, bStr, X - 1, y);}

Čtení všech LCS

Pokud si vyberete ${ displaystyle x_ {i}}$ a ${ displaystyle y_ {j}}$ dá stejně dlouhý výsledek, přečte obě výsledné podsekvence. To je vráceno jako sada touto funkcí. Všimněte si, že tato funkce není polynomická, protože pokud jsou řetězce podobné, může se větvit téměř v každém kroku.

funkce backtrackAll (C [0..m, 0..n], X [1..m], Y [1..n], i, j) -li i = 0 nebo j = 0 vrátit se {""}    -li X [i] = Y [j] vrátit se {Z + X [i] pro všechny Z v backtrackAll (C, X, Y, i-1, j-1)} R: = {}    -li C [i, j-1] ≥ C [i-1, j] R: = backtrackAll (C, X, Y, i, j-1) -li C [i-1, j] ≥ C [i, j-1] R: = R ∪ backtrackAll (C, X, Y, i-1, j) vrátit se R

Vytiskněte rozdíl

Tato funkce provede zpětný posun v matici C a vytiskne rozdíl mezi těmito dvěma sekvencemi. Všimněte si, že při výměně dostanete jinou odpověď ≥ a <, s > a ≤ níže.

funkce printDiff (C [0..m, 0..n], X [1..m], Y [1..n], i, j) -li i> = 0 a j> = 0 a X [i] = Y [j] printDiff (C, X, Y, i-1, j-1) tisk „“ + X [i] jinak pokud j> 0 a (i = 0 nebo C [i, j-1] ≥ C [i-1, j]) printDiff (C, X, Y, i, j-1) tisk "+" + Y [j] jinak pokud i> 0 a (j = 0 nebo C [i, j-1] jiný        tisk ""

Příklad

Nechat ${ displaystyle X}$ být „XMJYAUZ" a ${ displaystyle Y}$ být „MZJAWXU“. Nejdelší společná posloupnost mezi ${ displaystyle X}$ a ${ displaystyle Y}$ je "MJAU“. Stůl C níže, který je generován funkcí Délka LCSL, ukazuje délky nejdelších běžných subsekvencí mezi předponami ${ displaystyle X}$ a ${ displaystyle Y}$. The ${ displaystyle i}$th řádek a ${ displaystyle j}$tento sloupec ukazuje délku LCS mezi ${ displaystyle X_ {1..i}}$ a ${ displaystyle Y_ {1..j}}$.

The zvýrazněno čísla ukazují cestu funkce ústupek by při čtení LCS následoval z pravého dolního rohu do levého horního rohu. Pokud jsou aktuální symboly v ${ displaystyle X}$ a ${ displaystyle Y}$ jsou si rovni, jsou součástí LCS a jdeme nahoru i doleva (zobrazeno v tučně). Pokud ne, jdeme nahoru nebo doleva, podle toho, která buňka má vyšší číslo. To odpovídá buď užívání LCS mezi ${ displaystyle X_ {1..i-1}}$ a ${ displaystyle Y_ {1..j}}$nebo ${ displaystyle X_ {1..i}}$ a ${ displaystyle Y_ {1..j-1}}$.

Optimalizace kódu

Pro výše uvedený algoritmus lze provést několik optimalizací, které ho zrychlí pro případy z reálného světa.

Snižte problém

Matice C v naivním algoritmu kvadraticky roste s délkami sekvencí. Pro dvě sekvence 100 položek by byla zapotřebí matice 10 000 položek a bylo by třeba provést 10 000 srovnání. Ve většině případů v reálném světě, zejména u rozdílů a oprav zdrojového kódu, se počátky a konce souborů zřídka mění a téměř jistě ne oba současně. Pokud se uprostřed posloupnosti změnilo jen několik položek, lze eliminovat začátek a konec. To snižuje nejen požadavky na paměť pro matici, ale také počet srovnání, která je třeba provést.

funkce LCS (X [1..m], Y [1..n]) start: = 1 m_end: = m n_end: = n na začátku ořízněte odpovídající položky    zatímco start ≤ m_end a start ≤ n_end a X [start] = Y [start] start: = start + 1 na konci ořízněte odpovídající položky    zatímco start ≤ m_end a start ≤ n_end a X [m_end] = Y [n_end] m_end: = m_end - 1 n_end: = n_end - 1 C = pole (start-1..m_end, start-1..n_end) pouze smyčka přes položky, které se změnily    pro i: = start..m_end pro j: = start..n_end algoritmus pokračuje jako předtím ...

V nejlepším případě, sekvence bez změn, by tato optimalizace zcela eliminovala potřebu matice C. V nejhorším případě, změna na první a poslední položku v pořadí, se provedou pouze dvě další srovnání.

Zkraťte dobu porovnání

Většinu času naivní algoritmus stráví srovnáváním položek v sekvencích. U textových sekvencí, jako je zdrojový kód, chcete místo jednotlivých znaků zobrazit řádky jako prvky sekvence. To může znamenat srovnání relativně dlouhých řetězců pro každý krok v algoritmu. Lze provést dvě optimalizace, které mohou pomoci zkrátit čas, který tato srovnání spotřebují.

Omezte řetězce na hodnoty hash

A hashovací funkce nebo kontrolní součet lze použít ke zmenšení velikosti řetězců v sekvencích. To znamená, že u zdrojového kódu, kde je průměrný řádek dlouhý 60 nebo více znaků, může být hash nebo kontrolní součet pro tento řádek dlouhý pouze 8 až 40 znaků. Randomizovaná povaha hashů a kontrolních součtů by navíc zaručila, že se srovnání zkrátí rychleji, protože řádky zdrojového kódu budou na začátku zřídka změněny.

Tato optimalizace má tři hlavní nevýhody. Nejprve je třeba předem věnovat určitý čas předběžnému výpočtu hodnot hash pro dvě sekvence. Zadruhé je třeba přidělit další paměť pro nové hašované sekvence. Ve srovnání s zde použitým naivním algoritmem jsou však obě tyto nevýhody relativně minimální.

Třetí nevýhodou je kolize. Protože není zaručeno, že kontrolní součet nebo hash bude jedinečný, je malá šance, že by dvě různé položky mohly být redukovány na stejný hash. To je ve zdrojovém kódu nepravděpodobné, ale je to možné. Kryptografický hash by proto byl pro tuto optimalizaci mnohem vhodnější, protože jeho entropie bude výrazně větší než entropie jednoduchého kontrolního součtu. Výhody však nemusí stát za nastavení a výpočetní požadavky kryptografického hashu pro malé délky sekvencí.

Zmenšete požadovaný prostor

Pokud je požadována pouze délka LCS, lze matici zmenšit na a ${ displaystyle 2 krát min (n, m)}$ matice s lehkostí, nebo do a ${ displaystyle min (m, n) +1}$ vektor (chytřejší), protože přístup dynamického programování potřebuje pouze aktuální a předchozí sloupce matice. Hirschbergův algoritmus umožňuje konstrukci optimální optimální sekvence ve stejných kvadratických časových a lineárních prostorových mezích.^[7]

Další optimalizované algoritmy

Existuje několik algoritmů, které běží rychleji než prezentovaný přístup dynamického programování. Jedním z nich je Algoritmus Hunt – Szymanski, který obvykle běží ${ displaystyle O ((n + r) log (n))}$ čas na ${ displaystyle n> m}$), kde ${ displaystyle r}$ je počet shod mezi dvěma sekvencemi.^[8] U problémů s omezenou velikostí abecedy se Metoda čtyř Rusů lze použít ke snížení doby chodu algoritmu dynamického programování o logaritmický faktor.^[9]

Chování na náhodných řetězcích

Počínaje Chvátal & Sankoff (1975) chyba harvtxt: žádný cíl: CITEREFChvátalSankoff1975 (Pomoc),^[10] řada vědců zkoumala chování nejdelší běžné délky subsekvence, když jsou dva dané řetězce náhodně vylosovány ze stejné abecedy. Když je velikost abecedy konstantní, očekávaná délka LCS je úměrná délce dvou řetězců a konstanty proporcionality (v závislosti na velikosti abecedy) jsou známé jako Chvátal – Sankoffovy konstanty. Jejich přesné hodnoty nejsou známy, ale horní a dolní hranice jejich hodnot byla prokázána,^[11] a je známo, že rostou nepřímo úměrně druhé odmocnině velikosti abecedy.^[12] Ukázalo se, že zjednodušené matematické modely nejdelšího společného posloupnostního problému jsou kontrolovány Distribuce Tracy – Widom.^[13]

Viz také

• Nejdelší rostoucí posloupnost
• Nejdelší střídavá posloupnost
• Levenshteinova vzdálenost

Reference

externí odkazy

• Slovník algoritmů a datových struktur: nejdelší společná posloupnost
• Kolekce implementací nejdelší společné posloupnosti v mnoha programovacích jazycích
• Najděte nejdelší společnou posloupnost v Pythonu