Najdłuższy wspólny podciąg

Porównanie dwóch wersji przykładowego pliku na podstawie ich najdłuższej wspólnej podsekwencji (czarny)

Najdłuższa wspólna podsekwencja ( LCS ) to najdłuższa podsekwencja wspólna dla wszystkich sekwencji w zbiorze sekwencji (często tylko dwóch sekwencji). Różni się od najdłuższego wspólnego podciągu : w przeciwieństwie do podciągów, podsekwencje nie muszą zajmować kolejnych pozycji w oryginalnych sekwencjach. Problem obliczania najdłuższych wspólnych podciągów jest klasycznym informatycznym , podstawą programów do porównywania danych , takich jak narzędzie diff i ma zastosowanie w lingwistyka komputerowa i bioinformatyka . Jest również szeroko stosowany przez systemy kontroli wersji, takie jak Git, do uzgadniania wielu zmian wprowadzonych w zbiorze plików kontrolowanych przez zmiany.

Rozważmy na przykład ciągi (ABCD) i (ACBAD). Mają 5 wspólnych podciągów o długości 2: (AB), (AC), (AD), (BD) i (CD); 2 długości-3 wspólne podciągi: (ABD) i (ACD); i już nie wspólne podsekwencje. Tak więc (ABD) i (ACD) są ich najdłuższymi wspólnymi podciągami.

Złożoność

W ogólnym przypadku dowolnej liczby sekwencji wejściowych problem jest NP-trudny . Gdy liczba sekwencji jest stała, problem można rozwiązać w czasie wielomianowym za pomocą programowania dynamicznego .

Biorąc pod $sekwencje$ długości ${\ Displaystyle n_ {1}, ..., n_ {N}}$ , naiwne wyszukiwanie przetestowałoby każdy z podsekwencji pierwszej sekwencji do $\ Displaystyle 2 ^ {n_ {1}}}$ określić, czy są one również podciągami pozostałych ciągów; każdy podsekwencja może być testowana liniowo w czasie w długościach pozostałych sekwencji, więc czas dla tego algorytmu byłby

{\ Displaystyle O \ lewo (2 ^ {n_ {1}} \ suma _ {i> 1} n_ {i} \ prawo).}

W przypadku dwóch sekwencji elementów n i m czas działania metody programowania dynamicznego wynosi O ( n × m ). Dla dowolnej liczby sekwencji wejściowych podejście do programowania dynamicznego daje rozwiązanie w

{\ Displaystyle O \ lewo (N \ prod _ {i = 1} ^ {N} n_ {i} \ prawo).}

Istnieją metody o mniejszej złożoności, które często zależą od długości LCS, rozmiaru alfabetu lub obu.

LCS niekoniecznie jest unikalny; w najgorszym przypadku liczba wspólnych podsekwencji jest wykładnicza w długości danych wejściowych, więc złożoność algorytmiczna musi być co najmniej wykładnicza.

Rozwiązanie dla dwóch ciągów

Problem LCS ma optymalną podstrukturę : problem można podzielić na mniejsze, prostsze podproblemy, które z kolei można podzielić na prostsze podproblemy i tak dalej, aż w końcu rozwiązanie stanie się trywialne. W szczególności LCS ma nakładające się podproblemy : rozwiązania podproblemów wysokiego poziomu często ponownie wykorzystują rozwiązania podproblemów niższego poziomu. Problemy o tych dwóch właściwościach są podatne na podejście do programowania dynamicznego , w którym rozwiązania podproblemów są zapamiętywane , to znaczy rozwiązania podproblemów są zapisywane do ponownego wykorzystania.

Przedrostki

Przedrostek S _n z S jest zdefiniowany jako pierwszych n znaków S . Na przykład przedrostki S = (AGCA) to

₀ S = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA).

Niech LCS ( X , Y ) będzie funkcją obliczającą najdłuższy podciąg wspólny dla X i Y . Taka funkcja ma dwie interesujące właściwości.

