Algorytm Boyer-Moore

1. Przełom w wyszukiwaniu wzorców

Boyer-Moore (1977) to rewolucyjny algorytm, który często jest najszybszy w praktyce dla długich wzorców.

1.1. Kluczowa innowacja:

Skanuje wzorzec OD KOŃCA!

Algorytmy naiwny, KMP, Rabin-Karp:
Text:    ABCDEFGH
Pattern: DEF
         →→→ (od lewej do prawej)

Boyer-Moore:
Text:    ABCDEFGH
Pattern: DEF
         ←←← (od prawej do lewej!)

Po co? Gdy znajdziemy niezgodność, możemy przeskoczyć wiele pozycji!

2. Idea algorytmu

2.1. Przykład:

Text:    WHICH FINALLY HALTS AT THIS POINT
Pattern: AT THIS

Pozycja 0:
WHICH FINALLY HALTS AT THIS POINT
AT THIS
      ↑ Sprawdź od końca: 'H' != 'S'

'H' nie występuje w wzorcu → przesuń o całą długość wzorca!

WHICH FINALLY HALTS AT THIS POINT
       AT THIS  ← Przeskocz 7 pozycji!

Może przeskoczyć O(m) pozycji zamiast tylko 1! ✅

3. Dwie heurystyki

Boyer-Moore używa dwóch heurystyk do określenia, o ile przesunąć wzorzec:

3.1. Bad Character Rule (reguła złego znaku)

Gdy znajdziemy niezgodność, sprawdź: - Czy niezgodny znak z tekstu występuje we wzorcu? - Jeśli TAK → wyrównaj wzorzec do tego znaku - Jeśli NIE → przesuń wzorzec za ten znak

Text:    ...XYZ...
Pattern: ABC
           ↑ Niezgodność: Z != C

Czy 'Z' występuje w "ABC"? NIE
→ Przesuń wzorzec za 'Z'

...XYZ...
      ABC  ← Przeskocz całe "ABC"

3.2. Good Suffix Rule (reguła dobrego sufiksu)

Gdy znajdziemy niezgodność, ale już dopasowaliśmy sufiks: - Znajdź najbliższe wystąpienie tego sufiksu we wzorcu - Wyrównaj wzorzec do tego wystąpienia

Pattern: ABCXXABC
Text:    ...XXXABC...
            ✗✓✓✓✓✓ (dopasowaliśmy "ABC", niezgodność na X)

Sufiks "ABC" występuje wcześniej w wzorcu
→ Wyrównaj do tego wystąpienia

4. Bad Character Table (preprocessing)

4.1. Tablica przesunięć:

Dla każdego znaku w alfabecie: o ile przesunąć wzorzec, gdy ten znak powoduje niezgodność.

4.2. Użycie Bad Character:

5. Implementacja uproszczona (tylko Bad Character)

Złożoność: - Preprocessing: O(m + σ), gdzie σ = rozmiar alfabetu - Wyszukiwanie średnio: O(n/m) ✅ – może pominąć znaki! - Najgorszy: O(n × m)

6. Wizualizacja działania

Przykładowy wynik:

Text:    ABCDEFGH
Pattern: DEF

Bad Character Table: {'D': 0, 'E': 1, 'F': 2}

Iteracja 1: i=0
Text:    ABCDEFGH
Pattern: DEF
  ✗ Niezgodność: text[2]='C' != pattern[2]='F'
  'C' NIE występuje w wzorcu
  Przesunięcie: 2 + 1 = 3

Iteracja 2: i=3
Text:    ABCDEFGH
Pattern:    DEF
  ✓ ZNALEZIONO na pozycji 3!

7. Good Suffix Table (zaawansowane)

7.1. Idea:

Gdy dopasowaliśmy sufiks, ale jest niezgodność wcześniej:

Pattern: ABCXXABC
         ✗✓✓✓✓✓✓✓

Dopasowany sufiks: "ABC"
Szukamy: Gdzie jeszcze "ABC" występuje w wzorcu?

7.2. Preprocessing (koncepcyjnie):

Uwaga: Pełna implementacja Good Suffix jest złożona. W praktyce często używa się tylko Bad Character.

8. Porównanie z innymi algorytmami

8.1. Benchmark:

8.2. Średnia liczba porównań:

