Længste almindelige undersekvensproblem - Longest common subsequence problem

Sammenligning af to revisioner af en eksempelfil, baseret på deres længste fælles undersekvens (sort)

Det længste fælles undersekvens ( LCS ) problem er problemet med at finde den længste undersekvens, der er fælles for alle sekvenser i et sæt sekvenser (ofte kun to sekvenser). Det adskiller sig fra det længste fælles delstrengsproblem : I modsætning til substrater er undersekvenser ikke påkrævet for at indtage på hinanden følgende positioner inden for de originale sekvenser. Det længste almindelige undersekvensproblem er et klassisk datalogisk problem, grundlaget for datasammenligningsprogrammer såsom diff -værktøjet og har applikationer inden for beregningssproglig lingvistik og bioinformatik . Det er også meget udbredt afrevisionskontrolsystemer som Git til afstemning af flere ændringer foretaget i en revisionsstyret samling af filer.

Overvej f.eks. Sekvenserne (ABCD) og (ACBAD). De har 5 længde-2 fælles undersekvenser: (AB), (AC), (AD), (BD) og (CD); 2 længde-3 almindelige undersekvenser: (ABD) og (ACD); og ikke længere almindelige undersekvenser. Så (ABD) og (ACD) er deres længste fælles undersekvenser.

Kompleksitet

I det generelle tilfælde af et vilkårligt antal indgangssekvenser er problemet NP-hårdt . Når antallet af sekvenser er konstant, kan problemet løses i polynomisk tid ved dynamisk programmering .

I betragtning af længdesekvenser ville en naiv søgning teste hver af undersekvenserne i den første sekvens for at afgøre, om de også er undersekvenser af de resterende sekvenser; hver undersekvens kan testes i lineær tid i længderne af de resterende sekvenser, så tiden for denne algoritme ville være ${\ displaystyle N}$ ${\ displaystyle n_ {1}, ..., n_ {N}}$ ${\ displaystyle 2^{n_ {1}}}$

{\ displaystyle O \ venstre (2^{n_ {1}} \ sum _ {i> 1} n_ {i} \ højre).}

For to sekvenser af n og m -elementer er den dynamiske programmerings tilgangs driftstid O ( n × m ). For et vilkårligt antal indgangssekvenser giver den dynamiske programmeringsmetode en løsning i

{\ displaystyle O \ venstre (N \ prod _ {i = 1}^{N} n_ {i} \ højre).}

Der findes metoder med lavere kompleksitet, som ofte afhænger af længden af LCS, alfabetets størrelse eller begge dele.

LCS er ikke nødvendigvis unik; i værste fald er antallet af almindelige undersekvenser eksponentielt i længden af input, så den algoritmiske kompleksitet skal være mindst eksponentiel.

Løsning til to sekvenser

LCS -problemet har en optimal understruktur : problemet kan opdeles i mindre, enklere delproblemer, som igen kan opdeles i enklere delproblemer og så videre, indtil løsningen endelig bliver triviel. LCS har især overlappende delproblemer : løsningerne på delproblemer på højt niveau genbruger ofte løsninger til lavere problemer. Problemer med disse to egenskaber kan bruges til dynamiske programmeringsmetoder , hvor delproblemløsninger gemmes , det vil sige, at delproblemernes løsninger gemmes til genbrug.

Præfikser

Forstavelsen S _n af S er defineret som de første n tegn af S . For eksempel er præfikserne for S = (AGCA)

S ₀ = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (Ağca).

Lad LCS ( X , Y ) være en funktion, der beregner en længste delsekvens fælles for X og Y . En sådan funktion har to interessante egenskaber.

Første ejendom

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y ) ^ A , for alle strenge X , Y og alle symboler A , hvor ^ betegner streng sammenkædning. Dette gør det muligt at forenkle LCS -beregningen for to sekvenser, der ender på det samme symbol. F.eks. LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN")^"A", Fortsætter for de resterende fælles symboler, LCS ("BANANA", "ATANA") = LCS (" BAN "," AT ")^" ANA ".

Anden ejendom

Hvis A og B er forskellige symboler ( A ≠ B ), er LCS (X^A, Y^B) en af strengene med maksimal længde i sættet { LCS ( X ^ A , Y ), LCS ( X , Y ^ B )} for alle strengene X , Y .

