Algorytmy

Szukanie wzorca w tekscie metodą Boyera-Moorea

  • 6 komentarzy
  • 1913 odsłon
  • Oceń ten tekst jako pierwszy
Jest to chyba najszybszy algorytm na wyszukiwanie wzorca w texcie (złożoność teoretyczna to O(N/M) !!!) Jest on niesamowicie szybki przy dużych ciągach znakowych o sporym alfabecie.

<-- i ---------------------------------------------------->
a v e , C a e s a r , m o r i t u r i   t e  s o l u t a n t
s o  l u t
             s o l u t
                       s o l u t
                              s o l u t
                                        s o l u t
                                                   s o l u t
                                                        s o l u t
Jak widać z przykładu gdy algorytm sprawdzając ostatnią litere poszukiwanego wzorca do ciagu tekstu uzna za nie równą przeskakuje o całą długość wzorca, sprawdza jednak czy nie występują jakieś znaki które znajdują się we wzorcu, jeśli tak to nie przesuwa się o całą długość wzorca a tylko o taką długość aby te same znaki we wzorcu i tekscie pokryły się.
Metoda wykorzystuje zbadaną część wzorca do wyznaczenia optymalnego przesunięcia wzorca względem badanego fragmentu tekstu. Do tego
celu na wstępie generowana jest tablica optymalnych przesunięć shift. Algorytm wykonywany jest do momentu, aż cały fragment teksu będzie zgodny ze wzorcem, bądź osiągniemy koniec tekstu.
a teraz kod:
const K = 53; // litery(26+26) i spacja (1)
int shift[K];
 
int indeks(char c)
{ switch(c) {
     case 32: return 0; // spacja
     default: if(islower(c)) return c-'a'+1;
                 else return c-'A'+27;
     }
}
 
void InitShift(char *w)
{
   int i;
   for(i=0; i < K; i++) shift[i]=M;
      for(i=0; i < M; i++) shift[indeks(w[i])]=M-i-1;
}
 
int BM(char *t, char *w)
{
   int i,j,N=strlen(t),x;
   for(i=M-1,j=M-1; j > 0; i--,j--)
   while( t[i]!=w[j] )
   { x=shift[indeks(t[i])];
      if(M-j > x) i+=M-j; else i+=x;
        if(i >= N) return -1;
        j=M-1;
   }
   return i;
}

6 komentarzy

Sebo 2005-06-01 20:43

Jak dla mnie to najszybszy jest KMP (i moje programiki do testowania czasów to potwierdzają :]).
KR jest wolny bo trzeba tam dużo mnorzyć i dzielić :P

Ale nie czaję tego przykładu :(
Mógłby ktoś powywalać zbędne spacje i najlepiej zamknąc go w tagu < code> </ code>

poczatkujaca 2005-03-22 20:21

A co z wyszukiwaniem wzorca ze znakami specjalnymi. Przykładowy wzorzec:  *pulacj?. Pasują do niego manipulacja, manipulacje, populacja, populacją.

LukaszT 2004-11-11 14:52

Zauważyłem pewną nieścicłość w algorytmie. mianowicie pętla for
for(i=M-1,j=M-1; j > 0; i--,j--)
nie zostanie wykonan dla j=0, wiec nie zostanie dokonane porównanie
 t[0]!=w[j]
t[0] - czyli pierwszy znak szukanego wzorca nie zostanie poddany badaniu i zostanie potraktowany jako zgodny.
przykład działania:
jeżeli w powyższym przykładzie szukamy slowa "solut"  , to identyczny rezultat dało by poszukiwania ciągu "dolut", albo "nolut".
pętla for musi być :
for(i=M-1,j=M-1; j >= 0; i--,j--)

Túresairon 2004-06-18 12:46

Nieciekawy artykuł, nie widzę tu żadnych porządnych opisów. Tylko kawałek kodu w C (?) - mam go sobie sam analizować jak chcę wykorzystać tą metodę? Dużo tego na szczęście nie ma, mimo wszystko początkującym zapewne sprawiłoby to problemy.

Kri 2003-05-29 23:12

void InitShift(char *w)
{
int i;
for(i=0; i<K; i++) shift[i]=M;
for(i=0; i<M; i++) shift[indeks(w[i])]=M-i-1;
}

cos mi jakos ucielo to ;)
no i przyklad stracil czytelnosc poniewaz poprzesuwaly mi sie literki ;/

Dryobates 2003-05-30 00:17

Teraz chyba troszkę lepiej. Trzeba było < zamienić.
Co do przykładu, to jeszcze trzeba z tym popracować.
Natomiast o sam algorytm, to nie jestem pewien, czy Rabin-Karp nie okazałby się szybszy :)