NAIVNÍ ALGORITMUS POROVNÁNÍ

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
V nejhorším případě je časová složitost naivního porovnávacího algoritmu O(N**2).

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
 

NAIVE_STRING_MATCHER:
procedure expose T. P.
parse arg M, N
do S = 0 to N - M + 1
  do J = 1 to M
    SpJ = S + J
    if P.J <> T.SpJ then iterate S
  end
  say "Vzorek se nachází s posunutím" S
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.