ALGORITMUS BOYERA-MOORA

PROBLÉM
Text je pole T.1,T.2,...,T.N a vzorek je pole P.1,P.2,...,P.M. Prvky P. a T. jsou znaky konečné abecedy Sigma., Sigma. je pole R prvků. Řekneme, že vzorek P. se nachází v textu T. s posunutím S, jestliže 0<=S<=N-M a T.SpJ=P.J, kde SpJ označuje S+J, pro J=1,...,M. Problém porovnání řetězců spočívá v nalezení všech těchto posunutí.

ALGORITMUS
Algoritmus Boyera-Moora byl objeven Robertem S. Boyerem and J. Strotherem Moorem. V nejhorším případě je jeho časová složitost O((N-M+1)*M+R).

PRAXE
Jsou-li text i vzorek skutečné řetězce znaků, pak nejrychlejší řešení nabízí REAL_STRING_MATCHER. V obecném případě tu není jednoznačný vítěz a nejlépe uděláme, když si podprogramy otestujeme na typických datech. Uveďme si příklad, ve kterém M označuje počet prvků P., R označuje počet prvků Sigma. a S označuje počet objevených posunutí:

Doba běhu v sekundách pro N = 100000
Algoritmus M=10,R=1999,S=50 M=10,R=4,S=10000 M=100,R=4,S=10000
Naivní 16  25  150 
KMP 21  22  23 
Boyer-Moore 15  138 

IMPLEMENTACE
Jednotka: vnitřní podprogram
 
Globální proměnné: pole T.1,...,T.N řetězců, pole P.1,...,P.M řetězců, pole Sigma.1,...,Sigma.R řetězců
 
Parametry: přirozené číslo N - počet prvků T., přirozené číslo M - počet prvků P., přirozené číslo R - počet prvků Sigma.
 
Výstup: Pro všechna nalezená posunutí zobrazí Vzorek se nachází s posunutím S

 


BOYER_MOORE_MATCHER:
procedure expose T. P. Sigma.
parse arg M, N, R
call COMPUTE_LAST_OCCURENCE_FUNCTION M, R
call COMPUTE_GOOD_SUFFIX_FUNCTION M
S = 0
do while S <= N - M
  do J = M to 1 by -1
    SpJ = S + J
    if P.J <> T.SpJ then leave
  end
  if J = 0
    then do
      say "Vzorek se nachází s posunutím" S
      S = S + Gama.0
    end
    else do
      SpJ = S + J; TSpJ = T.SpJ
      S = S + MAX(Gama.J, J - Lambda.TSpJ)
    end
end
return
 
COMPUTE_LAST_OCCURENCE_FUNCTION:
procedure expose P. Lambda. Sigma.
parse arg M, R
do I = 1 to R
  SigmaI = Sigma.I; Lambda.SigmaI = 0
end
do J = 1 to M
  PJ = P.J; Lambda.PJ = J
end
return
 
COMPUTE_GOOD_SUFFIX_FUNCTION:
procedure expose Gama. P.
parse arg M
call COMPUTE_PREFIX_FUNCTION M
do I = 1 to M
  PuvPi.I = Pi.I; PuvP.I = P.I
end
do I = M to 1 by -1
  MmIp1 = M - I + 1; P.I = PuvP.MmIp1
end
call COMPUTE_PREFIX_FUNCTION M
do I = 1 to M; P.I = PuvP.I; end
do J = 0 to M
  Gama.J = M - PuvPi.M
end
do L = 1 to M
  J = M - Pi.L
  if Gama.J > L - Pi.L
    then Gama.J = L - Pi.L
end
return
 
COMPUTE_PREFIX_FUNCTION:
procedure expose Pi. P.
parse arg M
Pi.1 = 0; K = 0
do Q = 2 to M
  Kp1 = K + 1
  do while K > 0 & P.Kp1 <> P.Q
    K = Pi.K; Kp1 = K + 1
  end
  Kp1 = K + 1
  if P.Kp1 = P.Q then K = K + 1
  Pi.Q = K
end
return

 

SOUVISLOSTI

Literatura
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990


Obálka Obsah Index Hlavní stránka

změněno 1. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.