ALGORITMUS KNUTHA-MORRISE-PRATTA

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 Knutha-Morrise-Pratta má časovou složitost v průměrném i v nejhorším případě O(M+N).

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ů
 
Parametry: přirozené číslo N - počet prvků T., přirozené číslo M - počet prvků P.
 
Výstup: Pro všechna nalezená posunutí zobrazí Vzorek se nachází s posunutím S
 

KMP_MATCHER: procedure expose T. P.
parse arg M, N
call COMPUTE_PREFIX_FUNCTION M
Q = 0
do I = 1 to N
  Qp1=Q + 1
  do while Q > 0 & P.Qp1 <> T.I
    Q = Pi.Q; Qp1 = Q + 1
  end
  if P.Qp1 = T.I then Q = Q + 1
  if Q = M
    then do
      say "Vzorek se nachází s posunutím" I - M
      Q = Pi.Q
    end
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
  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 3. října 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.