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ę Ciebie czytelniku o pełne skupienie.

Miłego czytania!

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.

Tabela reprezentująca tekst z wyszukiwanym fragmentem i pokazanie jak działa algorytm BM
Rysunek 1. Przykład działania algorytmu BM.

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

  1. Szukane słowo porównujemy do pierwszych trzech znaków tekstu. Ostatni znak ze słowa NInie równa się ostatniemu znakowi z fragmentu PRO i znak O nie występuje w szukanym wzorcu
  2. Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NInie równa się ostatniemu znakowi z fragmentu GRA i znak A nie występuje w szukanym wzorcu
  3. Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NInie równa się ostatniemu znakowi z fragmentu MOi znak W nie występuje w szukanym wzorcu
  4. Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NInie równa się ostatniemu znakowi z fragmentu ANI i znak I występuje w szukanym wzorcu
  5. 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
  6. Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NInie równa się ostatniemu znakowi z fragmentu _Z_ i znak spacji nie występuje w szukanym wzorcu
  7. Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NInie równa się ostatniemu znakowi z fragmentu PAS i znak S nie występuje w szukanym wzorcu
  8. Szukane słowo porównujemy do trzech kolejnych znaków tekstu. Ostatni znak ze słowa NInie równa się ostatniemu znakowi z fragmentu ! i znak ! występuje w szukanym wzorcu
  9. 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!

Tablica znaków reprezentująca good-suffix shift w algorytmie Moyera Moore'a
Rysunek 2. Przykład działania zasady good-suffix shift.

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.

Tablica znaków reprezentująca bad-character shift w algorytmie Moyera Moore'a
Rysunek 3. Przykład działania zasady bad-character shift.

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

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ż klasa ta jest wariacją i normalnie nie musi zostać zastosowana. 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 posiadać 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ętle, która ma wiele zadań (tak, wiem nie jest to mądre posuniecie, ale zostawiam Tobie furtkę do refaktoryzacji).

Pierwszym z zadań jest zmiana koloru czcionki na szary oraz pobranie od użytkownika wzorca. Następnie następuje stworzenie obiektu 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.

Program konsolowy z przykładem działania algorytmu Boyera-Moore'a
Rysunek 4. Przykład działania algorytmu Boyera-Moore’a

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 temacie. Kod zaimplementowany poniżej może zostać zastosowany w projektach ale dopiero po wprowadzeniu kilku usprawnień.

Implementacja

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 &amp;&amp; obj != null &amp;&amp; i >= obj[j] &amp;&amp; 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 &amp;&amp; pattern[j] == text[i + j])
                    j--;

                if (j < 0)
                {
                    table.Add(i);
                }

                i += Math.Max(array] - 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!

PS. Będę wdzięczny za komentarze, każda uwaga i pomysł jest mile widziany. Zwłaszcza w kontekście merytorycznej analizy kodu i uwag co do niego. Zerknij też przy okazji do zakładki Skontaktuj się i zostaw po sobie ślad.
PS2. Czeka też na Ciebie autorski PDF z 10 algorytmami. Wystarczy, że zapiszesz się na Newsletter poniżej!


Zapisz się na Newsletter, odbierz Nagrodę i otrzymuj co niedzielę informacje na temat nowych wpisów, informacji ze świata programowania i matematyki oraz ciekawych wydarzeniach. Nie przegap i dołącz już dziś.

Ź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 
Autor

👨‍💻 .NET and Python programming passionate 🏦 Digtial Banking Solutions 🎓 Student 📊 Psychology 📚 Bookworm 🏠 Warsaw

Napisz komentarz

This site uses Akismet to reduce spam. Learn how your comment data is processed.