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

10

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.

Paresh
źródło
2
Jeśli wzorzec jest ustalony (ale dopasowany tekst jest różny), możesz potencjalnie utworzyć automat skończony i przepuścić przez niego tekst. Istnieją również algorytmy wykorzystujące drzewa sufiksów (zwykle dobre, jeśli tekst jest stały, a wzór różni się, ale można je również stosować, jeśli oba się różnią), może być w stanie znaleźć pewne odniesienia w Internecie. (Jeszcze nie dodałem odpowiedzi, ponieważ nie jestem pewien algorytmów opartych na drzewie sufiksów, jeśli ktoś wie, możesz zignorować ten komentarz).
Aryabhata
@Aryabhata Thanks! Zmienia się zarówno wzór, jak i tekst. W tym kontekście zbudowanie automatu skończonego byłoby zbyt kosztowne, zwłaszcza gdy uwzględniono by zakres niedopasowania 1. Jeśli chodzi o drzewa sufiksów / tablice sufiksów, nigdy ich nie używałem i niewiele o nich wiem, ale miałem wrażenie, że są one powolne w budowie i wydajne głównie w celu dokładnego dopasowania. Ale zbadam tę opcję dalej. Wszelkie wskazówki w tym kierunku lub w innym kierunku byłyby najbardziej przydatne!
Paresh,
1
Nie, drzewa sufiksów mogą być również używane do przybliżonych dopasowań. Przynajmniej wiki twierdzi, więc: en.wikipedia.org/wiki/Suffix_tree
Aryabhata

Odpowiedzi:

5

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(nlogn)Θ(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 ]uvu<vminu<=k<=v1LCP[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.LCPO(n)O(nlogn)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 PiTLCPTiPzaczynają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żdyPT[i]l0TPLCPT[i+l0+1]P[l0+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 ) .LCPO(1)O(k) LCPiTO(nk)

O(nk+(n+m)log(n+m))O(nk+nlogn)m=O(n)O(nk)

Paresh
źródło
Świetny! Mam teraz trochę lektury na mojej liście DO ZROBIENIA :-)
Aryabhata
Link siam.org w drugim akapicie jest zepsuty, ale link do papieru można znaleźć tutaj epubs.siam.org/doi/pdf/10.1137/1.9781611972917.3
leecbaker
4

O(n+m)kO(nk+m)

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

m2km/2k2k2k

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.

Aryabhata
źródło
Potrzebuję tylko wyjaśnienia. Przez „.. rozdziel każdy ciąg długości m na 2k bloków o rozmiarze m / 2k każdy ...”, masz na myśli to, że każdy podciąg długości mw T (o długości n) dzieli się na 2k bloków. Ten skrót można obliczyć w O (n) metodą mieszania ciągłego. Następnie łańcuch wzoru zostanie również podzielony na bloki 2k, a odpowiednie hasze zostaną porównane, z uwzględnieniem niedopasowania bloków k atmost. Jeśli tak, to moglibyśmy potencjalnie odrzucić wszystkie przypadki, w których liczba niezgodności jest większa niż k. Czy zrozumiałem, prawda?
Paresh
kΩ(nk)O(n)
Podoba mi się to podejście! Jednak to podejście jest ogólnie szybkie, ale obniża się do O (mnk), jeśli liczba dopasowań jest wysoka (O (n) dopasowań). Mając to na uwadze, utrzymałem dwa ciągłe hashe, przy założeniu, że oba nie mogą mieć kolizji dla tego samego wkładu (nie zrobiłem tego matematycznie, ponieważ chciałem zobaczyć prędkość). W ten sposób nie musimy weryfikować dopasowania char-by-char, jeśli oba skróty się zgadzają. Zasadniczo jest to dość szybkie, ale to też jest powolne, jeśli liczba dopasowań jest duża. Z tym i zgodnie ze wskazówkami, dla dużych meczów było wolno.
Paresh
mm/2kmO(nkm)
mm/2k2kk+1k+cΩ(nm)mm/2k