Dla losowych danych:
- Naiwny: ~n porównań
- KMP: ~n porównań
- Boyer-Moore: ~n/m porównań ✅

Przykład: n=1000, m=10
- Naiwny/KMP: ~1000 porównań
- Boyer-Moore: ~100 porównań (10x mniej!)

9. Najgorszy przypadek Boyer-Moore

10. Zastosowania Boyer-Moore

10.1. Wyszukiwanie w edytorach tekstu:

10.2. Grep (Unix):

10.3. Antywirusy:

11. Optymalizacje i warianty

11.1. Horspool Algorithm:

Uproszczenie Boyer-Moore – używa tylko Bad Character, ale z małą modyfikacją:

Prostszy i często tak samo szybki!

11.2. Boyer-Moore-Horspool:

Hybrydowa wersja łącząca zalety obu.

12. Kiedy Boyer-Moore świeci?

✅ Używaj Boyer-Moore gdy:

  1. Długie wzorce (m > 10)
  2. Duże alfabety (ASCII, Unicode)
  3. Losowe dane (średnio O(n/m))
  4. Wielokrotne wyszukiwania (ten sam wzorzec)

❌ NIE używaj gdy:

  1. Krótkie wzorce (m < 5) – naiwny wystarczy
  2. Małe alfabety (DNA: A,C,G,T) – KMP lepszy
  3. Wiele wzorców – Rabin-Karp lepszy
  4. Gwarancja O(n+m) – KMP bezpieczniejszy

13. Podsumowanie

Algorytm Boyer-Moore:

  • Skanuje wzorzec OD KOŃCA ✅
  • Używa dwóch heurystyk: Bad Character + Good Suffix
  • Może przeskakiwać wiele pozycji
  • Najszybszy w praktyce dla długich wzorców ✅

Złożoność:

Przypadek Złożoność Uwagi
Średni O(n/m) ✅ Może pominąć znaki!
Najlepszy O(n/m) Wzorzec nie występuje
Najgorszy O(n × m) ❌ Powtarzające się znaki
Preprocessing O(m + σ) σ = rozmiar alfabetu
Pamięć O(m + σ) Bad Char + Good Suffix

Bad Character Table:

Implementacja uproszczona:

Zalety: - ✅ O(n/m) średnio – najszybszy praktycznie! ✅ - ✅ Może przeskakiwać znaki (nie sprawdza wszystkich) - ✅ Świetny dla długich wzorców - ✅ Efektywny dla dużych alfabetów - ✅ Używany w praktyce (grep, edytory)

Wady: - ❌ Skomplikowany (pełna wersja z Good Suffix) - ❌ O(n × m) w najgorszym przypadku - ❌ Wymaga preprocessingu (Bad Char + Good Suffix) - ❌ Dla małych alfabetów może być wolniejszy od KMP

Porównanie algorytmów:

Algorytm Średni Najgorszy Prostota Praktyka
Naiwny O(n) O(n×m) ✅✅✅ Wolny
KMP O(n+m) O(n+m) ✅ ✅✅ Średni
Rabin-Karp O(n+m) O(n×m) ✅✅ Wielokrotny
Boyer-Moore O(n/m) ✅ O(n×m) ✅ Najszybszy ✅

Kluczowa obserwacja:

Boyer-Moore skanuje OD KOŃCA:

Text:    ...XYZ...
Pattern: ABC
           ↑ Sprawdź ostatni znak najpierw!

Jeśli ostatni znak nie pasuje:
  → Może przeskoczyć CAŁE "ABC"!

Text:    ...XYZ...
Pattern:       ABC ← Przeskok!

Średnio pomija n/m znaków! ✅

Zastosowania w praktyce:

  • grep (Unix/Linux) – wyszukiwanie w plikach
  • Edytory (Vim, Emacs) – Ctrl+F
  • Antywirusy – wyszukiwanie sygnatur
  • Intrusion Detection – network packets
  • Text editors – Find & Replace

Co dalej warto poznać:

  • Horspool Algorithm – uproszczenie Boyer-Moore
  • Turbo-Boyer-Moore – optymalizacja dla najgorszego przypadku
  • Galil's Rule – unikanie O(n × m)
  • Aho-Corasick – wiele wzorców (automat)
  • Suffix Array/Tree – preprocessing tekstu
Wróć do spisu lekcji