Najdłuższy wspólny podciąg (LCS)

Wprowadzenie

Najdłuższy wspólny podciąg (ang. Longest Common Subsequence, LCS) to fundamentalny problem w informatyce dotyczący porównywania sekwencji. Problem ten ma szerokie zastosowanie w: - Porównywaniu plików (np. narzędzie diff) - Wykrywaniu plagiatów - Bioinformatyce (porównywanie sekwencji DNA) - Systemach kontroli wersji (Git, SVN) - Sprawdzaniu podobieństwa tekstów

Definicja podciągu

Podciąg (subsequence) to sekwencja elementów, która może być uzyskana z innej sekwencji przez usunięcie niektórych (lub żadnych) elementów bez zmiany kolejności pozostałych.

Przykład:

Sekwencja: "ABCDEFG"

Podciągi:
✅ "ACE"     (usunięto B, D, F, G)
✅ "BDF"     (usunięto A, C, E, G)
✅ "ABCDEFG" (nic nie usunięto)
✅ ""        (wszystko usunięto)

NIE podciągi:
❌ "CBA"     (zmieniona kolejność)
❌ "AXC"     (dodano X)

Różnica: Podciąg vs Podstring:

Sekwencja: "ABCDE"

Podciąg: "ACE" ✅ (elementy mogą być nieciągłe)
Podstring: "BCD" ✅ (elementy MUSZĄ być ciągłe)

"ACE" to podciąg, ale NIE podstring
"BCD" to zarówno podciąg, jak i podstring

Problem LCS

Definicja formalna

Dane: - Dwie sekwencje X = [x₁, x₂, ..., xₘ] i Y = [y₁, y₂, ..., yₙ]

Znajdź: - Najdłuższą sekwencję Z, która jest podciągiem zarówno X, jak i Y

Przykład:

X = "ABCDGH"
Y = "AEDFHR"

Wspólne podciągi:
- "A"
- "AD"
- "ADH" ← najdłuższy (długość 3)
- "AH"

LCS(X, Y) = "ADH" (długość 3)

Uwaga: LCS może nie być unikalny!

X = "ABCD"
Y = "ABDC"

LCS może być:
- "ABC" (długość 3)
- "ABD" (długość 3)

Oba są poprawne!

Podejście 1: Rekurencja naiwna

Wzór rekurencyjny

Dla dwóch sekwencji X[0..m-1] i Y[0..n-1]:

LCS(X, Y, m, n) =
    0                                      jeśli m = 0 lub n = 0
    LCS(X, Y, m-1, n-1) + 1               jeśli X[m-1] = Y[n-1]
    max(LCS(X, Y, m, n-1),                jeśli X[m-1] ≠ Y[n-1]
        LCS(X, Y, m-1, n))

Intuicja: 1. Przypadek bazowy: Jeśli któraś sekwencja jest pusta, LCS = 0 2. Ostatnie znaki się zgadzają: Dołącz ten znak do LCS mniejszego problemu 3. Ostatnie znaki różne: Sprawdź dwie możliwości (usuń z X lub usuń z Y) i weź większą

Implementacja rekurencyjna

Drzewo rekurencji (fragment):

                    LCS("AGGTAB", "GXTXAYB")
                    /                         \
        LCS("AGGTAB", "GXTXAY")      LCS("AGGTA", "GXTXAYB")
        /               \                /                  \
      ...              ...              ...                ...

Problem: Wiele stanów obliczanych wielokrotnie!
Np. LCS("AG", "GX") pojawi się dziesiątki razy.

Podejście 2: Programowanie dynamiczne (Tabulation)

Implementacja tabelaryczna

Wizualizacja tablicy DP:

X = "AGGTAB"
Y = "GXTXAYB"

        ""  G  X  T  X  A  Y  B
    ""   0  0  0  0  0  0  0  0
    A    0  0  0  0  0  1  1  1
    G    0  1  1  1  1  1  1  1
    G    0  1  1  1  1  1  1  1
    T    0  1  1  2  2  2  2  2
    A    0  1  1  2  2  3  3  3
    B    0  1  1  2  2  3  3  4
                              ↑
                           WYNIK

Krok po kroku dla dp[6][7] (ostatnia komórka):
X[5]='B', Y[6]='B' → ZGADZA SIĘ!
dp[6][7] = dp[5][6] + 1 = 3 + 1 = 4

Drukowanie tablicy DP

Wyjście:

Tablica DP:
          A  E  D  F  H  R
        0  0  0  0  0  0  0
A       0  1  1  1  1  1  1
B       0  1  1  1  1  1  1
C       0  1  1  1  1  1  1
D       0  1  1  2  2  2  2
G       0  1  1  2  2  2  2
H       0  1  1  2  2  3  3

Długość LCS: 3

Rekonstrukcja LCS: Odtworzenie podciągu

Algorytm backtracingu

Wyjaśnienie backtracingu:

Start: i=6, j=7, dp[6][7]=4

