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)