Algorytm Boyera i Moore’a

Algorytm Boyera i Moore’a

Algorytm Boyera i Moore’a to metoda wyszukiwania wzorca w tekście, która polega na porównywaniu znaków, zaczynając od ostatniego elementu wzorca.

Zalety:

• Jeśli stwierdzimy, że znak, który obecnie analizujemy, nie należy do wzorca, możemy przeskoczyć w analizie tekstu o całą długość wzorca.
• Zazwyczaj skoki wzorca są większe niż 1 (można to porównać z algorytmem Knutha-Morrisa-Pratta).

Przykłady

tekst: WIKIPEDIA, WOLNA ENCYKLOPEDIA

wzorzec: CYKL

WIKIPEDIA, WOLNA ENCYKLOPEDIA

| | | | | |

CYKL | | | | |

CYKL | | | |

CYKL | | |

CYKL | |

CYKL |

CYKL

Pierwsze cztery porównania dotyczą liter: i, i, w, a, które nie występują we wzorcu, dlatego możemy za każdym razem przeskoczyć do przodu o całą długość wzorca, czyli 4 znaki. Następne porównanie odnosi się do litery 'c’, która znajduje się we wzorcu. Wówczas przesuwamy wzorzec, aby litery te się nałożyły. W tym przypadku odnajdujemy szukane słowo.

tekst: ALGORYTMY I STRUKTURY DANYCH

wzorzec: TUR

ALGORYTMY I STRUKTURY DANYCH

| | | | | | |

TUR | | | | | |

TUR | | | | |

TUR | | | |

TUR | | |

TUR | |

TUR |

TUR

Pierwsze cztery porównania dotyczą liter: g, y, y, 'spacja’, które nie należą do wzorca, co pozwala nam skoczyć o całą długość wzorca do przodu. Przy piątym porównaniu litera, którą sprawdzamy, znajduje się we wzorcu. W tym przypadku nie przesuwamy wzorca, ponieważ litery już się pokrywają. Kontynuujemy sprawdzanie kolejnych liter, ale okazuje się, że już się nie pokrywają, więc ponownie możemy skoczyć o całą długość wzorca. Następnie natrafiamy na literę 't’, która znajduje się we wzorcu. Przesuwamy wzorzec tak, aby litery pokrywały się, i tym razem odnajdujemy szukane słowo.

Linki zewnętrzne

Artykuł na temat algorytmu (en)