Algorytm Boyera-Moore’a to temat artykułu numer 12. Obiekty złożone ze znaków na pierwszy rzut oka wydaję się skomplikowaną strukturą, jednak można na niej robić ciekawe operacje. Jedną z nich jest właśnie algorytm Boyera-Moore’a.
Poniżej postaram się odpowiedzieć na następujące pytania:
- Czym jest algorytm BM?
- Jak wygląda implementacja?
- Kto jest twórcą algorytmu?
- Czym jest heurystyka good-suffix shift oraz bad-character shift?
Temat nie jest łatwy do przyswojenia, dlatego na wstępie proszę Cię czytelniku o pełne skupienie.
Miłego czytania!
Zatrzymaj się!
Książki to obowiązkowa pozycja dla każdego zainteresowanego programowaniem!
Jest to zdecydowanie jedno z najlepszych źródeł do nauki programowania! Zyskasz przewagę w branży IT i osiągniesz dużo jako deweloper.
Algorytm Boyera-Moore’a — Wprowadzenie
Jest to pierwszy algorytm dotyczący tekstu, z którym spotkałem się podczas pracy zawodowej. Ilość danych, która nas otacza, rośnie z roku na rok. W dużej części dane te składają się z tekstu, który jest możliwy do przeczytania przez człowieka. Jednym z zadań urządzeń elektronicznych poza wyświetlaniem tekstu jest jego przeszukiwanie. Służy do tego wiele algorytmów, ale jednym z najpopularniejszych i najbardziej wygodnych jest algorytm Boyera-Moore’a. Temat niby jest prosty i wydawać by się mogło, że ciężko go zoptymalizować poza to, by sprawdzać znak po znaku i dopasowywać fragment tekstu do szukanego wzorca. Nic bardziej mylnego i postaram się to pokazać w implementacji.
Podstawowe informacje
Omawiany algorytm powstał w roku 1975 za sprawą Roberta Boyera i Strothera Moore. Głównym założeniem jest to, by tekst przeszukiwać standardowo od lewej do prawej strony, jednak wzorzec, który jest szukany, był porównywany od prawej do lewej strony. Opis może być mało intuicyjny, dlatego posłużę się grafiką poniżej.
Po pierwsze, aby algorytm miał sens, musimy założyć, że tekst, w którym wyszukujemy, będzie miał więcej znaków niż wzorzec. Wydaje się to dość logiczne.
Tak więc szukamy frazy NIE w wyrażeniu PROGRAMOWANIE Z PASJĄ. Główną zaletą działania algorytmu, jest przeskakiwanie o długość szukanego słowa. W przypadku, gdy po porównaniu ostatniego znaku wzorca (w naszym przypadku jest to litera E) do litery jej odpowiadającej w szukanym tekście stwierdzimy, że znaki się różnią i znak z wyrażenia nie znajduje się w szukanym tekście, to następuje przesunięcie.
Przykładowa analiza
- Szukane słowo porównujemy do pierwszych trzech znaków tekstu. Ostatni znak ze słowa NIE nie równa się ostatniemu znakowi z fragmentu PRO i znak O nie występuje w szukanym wzorcu
- Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NIE nie równa się ostatniemu znakowi z fragmentu GRA i znak A nie występuje w szukanym wzorcu
- Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NIE nie równa się ostatniemu znakowi z fragmentu MOW i znak W nie występuje w szukanym wzorcu
- Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NIE nie równa się ostatniemu znakowi z fragmentu ANI i znak I występuje w szukanym wzorcu
- Skoro znak I występuje w słowie szukanym NIE, to przesuwamy nasz szukany tekst nie o całą długość tylko o długość do znaku I. Dzięki tej operacji znaleźliśmy szukany fragment w tekście. Idziemy dalej
- Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NIE nie równa się ostatniemu znakowi z fragmentu _Z_ i znak spacji nie występuje w szukanym wzorcu
- Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NIE nie równa się ostatniemu znakowi z fragmentu PAS i znak S nie występuje w szukanym wzorcu
- Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NIE nie równa się ostatniemu znakowi z fragmentu JĄ! i znak ! występuje w szukanym wzorcu
- Program doszedł do końca
Algorytm tak działający nazywa się pełnym algorytmem Boyera-Moore’a. Aby można było go tak nazwać, musi korzystać z dwóch heurystyk, o których poniżej.
good-suffix shift
Pierwszą z dwóch heurystyk jest heurystyka pasującego sufiksu (ang. good suffix shift). Przedstawia ona sytuację, gdzie początkowe X znaków wzorca pasuje do tekstu i w dalszej części wzorca ten początek się powtarza. W przypadku poniżej szukamy ciągu znaków ZBBDZBBDZ i fragment BDZ pojawia się we wzorcu dwa razy oraz został dopasowany w pierwszym kroku.
W kroku numer dwa przesuwamy szukany ciąg, aż do drugiego fragmentu BDZ. Spowoduje to przeskok o cztery znaki i wyszukanie 7 pasujących elementów tekstu z 9. Ostatnim, trzecim krokiem będzie powtórnie przesunięcie o cztery znaki i dopasowanie drugiego fragmentu BDZ. Tekst został odnaleziony!
bad-character shift
Drugi przykład obrazuje sytuację, gdy dopasowane pierwsze X znaków znajduje się tylko raz we wzorze. Nazywamy to wtedy heurystyką bad-character shift. Przykład poniżej składa się z tekstu KŁFFŁFKŁFMŁŁFFFFKŁ i szukanego wzorca ŁŁFFFFKŁ.
W pierwszym kroku pasuje do siebie fragment FKŁ. Nie powtarza się on jednak we wzorcu. Pierwszą niepasującą literą w tekście jest Ł, dlatego we wzorze szukamy pierwszej napotkanej litery Ł. Znajduje się ona na drugim miejscu, licząc od lewej strony. Przesuwamy więc wzorzec do tej litery w prawo i sprawdzamy, ile pierwszych znaków pokrywa się z tekstem. Jest to tylko pierwsza litera. Kolejną literą, która nie znalazła pokrycia ze wzorcem, jest litera numer 10, czyli M.
W kroku numer trzy sprawdzamy, czy litera M znajduje się we wzorcu. Nie ma jej, więc przesuwamy o całą długość wzorzec, czyli w przypadku poniżej do końca tekstu. Wszystkie litery znalazły pokrycie, więc algorytm znalazł pasujący tekst.
Podsumowując
Algorytm Boyera-Moore’a jest pełny tylko wtedy gdy korzysta zarówno z good-suffix shift, jak i bad-character-shift. Gdy jedna i druga heurystyka nie znajdzie zastosowania, to dopiero wtedy możliwe jest przesunięcie wzorca o całą długość. Bad-character shift oraz good-suffix shift powodują, że podczas dopasowywania szukanego ciągu nie pominiemy żadnego pasującego fragmentu tekstu. Jest to niewątpliwie jedna z największych zalet algorytmu. Co prawda przykłady powyżej są banalnie proste, ale idealnie wizualizują działanie. Poniżej zaimplementuję jedną z odmian algorytmu BM.
Implementacja – opis
Klasa LessArray
Klasa LessArray jest pomocniczą klasą, która jak sama nazwa wskazuje, tworzy tablicę. Zamysł jest głównie związany z optymalizacją, tablica ta zajmie mniej miejsca, a do tego pomieści wszystkie przesunięcia. Zazwyczaj tego typu tablica w algorytmie Boyera-Moore’a nazywa się tablicą przesunięć.
Istotę tablicy przesunięć można sprawdzić w filmie poniżej. Ja skupię się na pozostałym kodzie, ponieważ obiekt ten jest wariacją i normalnie nie musi zostać zastosowany. Można użyć zwykłej tablicy dwuwymiarowej.
Klasa BM
Nie ukrywam, że klasa BM jest mocno okrojona, brakuje, chociażby pełnej implementacji dotyczących dwóch opisywanych wyżej heurystyk. Na wejście zadeklarowane zostają dwie zmienne typu string i LessArray. Konstruktor w parametrze otrzymuje wyszukiwany wzorzec i uruchamia metodę inicjalizującą. W metodzie tej następuje utworzenie obiektu LessArray.
Klasa BM zawiera też metodę SearchPattern, która na wejście przyjmuje tekst, w którym następuje wyszukanie. Elementem zwracanym jest lista elementów typu int, która zawiera indeksy wyszukanych elementów. Pisząc indeksy, mam na myśli pierwszy znak pasujący do wzorca. Gdy będziemy chcieli wyszukać słowo PAS, to metoda zwróci listę z jednym elementem z wartością 30. Będzie to oznaczało, że wzorzec pasuje od znaku P w tekście.
Zamysł działania pętli while jest bardzo prosty, posiadamy zmienną j o długości wzorca pomniejszonego o 1. W momencie, gdy kolejne elementy wzorca pasują do miejsca w tekście, to następuje obniżenie go do wartości minusowej. Gdy zmienna j będzie mieć wartość ujemną, następuje dodanie elementu i do tablicy wyników. Na końcu następuje wyznaczenie nowej wartości i. Gdy szukany wzorzec nie zostaje dopasowany, to następuje przesunięcie o długość wzorca. Wszystko działa zgodnie z rysunkiem 1 przedstawionym powyżej.
Metoda Main
Metoda Main to już czysta przyjemność. Zachęcam do pobrania kodu i eksperymentów na niej. Stworzyłem nieskończoną pętlę, która ma wiele zadań (tak, wiem, nie jest to mądre posunięcie, ale zostawiam Ci furtkę do refaktoryzacji).
Pierwszym z zadań jest zmiana koloru czcionki na szary oraz pobranie od użytkownika wzorca. Następnie tworzę obiekt BM z parametrem o wartości wzorca. Kolejno deklarujemy zmienną text i podajemy ciąg znaków, w którym nastąpi wyszukiwanie. Oczywiście można tu pobrać coś od użytkownika z konsoli lub pliku. W tym przypadku byłem leniwy i do testów taka forma przekazania tekstu wystarczyła.
Pozostało tylko uruchomić metodę SearchPattern z tekstem, w którym nastąpi przeszukanie, zapisać wyniki do listy i zaprezentować na ekranie. Przykładowe wyszukane wzorce na rysunku poniżej.
Podsumowując
Algorytm Boyera-Moore’a można zaimplementować na wiele sposobów, ja znalazłem ciekawe zastosowanie z własnym obiektem tablicowym, trochę przy nim namieszałem i pokazałem w tym wpisie. Pragnę też nadmienić, że bałagan w funkcji Main zostawiam celowo, by każdy mógł spróbować refaktoryzacji i zabawy z kodem. Nie jest sztuką przeczytać ten artykuł i popatrzeć na kod. Ważne, by go spróbować uruchomić u siebie i sprawdzić jego działanie.
Jako jedno z zadań mogę Ci dać sprawdzenie, czy działają wyszukiwania dużych liter. Następnie wprowadź ewentualne zmiany oraz usprawnienia w tym wątku. Kod zaimplementowany poniżej może zostać zastosowany w projektach, ale dopiero po wprowadzeniu kilku usprawnień.
Implementacja – kod
using System;
using System.Collections.Generic;
namespace AlgorytmBM
{
class Program
{
static void Main(string[] args)
{
for (; ;)
{
Console.ForegroundColor = ConsoleColor.Gray;
Console.WriteLine("Podaj szukaną frazę: ");
string pattern = Console.ReadLine();
BM bm = new BM(pattern);
string text = "Mateusz Rus - Programowanie z pasją!";
List<int> obj = bm.SearchPattern(text);
int j = 0;
for (int i = 0; i < text.Length; i++)
{
if (obj.Count > 0 && obj != null && i >= obj[j] && i < (obj[j] + pattern.Length))
{
Console.ForegroundColor = ConsoleColor.Green;
for (int k = i; k < i + pattern.Length; k++)
{
Console.Write(text[k]);
}
i = i + pattern.Length;
if (j < obj.Count - 1)
j++;
}
Console.ForegroundColor = ConsoleColor.White;
if (i < text.Length)
Console.Write(text[i]);
}
Console.WriteLine(Environment.NewLine);
}
}
}
class LessArray
{
byte patternLength;
byte[] defaultArray;
byte[][] table;
const int BlockSize = 0x100;
public LessArray(int patternLength_)
{
patternLength = (byte)patternLength_;
defaultArray = new byte[BlockSize];
InitializeBlock(defaultArray);
table = new byte[BlockSize][];
for (int i = 0; i < BlockSize; i++)
table[i] = defaultArray;
}
public byte this[int index]
{
get
{
return table[index / BlockSize][index % BlockSize];
}
set
{
int i = (index / BlockSize);
if (table[i] == defaultArray)
{
table[i] = new byte[BlockSize];
InitializeBlock(table[i]);
}
table[i][index % BlockSize] = value;
}
}
private void InitializeBlock(byte[] block)
{
for (int i = 0; i < BlockSize; i++)
block[i] = patternLength;
}
}
class BM
{
string pattern;
LessArray array;
public BM(string pattern)
{
Initialize(pattern);
}
public void Initialize(string pattern_)
{
pattern = pattern_;
array = new LessArray(pattern.Length);
for (int i = 0; i < pattern.Length - 1; i++)
array[pattern[i]] = (byte)(pattern.Length - i - 1);
}
public List<int> SearchPattern(string text)
{
int i = 0;
List<int> table = new List<int>();
while (i <= (text.Length - pattern.Length))
{
int j = pattern.Length - 1;
while (j >= 0 && pattern[j] == text[i + j])
j--;
if (j < 0)
{
table.Add(i);
}
i += Math.Max(array[text[i + j]] - pattern.Length + 1 + j, 1);
}
return table;
}
}
}
Algorytm Boyera-Moore’a — Podsumowanie
Udało mi się zmierzyć z najpopularniejszym algorytmem używanym do przeszukiwania tekstu. Nawet nie zdajemy sobie sprawy, że gdy uruchamiamy funkcję „Szukaj” lub „Zastąp” w edytorze tekstowym to właśnie kod podobny do tego powyżej stoi za działaniem tego typu operacji.
Temat na pewno nie został wyczerpany w 100% i mam w planach kolejne dwa algorytmy, które pomagają w przeszukiwaniu tekstu. Warto mieć na uwadze, że algorytm Boyera-Moore’a jest w wielu kwestiach bezkonkurencyjny. Polecam poeksperymentować.
Temat 13 będzie bazował na statystykach bloga za listopad 2019!
Źródła
https://eduinf.waw.pl/inf/alg/001_search/0050.php http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_1 http://students.mimuw.edu.pl/~wt237242/studia/ALG/prezentacja2.pdf https://www.issi.uz.zgora.pl/pl/didactic/cichy/aisd_05.pdf http://math.uni.lodz.pl/~horzel/ZA_2008/6_poszukiwanie_wzorca.pdf https://www.youtube.com/watch?v=lkL6RkQvpMM http://www-igm.univ-mlv.fr/~lecroq/string/node15.html https://repo.pw.edu.pl/docstore/download/WUT6260b98880f44423b1063026d440f130/PiotrRoz-PracaMagisterska.pdf http://ktc.wieik.pk.edu.pl/wp-content/uploads/2012/05/gorski_a_Przyklady_algorytmow.pdf https://www-igm.univ-mlv.fr/~lecroq/string/node14.html
Newsletter
Nie przegap i dołącz już dziś do 838 osób będących w tym Newsletter! Otrzymuj co niedzielę o godzinie 20 listę kilku ciekawych tematów, które miałem okazję obserwować w mijającym tygodniu.
Tematy będą głównie techniczne, ale czasami pojawi się coś, co może wprowadzi Cię w stan zadumy i zmusi do dyskusji w szerszym gronie. Zero spamu!
1 Komentarz
Cześć,
Nie slyszalem jeszcze o tym algorytmie. Pewnie szukajac frazy za pomoca wyrazenia regularnego algorytm BM wykonuje sie pod maska.
Bardzi jestem ciekaw dlaczego algorytm BM jest bezkonkurencyjny oraz jak wypada jego zlozonosc czasowa oraz obliczeniowa w porownaniu z metoda brute force czy lucky guess.
Bardzo chetnie przeczytam wiecej o tego typu algorytmach na twoim blogu Mateusz.
Pozdrawiam