Pierwsza właściwość

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y )^ A , dla wszystkich łańcuchów X , Y i wszystkich symboli A , gdzie ^ oznacza konkatenację łańcuchów. Pozwala to uprościć LCS dla dwóch sekwencji kończących się tym samym symbolem. Na przykład LCS („BANAN”, „ATANA”) = LCS ("BANAN","ATAN")^"A", Kontynuując dla pozostałych wspólnych symboli, LCS ("BANANA","ATANA") = LCS ("BAN","AT")^"ANA".

Druga właściwość

Jeśli A i B są różnymi symbolami ( A ≠ B ), to LCS (X^A,Y^B) jest jednym z łańcuchów o maksymalnej długości w zbiorze { LCS ( X ^ A , Y ), LCS ( X , Y ^ B ) }, dla wszystkich łańcuchów X , Y.

Na przykład LCS („ABCDEFG”, „BCDGK”) jest najdłuższym ciągiem spośród LCS („ABCDEFG”, „BCDG”) i LCS („ABCDEF”, „BCDGK”); gdyby oba były równej długości, jeden z nich mógłby zostać wybrany arbitralnie.

Aby zrealizować właściwość, rozróżnij dwa przypadki:

Jeśli LCS („ABCDEFG”, „BCDGK”) kończy się na „G”, to końcowe „K” nie może znajdować się w LCS, stąd LCS („ABCDEFG”, „BCDGK”) = LCS („ABCDEFG”, „BCDG”) ").
Jeśli LCS („ABCDEFG”, „BCDGK”) nie kończy się na „G”, to końcowe „G” nie może znajdować się w LCS, stąd LCS („ABCDEFG”, „BCDGK”) = LCS ( „ ABCDEF”, „BCDGK”).

Zdefiniowana funkcja LCS

Niech dwie sekwencje zostaną zdefiniowane w następujący sposób: ${\ Displaystyle X = (x_ {1} x_ {2} \ cdots x_ {m})}$ i ${\ Displaystyle Y = (y_ {1} y_ {2} \ cdots y_ {n})}$ . Przedrostki ${\ Displaystyle X}$ to ${\ Displaystyle X_ {0}, X_ {1}, X_ {2}, \ kropki, X_ {m}}$ ; przedrostki ${\ Displaystyle Y}$ to ${\ Displaystyle Y_ {0}, Y_ {1}, Y_ {2}, \ kropki, Y_ {n}}$ . Niech ${\ Displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j})}$ reprezentuje zbiór najdłuższej wspólnej podsekwencji przedrostków ${\ Displaystyle X_ {i}}$ i ${\ Displaystyle Y_ {j}}$ . Ten zestaw sekwencji jest podany w następujący sposób.

{\ Displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j}) = {\ rozpocząć {przypadki} \ epsilon & {\ mbox {jeśli}} i = 0 {\ mbox {lub}} j = 0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\kapelusz {}}x_{i}&{\mbox{if}}i,j>0{\ mbox{ i }}x_{i}=y_{j}\\\nazwa_operatora {\max} \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS }}(X_{i-1},Y_{j})\}&{\mbox{if }}i,j>0{\mbox{ i }}x_{i}\neq y_{j}.\end {sprawy}}}

Aby znaleźć LCS $Displaystyle Y_ {j$ $}$ } , porównaj $jot$ $}$ { \ Displaystyle Y_ . ${\ Displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1}$ do ) przez ten element, ${\ displaystyle x_ {i}}$ . Jeśli nie są równe, to najdłuższa z dwóch sekwencji ${\ Displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j-1})}$ L ${\ Displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j})} ,$ zachowany. (Jeśli mają tę samą długość, ale nie są identyczne, to oba są zachowywane.) Przypadek podstawowy, gdy którykolwiek z nich ${\ Displaystyle X_ {i}}$ lub ${\ Displaystyle Y_ {i}}$ jest pusty, jest pustym łańcuchem , ${\ Displaystyle \ epsilon}$ .

