algorytm.org

Algorytm BM (Boyer-Moore'a)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm BM (Boyer-Moore'a)
Ocena użytkowników:***** / 24
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 23 marca 2007 14:39

Podstawowym problemem dotyczącym tekstów jest problem wyszukiwania wzorca. Polega on na znalezieniu wszystkich wystąpień tekstu wzorzec, w tekście tekst. Przyjmujemy ponadto, że: |wzorzec|=m, |tekst|=n oraz n≥m.

Algorytm Boyer-Moore uważany jest za najbardziej efektywny algorytm wyszukiwania wzorca. Wykorzystuje się go powszechnie w aplikacjach gdzie występuje polecenie "szukaj" albo "zamień".

Skanowanie w tym algorytmie odbywa się od prawej strony wzorca. W przypadku niespasowania danego znaku bądź dopsaowania całego wzorca stosuje się dwie funkcje z wcześniej wyliczonymi wartościami. Są tą: "good-suffix shift" oraz "bad-character shift". Najlepiej przeanalizować ich działanie na przykładach. Załóżmy że część wzorca i teskstu zaznaczona jako u pasuje do siebie. Natomiast na kolejnej pozycji występuje różnica. W zależności od sytuacji możemy przesunąć się w poszukiwaniu o różną wartość:
  • "good-suffix shift" - jeżeli wzorzec zawiera w sobie kolejne wystąpienie u to przesuwamy się aby pokrywało się ono z tekstem.
    Boyer-Moore good-suffix shift
    tekst: cccccccbbabbaababbacc
    wzorzec: abbaabba

    niedopasowanie występuje na 4 znaku licząc od końca, ale wzorzec zawiera w sobie fragment juz dopasowany (bba), zatem przesuwamy się tak by kolejny taki fragment we wzorcu spasował się z tekstem

    tekst: cccccccbbabbaababbacc
    wzorzec:     abbaabba

  • "good-suffix shift" - wzorzec nie zawiera w sobie kolejnego wystąpienia u to przesuwamy się tak by suffix wzorca spasował się maksymalnie z jego dotychczas spasowanym prefiksem
    Boyer-Moore good-suffix shift
    tekst: cccccbbabbaababbacc
    wzorzec: baabba

    niedopasowanie występuje na 4 znaku licząc od końca, wzorzec nie zawiera w sobie fragmentu juz dopasowanego (bba), ale możemy dopasować jak najdłuży suffix (będzie to ba)

    tekst: cccccbbabbaababbacc
    wzorzec:     baabba

  • "bad-character shift" - przesuwamy się tak by pierwszy znak od prawej w szukanym wzorcu spasował się z aktualnie rozpatrywanym znakiem w tekście
    Boyer-Moore bad-character shift
    tekst: cccccccbbabbaababbacc
    wzorzec: cbcaabba

    niedopasowanie występuje na 4 znaku licząc od końca (w tekście mamy "c" we wzorcu mamy "a"), zatem przesuwamy wzorzec w ten sposób by pierwsze "c" od prawej spasowało się z tym, które "popsuło" nam to dopasowanie

    tekst: cccccccbbabbaababbacc
    wzorzec:   cbcaabba

  • "bad-character shift" - przesuwamy się tak by pierwszy znak od prawej w szukanym wzorcu spasował się z aktualnie rozpatrywanym znakiem w tekście, jeżeli takiego znaku nie ma to ustawiamy koniec wzorca bezpośrednio za nim
    Boyer-Moore bad-character shift
    tekst: ccccccebbabbaababbacc
    wzorzec: cbcaabba

    niedopasowanie występuje na 4 znaku licząc od końca (w tekście mamy "e" we wzorcu mamy "a"), we wzorcu "e" nie występuje zatem przesuwamy się tak by wzorzec był bezpośrednio za nim

    tekst: ccccccebbabbaababbacc
    wzorzec:      cbcaabba


W algorytmie stosujemu zawsze maksymalną wartość wynikającą z "good-suffix shift" oraz "bad-character shift".

Wartości funkcji "good-suffix shift" możemy przechowywać w tabeli o długości m+1. Zdefiniujmy dwa warunki:
  • Cs(i, s): dla każdego k takiego że i < k < m, s ≥ k lub wzorzec[k-s]=wzorzec[k]
  • Co(i, s): jeżeli s < i to wzorzec[i-s]!=wzorzec[i]
