Algorytm przeszukiwania łańcuchów Boyera-Moore'a

Aby zapoznać się z dowodem twierdzenia Boyera-Moore'a, zobacz Nqthm .

Wyszukiwanie ciągów Boyera-Moore'a

Klasa	Wyszukiwanie ciągów
Struktura danych	Strunowy
Wydajność w najgorszym przypadku	Wstępne przetwarzanie Θ(m) + dopasowanie O(mn).
Najlepsza wydajność	Wstępne przetwarzanie Θ(m) + dopasowanie Ω(n/m).
Złożoność przestrzeni w najgorszym przypadku	Θ(k)

W informatyce algorytm wyszukiwania ciągów Boyera-Moore'a jest wydajnym algorytmem wyszukiwania ciągów , który jest standardowym punktem odniesienia dla praktycznej literatury dotyczącej wyszukiwania ciągów. Został opracowany przez Roberta S. Boyera i J Strothera Moore'a w 1977 roku. Oryginalny artykuł zawierał statyczne tabele do obliczania przesunięć wzoru bez wyjaśnienia, jak je utworzyć. Algorytm tworzenia tabel został opublikowany w kolejnym artykule; artykuł ten zawierał błędy, które później poprawił Wojciech Rytter w 1980 roku.

Algorytm wstępnie przetwarza szukany ciąg (wzorzec), ale nie szukany ciąg (tekst) . Dlatego dobrze nadaje się do aplikacji, w których wzorzec jest znacznie krótszy niż tekst lub w których powtarza się podczas wielu wyszukiwań. Algorytm Boyera-Moore'a wykorzystuje informacje zebrane podczas etapu przetwarzania wstępnego, aby pominąć sekcje tekstu, co skutkuje niższym stałym współczynnikiem niż wiele innych algorytmów wyszukiwania ciągów. Ogólnie rzecz biorąc, algorytm działa szybciej wraz ze wzrostem długości wzorca. Kluczowymi cechami algorytmu jest dopasowywanie na końcu wzorca, a nie na głowie, oraz przeskakiwanie wzdłuż tekstu skokami o wiele znaków, zamiast przeszukiwania każdego pojedynczego znaku w tekście.

Definicje

A	N	P	A	N	M	A	N	-
P	A	N	-	-	-	-	-	-
-	P	A	N	-	-	-	-	-
-	-	P	A	N	-	-	-	-
-	-	-	P	A	N	-	-	-
-	-	-	-	P	A	N	-	-
-	-	-	-	-	P	A	N	-

Dopasowania wzorca PAN do tekstu ANPANMAN , od k=3 do k=8 . Dopasowanie występuje przy k=5 .

• T oznacza tekst wejściowy do przeszukania. Jego długość wynosi n .
• P oznacza szukany ciąg znaków, zwany wzorcem . Jego długość wynosi m .
• S [ i ] oznacza znak w indeksie i łańcucha S , licząc od 1.
• S [ i .. j ] oznacza podłańcuch łańcucha S zaczynający się od indeksu i i kończący się na j włącznie.
• Przedrostek S jest podłańcuchem S [1.. i ] dla pewnego i w zakresie [1, l ] , gdzie l jest długością S .
• Przyrostek S jest podłańcuchem S [ i .. l ] dla pewnego i w zakresie [1, l ] , gdzie l jest długością S .
• Wyrównanie P do T jest indeksem k w T takim , że ostatni znak P jest wyrównany z indeksem k T .
• Dopasowanie lub wystąpienie P występuje na wyrównaniu k , jeśli P jest równoważne z T [ ( k - m +1 ).. k ].

Opis

Algorytm Boyera-Moore'a wyszukuje wystąpienia P w T , dokonując jawnych porównań znaków w różnych wyrównaniach. Zamiast brutalnego wyszukiwania wszystkich wyrównań (których jest $P,$ Moore wykorzystuje informacje uzyskane podczas wstępnego przetwarzania aby pominąć jak najwięcej wyrównań

Przed wprowadzeniem tego algorytmu zwykłym sposobem wyszukiwania w tekście było sprawdzanie każdego znaku tekstu pod kątem pierwszego znaku wzorca. Po jego znalezieniu porównywane byłyby kolejne znaki tekstu ze znakami wzorca. Jeśli nie wystąpiło dopasowanie, tekst byłby ponownie sprawdzany znak po znaku w celu znalezienia dopasowania. Dlatego prawie każdy znak w tekście wymaga zbadania.

