Na czym polega algorytm boyera i Moore a?

W świecie cyfrowym, gdzie ogromne ilości danych przepływają z prędkością światła, efektywne wyszukiwanie informacji jest kluczowe. Czy zastanawiałeś się kiedyś, jak szybko Twoja przeglądarka znajduje konkretne słowo na stronie, albo jak edytor tekstu błyskawicznie lokalizuje i zamienia frazy w obszernym dokumencie? Za tymi procesami często stoją sprytne algorytmy, a jednym z najbardziej efektywnych w dziedzinie wyszukiwania wzorców jest algorytm Boyera-Moore’a. Poznajmy jego fascynujące zasady działania, które pozwalają mu na błyskawiczne znajdowanie szukanych tekstów.

Wprowadzenie do wyszukiwania wzorców

Zanim zagłębimy się w szczegóły, wyjaśnijmy, czym jest wyszukiwanie wzorców. To proces polegający na znalezieniu wszystkich wystąpień danego wzorca (krótszego ciągu znaków) w dłuższym tekście. Wyobraź sobie, że masz książkę (tekst) i chcesz znaleźć w niej konkretne słowo (wzorzec). Najprostsze podejście, zwane naiwnym wyszukiwaniem, polega na porównywaniu wzorca z tekstem znak po znaku, przesuwając wzorzec o jedną pozycję, jeśli nie ma dopasowania. Jest to skuteczne, ale często bardzo powolne, zwłaszcza przy długich tekstach i wzorcach.

Czym wyróżnia się algorytm Boyera-Moore’a?

Algorytm Boyera-Moore’a, opracowany w 1977 roku przez Roberta S. Boyera i J. Strothera Moore’a, to jeden z najszybszych algorytmów wyszukiwania wzorców. Jego innowacyjność polega na dwóch kluczowych cechach:

• Porównuje wzorzec z tekstem od prawej do lewej.
• Potrafi wykonywać duże skoki w tekście, zamiast przesuwać się o jedną pozycję, co znacznie przyspiesza proces.

Te skoki są możliwe dzięki dwóm sprytnym heurystykom, które analizują niezgodności i pozwalają przewidzieć, o ile można bezpiecznie przesunąć wzorzec.

Reguła złego znaku (Bad Character Rule)

Ta reguła wykorzystuje informację o znaku w tekście, który nie pasuje do wzorca. Gdy algorytm natrafi na niezgodność, patrzy na "zły znak" w tekście i szuka jego ostatniego wystąpienia we wzorcu. Jeśli nie znajdzie tego znaku we wzorcu, przesuwa wzorzec o całą jego długość. Jeśli znajdzie, przesuwa wzorzec tak, aby ten "zły znak" w tekście zrównał się z jego ostatnim wystąpieniem we wzorcu.

Przykład:

Szukamy wzorca: ABC

Tekst: ABXABC

1. Początkowe ustawienie: ABXABC ABC
2. Porównujemy od prawej do lewej: C (tekst) vs C (wzorzec) - pasuje B (tekst) vs B (wzorzec) - pasuje X (tekst) vs A (wzorzec) - nie pasuje! X to "zły znak".
3. Sprawdzamy, czy X występuje we wzorcu ABC. Nie występuje.
4. Przesuwamy wzorzec o całą jego długość (3 pozycje): ABXABC ABC

Gdyby "zły znak" np. B wystąpił we wzorcu, wzorzec zostałby przesunięty tak, aby B z tekstu zrównało się z ostatnim B ze wzorca.

Reguła dobrego sufiksu (Good Suffix Rule)

Ta reguła jest nieco bardziej złożona, ale bardzo potężna. Zaczyna działać, gdy algorytm znajdzie dopasowanie części wzorca (sufiksu) w tekście, ale dalsze porównanie (na lewo) prowadzi do niezgodności.

Jeśli dopasowany sufiks S został znaleziony, a następny znak (na lewo od S) nie pasuje, algorytm szuka w pozostałej części wzorca (na lewo od S) innego wystąpienia sufiksu S lub jego prefiksu, który jest również sufiksem wzorca. Wzorzec jest przesuwany tak, aby to nowe wystąpienie zrównało się z dopasowanym sufiksem w tekście.

Przykład:

Szukamy wzorca: ABCABC

Tekst: ...ABCABXABC...

1. Początkowe ustawienie: ...ABCABXABC... ABCABC
2. Porównujemy od prawej do lewej: C (tekst) vs C (wzorzec) - pasuje B (tekst) vs B (wzorzec) - pasuje A (tekst) vs A (wzorzec) - pasuje Mamy "dobry sufiks" ABC.
3. Następnie X (tekst) vs C (wzorzec) - nie pasuje!
4. Algorytm szuka innego wystąpienia sufiksu ABC we wzorcu ABCABC. Znajduje je na początku.
5. Przesuwamy wzorzec tak, aby początkowe ABC wzorca zrównało się z dopasowanym sufiksem ABC w tekście: ...ABCABXABC... ABCABC (przesunięcie o 3 pozycje)

To pozwala na znaczne "przeskoczenie" potencjalnych pozycji.

Jak działają razem?

W praktyce algorytm Boyera-Moore’a wykorzystuje obie heurystyki jednocześnie. Kiedy dochodzi do niezgodności, oblicza przesunięcie zarówno na podstawie reguły złego znaku, jak i reguły dobrego sufiksu. Następnie wybiera większe z tych dwóch przesunięć. To właśnie ta strategia maksymalizacji przesunięcia sprawia, że algorytm jest tak niezwykle wydajny.

Zalety i zastosowania

Główną zaletą algorytmu Boyera-Moore’a jest jego wysoka wydajność. W najlepszym przypadku (gdy wzorzec nie występuje w tekście, a heurystyki pozwalają na duże skoki) złożoność czasowa może być podliniowa, co oznacza, że algorytm nie musi nawet przeglądać wszystkich znaków tekstu! W najgorszym przypadku jego złożoność to O(m+n), gdzie m to długość wzorca, a n to długość tekstu – co jest również bardzo dobre.

Jest szeroko stosowany w:

• Edytorach tekstu (funkcje "znajdź i zamień").
• Przeglądarkach internetowych (wyszukiwanie tekstu na stronie).
• Systemach antywirusowych (identyfikacja sygnatur wirusów w plikach).
• Systemach wykrywania intruzów (IDS/IPS) do analizy ruchu sieciowego.
• Narzędziach do przeszukiwania plików (np. grep w systemach Unix/Linux).

Ciekawostki

• Algorytm Boyera-Moore’a jest często uznawany za punkt odniesienia dla innych algorytmów wyszukiwania wzorców ze względu na swoją wydajność.
• Istnieją jego modyfikacje, takie jak Boyer-Moore-Horspool czy Boyer-Moore-Sunday, które upraszczają regułę dobrego sufiksu lub implementują ją w nieco inny sposób, często kosztem niewielkiej utraty wydajności w najgorszym przypadku, ale zyskiem w prostocie implementacji.
• W wielu językach programowania, takich jak Python czy Java, wewnętrzne implementacje funkcji wyszukiwania stringów często wykorzystują warianty algorytmu Boyera-Moore’a lub inne zaawansowane algorytmy, takie jak Rabin-Karp czy Knuth-Morris-Pratt.