Algorytm Boyera i Moore'a

Z Wikipedii

Ten artykuł wymaga dopracowania.
Należy w nim poprawić: sfromatoać tekst tak, zeby kod zajmował całe pole.
Więcej informacji co należy poprawić, być może znajdziesz na odpowiedniej stronie. W pracy nad artykułem należy korzystać z zaleceń edycyjnych. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.
Możesz także przejrzeć pełną listę stron wymagających dopracowania.

Algorytm Boyera i Moore'a - Jest to algorytm poszukiwania wzorca w tekście. Dużo prostszy niż np. K-M-P.

Polega na porównywaniu ostatniego elementu wzorca.

Zalety:

• jeżeli okaże się ze znak, który aktualnie sprawdzamy nie należy do wzorca możemy w takim przypadku przeskoczyć w analizie tekstu o całą długość wzorca
• z reguły skoki wzorca są większe od 1 (można sobie porównać z metodą K-M-P)

   ex1

   tekst:   WIKIPEDIA, WOLNA ENCYKLOPEDIA
   wzorzec: CYKL

   WIKIPEDIA, WOLNA ENCYKLOPEDIA
      |   |   |   |   |  |
   CYKL   |   |   |   |  |
       CYKL   |   |   |  |
           CYKL   |   |  |
               CYKL   |  |
                   CYKL  |
                      CYKL

Pierwsze 4 porównania trafiają na litery: i, i, w, a, które nie występują we wzorcu, możemy więc za każdym razem skoczyć do przodu o całą długość wzorca, a więc 4 znaki. Kolejne porównanie trafia jednak na literę 'c', która występuje we wzorcu. Należy wówczas przesunąć wzorzec tak by litery te nałożyły się na siebie i porównywanie jest kontynuowane. W tym przypadku okazuje się, że natrafiamy na szukane słowo.

   ex2

   tekst:   ALGORYTMY I STRUKTURY DANYCH
   wzorzec: TUR

   ALGORYTMY I STRUKTURY DANYCH
     |  |  |  |  |  | |
   TUR  |  |  |  |  | |
      TUR  |  |  |  | |
         TUR  |  |  | |
            TUR  |  | |
               TUR  | |
                  TUR |
                    TUR

Pierwsze 4 porównania trafiają na litery: g, y, y, 'spacja', które nie występuje we wzorcu, możemy więc skoczyć o całą długość wzorca do przodu. Przy 5 porównaniu zauważamy, że litera którą sprawdzamy znajduje się we wzorcu. W tym przypadku nie przesuwamy wzorca do przodu, ponieważ litery już się pokrywają. Sprawdzamy kolejne litery. Okazuje się jednak, że już się nie pokrywają, więc znów możemy skoczyć o całą długość wzorca. Natrafiamy na literę 't', która znajduje się we wzorcu. Przesuwamy wzorzec tak by litery pokrywały się. Tym razem okazuje się już, że znaleźliśmy szukane słowo.