Kluczowym spostrzeżeniem w tym algorytmie jest to, że jeśli koniec wzorca jest porównywany z tekstem, można wykonywać skoki wzdłuż tekstu, zamiast sprawdzać każdy znak tekstu. Powodem, dla którego to działa, jest to, że podczas wyrównywania wzorca z tekstem ostatni znak wzorca jest porównywany ze znakiem w tekście. Jeśli znaki nie pasują do siebie, nie ma potrzeby dalszego wyszukiwania wstecz wzdłuż tekstu. Jeśli znak w tekście nie pasuje do żadnego ze znaków we wzorcu, to następny znak w tekście do sprawdzenia znajduje się m znaków dalej w tekście, gdzie m jest długością wzorca. Jeśli znak w tekście znajduje się we wzorcu, następuje częściowe przesunięcie wzoru wzdłuż tekstu w celu wyrównania wzdłuż pasującego znaku i proces jest powtarzany. Przeskakiwanie po tekście w celu dokonywania porównań zamiast sprawdzania każdego znaku w tekście zmniejsza liczbę porównań, które należy wykonać, co jest kluczem do wydajności algorytmu.

formalnie , algorytm zaczyna się od wyrównania $P$ początek jest wyrównany z T . Znaki w P i T są następnie porównywane, zaczynając od indeksu m w P i k w T , przesuwając się do tyłu. Ciągi są dopasowywane od końca P do początku P . Porównania są kontynuowane, dopóki nie zostanie osiągnięty początek P (co oznacza dopasowanie) lub wystąpi niezgodność, po której wyrównanie zostanie przesunięte do przodu (w prawo) zgodnie z maksymalną wartością dozwoloną przez szereg reguł. Porównania są przeprowadzane ponownie przy nowym dopasowaniu i proces jest powtarzany, dopóki wyrównanie nie zostanie przesunięte poza koniec T , co oznacza, że ​​nie zostaną znalezione dalsze dopasowania.

Reguły przesunięcia są realizowane jako przeszukiwania tablicy w czasie stałym, przy użyciu tabel generowanych podczas wstępnego przetwarzania P .

Zasady zmiany

Przesunięcie oblicza się, stosując dwie zasady: regułę złego znaku i regułę dobrego sufiksu. Rzeczywiste przesunięcie przesunięcia jest maksymalnym przesunięciem obliczonym według tych reguł.

Zasada złego charakteru

Opis

-	-	-	-	X	-	-	k	-	-	-
A	N	P	A	N	M	A	N	A	M	-
-	N	N	A	A	M	A	N	-	-	-
-	-	-	N	N	A	A	M	A	N	-

Demonstracja reguły złego znaku za pomocą wzoru P = NNAAMAN . Występuje niezgodność między N (w tekście wejściowym) a A (we wzorcu) w kolumnie oznaczonej X . Wzorzec jest przesuwany w prawo (w tym przypadku o 2), tak że znalezione zostaje następne wystąpienie znaku N (we wzorcu P ) na lewo od bieżącego znaku (czyli środkowego A ).

Reguła złego znaku uwzględnia znak w T , przy którym proces porównania się nie powiódł (zakładając, że taki błąd wystąpił). Znaleziono następne wystąpienie tego znaku po lewej stronie w P i proponuje się przesunięcie, które dopasowuje to wystąpienie do niedopasowanego wystąpienia w T. Jeśli niedopasowany znak nie występuje po lewej stronie w P , proponuje się przesunięcie, które przesuwa całość P poza punkt niezgodności.

Przetwarzanie wstępne

Metody różnią się w zależności od dokładnej formy, jaką powinna przyjąć tabela reguły nieprawidłowego znaku, ale proste rozwiązanie wyszukiwania w czasie stałym jest następujące: utwórz tabelę 2D, która jest najpierw indeksowana przez indeks znaku c w alfabecie, a następnie przez indeks i we wzorze. To wyszukiwanie zwróci wystąpienie c w P $-1,$ kolejnym najwyższym indeksem lub jeśli nie ma takiego $_$ będzie $.$ z czasem $wyszukiwania$ _ o długości k .

Poniższe implementacje C i Java mają złożoność $make_delta1 ,$ ) Jest to to samo, co oryginalna tabela złych znaków delta1 i BMH . Ta tabela odwzorowuje znak na pozycji w $Displaystyle$ przesunięcia o $\ operatorname {len} (p) -1-i}$ , z ostatnim wystąpieniem - najmniejszym przesunięciem kwota — pierwszeństwo. Wszystkie nieużywane znaki są ustawione jako wartość wartownicza ${\ displaystyle \ operatorname {len} (p)}$

Zasada dobrego sufiksu

Opis

-

-

-

-

X

-

-

k

-

-

-

-

-

M

A

N

P

A

N

A

M

A

N

A

P

-

A

N

A

M

P

N

A

M

-

-

-

-

-

-

-

-

-

A

N

A

M

P

N

A

M

-

Demonstracja dobrej reguły sufiksu za pomocą wzorca P = ANAMPNAM . Tutaj t oznacza T [6..8], a t' oznacza P [2..4].

Reguła dobrego sufiksu jest znacznie bardziej złożona zarówno pod względem koncepcji, jak i implementacji niż reguła złego znaku. Podobnie jak reguła złego znaku, wykorzystuje ona również cechę algorytmu polegającą na porównaniach rozpoczynających się na końcu wzorca i przechodzących w kierunku początku wzorca. Można to opisać następująco:

