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 |
4 |
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
|