Działający przykład

₀₀ Zostanie znaleziony najdłuższy podsekwencja wspólna dla R = (GAC) i C = (AGCAT). Ponieważ funkcja LCS używa elementu „zerowego”, wygodnie jest zdefiniować przedrostki zerowe, które są puste dla tych sekwencji: R = ε; i C = ε. Wszystkie prefiksy są umieszczane w tabeli z C w pierwszym wierszu (co czyni go nagłówkiem kolumny ) i R w pierwszej kolumnie (co czyni go nagłówkiem wiersza).

Struny LCS
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε
A	ε
C	ε

Ta tabela służy do przechowywania sekwencji LCS dla każdego kroku obliczeń. Druga kolumna i drugi wiersz zostały wypełnione przez ε, ponieważ przy porównywaniu pustego ciągu z niepustym ciągiem, najdłuższy wspólny podciąg jest zawsze pustym ciągiem.

₀₀ LCS ( R1 , C1 ) _{określa się}_przez porównanie pierwszych elementów w każdej sekwencji. G i A nie są takie same, więc ten LCS otrzymuje (używając „drugiej właściwości”) najdłuższy z dwóch ciągów, LCS ( R ₁ , C ) i LCS ( R , C ₁ ). Zgodnie z tabelą oba są puste, więc LCS ( R ₁ , C ₁₀₀ ) jest również pusty, jak pokazano w poniższej tabeli. Strzałki wskazują _{, że sekwencja}_pochodzi zarówno z komórki powyżej, LCS ( R , C1 ), jak i komórki po lewej stronie, LCS ( R1 , C ).

₀ LCS ( R ₁ , C ₂ ) jest określany przez porównanie G i G. Są one zgodne, więc G jest dołączane do górnej lewej sekwencji, LCS ( R , C ₁ ), czyli (ε), dając (εG), czyli (G).

Dla LCS ( R1 , C3 ) _, G i C nie pasują do siebie _. Powyższa sekwencja jest pusta; ten po lewej zawiera jeden element, G. Wybierając najdłuższy z nich, LCS ( R ₁ , C ₃ ) to (G). Strzałka wskazuje w lewo, ponieważ jest to najdłuższa z dwóch sekwencji.

LCS ( R1 , C4 ₎ podobnie oznacza (G) _.

LCS ( R1 , C5 ₎ podobnie oznacza (G) _.

Rząd „G” zakończony
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ ε	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)
A	ε
C	ε

Dla LCS ( R ₂ , C ₁ ), A jest porównywane z A. Te dwa elementy są zgodne, więc A jest dołączane do ε, dając (A).

Dla LCS ( R ₂ , C ₂ ), A i G nie pasują do siebie, więc najdłuższy z LCS ( R ₁ , C ₂ ), czyli (G) i LCS ( R ₂ , C ₁ ), czyli (A ), Jest używane. W tym przypadku każdy z nich zawiera jeden element, więc ten LCS ma podane dwa podsekwencje: (A) i (G).

Dla LCS ( R2 , C3 ) _, A nie pasuje do C. _LCS ( R2 , C2 ) zawiera sekwencje (A) i (G ₎_; LCS( R ₁ , C ₃ ) to (G), które jest już zawarte w LCS ( R ₂ , C ₂ ). W rezultacie LCS ( R ₂ , C ₃ ) zawiera również dwa podsekwencje, (A) i (G).

Dla LCS ( R ₂ , C ₄ ), A pasuje do A, które jest dołączone do górnej lewej komórki, dając (GA).

Dla LCS ( R2 , C5 ), A nie pasuje do T. Porównując dwie sekwencje, (GA) i (G), najdłuższy to (GA), więc _LCS ( _R2 , C5 ) to ₍_GA ).

Rzędy „G” i „A” zakończone
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ ε	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)
A	ε	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (A)	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ (A) i (G)	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ (A) i (G)	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (GA)
C	ε

