Boyer–Moore szuka tekstu, zaczynając porównanie od końca wzorca
Szukając słowa w długim tekście, intuicyjnie można ustawić wzorzec na pierwszej pozycji, porównywać litery od lewej i po błędzie przesuwać go o jeden znak. Algorytm Boyera–Moore robi coś bardziej przewrotnego: porównuje wzorzec od prawej strony i wykorzystuje informację z niedopasowania, aby czasem przeskoczyć o wiele pozycji naraz. Oryginalna praca z 1977 roku podkreśla niezwykłą własność metody: w typowych warunkach algorytm nie musi nawet obejrzeć wszystkich znaków tekstu znajdujących się przed znalezionym wystąpieniem. Im dłuższy i bardziej informacyjny wzorzec, tym większe mogą być bezpieczne skoki.
Niedopasowanie może powiedzieć więcej niż „spróbuj następnej pozycji”
Załóżmy, że szukamy wzorca `KOMPUTER` w długim tekście. Naiwna metoda ustawia wzorzec nad kolejnymi fragmentami tekstu i po pierwszym błędzie przesuwa go o jedną pozycję. Taki algorytm wyrzuca jednak informację, którą właśnie zdobył. Skoro wiemy, jaki znak tekstu spowodował niedopasowanie i gdzie wystąpił względem wzorca, możemy czasem udowodnić, że kilka następnych pozycji startowych również nie ma szans zadziałać.
Boyer–Moore konstruuje reguły przesunięcia z samego wzorca. Najbardziej intuicyjna z nich, bad-character rule, patrzy na znak tekstu, który nie pasował. Jeśli znak w ogóle nie występuje w odpowiedniej części wzorca, wzorzec można przesunąć poza niego. Jeśli występuje, można ustawić odpowiednie wystąpienie nad tym znakiem, zamiast próbować wszystkich pozycji pośrednich.
Dlaczego porównuje się od prawej
Porównywanie od końca wzorca sprawia, że pierwsze zauważone niedopasowanie może dotyczyć znaku leżącego daleko od początku aktualnego ustawienia. To daje przestrzeń do większego przesunięcia. Oryginalna publikacja Roberta Boyera i J Strothera Moore'a opisuje wyszukiwanie, w którym znaki wzorca są dopasowywane od ostatniego znaku, a informacja zdobyta dzięki temu porządkowi często pozwala wykonywać duże skoki przez tekst.
Drugim klasycznym mechanizmem jest reguła dobrego sufiksu: jeśli końcowa część wzorca już pasowała, algorytm szuka innego miejsca wzorca, w którym taki sufiks może się sensownie ustawić, albo wykorzystuje jego odpowiedni prefiks. Dzięki temu także udane porównania sprzed błędu stają się informacją o bezpiecznym przesunięciu.
Można przeczytać mniej znaków niż ma fragment tekstu
Najbardziej zaskakujące stwierdzenie z pracy z 1977 roku brzmi, że w wielu przypadkach nie wszystkie znaki tekstu przed znalezionym wystąpieniem muszą zostać w ogóle sprawdzone. To nie sprzeczność: algorytm nie „wie” zawartości pominiętych znaków. Wie natomiast, że z powodu już zobaczonych znaków żadne dopasowanie zaczynające się w pominiętym obszarze nie może być poprawne.
W dobrych warunkach liczba inspekcji znaków na znak tekstu może więc być mniejsza niż jeden średnio. Wydajność zależy od alfabetu, wzorca, tekstu i konkretnej odmiany algorytmu. Dla niekorzystnych danych nie należy obiecywać magicznych skoków. Ciekawostką jest mechanizm: brak dopasowania staje się dowodem, że całe grupy kandydatów można pominąć.
Preprocessing kupuje szybsze wyszukiwanie
Przed rozpoczęciem właściwego wyszukiwania Boyer–Moore analizuje wzorzec i buduje tabele potrzebne do obliczania przesunięć. To kolejny przykład klasycznego kompromisu algorytmicznego. Płacimy z góry za przygotowanie danych, aby później wielokrotnie podejmować decyzje szybciej.
Jeśli wzorzec jest bardzo krótki albo tekst niewielki, koszt przygotowania i złożoność implementacji mogą nie być warte wysiłku. Jeśli jednak wzorzec ma być szukany w dużym tekście, możliwość przeskakiwania niepasujących regionów może być niezwykle cenna. Algorytm pokazuje, że czasem szybsze szukanie nie polega na sprawniejszym sprawdzaniu każdego kandydata, ale na matematycznym uzasadnieniu, dlaczego większości kandydatów w ogóle nie trzeba sprawdzać.
Dwie różne informacje z niedopasowania pozwalają wykonywać duże skoki
Klasyczny Boyer–Moore wykorzystuje dwie główne heurystyki. Reguła złego znaku patrzy na znak tekstu, który nie pasował do wzorca, i przesuwa wzorzec tak, aby wyrównać go z najbardziej prawą sensowną pozycją tego znaku — albo przeskoczyć jeszcze dalej, jeśli znak w ogóle nie występuje w odpowiednim fragmencie wzorca. Reguła dobrego sufiksu wykorzystuje z kolei fakt, że pewien końcowy fragment wzorca już się zgodził: szuka innego wystąpienia tego fragmentu lub zgodnego prefiksu, zamiast zapominać o wykonanych porównaniach. Preprocessing buduje tablice potrzebne do takich decyzji. Dzięki temu jedno niedopasowanie może uzasadnić przesunięcie o kilka znaków, a nie tylko o jeden. Siła algorytmu bierze się z informacji zawartej w porażce, nie z szybszego porównywania pojedynczych znaków.