Załóżmy, że dla danego wyrównania P i T podłańcuch t z T pasuje do sufiksu P , ale przy następnym porównaniu po lewej stronie pojawia się niezgodność.

1. Następnie znajdź, jeśli istnieje, najbardziej wysuniętą na prawo kopię t' t w P taką, że t' nie jest sufiksem P , a znak na lewo od t' w P różni się od znaku na lewo od t w P . Przesuń P w prawo, aby podciąg t' w P był wyrównany z podłańcuchem t w T .
2. Jeśli t' nie istnieje, przesuń lewy koniec P poza lewy koniec t w T o najmniejszą wartość, tak aby przedrostek przesuniętego wzorca pasował do sufiksu t w T .
3. Jeśli takie przesunięcie nie jest możliwe, przesuń P o m (długość P) miejsc w prawo.
4. Jeśli zostanie znalezione wystąpienie P , przesuń P o najmniejszą wartość, tak aby właściwy przedrostek przesuniętego P pasował do sufiksu wystąpienia P w T .
5. Jeśli takie przesunięcie nie jest możliwe, to przesuń P o m miejsc, czyli przesuń P poza t .

Przetwarzanie wstępne

Reguła dobrego sufiksu wymaga dwóch tabel: jednej do użycia w przypadku ogólnym, a drugiej do użycia, gdy przypadek ogólny nie zwraca żadnego znaczącego wyniku lub występuje dopasowanie. Tabele te będą oznaczone odpowiednio jako L i H. Ich definicje są następujące:

Dla każdego ja , ${\ Displaystyle L [i]}$ jest największą pozycją mniejszą niż m taką, że ciąg ${\ Displaystyle P [i.. m]}$ pasuje do sufiksu ${\ Displaystyle P [1.. L [i]]}$ i tak, że znak poprzedzający ten sufiks to nie równa się ${\ Displaystyle P [i-1]}$ . ${\ Displaystyle L [i]}$ definiuje się jako zero, jeśli nie ma pozycji spełniającej warunek.

Niech ${\ Displaystyle H [i]}$ oznacza długość największego sufiksu ${\ Displaystyle P [i.. m]}$ , który jest również przedrostkiem P. , jeśli taki istnieje. Jeśli $niech$ istnieje, zero

Obie $_$$skonstruować$ i _ Przesunięcie wyrównania dla indeksu i w P jest podane przez ${\ Displaystyle mL [i]}$ lub ${\ Displaystyle mH [i]}$ . H powinno być używane tylko wtedy, gdy $wynosi$ znaleziono

Reguła Galila

Prosta, ale ważna optymalizacja Boyera-Moore'a została przedstawiona przez Zvi Galila w 1979 r. W przeciwieństwie do przesuwania, reguła Galila dotyczy przyspieszenia rzeczywistych porównań wykonywanych przy każdym wyrównaniu poprzez pominięcie sekcji, o których wiadomo, że pasują. Załóżmy, że przy wyrównaniu k ₁ , P jest porównywane z T aż do znaku c z T . Następnie, jeśli P zostanie przesunięte do k2 tak, _że jego T [( k2 _- n ) k1 _] . lewy koniec znajduje się między c a k1 _.. , w następnej fazie porównania przedrostek P musi pasować do podłańcucha Tak więc, jeśli porównania dotrą do pozycji k1 _k1 z _przeszłego T , wystąpienie P może zostać odnotowane bez jawnego porównywania . Oprócz zwiększenia wydajności Boyera-Moore'a, reguła Galila jest wymagana do udowodnienia wykonania w czasie liniowym w najgorszym przypadku.

Reguła Galil w swojej oryginalnej wersji jest skuteczna tylko w przypadku wersji, które generują wiele dopasowań. Aktualizuje zakres podłańcuchów tylko dla c = 0 , czyli pełnego dopasowania. Uogólniona wersja do obsługi dopasowań podrzędnych została zgłoszona w 1985 roku jako algorytm Apostolico – Giancarlo .

Wydajność

$Moore'a$ w oryginalnym artykule ma czas działania w najgorszym przypadku tylko wzór nie się w tekście Po raz pierwszy udowodnili to Knuth , Morris i Pratt w 1977 r., a następnie Guibas i Odlyzko w 1980 r., z górną granicą 5 n porównań w najgorszym przypadku. Richard Cole dał dowód z górną granicą 3 n porównań w najgorszym przypadku w 1991 roku.

Kiedy wzór występuje w tekście, czas działania oryginalnego algorytmu w najgorszym przypadku wynosi ${\ displaystyle O (nm)} .$ Łatwo to zauważyć, gdy zarówno wzór, jak i tekst składają się wyłącznie z tego samego powtarzającego się znaku. Jednak włączenie reguły Galila skutkuje liniowym czasem działania we wszystkich przypadkach.

Implementacje