F.eks. Er LCS ("ABCDEFG", "BCDGK") den længste streng blandt LCS ("ABCDEFG", "BCDG") og LCS ("ABCDEF", "BCDGK"); hvis begge tilfældigvis var lige lange, kunne en af dem vælges vilkårligt.

For at realisere ejendommen skal du skelne mellem to sager:

Hvis LCS ("ABCDEFG", "BCDGK") ender med et "G", kan det sidste "K" ikke være i LCS, derfor LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEFG", "BCDG ").
Hvis LCS ("ABCDEFG", "BCDGK") ikke slutter med et "G", kan det sidste "G" ikke være i LCS, derfor LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEF", "BCDGK").

LCS -funktion defineret

Lad to sekvenser defineres som følger: og . Præfikserne for er ; præfikserne for are . Lad repræsentere sættet med længste fælles undersekvens af præfikser og . Dette sæt sekvenser er givet ved følgende. ${\ 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 {og}} 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 {og}} x_ {i} \ neq y_ {j}. \ End {cases}}}

For at finde LCS for og sammenligne og . Hvis de er ens, så sekvensen er forlænget med dette element, . Hvis de ikke er lige, beholdes den længste blandt de to sekvenser,, og ,. (Hvis de er af samme længde, men ikke identiske, beholdes begge.) ${\ 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})}$

Virkede eksempel

Den længste delsekvens, der er fælles for R = (GAC) og C = (AGCAT), vil blive fundet. Fordi LCS -funktionen anvender et "zeroth" -element, er det praktisk at definere nul -præfikser, der er tomme for disse sekvenser: R ₀ = Ø; og C ₀ = Ø. Alle præfikser er placeret i en tabel med C i den første række (hvilket gør det en c olumn header) og R i den første søjle (gør det en r ow header).

LCS -strenge
	Ø	EN	G	C	EN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
EN	Ø
C	Ø

Denne tabel bruges til at gemme LCS -sekvensen for hvert trin i beregningen. Den anden kolonne og anden række er udfyldt med Ø, for når en tom sekvens sammenlignes med en ikke-tom sekvens, er den længste fælles undersekvens altid en tom sekvens.

LCS ( R ₁ , C ₁ ) bestemmes ved at sammenligne de første elementer i hver sekvens. G og A er ikke det samme, så denne LCS får (ved hjælp af den "anden egenskab") den længste af de to sekvenser, LCS ( R ₁ , C ₀ ) og LCS ( R ₀ , C ₁ ). Ifølge tabellen er begge disse tomme, så LCS ( R ₁ , C ₁ ) er også tom, som vist i tabellen herunder. Pilene angiver, at sekvensen kommer fra både cellen ovenfor, LCS ( R ₀ , C ₁ ) og cellen til venstre, LCS ( R ₁ , C ₀ ).

LCS ( R ₁ , C ₂ ) bestemmes ved at sammenligne G og G. De matcher, så G føjes til den øverste venstre sekvens, LCS ( R ₀ , C ₁ ), som er (Ø), hvilket giver (ØG), som er (G).

For LCS ( R ₁ , C ₃ ) stemmer G og C ikke overens. Sekvensen ovenfor er tom; den til venstre indeholder et element, G. Ved at vælge den længste af disse er LCS ( R ₁ , C ₃ ) (G). Pilen peger til venstre, da det er den længste af de to sekvenser.

LCS ( R ₁ , C ₄ ), ligeledes er (G).

LCS ( R ₁ , C ₅ ) ligeledes er (G).

"G" -række afsluttet
	Ø	EN	G	C	EN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
EN	Ø
C	Ø

For LCS ( R ₂ , C ₁ ) sammenlignes A med A. De to elementer matcher, så A tilføjes Ø, hvilket giver (A).

For LCS ( R ₂ , C ₂ ) matcher A og G ikke, så den længste af LCS ( R ₁ , C ₂ ), som er (G) og LCS ( R ₂ , C ₁ ), som er (A ), anvendes. I dette tilfælde indeholder de hver et element, så denne LCS får to undersekvenser: (A) og (G).

For LCS ( R ₂ , C ₃ ), A ikke matcher C. LCS ( R ₂ , C ₂ ) indeholder sekvenser (A) og (G); LCS ( R ₁ , C ₃ ) er (G), som allerede er indeholdt i LCS ( R ₂ , C ₂ ). Resultatet er, at LCS ( R ₂ , C ₃ ) indeholder også de to undersekvenser, (A) og (G).

