Dystans Edytowy: Macierz Programowania Dynamicznego Levenschteina

Definicja "jak różnią się" dwie ciągi znaków

Długość Levenshteina między dwoma ciągami znaków to minimalna liczba pojedynczych operacji wstawienia, usunięcia i zamiany znaków potrzebnych do przekształcenia jednego w drugi. Daje to odległość 3 dla sekwencji "kitten" → "sitting": zamień k→s, zamień e→i, wstaw g. Nie istnieje bardziej sprytna sekwencja edycji, która zrobi to w mniej niż 3 kroków, a tabela DP jest tego dowodem.

Powtórzenie

Niech dp[i][j] oznacza odległość edycji między pierwszymi i j znakami ciągu A i pierwszymi i j znakami ciągu B. Każda komórka musi jedynie rozważyć trzy możliwe ostatnie ruchy — wstawienie, usunięcie lub dopasowanie/zamianę końcowych znaków:

dp[0][j] = j // j wstawień do zbudowania B z pustego A dp[i][0] = i // i usunięć do zmniejszenia A do pustego dp[i][j] = dp[i-1][j-1] jeśli A[i] == B[j] (dopasowanie bez kosztu) dp[i][j] = 1 + min( dp[i-1][j], // usunięcie A[i] dp[i][j-1], // wstawienie B[j] dp[i-1][j-1] // zamiana A[i] -> B[j] ) jeśli A[i] != B[j] Wypełnianie siatki wiersz po wierszu (lub kolumna po kolumnie), każda komórka jest pracą O(1) przy uwzględnieniu, że jej trzech sąsiadów już znamy, więc cała tabela (n+1)×(m+1) wypełnia się w czasie O(nm) i, w naiwnej wersji, zajmuje przestrzeń O(nm). Ostateczna odpowiedź znajduje się w prawym dolnym rogu, dp[n][m].

dp[0][j] = j                         // j inserts to build B from empty A
dp[i][0] = i                         // i deletes to reduce A to empty

dp[i][j] = dp[i-1][j-1]                          if A[i] == B[j]   (free match)
dp[i][j] = 1 + min(
             dp[i-1][j],      // delete A[i]
             dp[i][j-1],      // insert B[j]
             dp[i-1][j-1]     // substitute A[i] -> B[j]
           )                                     if A[i] != B[j]

Śledzenie powrotnej ścieżki dopasowania

Liczba dp[n][m] sama w sobie jedynie mówi Ci, ile edycji jest potrzebnych, a nie jakie. Aby odzyskać rzeczywistą sekwencję, należy iść wstecz od komórki narożnej z dołu prawego: w każdej komórce sprawdź, skąd mogła pochodzić pod kątem rekurencji (do do 3 sąsiednich komórek), i przejdź do tej, która pasuje — krok po przekątnej to dopasowanie lub zamiana, krok w górę to usunięcie, a krok w lewo to wstawienie. Śledzona ścieżka jest dokładnie tym, co pokazuje narzędzie diff jako sekwencję niezmienionych, dodanych i usuniętych znaków.

Oszczędzanie pamięci: algorytm Hirschberga

Ponieważ każdy wiersz tabeli DP zależy wyłącznie od wiersza powyżej, obliczenie wartości dp[n][m] wymaga jedynie O(min(n, m)) przestrzeni – zachowujemy dwa wiersze i eliminujemy resztę. Przywracanie ułożenia normalnie wydaje się wymagać przechowywania całej tabeli do celów backtrackingowych, ale algorytm Hirschberga (1975) to omija: uruchamia on równolegle tylko wierszowy forward pass z A’s startu i tylko wierszowy backward pass z A’’s endu, znajduje kolumnę, w której oba półrozwiązania optymalnie się spotykają, dzieli problem tam i rekursywnie działa na każdej połowie. Rezultatem jest pełne ułożenie w tym samym czasie O(nm), ale tylko w przestrzeni O(n+m) – standardowa technika ułożenia milionowych sekwencji genomicznych, dla których tabela O(nm) nie zmieściłaby się w pamięci.

Gdzie się pojawia

Sprawdzanie pisowni polega na wykorzystywaniu odległości edycyjnych do oceniania kandydatury poprawek, w oparciu o to, ile poprawek różni je od słowa z literówką. Narzędzia wiersze polegające na komendach i systemy kontroli wersji używają blisko spokrewnionego algorytmu najdłuższej wspólnej podciągu DP do obliczania różnic. Bioinformatyka wykorzystuje warianty o ważności - algorytmy Needleman-Wunsch (globalny) i Smith-Waterman (lokalny), gdzie koszty substytucji pochodzą z macierzy punktów, odzwierciedlającej jak biologicznie podobne są dwa aminokwasy lub nukleotydy, a przerwanie (wstawienie/usunięcie) zazwyczaj kosztuje więcej do otwarcia niż do rozszerzenia.

Frequently asked questions

Wypróbuj na żywo

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