Istnieją różne implementacje w różnych językach programowania. W C ++ jest częścią Biblioteki Standardowej od C ++ 17, a także Boost zapewnia ogólną implementację wyszukiwania Boyer-Moore w ramach biblioteki Algorithm . W Go (język programowania) istnieje implementacja w search.go . D (język programowania) używa BoyerMooreFinder do dopasowywania opartego na predykatach w zakresach jako część Phobos Runtime Library.

Algorytm Boyera-Moore'a jest również używany w grep GNU .

Implementacja Pythona

   





  

    
    
        
       0    
     

        
    
       
           
      0
               
          
          
          
     

    
    




       0  
         
         
         
      0    
    0  
       0 
            
              
    
      0
      0
          
             
                
              
                  
                 
                  
              
                        
                  
                      
          
               0 
               0
                  
                      
     

    
    







       0
             
          
          
        
          
            
            
     

    
    









          
        
    
       0   
            
           
              
     

    
    





      0    
      
      0
        
                   
            
     

    
    






       0    0    
         

      

    
      
      
      

              
           
       
              
                     
           0          
              
              
                 
                
                      
          
                
                   
                  
                   
                      
                           
                        
               
                        
              
      od  wpisywania  import  *  # Ta wersja jest wrażliwa na alfabet angielski w ASCII w celu dopasowania bez rozróżniania wielkości liter.  # Aby usunąć tę cechę, zdefiniuj index_alfabetu jako ord(c) i zamień wystąpienia "26"  # na "256" lub dowolny maksymalny punkt kodowy, jaki chcesz. W przypadku Unicode możesz chcieć dopasować w UTF-8   # bajtów zamiast tworzyć tabelę o rozmiarze 0x10FFFF.  ROZMIAR_ALFABETU  =  26  def  alfabet_index  (  c  :  str  )  ->  int  :  """Zwróć indeks podanego znaku alfabetu angielskiego, licząc od 0."""  val  =  ord  (  c  .  lower  ())  -  ord  (  " a"  )  assert  val  >=  and  val  <  ROZMIAR_ALPHABETu  return  val  def  długość_dopasowania  (  S  :  str  ,  idx1  :  int  ,  idx2  :  int  )  ->  int  :  """Zwróć długość dopasowania podłańcuchów S począwszy od idx1 i idx2."""  if  idx1  ==  idx2  :  return  len  (  S  )  -  idx1  liczba_dopasowań  =  podczas gdy  idx1  <  długość  (  S  )  i  idx2  <  długość  (  S  )  i  S  [  idx1  ]  ==  S  [  idx2  ]:  liczba_dopasowań  +=  1  idx1  +=  1  idx2  +=  1  return  liczba_dopasowań  def  fundamental_preprocess  (  S  :  str  )  ->  list  [  int  ]:  """Return Z, podstawowe przetwarzanie wstępne S.  Z[i] to długość podciągu rozpoczynającego się od i, który jest również prefiksem S.  To wstępne przetwarzanie odbywa się w czasie O(n), gdzie n jest długością S.  """  if  len  (  S  )  ==  :  # Obsługuje przypadek pustego łańcucha  return  []  if  len  (  S  )  ==  1  : # Obsługuje przypadek   zwrotu  łańcucha jednoznakowego  [  1  ]  z  =  [  for  x  in  S  ]  z  [  ]  =  len  (  S  )  z  [  1  ]  =  długość_dopasowania  (  S  ,  ,  1  )  for  i  in  range  (  2  ,  1  +  z  [  1  ]):  # Optymalizacja z ćwiczenia 1-5  z  [  i  ]  =  z  [  1  ]  -  i  +  1  # Definiuje dolną i górną granicę pola z  l  =  r  =  dla  i  w  zakresie  (  2  +  z  [  1  ],  len  (  S  )):  if  i  <=  r  :  # i mieści się w istniejącym polu z  k  =  i  -  l  b  =  z  [  k  ]  a  =  r  -  i  +  1  if  b  <  a  :  # b kończy się w obrębie istniejącego pola z  z  [  i  ]  =  b  else  :  # b kończy się na końcu pola Z lub po nim, musimy przeprowadzić jawne dopasowanie na prawo od pola Z  z  [  i  ]  =  a  +  długość_dopasowania  (  S  ,  a  ,  r  +  1  )  l  =  i  r  =  i  +  z  [  i  ]  -  1  else  :  # i nie znajduje się w istniejącym polu  z z  [  i  ]  =  długość_dopasowania  (  S  ,  ,  i  )  if  z  [  i  ]  >  :  l  =  i  r  =  i  +  z  [  i  ]  -  1  return  z  def  bad_character_table  (  S  :  str  )  ->  list  [  list  [  int  ]]:  """  Generuje R dla S, które jest tablica indeksowana przez pozycję jakiegoś znaku c w  alfabecie angielskim. Przy tym indeksie w R znajduje się tablica o długości |S|+1, określająca dla każdego   indeksu i w S (plus indeks po S) następne położenie znaku c napotkanego podczas  przechodzenia przez S od prawej do lewej, zaczynając od i. Jest to używane do wyszukiwania w czasie stałym   reguły złego znaku w algorytmie wyszukiwania łańcuchów Boyera-Moore'a, chociaż ma  znacznie większy rozmiar niż rozwiązania o czasie innym niż stały.  """  if  len  (  S  )  ==  :  return  [[]  for  a  in  range  (  ALPHABET_SIZE  )]  R  =  [[  -  1  ]  for  a  in  range  (  ALPHABET_SIZE  )]  alpha  =  [  -  1  for  a  in  range  (  ALPHABET_SIZE  ) ]  for  i  ,  c  in  enumerate  (  S  ):  alfa  [  index_alfabetu  (  c  )]  =  i  for  j  ,  a  in  enumerate  (  alpha  ):  R  [  j  ]  .  append  (  a  )  return  R  def  good_suffix_table  (  S  :  str  )  ->  list  [  int  ]:  """  Generuje L dla S, tablicę używaną w implementacji reguły silnego dobrego sufiksu.  L[i] = k, największa pozycja w S taka, że ​​S[i:] (sufiks S zaczynający się od i) pasuje do  sufiksu S[:k] (podciąg w S kończący się na k). Używane w Boyer-Moore, L daje wielkość przesunięcia   P względem T, tak że żadne wystąpienia P w T nie są pomijane, a sufiks P[:L[i]]  pasuje do podłańcucha T dopasowanego przez sufiks P w poprzednia próba dopasowania.  W szczególności, jeśli niedopasowanie miało miejsce w pozycji i-1 w P, wielkość przesunięcia jest określona  równaniem len(P) - L[i]. W przypadku, gdy L[i] = -1, używana jest pełna tablica przesunięć.   Ponieważ liczą się tylko właściwe sufiksy, L[0] = -1.  """  L  =  [  -  1  for  c  in  S  ]  N  =  fundamental_preprocess  (  S  [::  -  1  ])  #  S[::-1] odwraca S  N.  reverse  ()  for  j  in  range  (  ,  len  (  S  )  -  1  ):  i  =  len  (  S  )  -  N  [  j  ]  if  i  !=  len  (  S  ):  L  [  i  ]  =  j  return  L  def  full_shift_table  (  S  :  str  )  ->  list  [  int  ]:  """  Generuje F dla S , tablica używana w szczególnym przypadku reguły dobrego sufiksu w  algorytmie wyszukiwania ciągów Boyera-Moore'a. F[i] to długość najdłuższego sufiksu S[i:], który jest również przedrostkiem   S. W przypadkach, w których jest używany, wielkość przesunięcia wzorca P względem tekstu  T wynosi len(P) - F[i] dla niedopasowania występującego przy i-1.  """  F  =  [  for  c  in  S  ]  Z  =  fundamental_preprocess  (  S  )  najdłuższy  =  dla  i  ,  zv  in  enumerate  (  odwrócony  (  Z  )):  najdłuższy  =  max  (  zv  ,  najdłuższy  )  if  zv  ==  i  +  1  jeszcze  najdłuższy  F  [  -  i  -  1  ]  =  najdłuższy  powrót  F  def  string_search  (  P  ,  T  )  ->  list  [  int  ]:  """  Implementacja algorytmu przeszukiwania stringów Boyera-Moore'a. Znajduje to wszystkie wystąpienia P   w T i zawiera wiele sposobów wstępnego przetwarzania wzorca w celu określenia optymalnej  wielkości przesunięcia łańcucha i pominięcia porównań. W praktyce działa w   czasie O(m) (a nawet podliniowym), gdzie m jest długością T. Ta implementacja przeprowadza  wyszukiwanie bez rozróżniania wielkości liter na znakach alfabetu ASCII, bez spacji.  """  if  len  (  P  )  ==  lub  len  (  T  )  ==  lub  len  (  T  )  <  len  (  P  ):  return  []  pasuje  =  []  # Przetwarzanie wstępne  R  =  tablica_złych_znaków  (  P  )  L  =  tabela_dobrych sufiksów  (  P  )  F  =  full_shift_table  (  P  )  k  =  len  (  P  )  -  1  # Reprezentuje wyrównanie końca P względem T  poprzedni_k  =  -  1  # Reprezentuje wyrównanie w poprzedniej fazie (reguła Galila),  podczas gdy  k  <  len  (  T  ):  i  =  len  (  P  )  -  1  # Znak do porównania w P  h  =  k  # Znak do porównania w T  podczas gdy  i  >=  i  h  >  poprzedni_k  i  P  [  i  ]  ==  T  [  h  ]:  # Dopasowania zaczynające się od końca P  i  -=  1  h  -=  1  if  i  ==  -  1  lub  h  ==  poprzedni_k  :  # Znaleziono dopasowanie (reguła Galila)  pasuje  .append  (  k  -  len  (  P  )  +  1  )  k  +  =  len  (  P  )  -  F  [  1  ]  if  len  (  P  )  >  1  else  1  else  :  # Brak dopasowania, przesunięcie o maksimum złego znaku i zasady dobrego sufiksu  char_shift  =  i  -  R  [  index_alfabetu  (  T  [  h  ])][  i  ]  if  i  +  1  ==  len  (  P  ):  # Niezgodność wystąpiła przy pierwszej próbie  suffix_shift  =  1  elif  L  [  i  +  1  ]  ==  -  1  :  # Dopasowany sufiks nie pojawia się nigdzie w P  suffix_shift  =  len  (  P  )  -  F  [  i  +  1  ]  else  :  # Dopasowany sufiks występuje w P  sufiks_przesunięcie  =  len  (  P  )  -  1  -  L  [  i  +  1  ]  przesunięcie  =  max  (  przesunięcie_ znaku  ,  przesunięcie_ przyrostka  )  poprzedni_k  =  k  jeśli  przesunięcie  >=  i  +  1  inaczej  poprzedni_k  # Reguła Galila  k  +=  przesunięcie  powrót  pasuje 