For LCS ( R ₂ , C ₄ ) matcher A A, som er tilføjet til cellen øverst til venstre, hvilket giver (GA).

For LCS ( R ₂ , C ₅ ) matcher A ikke T. Ved sammenligning af de to sekvenser (GA) og (G) er den længste (GA), så LCS ( R ₂ , C ₅ ) er (GA).

"G" & "A" rækker afsluttet
	Ø	EN	G	C	EN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
EN	Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (EN)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	Ø

For LCS ( R ₃ , C ₁ ) matcher C og A ikke, så LCS ( R ₃ , C ₁ ) får den længste af de to sekvenser, (A).

For LCS ( R ₃ , C ₂ ) stemmer C og G ikke overens. Både LCS ( R ₃ , C ₁ ) og LCS ( R ₂ , C ₂ ) har et element. Resultatet er, at LCS ( R ₃ , C ₂ ) indeholder de to undersekvenser, (A) og (G).

For LCS ( R ₃ , C ₃ ) matcher C og C, så C tilføjes til LCS ( R ₂ , C ₂ ), som indeholder de to undersekvenser, (A) og (G), hvilket giver (AC) og (GC ).

For LCS ( R ₃ , C ₄ ) stemmer C og A ikke overens. Kombination af LCS ( R ₃ , C ₃ ), som indeholder (AC) og (GC), og LCS ( R ₂ , C ₄ ), som indeholder (GA), giver i alt tre sekvenser: (AC), (GC) og (GA).

Endelig matcher C og T ikke for LCS ( R ₃ , C ₅ ). Resultatet er, at LCS ( R ₃ , C ₅ ) indeholder også de tre sekvenser, (AC), (GC), og (GA).

Gennemført LCS -tabel
	Ø	EN	G	C	EN	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
EN	Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (EN)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	Ø	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ (EN)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) & (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (AC) og (GC)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) & (GC) & (GA)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) & (GC) & (GA)

Det endelige resultat er, at den sidste celle indeholder alle de længste undersekvenser, der er fælles for (AGCAT) og (GAC); disse er (AC), (GC) og (GA). Tabellen viser også de længste fælles undersekvenser for hvert muligt par præfikser. For eksempel for (AGC) og (GA) er den længste fælles undersekvens (A) og (G).

Sporvendt tilgang

Beregning af LCS for en række i LCS -tabellen kræver kun løsningerne til den aktuelle række og den foregående række. Men for lange sekvenser kan disse sekvenser blive mange og lange, hvilket kræver meget lagerplads. Lagringsplads kan gemmes ved ikke at gemme de faktiske undersekvenser, men længden af undersekvensen og pilens retning, som i tabellen nedenfor.

Lagring af længde frem for sekvenser
	EN	G	C	EN	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
