PL 
EnglishDomyślny
Українська📝 Odległość edycyjna — tablica DP Levenshteina
Wypełnij komórka po komórce tablicę programowania dynamicznego Levenshteina, a potem odtwórz najtańszą ścieżkę wstawień, usunięć i podstawień zamieniającą jeden napis w drugi.
O odległości edycyjnej (Levenshteina)
Odległość edycyjna, sformalizowana przez Władimira Lewensteina w 1965 roku, mierzy minimalną liczbę pojedynczych wstawień, usunięć i podstawień znaków wymaganych, by przekształcić jeden ciąg znaków w drugi. Jest obliczana w czasie O(mn) i pamięci O(mn) (lub O(min(m,n)) pamięci przy triku wiersz-po-wierszu) za pomocą programowania dynamicznego: wypełniania tabeli (m+1)×(n+1), gdzie każda komórka d[i][j] przechowuje odległość edycyjną między pierwszymi i znakami źródła a pierwszymi j znakami celu. Algorytm jest fundamentalny w sprawdzaniu pisowni, dopasowywaniu sekwencji DNA (gdzie podstawienia modelują mutacje) oraz w rozmytym dopasowywaniu ciągów w wyszukiwarkach.
Symulacja wypełnia tabelę PD komórka po komórce z regulowaną prędkością, kolorując każdą operację. Po ukończeniu wsteczne śledzenie podświetla optymalną ścieżkę dopasowania przez macierz, pokazując dokładnie, które wstawienia, usunięcia i podstawienia zostały wybrane.
Najczęściej zadawane pytania
Jaka jest relacja rekurencyjna używana do wypełnienia macierzy Levenshteina?
Każda komórka jest wypełniana jako: d[i][j] = d[i−1][j−1], jeśli s[i] = t[j] (znaki się zgadzają, brak kosztu); w przeciwnym razie d[i][j] = 1 + min(d[i−1][j], d[i][j−1], d[i−1][j−1]) odpowiednio dla usunięcia, wstawienia i podstawienia. Pierwszy wiersz i kolumna są inicjalizowane jako 0…m i 0…n, ponieważ przekształcenie pustego ciągu wymaga i wstawień lub j usunięć.
Jaka jest różnica między odległością edycyjną a odległością Hamminga?
Odległość Hamminga liczy tylko podstawienia między dwoma ciągami o równej długości. Odległość edycyjna jest ściśle bardziej ogólna: dopuszcza wstawienia i usunięcia, czyniąc ją stosowalną do ciągów o różnych długościach. Dla ciągów o równej długości bez indeli odległości Hamminga i Levenshteina są zgodne. Odległość Hamminga oblicza się w O(n), podczas gdy Levenshteina w O(mn), co odzwierciedla jej większą ekspresywność.
Jak odległość edycyjna wiąże się z najdłuższym wspólnym podciągiem (LCS)?
Jeśli dozwolone są tylko wstawienia i usunięcia (bez podstawień), to odległość edycyjna = m + n − 2·LCS(s, t): dwa dodatkowe znaki dla każdej dopasowanej pary w LCS znoszą jedno usunięcie i jedno wstawienie. Levenshtein dodaje podstawienia (koszt 1) jako skrót zastępujący usunięcie + wstawienie (koszt 2), gdy jest to korzystne. Tabele PD mają tę samą strukturę, różniącą się jedynie członem kosztu podstawienia.
Jak wsteczne śledzenie odzyskuje optymalne dopasowanie z tabeli PD?
Zaczynając od d[m][n], algorytm przechodzi do dowolnej komórki poprzedzającej (po przekątnej dla dopasowania/podstawienia, w lewo dla wstawienia, w górę dla usunięcia) o najmniejszej wartości. Remisy mogą być rozstrzygane arbitralnie; każdy wybór daje inne, ale równie optymalne dopasowanie. Sekwencja ruchów odczytana wstecz daje skrypt edycji (ciąg CIGAR w notacji bioinformatycznej).
Czym jest odległość Damerau-Levenshteina?
Odległość Damerau-Levenshteina dodaje transpozycję dwóch sąsiadujących znaków jako czwartą operację elementarną o koszcie 1. Jest to bardziej odpowiednie do modelowania błędów popełnianych przez ludzi podczas pisania, gdzie transpozycje odpowiadają za do 80% literówek. Jej obliczenie wymaga bardziej złożonego PD z O(|Σ|) dodatkowymi tablicami śledzącymi ostatnią pozycję wystąpienia każdego znaku, dając czas O(mn), ale z większą stałą.
Czy odległość edycyjną można obliczyć szybciej niż O(mn)?
Dla ogólnych ciągów najlepszy znany algorytm działa w O(mn/log n), wykorzystując równoległość na poziomie słowa (algorytm Maska-Patersona i warianty wektorów bitowych). Dla ciągów, które są „niemal równe” (odległość k ≪ n), istnieje algorytm Ukkonena O(kn), który wypełnia jedynie diagonalny pas o szerokości 2k+1 w macierzy. W praktyce warianty bit-równoległe są używane w narzędziach takich jak agrep i uniksowe narzędzie diff.
Jak odległość edycyjna jest wykorzystywana w bioinformatyce?
W dopasowywaniu sekwencji nukleotydy A, C, G, T stanowią alfabet, a macierz podstawień (np. BLOSUM62 dla białek) zastępuje jednolitą karę kosztu 1. Algorytm Smitha-Watermana to lokalny wariant odległości edycyjnej, który znajduje najwyżej ocenione dopasowane podsekwencje, ujawniając zachowane domeny funkcjonalne. Dopasowanie globalne używa algorytmu Needlemana-Wunscha, matematycznie identycznego z Levenshteinem przy afinicznych karach za przerwy.
Jaka jest odległość edycyjna między „kitten” a „sitting”?
Odległość edycyjna wynosi 3: podstaw 'k'→'s' (kitten→sitten), podstaw 'e'→'i' (sitten→sittin) i wstaw 'g' na końcu (sittin→sitting). Jest to klasyczny przykład podręcznikowy używany do ilustracji algorytmu, z tabelą PD 7×8 często pokazywaną na kursach algorytmów.
Jak sprawdzacze pisowni wykorzystują odległość edycyjną?
Sprawdzacz pisowni oblicza odległość edycyjną między błędnie napisanym słowem a każdym słowem w słowniku (lub przyciętej liście kandydatów z drzewa BK), a następnie sugeruje słowa w odległości 1 lub 2 jako poprawki. Drzewa BK wykorzystują nierówność trójkąta odległości edycyjnej, by przycinać wyszukiwanie w słowniku, redukując średnią liczbę porównań z O(|słownik|) do O(|słownik|0,2) w praktyce.
Czy odległość edycyjna spełnia nierówność trójkąta?
Tak — odległość edycyjna jest prawdziwą metryką: jest nieujemna, symetryczna, zerowa wtedy i tylko wtedy, gdy ciągi są identyczne, i spełnia d(s, u) ≤ d(s, t) + d(t, u). Ta własność metryczna umożliwia drzewom BK i VP indeksowanie ciągów dla szybkiego przybliżonego wyszukiwania najbliższego sąsiada, co leży u podstaw wyszukiwania podobieństwa w korekcji pisowni i bazach danych DNA.