Wówczas wartość w tablicy funkcji "good-suffix shift" w indeksie i + 1 (0 ≤ i < m) = min {s > 0: Warunki Cs(i, s) oraz Co(i, s) są spełnione}.
Wartość w tablicy funkcji "good-suffix shift" w indeksie 0 definiujemy jako długość okresu wzorca. Czyli na przykład dla wzorca ababab będzie to 2, a dla wzorca abcdass będzie to 7.
W trakcie obliczeń tablicy funkcji "good-suffix shift" używać będziemy pomocniczej tablicy suff zdefiniowanej następująco: dla 1 ≤ i < m, suff[i] = max{k : wzorzec[i-k+1 .. i] = wzorzec[m-k .. m-1]}.
Algorytm tworzenia tablicy "good-suffix shift" wygląda następująco:
  • na początku zakładamy, że możemy zawsze przesunąć o cały wzorzec czyli m
  • poruszamy sie od końca tablicy suff, jeżeli odnajdujemy w niej wpis, który mówi nam, że wzorzec od poczatku do danego miejsca jest zgodny z sufiksem (czyli suff[i] == i + 1), to modyfikujemy wszystkie wpisy "good-suffix shift" dotychczas nie zmodyfikowane (te z wartością m) o indeksach mniejszych niz m - 1 - ina wartość m - suff[i]
  • następnie poruszając się w tablicy suff od 0 do m - 1 modyfikujemy wpisy w tablicy "good-suffix shift" według następującego wzoru:
    wpis pod indeksem m - 1 - suff[i] modyfikujemy na m - 1 - i


Wartości funkcji "bad-character shift" przechowywane są w tablicy o rozmiarze alfabetu (ponieważ skok zależy od wartości niedopasowanego znaku). Dla każdego znaku c wynosi ona min{i : 1 ≤ i < m-1 oraz wzorzec[m-1-i] = c} jeżeli c występuje we wzorcu, w przeciwnym razie wynosi ona m.

Tablice z wartościami dla obu funkcji obliczane są przed rozpoczęciem wyszukiwania.

Przykład:

Mamy dany wzorzec "abcdabc".
Najpierw obliczymy wartości tablicy suff
Wartości tej tablicy to długość zgodności sufiksu całeg wzorca, z sufiksem wzorca od danego indeksu.
 abcdabc
suff0030007
"good-suffix shift"-------

Zainicjujemy tablicę "good-suffix shift" wartościami m.
 abcdabc
suff0030007
"good-suffix shift"7777777

Poruszamy sie od końca tablicy, jeżeli w tablicy suff i odnajdujemy wpisy, które mówią nam, że wzorzec od poczatku do danego miejsca jest zgodny z sufiksem
 abcdabc
suff0030007
"good-suffix shift"4444777

modyfikujemy wpisy w tablicy "good-suffix shift" według następującego wzoru:
wpis pod indeksem m - 1 - suff[i] modyfikujemy na m - 1 - i
 abcdabc
suff0030007
"good-suffix shift"4444771

Obliczymy wartości funkcji "bad-character shift" - czyli wartość pierwszej pozycji danej litery licząc od prawej strony wzorca, bez pierwszego znaku od prawej.
abcde .. z
21437

Mamy dany tekst "abceabcdabc".
efceabcdabc
abcdabc

Pierwszą znalezioną (od tyłu) niezgodność znaznaczono pogrubieniem, przesuwamy zatem wzorzec o maksimum z "good-suffix shift" i "bad-character shift". Dla "good-suffix shift"[4] (dla pogrubionej litery) jest to wartosc 4, dla "bad-character shift" dla litery "e" mamy wartość 7, musimy od niej odjąć długość wzorca i dodać indeks (licząc od przodu), na którym mamy niezgodną wartość czyli 7 - 7 + 4 = 4. Maksimum z 4 i 4 to 4 a więc przesuwamy wzorzec o 4.
efceabcdabc
    abcdabc

Po takim przesunięciu widać, że dopasowaliśmy wzorzec, gyby tekst wejściowy był dłuższy to przesunęlibyśmy się teraz o wartość "good-suffix shift"[0], której wartość wynosi 4 - po dopasowaniu zawsze przesuwamy się o wartość "good-suffix shift"[0].

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 7
needplayazC/C++wersja uproszczona zawierajaca jedynie "bad-character shift"
.cpp
.cpp
***** / 2
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 lipca 2012 18:30
Komentarze
photo
+1 # Henryk 2010-05-26 20:47
Poprostu dziękuję
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz