Rabin-Karp: Wyszukiwanie Tekstu z Użyciem Przelicznikowego Słownika

Porównywanie liczb zamiast znaków

Najprostszym sposobem na znalezienie wzorca o długości m w tekście o długości n jest próba każdej pozycji początkowej i porównywanie znak po znaku: O(n*m) w najgorszym przypadku. Sztuczka Rabinowa i Karp z 1987 roku polega na sparsowaniu wzorca raz i sparsowaniu każdego okna o długości m tekstu, a następnie porównywaniu tanich liczb zamiast drogich ciągów znaków. Dwa okna mogą być tylko potencjalnie równe, jeśli ich hasze są równe, więc prawie każda pozycja jest eliminowana dzięki pojedynczej porovnaniu liczb.

Własny sumowy hash

Hash traktuje ciąg znaków jako cyfry w jakimś oparciu b, zredukowane modulo liczbę pierwszą q, aby zmieściło się w słowie maszyny:

H(s0 s1 ... s(m-1)) = ( s0*b^(m-1) + s1*b^(m-2) + ... + s(m-1) ) mod q To dokładnie jak byś obliczył wartość dziesiętną ciągu cyfr, tylko w oparciu b z użyciem znaków jako wartości cyfrowych i wszystko spakowane modulo q, aby liczby nigdy nie przekroczyły.

H(s0 s1 ... s(m-1)) = ( s0*b^(m-1) + s1*b^(m-2) + ... + s(m-1) ) mod q

Przesuwanie okna w czasie O(1)

Wybierzono formę wielomianową, aby precyzyjnie określić sposób inkrementalnego aktualizowania hasha okna zamiast ponownego obliczania go od zera. Przesuwanie okna o jeden znak w prawo usuwa wkład pierwszego znaku na lewo, przesuwa wszystkie pozostałe znaki o jedno miejsce w górę i dodaje nowy znak na końcu:

text[i..i+m-1] -> text[i+1..i+m], b^(m-1) obliczane raz z góry h = ( (h - text[i] * bPow) * b + text[i + m] ) mod q; if (h < 0) h += q; // utrzymujemy resztę nieujemną

Tylko jedno mnożenie, jedno odejmowanie, jedna dodawanie i jedno modulo – to samo stałe koszty niezależnie od tego, jak długi jest wzorzec. To właśnie jest główny powód istnienia algorytmu Rabin-Karp: naiwne ponowne haszowanie każdego okna kosztowałoby O(m) na przesunięcie, co zniweczyłoby korzyści płynące z haszowania.

// text[i..i+m-1] -> text[i+1..i+m], b^(m-1) precomputed once
h = ( (h - text[i] * bPow) * b + text[i + m] ) mod q;
if (h < 0) h += q;   // keep the remainder non-negative

Podstawa, moduł i kolizje, które nie ustępują

Zgodność z funkcją hash to jedynie kandydat, nigdy dowód. Różne ciągi znaków mogą uderzyć w ten sam wynik modulo q, więc każda rzeczywista implementacja zawsze weryfikuje trafienie znaku haszowego przez przejście na znak po znaku przeciwko wzorowi przed zgłoszeniem dopasowania - fałszywe pozytywy, które przebiegają, są wystarczająco rzadkie, aby ten krok weryfikacji prawie nic nie kosztował średnio. Wybór q jako dużego liczby pierwszej i b wartości niezwiązanej z rozmiarem alfabetu (lub losowanie b w czasie wykonywania) zapobiega konstruowaniu przez przeciwnika tekstu, który celowo uderza w ten sam sposób - użycie dwóch niezależnych funkcji hash równolegle czyni przypadkowe kolizje pomijalnie niskimi.

Średni czas O(n+m), w najgorszym przypadku O(n*m)

Przy dobrym rozproszeniu, prawie każde okno ma inny hash niż wzorzec, więc średni czas wykonania wynosi O(n + m): jeden przejazd do haszowania tekstu i kilka operacji O(m) na rzadkich, prawdziwych i fałszywych dopasowaniach. W najgorszym przypadku nadal wynosi O(n*m), co wystąpi jedynie wtedy, gdy przeciwnik wymusza masowe kolizje – dlatego algorytmy takie jak Knuth-Morris Pratt lub Z-algorytm, które w najgorszym przypadku mają czas O(n+m) bez wykorzystania losowości, są preferowane, gdy gwarancja jest ważniejsza niż prostota. Zaleta Rabina-Karp pokazuje się gdzie indziej: ponieważ dwa hasze o tej samej długości zawsze można bezpośrednio porównać, doskonale uogólnia się na wyszukiwanie wielu wzorców jednocześnie poprzez haszowanie ich wszystkich do zestawu do wyszukiwania.

Poza wyszukiwaniem tekstu

Ten sam hash opartej na okienku przesuwnym leży u podstaw narzędzi znacznie poza dopasowywaniem ciągów znaków. Detektory plagiatów i duplikatów treści hasują nakładające się k-gramy dokumentu, aby stworzyć tanie odcisk palców. Podział opartej na definicjach zawartości w rsync oraz systemach backupowych z redundancją wykorzystuje wahający się hash do określania granic fragmentów, tak że wstawienie bajtu na początku pliku nie przesuwa wszystkich granic fragmentów – zmieniają się tylko dotknięte fragmenty. Każde miejsce, w którym potrzebujesz wykryć ruchomy wzorzec w strumieniu bez ponownego skanowania wszystkiego od zera, jest kandydatem do tej samej sztuczki.

Frequently asked questions

Wypróbuj na żywo

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