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

Gdy porównujesz dwie wersje pliku, wiersze, które się nie zmieniły, tworzą wspólny podciąg obu wersji. Znalezienie najdłuższego mówi dokładnie, co dodano, a co usunięto. Ta sama idea pozwala dopasowywać do siebie nici DNA i podpowiadać poprawki pisowni, a rozwiązuje ją jedna z najbardziej eleganckich tabel w informatyce.

Tabela z jednym słowem u góry i drugim z boku, liczbami w komórkach i ścieżką pomarańczowych komórek wspinającą się od prawego dolnego rogu
Tabela z jednym słowem u góry i drugim z boku, liczbami w komórkach i ścieżką pomarańczowych komórek wspinającą się od prawego dolnego rogu

Problem

Podciąg słowa zachowuje niektóre jego litery w pierwotnej kolejności: ACE jest podciągiem ABCDE, ale EA nie jest. Wspólny podciąg dwóch słów jest podciągiem obu, a zadanie polega na znalezieniu najdłuższego. Słowo o długości n ma 2ⁿ podciągów, więc sprawdzanie wszystkich jest beznadziejne, gdy liter jest więcej niż kilka.

Tabela

Niech len[i][j] będzie długością najdłuższego wspólnego podciągu pierwszych i liter jednego słowa i pierwszych j liter drugiego. Puste słowo nie ma nic wspólnego z niczym, więc pierwszy wiersz i pierwsza kolumna mają wartość 0. Jeśli litera i jest równa literze j, to len[i][j] = len[i − 1][j − 1] + 1: dopasowanie przedłuża to, co było przed nim. W przeciwnym razie len[i][j] jest większą z wartości len[i − 1][j] i len[i][j − 1]: pomijamy jedną z dwóch liter i zachowujemy lepszy wynik.

Przykład

Porównaj ABCBDAB z BDCABA. Pierwsza litera drugiego słowa, B, pasuje do B w wierszu 2; C w trzeciej kolumnie pasuje do wiersza 3 i tak dalej, a każde dopasowanie dodaje jeden do komórki na ukos w lewo w górę. Prawa dolna komórka kończy na 4. Odczyt wstecz od niej daje BCBA, ale BCAB i BDAB są równie długie: najdłuższy wspólny podciąg nie musi być jednoznaczny.

Odczytywanie odpowiedzi wstecz

Zacznij od prawej dolnej komórki. Jeśli litery jej wiersza i kolumny pasują, ta litera należy do odpowiedzi: zapisz ją i przejdź na ukos w lewo w górę. W przeciwnym razie przejdź do sąsiada, powyżej lub po lewej, o większej wartości, bo to od niego komórka wzięła swoją wartość. Zatrzymaj się na pierwszym wierszu lub pierwszej kolumnie. Zapisane litery w odwrotnej kolejności tworzą podciąg.

Historia i zastosowania

Metodę tabeli odkryło niezależnie kilka osób około 1970 roku, wśród nich Robert Wagner i Michael Fischer, których praca z 1974 roku rozwiązała blisko spokrewniony problem odległości edycyjnej. W 1975 roku Dan Hirschberg pokazał, jak znaleźć podciąg przy znacznie mniejszym zużyciu pamięci, a w 1976 roku James Hunt i Douglas McIlroy oparli program Unix diff na najdłuższych wspólnych podciągach wierszy. Biolodzy używają tej samej idei, z punktacją, do dopasowywania sekwencji DNA i białek.

Douglas McIlroy sfotografowany przez Petera Adamsa dla Faces of Open Source. W 1976 roku wraz z Jamesem Huntem oparł uniksowy program diff na najdłuższych wspólnych podciągach wierszy.
Douglas McIlroy sfotografowany przez Petera Adamsa dla Faces of Open Source. W 1976 roku wraz z Jamesem Huntem oparł uniksowy program diff na najdłuższych wspólnych podciągach wierszy.

Sprawdź sam

Otwórz aplikację i naciśnij Krok. Dwie porównywane litery podświetlają się w nagłówkach; przy dopasowaniu odczytywana jest niebieska komórka na ukos w lewo w górę, przy różnicy dwie niebieskie komórki powyżej i po lewej. Gdy tabela jest pełna, pomarańczowa ścieżka wspina się wstecz od rogu, a litery odpowiedzi pojawiają się pod tabelą.

Często zadawane pytania

Ile czasu i pamięci potrzebuje algorytm LCS?

Czas O(m·n) dla słów o długościach m i n. Pełna tabela wymaga też O(m·n) pamięci, aby odczytać odpowiedź wstecz; Dan Hirschberg pokazał w 1975 roku, jak znaleźć sam podciąg przy użyciu tylko O(min(m, n)) pamięci.

Jak diff wykorzystuje najdłuższy wspólny podciąg?

Traktuje każdy wiersz pliku jako jeden symbol i znajduje najdłuższy wspólny podciąg wierszy obu plików. Wiersze w tym podciągu się nie zmieniły; pozostałe wiersze starego pliku zostały usunięte, a pozostałe wiersze nowego pliku zostały dodane.

A co z trzema lub więcej słowami?

Tabela dostaje jeden wymiar na każde słowo, więc trzy słowa o długości n wymagają n³ komórek. Dla dowolnej liczby słów problem jest NP-trudny.

Jak LCS ma się do odległości edycyjnej?

Jeśli dozwolone są tylko wstawienia i usunięcia, odległość edycyjna dwóch słów to ich łączna długość minus podwojona długość ich najdłuższego wspólnego podciągu. Jeśli dopuścimy też zamiany, otrzymamy odległość Levenshteina, obliczaną za pomocą bardzo podobnej tabeli.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj najdłuższy wspólny podciąg