ALGORYTMY

TEKSTOWE

WYSZUKIWANIE WZORCA



Sprawdź czy wzorzec

P

występuje w tekście

T

DANE :

T , P





* ,



- skończony zbiór (alfabet)

( T - tekst , P - wzorzec ).



Znajdź wzorzec

P

w tekście

T



Znajdź wszystkie wystąpienia wzorca

P

w tekście

T



Policz ile razy występuje wzorzec

P

w tekście

T



Zamień wszystkie wystąpienia słowa (tekstu)

P

na słowo

(tekst)

P’

w tekście

T

RABIN-KARP-MATCHER (T ,P, 10);

{ Alfabet = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
T[1..n] - tekst, P[1..m] - wzorzec;
Dla “niedużych” P , sprawdza czy P występuje w T }

begin

h := 10

m-1

;

p := 0 ;
t := 0 ;

for i := 1 to m do
begin
p := (10 * p +
P[i]);
t := (10 * t +
T[i]);
end;

for s := 0 to n-m do

begin
if p = t then
write (

“

Wzorzec występuje z

przesunięciem

”

, s);

if s < n-m
then t := 10 * (t – T[s+1] * h ) +
T[s+m+1];
end;

end;

RABIN-KARP-MATCHER (T,P,d,q);

{ Alfabet = {0, 1, ..., d }
T[1..n] - tekst, P[1..m] - wzorzec.
Sprawdza czy P występuje w T }

begin
h := d

m-1

mod q ;

p := 0 ;
t := 0 ;

for i := 1 to m do
begin

p :=(d * p + P[i])

mod q;
t := (d * t + T[i])
mod q;
end;

for s := 0 to n-m do

begin
if p = t then
if P[1..m] = T[s+1..s+m]
then
write (

“

Wzorzec

występuje
z przesunięciem

”

, s);
if s < n-m then

t := (d * (t – T[s+1] * h ) +
T[s+m+1] )
mod q;

end;
end;

KODOWANIE

PRZYKŁAD



Sortowanie

niemalejąco wdług f

T

(lub kolejka
priorytetowa)

DANE :



= { A, B, C, D, E, F } A B C D

E F
T





* ,

f

T

:T N f

T

45 13 12 16

9 5

WYNIK

: Optymalny kod prefiksowy , tzn.:

K :



{0,1}* taki, że K(T) ma najmniejszy

rozmiar



Połącz 2 węzły o

najmniejszej
wartości f

T.

(mniejsza z lewej,

większa z prawej)



Utwórz nowy węzeł o

wartości f

T

równej sumie.



Przesuń we "właściwe"

miejsce
(lub przywróć własność
kolejki
priorytetowej )

Po wykonaniu powyższych
czynności

Powtarzaj :

HUFFMAN (, f);

{

Tworzy regularne drzewo binarne

reprezentujące optymalny kod prefiksowy

}

begin

n := ||;

Q := ;

{Kolejka priorytetowa:
(a) f(a) jest

kluczem}

for i := 1 to n-1 do

begin
New(w);
x := EXTRACT-MIN(Q);
y := EXTRACT-MIN(Q);
w.left := x;
w.right := y;
w.f := x.f + y.f;
INSERT(Q,w);
end;
return EXTRACT-MIN(Q);
{zwraca korzeń
drzewa}
end;

T(n) = O(n log n)