Dla LCS ( R ₃ , C ₁ ), C i A nie pasują do siebie, więc LCS ( R ₃ , C ₁ ) otrzymuje najdłuższą z dwóch sekwencji, (A).

Dla LCS ( R3 , C2 ) _, C i G nie pasują do siebie _. Zarówno LCS ( R3 , C1 ), jak i _LCS ( R2 , C2 ) mają po _jednym_elemencie_. W rezultacie LCS ( R ₃ , C ₂ ) zawiera dwa podsekwencje, (A) i (G).

Dla LCS ( R ₃ , C ₃ ), C i C pasują, więc C jest dołączane do LCS ( R ₂ , C ₂ ), który zawiera dwa podsekwencje, (A) i (G), dając (AC) i (GC ).

Dla LCS ( R3 , C4 ) _, C i A nie pasują do siebie _. Połączenie LCS ( R ₃ , C ₃ ), który zawiera (AC) i (GC) oraz LCS ( R ₂ , C ₄ ), który zawiera (GA), daje łącznie trzy sekwencje: (AC), (GC) i (GA).

Wreszcie, dla LCS ( R3 , C5 ) _, C i T nie pasują do siebie _. W rezultacie LCS ( R3 , C5 ) zawiera również trzy sekwencje, (AC), (GC) i (GA ₎_.

Wypełniona tabela LCS
	ε	A	G	C	A	T
ε	ε	ε	ε	ε	ε	ε
G	ε	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ ε	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (G)
A	ε	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (A)	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ (A) i (G)	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ (A) i (G)	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ (GA)
C	ε	${\ Displaystyle {\ overset {\ \ uparrow} {\}}}$ (A)	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ (A) i (G)	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ (AC) i (GC)	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ (AC) i (GC) i (GA)	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ (AC) i (GC) i (GA)

Końcowy wynik jest taki, że ostatnia komórka zawiera wszystkie najdłuższe podsekwencje wspólne dla (AGCAT) i (GAC); są to (AC), (GC) i (GA). Tabela pokazuje również najdłuższe wspólne podsekwencje dla każdej możliwej pary przedrostków. Na przykład dla (AGC) i (GA) najdłuższą wspólną podsekwencją są (A) i (G).

Podejście śladowe

Obliczenie LCS wiersza tabeli LCS wymaga tylko rozwiązań dla bieżącego wiersza i poprzedniego wiersza. Jednak w przypadku długich sekwencji sekwencje te mogą być liczne i długie, co wymaga dużo miejsca do przechowywania. Miejsce w pamięci można zaoszczędzić, zapisując nie rzeczywiste podsekwencje, ale długość podsekwencji i kierunek strzałek, jak w poniższej tabeli.

Przechowywanie długości zamiast sekwencji
	A	G	C	A	T
ε	0	0	0	0	0
G	${\ Displaystyle {\ overset {\ \ \ uparrow} {\ lefttarrow}}}$ 0	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 1	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 1	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 1
A	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 1	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 1	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 2
C	${\ Displaystyle {\ overset {\ \ uparrow} {\}}}$ 1	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 1	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 2	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 2

Rzeczywiste podsekwencje są dedukowane w procedurze „śledzenia wstecznego”, która podąża za strzałkami do tyłu, zaczynając od ostatniej komórki w tabeli. Kiedy długość maleje, sekwencje musiały mieć wspólny element. Możliwych jest kilka ścieżek, gdy w komórce są wyświetlane dwie strzałki. Poniżej znajduje się tabela do takiej analizy, z kolorowymi liczbami w komórkach, w których długość ma się zmniejszyć. Pogrubione liczby śledzą sekwencję (GA).

Przykład śledzenia wstecznego
	A	G	C	A	T
ε	0	0	0	0	0
G	${\ Displaystyle {\ overset {\ \ \ uparrow} {\ lefttarrow}}}$ 0	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 1	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 1	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 1
A	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 1	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 1	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ Displaystyle {\ overset {\ } {\ strzałka w lewo}}}$ 2
C	${\ Displaystyle {\ overset {\ \ uparrow} {\}}}$ 1	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 1	${\ Displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 2	${\ Displaystyle {\ overset {\ \ \ górna część} {\ lewa strzałka}}}$ 2

Stosunek do innych problemów

Dla dwóch łańcuchów i Y $\ Displaystyle Y_ {1 \ kropek n}$ $długość najkrótszej wspólnej supersekwencji jest związana z długością LCS X 1 … m {\ Displaystyle X_ {$ 1 \ m przez

{\ Displaystyle \ lewo | SCS (X, Y) \ prawo | = n + m- \ lewo | LCS (X, Y) \ prawo |.}

Odległość edycji , gdy dozwolone jest tylko wstawianie i usuwanie (bez podstawienia) lub gdy koszt podstawienia jest dwukrotnością kosztu wstawienia lub usunięcia, wynosi:

{\ Displaystyle d' (X, Y) = n + m-2 \ cdot \ lewo | LCS (X, Y) \ prawo |.}

Kod rozwiązania do programowania dynamicznego

Obliczanie długości LCS

Poniższa funkcja przyjmuje jako sekwencje wejściowe X[1..m] i Y[1..n] , oblicza LCS między X[1..i] a Y[1...j] dla wszystkich 1 ≤ i ≤ m i 1 ≤ j ≤ n i przechowuje to w C[i,j] . C[m,n] będzie zawierać długość LCS X i Y .

 funkcja  LCSLength(X[1..m], Y[1..n]) C = tablica(0..m, 0..n)  dla  i := 0..m C[i,0] = 0  dla  j := 0..n C[0,j] = 0  dla  i := 1..m  dla  j := 1..n  jeśli  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]

Alternatywnie można zastosować zapamiętywanie .

Przykład w C#

     

	   
	   
	         
	    0    static  int  LcsLength  (  string  a  ,  string  b  )  {  int  m  =  a  .  długość  ;  int  n  =  b  .  długość  ;  int  [,]  C  =  nowy  int  [  m  +  1  ,  n  +  1  ];  for  (  int  i  =  ;  i  <=  m  
		 0  0
	    0    
		0   0
	        
		       ;  ja  ++)  do  [  ja  ,  ]  =  ;  dla  (  int  j  =  ;  j  <=  n  ;  j  ++)  do  [  ,  j  ]  =  ;  for  (  int  i  =  1  ;  i  <=  m  ;  i  ++)  for  (  int  j  =  1  ;  j  <=   
		
			       
				          
			
				    n  ;  jot  ++)  {  gdyby  (  za  [  ja  -  1  ]  ==  b  [  jot  -  1  ])  do  [  ja  ,  jot  ]  =  do  [  ja  -  1  ,  j  -  1  ]  +  1  ;  w przeciwnym razie  C  [  i  ,  j  ]  =  Matematyka  .  maks  (        
		
	  
 do  [  ja  ,  j  -  1  ],  do  [  i  -  1  ,  j  ]);  }  powrót  C  [  m  ,  n  ];  }

Odczyt LCS

Poniższa funkcja cofa wybory dokonane podczas obliczania tabeli C. Jeśli ostatnie znaki w prefiksach są równe, muszą należeć do LCS. Jeśli $displaystyle y_ {j}}$ , sprawdź, co dało największy LCS utrzymania $\$ jot { i dokonaj tego samego wyboru Po prostu wybierz jeden, jeśli byłyby równie długie. Wywołaj funkcję za pomocą i=m i j=n .

 funkcja  backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)  jeśli  i = 0  lub  j = 0  zwróć  ""  jeśli  X[ i] = Y[j]  powrót  wstecz (C, X, Y, i-1, j-1) + X[i]  jeśli  C[i,j-1] > C[i-1,j]  powrót  wstecz( C, X, Y, i, j-1)  powrót  wstecz (C, X, Y, i-1, j)

Przykład w C#

          

       0    0
         
            string  backtrack  (  int  [,]  C  ,  char  []  aStr  ,  char  []  bStr  ,  int  x  ,  int  y  )  {  if  (  x  ==  |  y  ==  )  return  ""  ;  jeśli  (  aStr  [  x  -  1  ]  ==  bStr  [  y  -  1  ])  
                      
             
          // x-1, y-1  powrót  wstecz  (  C  ,  aStr  ,  bStr  ,  x  -  1  ,  y  -  1  )  +  aStr  [  x  -  1  ];  // x-1  if  (  C  [  x  ,  y  -  1  ]  >  C  [  x  -  1  ,  y  ])  powrót do  poprzedniej ścieżki  (  C       
           
 ,  aStr  ,  bStr  ,  x  ,  y  -  1  );  powrót  wstecz  (  C  ,  aStr  ,  bStr  ,  x  -  1  ,  y  );  }

Odczytywanie wszystkich LCS

Jeśli wybranie $podsekwencje$ dałoby równie długi wynik, $.$ Jest to zwracane jako zestaw przez tę funkcję. Zauważ, że ta funkcja nie jest wielomianem, ponieważ może rozgałęziać się w prawie każdym kroku, jeśli łańcuchy są podobne.

 funkcja  backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)  jeśli  i = 0  lub  j = 0  return  {""}  jeśli  X[i] = Y[j]  return  {Z + X[i]  dla wszystkich  Z  w  backtrackAll(C, X, Y, i-1, j-1)} R := {}  jeśli  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

