Algorytm szybkiego dopasowywania ciągów niezgodności k

Szukam szybkiego algorytmu dopasowywania ciągów typu k-mismatch. Biorąc pod uwagę ciąg wzorca P o długości m i ciąg tekstowy T o długości n, potrzebuję szybkiego algorytmu (czas liniowy), aby znaleźć wszystkie pozycje, w których P pasuje do podłańcucha T z co najwyżej k niedopasowań. Różni się to od problemu różnic k (edycja odległości). Niedopasowanie oznacza podłańcuch, a wzór ma inną literę w co najwyżej k pozycjach. Naprawdę wymagam tylko k = 1 (maksymalnie 1 niedopasowanie), więc wystarczy szybki algorytm dla konkretnego przypadku k = 1. Rozmiar alfabetu to 26 (tekst angielski bez rozróżniania wielkości liter), więc zapotrzebowanie na miejsce nie powinno rosnąć zbyt szybko wraz z rozmiarem alfabetu (np. Algorytm FAAST, jak sądzę, zajmuje miejsce wykładniczo w wielkości alfabetu, i tak nadaje się tylko do sekwencji białkowych i genowych).

Podejście oparte na programowaniu dynamicznym będzie w najgorszym przypadku wynosić O (mn), co będzie zbyt wolne. Sądzę, że istnieją modyfikacje algorytmu Boyera-Moore'a, ale nie jestem w stanie zdobyć takich dokumentów. Nie mam abonamentu na dostęp do czasopism naukowych ani publikacji, więc wszelkie odniesienia będą musiały być własnością publiczną.

Byłbym bardzo wdzięczny za wszelkie wskazówki lub odniesienia do swobodnie dostępnych dokumentów lub samego algorytmu dla tego problemu.

W przypadku tego problemu można zastosować tablice sufiksów . Zawierają pozycje początkowe każdego sufiksu ciągu posortowane w kolejności leksykograficznej. Mimo że można je konstruować naiwnie ze złożonością , istnieją metody ich konstruowania ze złożonością Θ ( n ) . Zobacz na przykład to i to . Nazwijmy tę tablicę przyrostków SA.$O(n\log n)$$\Theta(n)$

Po zbudowaniu tablicy sufiksów musimy zbudować najdłuższą wspólną tablicę prefiksów (LCP) dla tablicy sufiksów. Tablica LCP przechowuje długość najdłuższego wspólnego przedrostka między dwoma kolejnymi przedrostkami w tablicy przyrostków (leksykograficzne kolejne przyrostki). Zatem LCP [i] zawiera długość najdłuższego wspólnego przedrostka między SA [i] i SA [i + 1]. Tę tablicę można również skonstruować w czasie liniowym: patrz tutaj , tutaj i tutaj, aby znaleźć dobre referencje.

Teraz, aby obliczyć długość najdłuższego prefiksu wspólnego dla dowolnych dwóch sufiksów w drzewie sufiksów (zamiast kolejnych sufiksów), musimy użyć struktury danych RMQ . W powyższych odnośnikach pokazano (i można to łatwo zobaczyć, jeśli tablica jest wizualizowana jako drzewo sufiksów), że długość najdłuższego wspólnego prefiksu między dwoma sufiksami mającymi pozycje i v ( u < v ) w tablicy sufiksów , można otrzymać jako m i n u < = k < = v - 1 L C P [ k $u$$v$$u < v$$min_{u<=k<=v-1}{LCP[k]}$. Dobra RMQ może wstępnie przetwarzać tablicę w czasie O ( n ) lub O ( n log n ) i odpowiadać na zapytania o formę L C P [ u , v ] w czasie O ( 1 ) . Zobacz tutaj, aby uzyskać pomocny algorytm RMQ, a tutaj dobry poradnik na temat RMQ oraz relacji (i redukcji) między LCA i RMQ. To ma inne miłe alternatywne podejście.$LCP$$O(n)$$O(n\log n)$$LCP[u, v]$$O(1)$

Na podstawie tych informacji konstruujemy tablicę sufiksów i powiązane tablice (jak opisano powyżej) do konkatenacji dwóch łańcuchów z separatorem pomiędzy nimi (takich jak T # P, gdzie „#” nie występuje w żadnym ciągu). Następnie możemy wykonać dopasowanie k niezgodnego ciągu znaków przy użyciu metody „kangur”. To i to wyjaśnia metodę kangura w kontekście drzewek sufiksów, ale może być również bezpośrednio stosowane do tablic sufiksów. Dla każdego indeksu tekstu T znajdź L C P sufiksu T rozpoczynającego się od i i sufiksu $i$$T$$LCP$$T$$i$$P$zaczynając od 0. Daje to lokalizację, po której następuje pierwsze niedopasowanie podczas dopasowywania do T [ i ] . Niech ta długość będzie l 0 . Pomiń niedopasowany znak w T i P i spróbuj dopasować pozostałe ciągi. Oznacza to, że ponownie znajdź L C P z T [ i + l 0 + 1 ] i P [ l 0 + 1 ] . Powtarzaj tę czynność, aż uzyskasz k niedopasowania lub którykolwiek z łańcuchów zakończy się. Każdy$P$$T[i]$$l_0$$T$$P$$LCP$$T[i + l_0 + 1]$$P[l_0 + 1]$$k$ oznacza O ( 1 ) . Istnieje O ( K ) l C P „S dla każdego indeksu i z T , co daje to całkowity złożoność O ( n- k ) .$LCP$$O(1)$$O(k)$ $LCP$$i$$T$$O(nk)$

$O(nk + (n+m)\log(n+m))$$O(nk + n\log n)$$m = O(n)$$O(nk)$

$\mathcal{O}(n + m )$$k$$\mathcal{O}(nk +m )$

Pomysł jest podobny do algorytmu toczenia hash Rabin-Karp dla dokładnych dopasowań podciągów.

$m$$2k$$m/2k$$2k$$2k$

$k$

$k$

Spodziewam się (zastrzeżenie: sam tego nie próbowałem) w praktyce będzie to prawdopodobnie szybsze i być może łatwiejsze do zakodowania / konserwacji, niż przy użyciu podejścia opartego na drzewie sufiksów.