Implementacja C

 
 
 
 
 


















       
      0     
          
    
      0     
            
    




       
         
    
    
        0     
            
             
        
    
     




       
     
    
    
       0        
     






































       
     
       

    
      0  
            
              
        
              
    

    
     0     
             
                
                    
        
    




          
     
      
      
      

    
       0 
         
    

                 
        
              
           0     
            
            
        
           0 
             
        

            
          
    
     
 #include  <stdint.h>  #include  <stddef.h>  #include  <stdbool.h>  #include  <stdlib.h>  #include  <unistd.h>  #define ALPHABET_LEN 256  #define max(a, b) ((a < b) ? b : a)  // ZASADA ZŁEGO CHARAKTERU.  // tabela delta1: delta1[c] zawiera odległość między ostatnim  // znakiem pat a najbardziej wysuniętym na prawo wystąpieniem c w pat.  //  // Jeśli c nie występuje w pat, to delta1[c] = patlen.  // Jeśli c jest w punkcie string[i] i c != pat[patlen-1], możemy bezpiecznie przesunąć i //  o delta1[c], czyli minimalną odległość potrzebną do przesunięcia  // pat do przodu w celu uzyskania łańcucha [i] ułożony w jednej linii z jakąś postacią w pat.  // c == pat[patlen-1] zwracanie zera jest problemem tylko dla BMH, który  // nie ma delta2. W takim przypadku BMH opatentowuje wartość.   // Podążamy za tym wyborem zamiast oryginalnego 0, ponieważ pomija  // więcej. (poprawność?)   //  // Ten algorytm działa w czasie alfabetu_len+patlen.  void  make_delta1  (  ptrdiff_t  *  delta1  ,  uint8_t  *  pat  ,  size_t  patlen  )  {  for  (  int  i  =  ;  i  <  DŁUG_ALFABETU  ;  i  ++  )  {  delta1  [  i  ]  =  patlen  ;  }  for  (  int  ja  =  ;  ja  <  patlen  ;  i  ++  )  {  delta1  [  pat  [  i  ]]  =  patlen  -1  -  i  ;  }  }  // prawda, jeśli sufiks słowa zaczynający się od word[pos] jest przedrostkiem  // słowa  bool  is_prefix  (  uint8_t  *  word  ,  size_t  wordlen  ,  ptrdiff_t  poz  )  {  int  suffixlen  =  wordlen  -  pos  ;  // tutaj również można użyć funkcji bibliotecznej strncmp()  // return ! strncmp(słowo, &słowo[pos], suffixlen);   for  (  int  i  =  ;  i  <  przyrostek  ;  i  ++  )  {  if  (  słowo  [  i  ]  ! =  słowo  [  poz  +  i  ])  {  return  false  ;  }  }  zwróć  prawdę  ;  }  // długość najdłuższego sufiksu słowa kończącego się na słowie [pos].  // suffix_length("dddbcabc", 8, 4) = 2  size_t  suffix_length  (  uint8_t  *  słowo  ,  size_t  wordlen  ,  ptrdiff_t  poz  )  {  size_t  i  ;  // zwiększanie długości sufiksu i do pierwszego niezgodności lub początku  // słowa  for  (  i  =  ;  (  słowo  [  poz  -  i  ]  ==  słowo  [  słowo len  -1  -  i  ])  &&  (  i  <=  poz  );  i  + +  );  zwróć  ja  ;  }  // DOBRA ZASADA SUFIKSÓW.  // tabela delta2: biorąc pod uwagę niezgodność w pat[pos], chcemy wyrównać  // z następnym możliwym pełnym dopasowaniem, może być oparte na tym, co // wiemy  o pat[pos+1] do pat[patlen-1].  //  // W przypadku 1:  // pat[pos+1] do pat[patlen-1] nie występuje gdzie indziej w pat,  // następne prawdopodobne dopasowanie rozpoczyna się w momencie niezgodności lub po niej.  // Jeśli w podłańcuchu pat[pos+1 .. patlen-1] znajduje się przedrostek  // pat, następne prawdopodobne dopasowanie jest tutaj (jeśli  w podłańcuchu jest wiele // prefiksów, wybierz najdłuższy). W przeciwnym razie   // następne prawdopodobne dopasowanie rozpoczyna się za znakiem wyrównanym do  // pat[patlen-1].  //  // W przypadku 2:  // pat[pos+1] do pat[patlen-1] występuje gdzie indziej w pat. //  niezgodność   mówi nam, że nie patrzymy na koniec dopasowania.  // Możemy jednak patrzeć na środek meczu.  //  // Pierwsza pętla, która zajmuje się przypadkiem 1, jest analogiczna  // do tablicy KMP, dostosowana do kolejności skanowania „wstecz” z  // dodatkowym ograniczeniem, że wszystkie podłańcuchy, które uważa za  potencjalne // prefiksy, to wszystkie przyrostki. W najgorszym przypadku   // pat składa się z powtórzeń tej samej litery, więc każdy sufiks jest  // prefiksem. Jednak sama ta pętla nie wystarczy:   // Załóżmy, że pat to "ABYXCDBYX", a tekst to ".....ABYXCDEYX".  // Dopasujemy X, Y i znajdziemy B != E.  W sufiksie „YX” nie ma przedrostka pat //, więc pierwsza pętla każe nam przeskoczyć  // do przodu o 9 znaków.  // Chociaż z pozoru podobna do tablicy KMP, tablica KMP  // opiera się na informacjach o początku częściowego dopasowania  , // których algorytm BM nie posiada.  //  // Druga pętla odnosi się do przypadku 2. Ponieważ suffix_length może nie być  // unikalny, chcemy wziąć minimalną wartość, która powie nam  // jak daleko znajduje się najbliższe potencjalne dopasowanie.  void  make_delta2  (  ptrdiff_t  *  delta2  ,  uint8_t  *  pat  ,  size_t  patlen  )  {  ssize_t  p  ;  size_t  last_prefix_index  =  1  ;  // pierwsza pętla  for  (  p  =  patlen  -1  ;  p  >=  ;  p  --  )  {  if  (  is_prefix  (  pat  ,  patlen  ,  p  +  1  ))  {  last_prefix_index  =  p  +  1  ;  }  delta2  [  p  ]  =  ostatni_przedrostek_indeks  +  (  patlen  -1  -  p  );  }  // druga pętla  for  (  p  =  ;  p  <  patlen  -1  ;  p  ++  )  {  size_t  slen  =  suffix_length  (  pat  ,  patlen  ,  p  );  if  (  pat  [  p  -  slen  ]  !=  pat  [  patlen  -1  -  slen  ])  {  delta2  [  patlen  -1  -  slen  ]  =  patlen  -1  -  p  +  slen  ;  }  }  }  // Zwraca wskaźnik do pierwszego dopasowania.  // Zobacz także glibc memmem() (nie-BM) i std::boyer_moore_searcher (pierwsze dopasowanie).  uint8_t  *  boyer_moore  (  uint8_t  *  string  ,  size_t  stringlen  ,  uint8_t  *  pat  ,  size_t  patlen  )  {  ptrdiff_t  delta1  [  ALPHABET_LEN  ];  ptrdiff_t  delta2  [  wzór  ];  // C99 VLA  make_delta1  (  delta1  ,  pat  ,  patlen  );  make_delta2  (  delta2  ,  pat  ,  patlen  );  // Pusty wzorzec musi być szczególnie brany pod uwagę  if  (  patlen  ==  )  {  return  string  ;  }  size_t  i  =  patlen  -  1  ;  // str-idx  while  (  i  <  stringlen  )  {  ptrdiff_t  j  =  patlen  -  1  ;  // pat-idx  while  (  j  >=  &&  (  string  [  i  ]  ==  pat  [  j  ]))  {  --  i  ;  --  j  ;  }  if  (  j  <  )  {  return  &  string  [  i  +  1  ];  }  ptrdiff_t  przesunięcie  =  max  (  delta1  [  łańcuch  [  i  ]],  delta2  [  j  ]);  ja  +=  przesunięcie  ;  }  zwróć  NULL  ;  } 