Wydrukuj różnicę

Ta funkcja cofnie się przez macierz C i wypisze różnicę między dwiema sekwencjami. Zauważ, że otrzymasz inną odpowiedź, jeśli zamienisz ≥ i < , z > i ≤ poniżej.

 funkcja  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] inaczej jeśli j > 0 i (i = 0  lub  C  [  i  ,  j-1] ≥ C[i-1,j]) printDiff(C, X,   Y  , i, j-1) print "+ " + Y[j] inaczej jeśli i > 0 i (j = 0  lub  C  [  i  ,j-1 ] < C[i-1,j]) printDiff(C, X, Y, i-1, j) print "- " + X[i]  jeszcze  drukuj ""

Przykład

Niech ${\ displaystyle X}$ będzie „ XMJYAUZ ” i ${\ displaystyle Y}$ będzie „ MZJAWXU ”. Najdłuższy wspólny podsekwencja między i $displaystyle$ $Y}$ to „ MJAU ”. Tabela C pokazana poniżej, która jest generowana przez funkcję LCSLength , pokazuje długości najdłuższych wspólnych podsekwencji między przedrostkami ${\ displaystyle X}$ i ${\ displaystyle Y}$ . ja ${\ displaystyle i}$ th wiersz i $kolumna$ pokazuje długość LCS między ${\ Displaystyle X_ {1 .. i}}$ 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	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

