Najdłuższa Wspólna Podciągła: Algorytm Diffa

Podzbiór, a nie podciąg

Podzbiór zachowuje względny porządek znaków, ale nie wymaga ich sąsiedztwa – "ACE" jest podzbiorem "ABCDE", pomijając B i D. Najdłuższy wspólny podzbiór (LCS) dwóch ciągów to najdłuższa sekwencja, która jest podzbiorem obu. To pozornie proste pytanie – "jaki największy fragment te dwie rzeczy mają ze sobą współdzieląc, pozwalając na przerwy?" – okazuje się być idealną formalizacją pytania "jak bardzo są podobne te dwa pliki, te dwa nici DNA, te dwie wersje dokumentu."

Rekurencja

Niech dp[i][j] oznacza długość LCS (najdłuższej wspólnej podciągu) pierwszych i-kich znaków ciągu A i pierwszych j-kich znaków ciągu B. W przeciwieństwie do odległości edycyjnej, nie ma kosztu niezgodności – niepasujący parę nie może być włączona ani do jednego, ani do drugiego ciągu, więc rekurencja przyjmuje najlepszą z możliwości pominięcia jednego znaku z dowolnego łańcucha:

dp[0][j] = dp[i][0] = 0 dp[i][j] = dp[i-1][j-1] + 1 jeśli A[i] == B[j] dp[i][j] = max(dp[i-1][j], dp[i][j-1]) jeśli A[i] != B[j]

Wypełnianie tej (n+1)×(m+1) siatki kosztuje O(nm) czasu i miejsca, tak samo jak odległość edycyjna – oba problemy są bliskimi krewnymi, a długość LCS w rzeczywistości równa się n + m pomniejszonej o dwa razy odległości edycyjnej, gdy dopuszczamy tylko operacje wstawiania i usuwania (bez substytucji).

dp[0][j] = dp[i][0] = 0

dp[i][j] = dp[i-1][j-1] + 1              if A[i] == B[j]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])   if A[i] != B[j]

Śledzenie diagonali dopasowań

Zaczynając od komórki narożnej z dołu i pychu, postępuj po analogicznym torze wstecznym, używanym w obliczaniu dystansu edycji: gdyby A[i] równało się B[j], komórka musiała pochodzić z kroku diagonalnego i ten znak należy do LCS; w przeciwnym razie wykonaj krok do dowolnego sąsiada (góry lub lewej) który pasuje do dp[i][j] i spróbuj ponownie. Gromadząc znaki znalezione na krokach diagonalnych, w odwrotnej kolejności, tworzy się jeden poprawny najdłuższy wspólny podciąg – może być ich kilka o równej długości, a który z nich tor odzyskuje zależy od rozwiązywania konfliktów.

Algorytm stojący za każdym różnicą, którą przeczytałeś

Różnica oparta na liniach traktuje każdy plik jako sekwencję linii i oblicza LCS (Najdłuższą Wspólną Sekwencję) tych dwóch sekwencji. Linie występujące w LCS są oznaczane jako niezmienione; wszystko inne jest oznaczone jako dodane (obecne w nowym pliku, ale nie w LCS) lub usunięte (obecne w starym pliku, ale nie w LCS). Git i większość nowoczesnych narzędzi do różnicowania nie uruchamiają bezpośrednio podręcznikowego algorytmu DP o złożoności O(nm) – wykorzystują oni algorytm Myer's, który znajduje tę samą najkrótszą sekwencję edycji, przeszukując "przeciwediagony" w implikowanej grafie edycji, co zwykle działa znacznie szybciej niż O(nm), gdy dwa pliki są w dużej mierze podobne – co jest typowym przypadkiem w systemach kontroli wersji.

DNA, białka i poza nimi

LCS traktuje każdy dopasowanie jako bezpłatne oraz każde niezgodność jako wymuszone ominięcie, co stanowi rozsądny model dla zwykłego tekstu, ale zbyt niedokładny dla biologii, gdzie substytucja i wstawienie rzadko wiążą się z tym samym kosztem ewolucyjnym. Bioinformatyka wykorzystuje tę samą strukturę diagonalną/wertykalną/poziomo-górną DP, ale z macierzą ocen, algorytm Needleman-Wunsza do pełnego wyrównania end-to-end, a Smitha-Watermana do znalezienia najlepszego dopasowującego regionu lokalnego w dwóch dłuższych sekwencjach. Oba są strukturalnie LCS z przypisanymi wagami, dlatego zrozumienie nieobciążonej wersji ułatwia śledzenie algorytmów biologicznych.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Longest Common Subsequence i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.