Krok 1:
  X[5]='B', Y[6]='B' → ZGADZA SIĘ
  Dodaj 'B' do LCS, idź do (5, 6)

Krok 2:
  X[4]='A', Y[5]='Y' → RÓŻNE
  dp[4][6]=3, dp[5][5]=3 → Idź w lewo (j--)
  Przejdź do (5, 5)

Krok 3:
  X[4]='A', Y[4]='A' → ZGADZA SIĘ
  Dodaj 'A' do LCS, idź do (4, 4)

...

LCS (od tyłu): ['B', 'A', 'T', 'G']
Po odwróceniu: ['G', 'T', 'A', 'B'] → "GTAB"

Optymalizacja pamięci: O(m·n) → O(min(m, n))

Obserwacja

Przy obliczaniu dp[i][j] potrzebujemy tylko: - Bieżącego wiersza: dp[i][...] - Poprzedniego wiersza: dp[i-1][...]

Możemy użyć tylko dwóch tablic 1D zamiast tablicy 2D!

Implementacja z optymalizacją pamięci

Zużycie pamięci:

Bez optymalizacji: O(m·n)
  m=1000, n=1000 → 1,000,000 komórek → ~8 MB

Z optymalizacją: O(min(m, n))
  m=1000, n=1000 → 1,000 komórek → ~8 KB

Oszczędność: 1000× mniej pamięci!

Warianty problemu LCS

1. Najdłuższy wspólny podstring (Longest Common Substring)

Różnica: Podstring musi być ciągły!

2. LCS dla więcej niż 2 sekwencji

3. Shortest Common Supersequence (SCS)

Definicja: Najkrótsza sekwencja zawierająca obie sekwencje jako podciągi.

Wzór:

SCS(X, Y) = len(X) + len(Y) - LCS(X, Y)

Praktyczne zastosowania LCS

1. Narzędzie diff (porównywanie plików)

Wyjście:

Różnice:
  def hello():
- print('Hello')
+ print('Hello, World!')
+ print('Welcome')
  return 0

2. Wykrywanie plagiatu

3. Bioinformatyka: Porównywanie sekwencji DNA

Wyjście:

Sekwencja 1: AGGTAB
Sekwencja 2: GXTXAYB
LCS: GTAB (długość: 4)
Podobieństwo: 57.1%

Benchmark: Porównanie implementacji

Przykładowe wyniki:

n=15, m=15:
  Rekurencja          → czas: 0.124567s, długość LCS: 8
  DP (2D tablica)     → czas: 0.000234s, długość LCS: 8
  DP (optymalizacja)  → czas: 0.000189s, długość LCS: 8

n=100, m=100:
  DP (2D tablica)     → czas: 0.004521s, długość LCS: 52
  DP (optymalizacja)  → czas: 0.003876s, długość LCS: 52

n=500, m=500:
  DP (2D tablica)     → czas: 0.089234s, długość LCS: 261
  DP (optymalizacja)  → czas: 0.078912s, długość LCS: 261

Podsumowanie

Algorytm Złożoność czasowa Złożoność pamięciowa Uwagi
Rekurencja naiwna O(2^(m+n)) O(m+n) Za wolne dla m,n > 20
Memoization O(m·n) O(m·n) Top-down DP
Tabulation O(m·n) O(m·n) Bottom-up DP
Optymalizacja pamięci O(m·n) O(min(m,n)) Najbardziej efektywne

Co dalej?

Po opanowaniu problemu LCS, następne kroki to:

  1. Lekcja 53: Najdłuższy rosnący podciąg (LIS)
  2. Problem optymalizacji sekwencji numerycznych
  3. Rozwiązanie O(n²) i O(n log n)

  4. Zastosowania w analizie danych

  5. Inne problemy na stringach z DP:

  6. Edit Distance (odległość Levenshteina)
  7. Longest Palindromic Subsequence

  8. Pattern Matching z DP

  9. Zaawansowane algorytmy sekwencyjne:

  10. Smith-Waterman (bioinformatyka)
  11. Needleman-Wunsch (global alignment)
  12. Suffix Trees i Suffix Arrays

Zadania praktyczne

Zadanie 1: Diff dla znaków

Zmodyfikuj funkcję diff_lines aby działała na poziomie znaków, nie linii. Pokaż różnice jak w narzędziu diff.

Zadanie 2: LCS trzech sekwencji

Zaimplementuj efektywny algorytm LCS dla dokładnie 3 sekwencji (tablica 3D).

Zadanie 3: Wizualizacja

Stwórz wizualizację tablicy DP pokazującą, jak wypełniane są kolejne komórki.

Zadanie 4: LCS z kosztami

Rozszerz LCS o koszty: każdy znak ma określoną wagę, znajdź podciąg o maksymalnej sumie wag.

Następna lekcja: Najdłuższy rosnący podciąg (LIS) - problem optymalizacji sekwencji numerycznych

Wróć do spisu lekcji