Podświetlone liczby pokazują ścieżkę, po której podążałaby funkcja wstecz od prawego dolnego rogu do lewego górnego rogu podczas odczytywania LCS. $Jeśli$ obecne symbole w $są$ równe, są częścią LCS i idziemy zarówno w górę, jak iw lewo (pokazane pogrubioną ) . Jeśli nie, idziemy w górę lub w lewo, w zależności od tego, która komórka ma wyższy numer. Odpowiada to przyjęciu LCS między $}}$ 1 ${\ Displaystyle Y_ {1 j}}$ lub ${\ Displaystyle X_ {1 .. i}}$ i ${\ Displaystyle Y_ {1 .. j-1}}$ .

Optymalizacja kodu

W powyższym algorytmie można wprowadzić kilka optymalizacji, aby przyspieszyć go w rzeczywistych przypadkach.

Zmniejsz zestaw problemów

Macierz C w algorytmie naiwnym rośnie kwadratowo wraz z długością sekwencji. W przypadku dwóch sekwencji po 100 pozycji potrzebna byłaby macierz zawierająca 10 000 pozycji i należałoby wykonać 10 000 porównań. W większości rzeczywistych przypadków, zwłaszcza różnic i poprawek kodu źródłowego, początki i końce plików rzadko się zmieniają, a prawie na pewno nie oba jednocześnie. Jeśli w środku sekwencji zmieniło się tylko kilka elementów, początek i koniec można wyeliminować. Zmniejsza to nie tylko wymagania pamięciowe dla macierzy, ale także liczbę porównań, które należy wykonać.

    
     funkcja  LCS(X[1..m], Y[1..n]) start := 1 m_end := m n_end := n  odetnij pasujące elementy na początku  , podczas gdy  start ≤ m_end  i  start ≤ n_end  i  X[ start] = Y[początek] start := start + 1  odetnij pasujące elementy na końcu  while  start ≤ m_end  i  start ≤ n_end  i  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) tylko w pętli   nad  elementami, które się zmieniły 
     i := start..m_end  for  j := start..n_end  algorytm kontynuuje jak poprzednio...