Implementacja Javy

    









           
           0 
             0
        
           
           
                   
                       
                   0 
                     
                
            
            
                   
        
         
    

    


         
               
            
            0     
              
        
            0     
                  
        
         
    

    



         
            
           
               0  
               
                  
            
                    
        
            0       
                
                    
        
         
    

    


           
               0      
                
                 
            
        
         
    

    



           
           0
                 
                   0       
              
        
         
     /**  * Zwraca indeks pierwszego wystąpienia  * podanego podłańcucha w tym łańcuchu. Jeśli nie jest to podłańcuch, zwróć -1.   *  * Galil nie istnieje, ponieważ generuje tylko jedno dopasowanie.  *  * @param stogu siana Ciąg znaków do przeskanowania  * @param needle Ciąg docelowy do wyszukania  * @return Indeks początkowy podłańcucha  */  public  static  int  indexOf  (  char  []  stogu siana  ,  char  []  igła  )  {  if  (  igła  .  długość  ==  )  {  powrót  ;  }  int  charTable  []  =  makeCharTable  (  igła  );  int  offsetTable  []  =  makeOffsetTable  (  igła  );  for  (  int  i  =  igła  .  długość  -  1  ,  j  ;  i  <  stóg siana  .  długość  ;)  {  for  (  j  =  igła  .  długość  -  1  ;  igła  [  j  ]  ==  stóg siana  [  i  ]  ;  --  i  ,  --  j  )  {  jeśli  (  j  ==  )  {  zwróć  ja  ;  }  }  // i += igła.długość - j; // Dla metody naiwnej   i  +=  Math  .  max  (  offsetTable  [  igła  .  długość  -  1  -  j  ]  ,  charTable  [  stóg siana  [  i  ]]  );  }  powrót  -  1  ;  }  /**  * Tworzy tabelę przeskoków na podstawie informacji o niedopasowanych znakach.  */  private  static  int  []  makeCharTable  (  char  []  igła  )  {  final  int  ALPHABET_SIZE  =  Znak  .  MAKS_WARTOŚĆ  +  1  ;  // 65536  int  []  table  =  new  int  [  ALPHABET_SIZE  ]  ;  for  (  int  ja  =  ;  i  <  tabela  .  długość  ;  ++  ja  )  {  tabela  [  i  ]  =  igła  .  długość  ;  }  for  (  int  i  =  ;  i  <  igła  .  długość  ;  ++  i  )  {  table  [  igła  [  i  ]]  =  igła  .  długość  -  1  -  i  ;  }  zwróć  tabelę  ;  }  /**  * Tworzy tabelę przeskoków na podstawie przesunięcia skanowania, w którym występuje niezgodność.  * (zasada złego znaku).  */  private  static  int  []  makeOffsetTable  (  char  []  igła  )  {  int  []  table  =  new  int  [  igła  .  długość  ]  ;  int  lastPrefixPosition  =  igła  .  długość  ;  for  (  int  i  =  igła  .  długość  ;  i  >  ;  --  i  )  {  if  (  isPrefix  (  igła  ,  i  ))  {  lastPrefixPosition  =  i  ;  }  tabela  [  igła  .  długość  -  i  ]  =  lastPrefixPosition  -  i  +  igła  .  długość  ;  }  for  (  int  i  =  ;  i  <  igła  .  długość  -  1  ;  ++  i  )  {  int  slen  =  przyrostek Długość  (  igła  ,  i  );  table  [  slen  ]  =  igła  .  długość  -  1  -  i  +  slen  ;  }  zwróć  tabelę  ;  }  /**  * Czy igła[p:koniec] jest przedrostkiem igły?  */  private  static  boolean  isPrefix  (  char  []  igła  ,  int  p  )  {  for  (  int  i  =  p  ,  j  =  ;  i  <  igła  .  długość  ;  ++  i  ,  ++  j  )  {  if  (  igła  [  i  ]  ! =  igła  [  j  ]  )  {  zwróć  fałsz  ;  }  }  zwróć  prawdę  ;  }  /**  * Zwraca maksymalną długość podłańcucha kończącego się na p i jest sufiksem.  * (dobra reguła sufiksu)  */  private  static  int  suffixLength  (  char  []  needle  ,  int  p  )  {  int  len  ​​=  ;  for  (  int  i  =  p  ,  j  =  igła  .  długość  -  1  ;  i  >=  &&  igła  [  i  ]  ==  igła  [  j  ]  ;  --  i  ,  --  j  )  {  len  +=  1  ;  }  powrót  długość  ;  } 

Warianty

Boyera – Moore'a – Horspoola jest uproszczeniem algorytmu Boyera – Moore'a, wykorzystującym tylko regułę złego znaku.

Algorytm Apostolico – Giancarlo przyspiesza proces sprawdzania, czy w danym dopasowaniu wystąpiło dopasowanie, pomijając wyraźne porównania znaków. Wykorzystuje to informacje zebrane podczas wstępnego przetwarzania wzorca w połączeniu z długościami dopasowania sufiksów rejestrowanymi przy każdej próbie dopasowania. Przechowywanie długości dopasowań sufiksów wymaga dodatkowej tabeli o rozmiarze odpowiadającym wyszukiwanemu tekstowi.

Algorytm Raita poprawia wydajność algorytmu Boyera-Moore'a-Horspoola. Schemat wyszukiwania poszczególnych podłańcuchów w danym łańcuchu różni się od algorytmu Boyera-Moore'a-Horspoola.

Linki zewnętrzne

• Oryginalny artykuł na temat algorytmu Boyera-Moore'a
• Przykład algorytmu Boyera-Moore'a ze strony domowej J. Strothera Moore'a , współtwórcy algorytmu
• Artykuł Richarda Cole'a z 1991 r. Dowodzący liniowości czasu wykonywania