Używanie Rabin-Karp do wyszukiwania wielu wzorców w łańcuchu

Question

Zgodnie z wikipedia entry algorytmu dopasowywania ciągów Rabina-Karpa, można go wykorzystać do wyszukiwania kilku różnych wzorów w ciągu jednocześnie zachowując liniową złożoność. Oczywiste jest, że łatwo to zrobić, gdy wszystkie wzory mają tę samą długość, ale nadal nie rozumiem, jak zachować złożoność O (n) przy jednoczesnym wyszukiwaniu wzorów o różnej długości. Czy ktoś może rzucić trochę światła na to?

Edit (grudzień 2011):

artykułu z Wikipedii został już zaktualizowany i nie twierdzi, że pasuje do wielu modeli o różnej długości w czasie O (n).

Answer 1

Nie jestem pewien, czy to jest poprawna odpowiedź, ale tak czy owak:

Podczas konstruowania wartość hash, możemy sprawdzić na mecz w zestawie skrótów smyczkowych. Wartość mieszania Aka, bieżącego. Funkcja/kod skrótu jest zwykle zaimplementowana jako pętla, a wewnątrz tej pętli możemy wstawić naszą szybką wyszukiwarkę.
Oczywiście, musimy wybrać m, aby uzyskać maksymalną długość ciągu ze zbioru ciągów.

Aktualizacja: Z Wikipedii,

[...] 
for i from 1 to n-m+1 
     if hs ∈ hsubs 
      if s[i..i+m-1] = a substring with hash hs 
       return i 
     hs := hash(s[i+1..i+m]) // <---- calculating current hash 
[...] 

Obliczamy aktualny hash w m krokach. Na każdym kroku znajduje się wartość mieszania, którą możemy sprawdzić (złożoność O (1)) w zestawie skrótów. Wszystkie skróty będą miały ten sam rozmiar, tj. 32-bitowy.

Aktualizacja 2: zamortyzowany (średnia) O (n) Złożoność?
Powyżej powiedziałem, że m musi mieć maksymalną długość ciągu. Okazuje się, że możemy wykorzystać przeciwieństwo.
Z hashing for shifting substring search i stałym rozmiarem m możemy uzyskać złożoność O (n).
Jeśli posiadamy łańcuchy o zmiennej długości, możemy ustawić m na minimalną długość ciągu znaków. Dodatkowo w zestawie skrótów nie łączymy hasha z całym ciągiem znaków, ale z pierwszymi znakami m temu.
Teraz podczas przeszukiwania tekstu sprawdzamy, czy aktualny hash znajduje się w zestawie skrótów i sprawdzamy powiązane łańcuchy dla dopasowania.

Ta technika zwiększy liczbę fałszywych alarmów, ale średnio ma złożoność O (n).

Answer 2

Dzieje się tak dlatego, że wartości skrótów podciąganych są matematycznie powiązane. Obliczanie mieszania H (S, j) (hash postaci począwszy od położenia j łańcucha S) wykonuje O (m) czasu na sznurku o długości m. Ale gdy już to zrobisz, możesz wykonać obliczenia w stałym czasie, ponieważ H (S, j + 1) może być wyrażone jako funkcja H (S, j) .

O (m) + O (1) => O (m), tj. Czas liniowy.

Here's a link gdzie to jest opisane bardziej szczegółowo (patrz np sekcja „Co sprawia, że ​​Rabin-Karp szybko?”)