W najlepszym przypadku, w sekwencji bez zmian, ta optymalizacja wyeliminowałaby potrzebę stosowania macierzy C. W najgorszym przypadku, gdy zmienia się pierwszy i ostatni element w sekwencji, wykonywane są tylko dwa dodatkowe porównania.

Skróć czas porównania

Algorytm naiwny spędza większość czasu na porównywaniu elementów w sekwencjach. W przypadku sekwencji tekstowych, takich jak kod źródłowy, chcesz wyświetlać wiersze jako elementy sekwencji, a nie pojedyncze znaki. Może to oznaczać porównania stosunkowo długich łańcuchów dla każdego kroku algorytmu. Można wprowadzić dwie optymalizacje, które mogą pomóc skrócić czas, jaki zajmują te porównania.

Zredukuj łańcuchy do skrótów

Funkcja skrótu lub suma kontrolna mogą być użyte do zmniejszenia rozmiaru łańcuchów w sekwencjach. Oznacza to, że dla kodu źródłowego, w którym przeciętna linia ma długość 60 lub więcej znaków, skrót lub suma kontrolna dla tej linii może mieć tylko 8 do 40 znaków. Dodatkowo losowy charakter skrótów i sum kontrolnych gwarantowałby, że porównania byłyby szybsze, ponieważ linie kodu źródłowego rzadko byłyby zmieniane na początku.

Ta optymalizacja ma trzy podstawowe wady. Po pierwsze, należy wcześniej poświęcić trochę czasu na wstępne obliczenie skrótów dla dwóch sekwencji. Po drugie, należy przydzielić dodatkową pamięć dla nowych zaszyfrowanych sekwencji. Jednak w porównaniu z zastosowanym tutaj algorytmem naiwnym obie te wady są stosunkowo minimalne.

Trzecią wadą są kolizje . Ponieważ suma kontrolna lub skrót nie gwarantuje, że są unikalne, istnieje niewielka szansa, że dwa różne elementy zostaną zredukowane do tego samego skrótu. Jest to mało prawdopodobne w kodzie źródłowym, ale jest możliwe. Hash kryptograficzny byłby zatem znacznie lepiej dostosowany do tej optymalizacji, ponieważ jego entropia będzie znacznie większa niż w przypadku prostej sumy kontrolnej. Jednak korzyści mogą nie być warte konfiguracji i wymagań obliczeniowych skrótu kryptograficznego dla małych długości sekwencji.

Zmniejsz wymaganą przestrzeń

${\ Displaystyle \ min (m, n) + 1},$ $m$ długość LCS, macierz do ponieważ podejście do programowania dynamicznego wymaga tylko bieżącej i poprzednich kolumn macierzy. Algorytm Hirschberga pozwala na zbudowanie samej sekwencji optymalnej w tych samych kwadratowych granicach czasu i liniowej przestrzeni.

