Algorytm Rabin-Karp

1. Idea algorytmu

Rabin-Karp (1987) wykorzystuje hashing do szybkiego porównywania substringów.

1.1. Problem z algorytmem naiwnym:

Text:    ABCDEFGH
Pattern: DEF

Naiwny: Porównuje znak po znaku
  ABC vs DEF → A != D ✗
  BCD vs DEF → B != D ✗
  CDE vs DEF → C != D ✗
  DEF vs DEF → D == D, E == E, F == F ✓

Rabin-Karp: Porównuje HASH(substring) == HASH(pattern)
  HASH("ABC") vs HASH("DEF") → różne hasze ✗
  HASH("BCD") vs HASH("DEF") → różne hasze ✗
  HASH("CDE") vs HASH("DEF") → różne hasze ✗
  HASH("DEF") vs HASH("DEF") → te same hasze! ✓ → weryfikuj znak po znaku

Kluczowa idea: Hashing jest szybki O(1), gdy używamy rolling hash!

2. Rolling Hash (hash przesuwany)

2.1. Czym jest rolling hash?

Rolling hash to funkcja hashująca, która może być efektywnie aktualizowana przy przesuwaniu okna o jeden znak.

Text: ABCDEF

Hash("ABC") → oblicz od zera
Hash("BCD") → usuń 'A', dodaj 'D' (O(1)!)
Hash("CDE") → usuń 'B', dodaj 'E' (O(1)!)

2.2. Funkcja hash - polynomial rolling hash:

Dla stringa s = [c₀, c₁, c₂, ..., c_{m-1}]:

hash(s) = (c₀ × d^{m-1} + c₁ × d^{m-2} + ... + c_{m-1} × d^0) mod q

gdzie:
- d = baza (np. 256 dla ASCII)
- q = duża liczba pierwsza (unikanie kolizji)
- c_i = wartość znaku (np. ord(c_i))

2.3. Przykład:

3. Implementacja podstawowa

3.1. Prosty hash (bez rolling):

3.2. Algorytm Rabin-Karp bez rolling hash:

Problem: Obliczanie hasha każdego substringa to O(m) → razem O(n × m)!

4. Rolling Hash - efektywna aktualizacja

4.1. Formuła aktualizacji:

Mamy: hash(s[i:i+m])
Chcemy: hash(s[i+1:i+m+1])

Strategia:
1. Usuń pierwszy znak: s[i]
2. Dodaj nowy znak: s[i+m]

hash_new = (d × (hash_old - s[i] × d^{m-1}) + s[i+m]) mod q

4.2. Wizualizacja:

Text: ABCDEF
m = 3

hash("ABC") = 65×10² + 66×10¹ + 67×10⁰
            = 6500 + 660 + 67 = 7227

hash("BCD") = ?

Usuń 'A': 7227 - 65×10² = 7227 - 6500 = 727
Przesuń: 727 × 10 = 7270
Dodaj 'D': 7270 + 68 = 7338

hash("BCD") = 7338 (mod q)

5. Implementacja z rolling hash

Złożoność: - Preprocessing: O(m) - Rolling hash update: O(1) ✅ - Razem średnio: O(n + m) ✅

6. Wizualizacja działania

7. Obsługa kolizji

7.1. Problem kolizji:

7.2. Rozwiązanie:

7.3. Wybór parametrów:

8. Wyszukiwanie wielu wzorców

Rabin-Karp jest idealny do wyszukiwania WIELU wzorców jednocześnie!

Złożoność: O(n × k + m_total) - k = liczba wzorców - m_total = suma długości wzorców

9. Zastosowania praktyczne

9.1. Wykrywanie plagiatów:

9.2. Filtrowanie spamu:

10. Porównanie z innymi algorytmami

11. Optymalizacje

11.1. Używanie większej liczby pierwszej:

11.2. Double hashing:

12. Podsumowanie

Algorytm Rabin-Karp:

  • Używa hashingu do szybkiego porównywania
  • Rolling hash → aktualizacja O(1) ✅
  • Idealny dla wielu wzorców jednocześnie ✅
  • Wymaga weryfikacji (kolizje możliwe)

Złożoność:

Przypadek Złożoność Uwagi
Średni O(n + m) ✅ Mało kolizji
Najgorszy O(n × m) ❌ Wiele kolizji hash
Preprocessing O(m) Obliczanie hash wzorca
Pamięć O(1) Tylko zmienne

Rolling hash:

hash_new = (d × (hash_old - s[i] × d^{m-1}) + s[i+m]) mod q

Aktualizacja w O(1)! ✅

Implementacja podstawowa:

Zalety: - ✅ Średnio O(n + m) – efektywny - ✅ Wiele wzorców → bardzo szybki! ✅ - ✅ O(1) pamięci dodatkowej - ✅ Prosty koncept (hashing) - ✅ Rolling hash → elegancka optymalizacja

Wady: - ❌ Wymaga weryfikacji (kolizje) - ❌ Najgorszy przypadek O(n × m) - ❌ Wrażliwy na dobór parametrów (d, q) - ❌ Dla jednego wzorca KMP często lepszy

Kiedy używać Rabin-Karp:

✅ Wiele wzorców jednocześnie (główna siła!) ✅ Wykrywanie plagiatów (porównywanie dokumentów) ✅ Filtrowanie spamu (wiele słów kluczowych) ✅ DNA sequencing (wiele sekwencji) ✅ Prostota – łatwiejszy niż KMP/Boyer-Moore

❌ Jeden wzorzec → KMP/Boyer-Moore lepsze ❌ Gwarancja O(n+m) → KMP ❌ Krytyczne aplikacje (kolizje niedopuszczalne)

Porównanie algorytmów:

Algorytm Średni Najgorszy Wiele wzorców Prostota
Naiwny O(n) O(n×m) ❌ ✅✅✅
KMP O(n+m) O(n+m) ✅ ❌ ✅✅
Rabin-Karp O(n+m) O(n×m) ✅✅✅ ✅✅
Boyer-Moore O(n/m) ✅ O(n×m) ❌ ✅

Kluczowa obserwacja:

Rabin-Karp świeci przy WIELU wzorcach:

Szukanie 1 wzorca:
- KMP: O(n + m)
- Rabin-Karp: O(n + m)
Podobne!

Szukanie k wzorców:
- KMP: O(k × (n + m)) ← k razy wolniej!
- Rabin-Karp: O(n + m_total) ← prawie bez narzutu! ✅

Zastosowania w praktyce:

  • Wykrywanie plagiatów (document comparison)
  • Spam filtering (multiple keywords)
  • Intrusion detection (network signatures)
  • DNA sequence matching (bioinformatics)
  • File deduplication (content-defined chunking)

Co dalej warto poznać:

  • Boyer-Moore – najszybszy dla długich wzorców
  • Aho-Corasick – optymalizacja dla wielu wzorców (automat)
  • Suffix Array/Tree – preprocessing tekstu zamiast wzorca
  • Content-Defined Chunking – zastosowanie w deduplikacji
  • Bloom Filters – probabilistyczne wyszukiwanie
Wróć do spisu lekcji