EN	${\ 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 faktiske undersekvenser er udledt i en "traceback" -procedure, der følger pilene baglæns, startende fra den sidste celle i tabellen. Når længden falder, må sekvenserne have haft et fælles element. Flere stier er mulige, når to pile vises i en celle. Nedenfor er tabellen til en sådan analyse med tal farvet i celler, hvor længden er ved at falde. De fede tal sporer sekvensen, (GA).

Spor tilbage eksempel
	EN	G	C	EN	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
EN	${\ 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

Forhold til andre problemer

For to strenge og længden af den korteste almindelige supersekvens er relateret til længden af LCS med ${\ displaystyle X_ {1 \ prikker m}}$ ${\ displaystyle Y_ {1 \ prikker n}}$

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

Den edit afstand , når kun indsætning og sletning er tilladt (ingen substitution), eller når omkostningerne ved substitutionen er det dobbelte af prisen for en insertion eller deletion, er:

{\ displaystyle d '(X, Y) = n+m-2 \ cdot \ venstre | LCS (X, Y) \ højre |.}

Kode til den dynamiske programmeringsløsning

Beregning af længden af LCS

Funktionen nedenfor tager inputsekvenser X[1..m]og Y[1..n], beregner LCS mellem X[1..i]og Y[1..j]for alle 1 ≤ i ≤ mog 1 ≤ j ≤ n, og lagrer den i C[i,j]. C[m,n]vil indeholde længden af LCS for Xog 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 memoisering bruges.

Eksempel 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 en LCS op

Den følgende funktion sporer de valg, der er taget, når Ctabellen beregnes . Hvis de sidste tegn i præfikset er ens, skal de være i en LCS. Hvis ikke, skal du kontrollere, hvad der gav den største LCS -beholdning og , og foretage det samme valg. Vælg bare en, hvis de var lige lange. Kald funktionen med og . ${\ 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)

Eksempel 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 alle LCS'er op

Hvis du vælger og vil give et lige langt resultat, skal du læse begge resulterende undersekvenser op. Dette returneres som et sæt af denne funktion. Bemærk, at denne funktion ikke er polynom, da den kan forgrenes i næsten hvert trin, hvis strengene er ens. ${\ 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

Udskriv diff

Denne funktion går tilbage gennem C -matrixen og udskriver forskellen mellem de to sekvenser. Bemærk, at du får et andet svar, hvis du udveksler ≥og <med >og ≤under.

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

Eksempel

Lad være " " og være " ". Den længste fælles undersekvens mellem og er “ ”. Tabellen nedenfor, som genereres af funktionen , viser længderne af de længste fælles undersekvenser mellem præfikser for og . Den th række og th kolonne viser længden af LCS mellem og . ${\ 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	EN	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	Y	0	1	1	2	2	2	2	2
5	EN	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 fremhævede tal viser den sti, funktionen backtrackville følge fra nederste højre til øverste venstre hjørne, når en LCS læses op. Hvis de nuværende symboler er og er ens, er de en del af LCS, og vi går både op og til venstre (vist med fed skrift ). Hvis ikke, går vi op eller til venstre, afhængigt af hvilken celle der har et højere tal. Dette svarer til enten at tage LCS mellem og , eller og . ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X_ {1..i-1}}$ ${\ displaystyle Y_ {1..j}}$ ${\ displaystyle X_ {1..i}}$ ${\ displaystyle Y_ {1..j-1}}$

Kodeoptimering

Flere optimeringer kan foretages til algoritmen ovenfor for at fremskynde den i virkelige sager.

Reducer opgavesættet

C -matrixen i den naive algoritme vokser kvadratisk med sekvensernes længder. For to sekvenser på 100 emner ville en matrix på 10.000 varer være nødvendig, og der skulle foretages 10.000 sammenligninger. I de fleste sager i den virkelige verden, især kildekodeforskelle og -rettelser, ændres begyndelsen og slutningen af filer sjældent, og næsten bestemt ikke begge på samme tid. Hvis kun få punkter er ændret i midten af sekvensen, kan begyndelsen og slutningen elimineres. Dette reducerer ikke kun hukommelseskravene til matricen, men også antallet af sammenligninger, der skal foretages.

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 bedste tilfælde, en sekvens uden ændringer, ville denne optimering fuldstændigt eliminere behovet for C-matrixen. I værste fald, en ændring til de allerførste og sidste punkter i sekvensen, udføres kun to yderligere sammenligninger.

Reducer sammenligningstiden

Det meste af den tid, den naive algoritme tager, bruges på at udføre sammenligninger mellem emner i sekvenserne. For tekstsekvenser som f.eks. Kildekode, vil du se linjer som sekvenselementer i stedet for enkelttegn. Dette kan betyde sammenligninger af relativt lange strenge for hvert trin i algoritmen. Der kan foretages to optimeringer, der kan bidrage til at reducere den tid, disse sammenligninger bruger.

Reducer strenge til hash

En hash -funktion eller kontrolsum kan bruges til at reducere størrelsen på strengene i sekvenserne. Det vil sige for kildekoden, hvor den gennemsnitlige linje er 60 eller flere tegn lang, kan hash- eller kontrolsummen for denne linje kun være 8 til 40 tegn lang. Derudover ville hash og kontrolsummeres randomiserede karakter garantere, at sammenligninger ville kortslutte hurtigere, da linjer med kildekode sjældent vil blive ændret i begyndelsen.

Der er tre primære ulemper ved denne optimering. Først skal der bruges en mængde tid på forhånd til at forberede hash for de to sekvenser. For det andet skal der tildeles yderligere hukommelse til de nye hashed -sekvenser. I sammenligning med den naive algoritme, der bruges her, er begge disse ulemper imidlertid relativt minimale.

Den tredje ulempe er kollisioner . Da kontrolsummen eller hash ikke er garanteret at være unik, er der en lille chance for, at to forskellige varer kan reduceres til den samme hash. Dette er usandsynligt i kildekoden, men det er muligt. En kryptografisk hash ville derfor være langt bedre egnet til denne optimering, da dens entropi vil være betydeligt større end for en simpel kontrolsum. Fordelene er dog muligvis ikke værd at opsætte og beregne krav til en kryptografisk hash til små sekvenslængder.

Reducer den nødvendige plads

Hvis kun længden af LCS er påkrævet, kan matricen let reduceres til en matrix eller til en vektor (smartere), da den dynamiske programmeringsmetode kun har brug for matrixens nuværende og tidligere kolonner. Hirschbergs algoritme tillader konstruktion af selve den optimale sekvens i samme kvadratiske tid og lineære rumgrænser. ${\ displaystyle 2 \ times \ min (n, m)}$ ${\ displaystyle \ min (m, n) +1}$

Yderligere optimerede algoritmer

Der findes flere algoritmer, der kører hurtigere end den præsenterede dynamiske programmeringsmetode. En af dem er Hunt – Szymanski -algoritmen , der typisk kører i tid (for ), hvor er antallet af kampe mellem de to sekvenser. Ved problemer med en afgrænset alfabetstørrelse kan metoden for fire russere bruges til at reducere den dynamiske programmeringsalgoritms driftstid med en logaritmisk faktor. ${\ displaystyle O ((n+r) \ log (n))}$ ${\ displaystyle n> m}$ ${\ displaystyle r}$

Adfærd på tilfældige strenge

Fra og med Chvátal & Sankoff (1975) har en række forskere undersøgt adfærden for den længste fælles undersekvenslængde, når de to givne strenge tilfældigt trækkes fra det samme alfabet. Når alfabetstørrelsen er konstant, er den forventede længde af LCS proportional med længden af de to strenge, og proportionalitetskonstanterne (afhængig af alfabetstørrelse) er kendt som Chvátal – Sankoff -konstanterne . Deres nøjagtige værdier kendes ikke, men øvre og nedre grænser for deres værdier er blevet bevist, og det vides, at de vokser omvendt proportionelt med kvadratroden af alfabetstørrelsen. Forenklede matematiske modeller af det længste almindelige undersekvensproblem har vist sig at være styret af Tracy -Widom -distributionen .

Languages

In other projects

Længste almindelige undersekvensproblem - Longest common subsequence problem

Indhold

Kompleksitet

Løsning til to sekvenser

Præfikser

Første ejendom

Anden ejendom

LCS -funktion defineret

Virkede eksempel

Sporvendt tilgang

Forhold til andre problemer

Kode til den dynamiske programmeringsløsning

Beregning af længden af LCS

Eksempel i C#

Læser en LCS op

Eksempel i C#

Læser alle LCS'er op

Udskriv diff

Eksempel

Kodeoptimering

Reducer opgavesættet

Reducer sammenligningstiden

Reducer strenge til hash

Reducer den nødvendige plads

Yderligere optimerede algoritmer

Adfærd på tilfældige strenge

Se også

Referencer

eksterne links

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	EN	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	Y	0	1	1	2	2	2	2	2
5	EN	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	EN	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	Y	0	1	1	2	2	2	2	2
5	EN	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

Languages

In other projects

Længste almindelige undersekvensproblem - Longest common subsequence problem

Kompleksitet

Løsning til to sekvenser

Præfikser

Første ejendom

Anden ejendom

LCS -funktion defineret

Virkede eksempel

Sporvendt tilgang

Forhold til andre problemer

Kode til den dynamiske programmeringsløsning

Beregning af længden af ​​LCS

Eksempel i C#

Læser en LCS op

Eksempel i C#

Læser alle LCS'er op

Udskriv diff

Eksempel

Kodeoptimering

Reducer opgavesættet

Reducer sammenligningstiden

Reducer strenge til hash

Reducer den nødvendige plads

Yderligere optimerede algoritmer

Adfærd på tilfældige strenge

Se også

Referencer

eksterne links

Beregning af længden af LCS

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	EN	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	Y	0	1	1	2	2	2	2	2
5	EN	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