Zmniejsz braki w pamięci podręcznej

Chowdhury i Ramachandran opracowali algorytm przestrzeni liniowej w czasie kwadratowym do znajdowania długości LCS wraz z optymalną sekwencją, która w praktyce działa szybciej niż algorytm Hirschberga ze względu na lepszą wydajność pamięci podręcznej. Algorytm ma asymptotycznie optymalną złożoność pamięci podręcznej w ramach modelu idealnej pamięci podręcznej . Co ciekawe, sam algorytm nie zwraca uwagi na pamięć podręczną, co oznacza, że nie dokonuje żadnych wyborów w oparciu o parametry pamięci podręcznej (np. rozmiar pamięci podręcznej i rozmiar linii pamięci podręcznej) maszyny.

Dalsze zoptymalizowane algorytmy

Istnieje kilka algorytmów, które działają szybciej niż przedstawione podejście do programowania dynamicznego. $_$ z Hunta - w $_ \ displaystyle n> m}$ ), gdzie jest $.$ dopasowań między dwiema sekwencjami W przypadku problemów z ograniczonym rozmiarem alfabetu, Metodę Czterech Rosjan można wykorzystać do skrócenia czasu działania algorytmu programowania dynamicznego o czynnik logarytmiczny.

Zachowanie na losowych ciągach znaków

Począwszy od Chvátal & Sankoff (1975) , wielu badaczy badało zachowanie najdłuższej wspólnej długości podsekwencji, gdy dwa podane ciągi są losowane z tego samego alfabetu. Gdy rozmiar alfabetu jest stały, oczekiwana długość LCS jest proporcjonalna do długości dwóch ciągów, a stałe proporcjonalności (w zależności od rozmiaru alfabetu) są znane jako stałe Chvátala- Sankoffa . Ich dokładne wartości nie są znane, ale udowodniono górne i dolne granice ich wartości i wiadomo, że rosną one odwrotnie proporcjonalnie do pierwiastka kwadratowego z rozmiaru alfabetu. Wykazano, że uproszczone modele matematyczne najdłuższego wspólnego problemu podsekwencji są kontrolowane przez rozkład Tracy-Widoma .

Zobacz też

Linki zewnętrzne

Smyczki
Metryka ciągu	Przybliżone dopasowanie ciągów Algorytm bitapowy Odległość Damerau-Levenshteina Edytuj odległość Dopasowanie wzorca Gestalt Odległość Hamminga Odległość Jaro-Winklera Odległość Lee Automat Levenshteina Odległość Levenshteina Algorytm Wagnera-Fischera
Algorytm przeszukiwania ciągów znaków	Algorytm Apostolico – Giancarlo Algorytm przeszukiwania łańcuchów Boyera-Moore'a Algorytm Boyera-Moore'a-Horspoola Algorytm Knutha – Morrisa – Pratta Algorytm Rabina-Karpa
Wyszukiwanie wielu ciągów	Aho-Corasick Algorytm Commentza-Waltera
Wyrażenie regularne	Porównanie silników wyrażeń regularnych Zwykła gramatyka Konstrukcja Thompsona Niedeterministyczny automat skończony
Wyrównanie sekwencji	Algorytm Hirschberga Algorytm Needlemana-Wunscha Algorytm Smitha-Watermana
Struktura danych	DAFSA Tablica sufiksów Automat sufiksowy Drzewo sufiksów Uogólnione drzewo sufiksów Lina Trójskładnikowe drzewo wyszukiwania Spróbuj
Inny	Rozbiór gramatyczny zdania Dopasowanie wzorca Skompresowane dopasowanie wzorca Najdłuższy wspólny podciąg Najdłuższy wspólny podciąg Eksploracja wzorców sekwencyjnych Sortowanie

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