longest common subsequence

Angol

Főnév

longest common subsequence (tsz. longest common subsequences)

(informatika) leghosszabb közös részsorozat

A leghosszabb közös részszekvencia (LCS) két (vagy több) szöveg, karakterlánc vagy szekvencia közötti legnagyobb hosszúságú olyan karaktersorozat, amely mindkettőben előfordul ugyanabban a sorrendben, de nem feltétlenül egymás után.

Fontos:

Nem azonos a “substring”-gel (folyamatos rész),
A “subsequence” engedi, hogy karakterek kimaradjanak.

2. Példa

S1 = "ABCBDAB"
S2 = "BDCABA"

LCS = "BCBA" vagy "BDAB" vagy "BCAB" (mind hossz: 4)

3. Probléma célja

Meghatározni a két adott sorozat egyik legnagyobb hosszú közös részszekvenciáját.

Ez egy klasszikus dinamikus programozási feladat.

4. Alkalmazások

🧬 Bioinformatika – DNS/fehérje-szekvenciák hasonlósága
🔎 Verziókövetés – fájlváltozások detektálása (diff)
📄 Szövegelemzés – plagizálás, hasonlóság
🤖 Gépi tanulás – hasonlósági metrikák
🧠 Memória algoritmusok – memóriaalapú tanulásnál

5. LCS formális definíciója

Adott két sorozat:

${\textstyle X=x_{1},x_{2},...,x_{m}}$
${\textstyle Y=y_{1},y_{2},...,y_{n}}$

Egy ${\textstyle Z=z_{1},...,z_{k}}$ sorozat LCS, ha:

${\textstyle Z}$ részszekvenciája mind ${\textstyle X}$ -nek, mind ${\textstyle Y}$ -nak
${\textstyle k}$ a lehető legnagyobb

6. Megoldás – Dinamikus programozással

🧮 Definíció:

Legyen ${\textstyle dp[i][j]}$ : az ${\textstyle X[0..i-1]}$ és ${\textstyle Y[0..j-1]}$ közös részszekvencia maximális hossza

📐 Rekurzív képlet:

$dp[i][j]={\begin{cases}0&{\text{ha }}i=0{\text{ vagy }}j=0\\dp[i-1][j-1]+1&{\text{ha }}X[i-1]=Y[j-1]\\\max(dp[i-1][j],\ dp[i][j-1])&{\text{ha }}X[i-1]\neq Y[j-1]\end{cases}}$

🧱 Táblázatos (bottom-up) feltöltés:

Soronként, oszloponként kitöltjük a mátrixot
A jobb alsó sarokban lesz az LCS hossza

7. Python megoldás

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    return dp[m][n]

Példa:

print(lcs("ABCBDAB", "BDCABA"))  # Kimenet: 4

8. LCS visszafejtése (a részszekvencia)

A dp tábla alapján rekurzívan visszafejthető az LCS:

def lcs_sequence(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    # visszafejtés
    i, j = m, n
    seq = []
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            seq.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(seq))

print(lcs_sequence("ABCBDAB", "BDCABA"))  # Lehet: "BCBA"

9. Optimalitás és bonyolultság

Időkomplexitás: ${\textstyle O(mn)}$
Térkomplexitás: ${\textstyle O(mn)}$ , optimalizálható ${\textstyle O(n)}$ -re, ha csak a hossz érdekel
NP-nehéz probléma több szekvencia esetén (pl. LCS 3 szóra: NP-nehéz)

10. Vizualizáció – DP tábla (részlet)

Például:

X = A B C B D A B
Y = B D C A B A

        B D C A B A
      ----------------
    | 0 0 0 0 0 0 0
  A | 0
  B | 0
  C | 0
  B | 0
  D | 0
  A | 0
  B | 0

Fokozatosan kitöltve a képlet alapján.

11. Alternatív algoritmusok

Rekurzív, memoizációval: lassabb, tanulási célokra jó
Hirschberg-algoritmus: O(n) memóriás változat, csak a szekvenciát állítja elő
LCS több sorozatra: sokkal bonyolultabb, exponenciális idő

12. Összefoglalás

A Longest Common Subsequence (LCS) probléma:

Két szekvencia közös elemeinek legnagyobb hossza
Nem feltétlenül folyamatos, csak sorrendben szereplő karakterek
Dinamikus programozással hatékonyan megoldható
Széleskörű alkalmazás szöveg-összehasonlításban, DNS-elemzésben, verziókövetésben

További információk

longest common subsequence - Szótár.net (en-hu)
longest common subsequence - Sztaki (en-hu)
longest common subsequence - Merriam–Webster
longest common subsequence - Cambridge
longest common subsequence - WordNet
longest common subsequence - Яндекс (en-ru)
longest common subsequence - Google (en-hu)
longest common subsequence - Wikidata
longest common subsequence - Wikipédia (angol)