Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie wzorca algorytmem Karpa-Rabina

SPIS TREŚCI
Tematy pomocnicze

Problem

W łańcuchu s  należy wyznaczyć wszystkie wystąpienia wzorca p.

Rozwiązanie

W celu znalezienia wzorca p  w łańcuchu s  algorytm naiwny porównuje każdorazowo zawartość okna wzorca ze wzorcem. Prowadzi to do kwadratowej klasy złożoności obliczeniowej O ( n 2 ). W algorytmie Karpa-Rabina postępujemy nieco inaczej. Najpierw odwzorowujemy poszukiwany wzorzec p  w liczbę całkowitą H p  za pomocą tzw. funkcji haszującej ( ang. hash function ). Funkcja haszująca posiada taką własność, iż identyczne łańcuchy znakowe odwzorowuje w identyczne liczby – hasze. Następnie ustawiamy okno wzorca na początku tekstu i haszujemy je przy pomocy tej samej funkcji w liczbę całkowitą H s. Porównujemy ze sobą liczby H p  i H s. Jeśli są równe, to oznacza to, iż wzorzec i jego okno są do siebie podobne z dokładnością do haszów. Aby mieć pewność, iż są identyczne, sprawdzamy je znak po znaku, podobnie jak w algorytmie naiwnym, lecz teraz nie wykonujemy tego każdorazowo, tylko wtedy, gdy jest zgodność haszy. Jeśli hasze nie są zgodne ( lub chcemy znaleźć następne wystąpienia wzorca ), to okno wzorca przesuwamy o jedną pozycję w obrębie łańcucha s, ponownie haszujemy zawartość okna i otrzymaną nową liczbę H s  porównujemy z haszem wzorca H p. Zatem cała procedura się powtarza. Gdy okno wzorca wyjdzie poza łańcuch, przeszukiwanie przerywamy.

Funkcja haszująca najczęściej traktuje przetwarzany łańcuch tekstu jak liczbę, zapisaną przy wybranej podstawie ( zwykle podstawa jest równa rozmiarowi alfabetu ). Kolejne znaki tekstu są traktowane jak cyfry tej liczby. Dodatkowo w celu uniknięcia zbyt dużych wartości haszu stosowana jest arytmetyka modularna – wyniki wszystkich działań są sprowadzane do reszty z dzielenia przez wybrany moduł, który jest liczbą pierwszą. Aby zrozumieć zasadę wyznaczania haszu, przyjrzyjmy się prostemu przykładowi.

Przykład:

Alfabet składa się z trzech liter: A, B i C.
Wyznaczyć hasz dla tekstu:  "CBBAB".

Jako bazę systemu liczbowego przyjmiemy 3, ponieważ z tylu liter składa się alfabet. Cyfry posiadają wartości: A = 0, B = 1 i C = 2. Jako moduł przyjmiemy liczbę pierwszą 23. Wtedy:

H [ CBBAB ] = ( 2 × 3 4 + 1 × 3 3 + 1 × 3 2 + 0 × 3 1 + 1 × 3 0 ) mod 23
H [ CBBAB ] = ( 2 × 81 + 1 × 27 + 1 × 9 + 0 × 3 + 1 × 1 ) mod 23
H [ CBBAB ] = ( 162 + 27 + 9 + 0 + 1 ) mod 23
H [ CBBAB ] = 199 mod 23
H [ CBBAB ] = 15

Funkcja haszująca powinna być tak dobrana, aby w prosty sposób można było wyznaczyć hasz okna wzorca po przesunięciu o jedną pozycję w obrębie przeszukiwanego łańcucha s. Podana w poprzednim przykładzie funkcja spełnia ten warunek.

Przykład:

Tekst ma postać "CBBABB". Wyznaczyliśmy hasz pierwszych pięciu liter, czyli H [ CBBAB ] = 15. Teraz przesuwamy okno o jedną pozycję w prawo. Okno zawiera tekst "BBABB". Wyznaczymy H [ BBABC ] na podstawie poprzednio wyznaczonego haszu H [ CBBAB ] .

Najpierw pozbywamy się z haszu najstarszej cyfry, czyli C = 2. W tym celu wyznaczamy mnożnik d  = 3 4 mod 23 = 12. Od haszu H [ CBBAB ] odejmujemy modularnie iloczyn d  i cyfry C:

H = ( H [ CBBAB ] - d  × 2 ) mod 23
H = ( 15 - 12 × 2 ) mod 23
H = ( -9 ) mod 23
H = 14

Teraz otrzymany hasz H mnożymy modularnie przez 3 – spowoduje to przesunięcie w nim wszystkich cyfr o jedną pozycję w lewo:

H = ( H × 3 ) mod 23
H = ( 14 × 3 ) mod 23
H = 42 mod 23
H = 19

Na koniec do haszu H dodajemy modularnie nową cyfrę B:

H = ( H + 1 ) mod 23
H = ( 19 + 1 ) mod 23
H = 20 mod 23
H = 20

Sprawdźmy, czy otrzymaliśmy H [ BBABB ]:

H [ BBABB ] = ( 1 × 3 4 + 1 × 3 3 + 0 × 3 2 + 1 × 3 1 + 1 × 3 0 ) mod 23
H [ BBABB ] = ( 81 + 27 + 0 + 3 + 1 ) mod 23
H [ BBABB ] = 112 mod 23
H [ BBABB ] = 20 = H

Zwróć uwagę, iż wyznaczenie haszu okna po przesunięciu wymaga stałej liczby operacji, zatem jest wykonywane w czasie stałym O ( 1 ). Co więcej, operacje dodawania i odejmowania można z powodzeniem zastąpić operacją logiczną xor, mnożenie przesunięciami bitów, a operację modulo obcinaniem bitowym wyniku do długości słowa maszynowego – np do 32 bitów. Rozstrzygnięcie tych kwestii pozostawiamy już konkretnej implementacji algorytmu Karpa-Rabina.

Moduł powinien być względnie dużą liczbą, aby ograniczyć liczbę fałszywych zgodności haszów wzorca i jego okna.

Typowo algorytm Karpa-Rabina pracuje w liniowej klasie złożoności obliczeniowej O ( m + n  ), zatem dla długich tekstów ma on zdecydowaną przewagę nad algorytmem naiwnym.

Algorytm Karpa-Rabina wyszukiwania wzorca

Wejście:

s  – przeszukiwany łańcuch
p  – poszukiwany wzorzec

Wyjście:

Kolejne pozycje wystąpień wzorca w łańcuchu.

Zmienne pomocnicze:

i  –  położenie okna wzorca p  w przeszukiwanym łańcuchu s, i  ∈ N
m  – długość wzorca p, m  ∈ N
n  – długość łańcucha s, n  ∈ N
H p  – hasz wzorca
H s  – hasz okna wzorca
h ( x )  – wybrana funkcja haszująca

Lista kroków:

K01: m  ← | p | obliczamy liczbę znaków wzorca
K02: n  ← | s | oraz liczbę znaków łańcucha
K03: H p  ← h ( p  ) obliczamy hasz wzorca
K04: H s  ← h ( s [ 0:m  ] ) obliczamy hasz okna
K05: i  ← 0 ustawiamy pozycję okna
K06: Jeśli H s  ≠ H p,
to idź do kroku K08
sprawdzamy równość haszy
K07: Jeśli p  = s [ i : i + m  ],
to przetwarzaj i
znaleziono wzorzec p w s na pozycji i-tej
K08: i  ← i  + 1 przesuń okno wzorca o jedną pozycję w prawo w łańcuchu s
K09: Jeśli i  = n  - m,
to zakończ
koniec łańcucha?
K10: Oblicz nowe H s
dla s [ i:i+m  ]
wyznaczamy hasz przesuniętego okna, wykorzystując poprzedni hasz
K11: Idź do kroku K06 kontynuujemy pętlę

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program generuje 79 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A, B i C oraz 4 znakowy wzorzec wg tego samego schematu. Funkcja haszująca ma postać:

h ( s  ) = c  × 3 3 + c  × 3 2 + c  × 3 1 + c  × 3 0,
gdzie c  oznacza cyfrę trójkową uzyskaną z liter łańcucha przez odjęcie od ich kodu liczby 65.

Ponieważ 4 cyfrowa liczba trójkowa posiada największą wartość 2222 ( 3 ) = 80 ( 10 ) i mieści się bez problemu w 32 bitowym typie całkowitym, zrezygnowaliśmy z arytmetyki modulo.

Pascal
// Wyszukiwanie wzorca algorytmem KR
// Data:  4.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const
  N  = 79;  // długość łańcucha s
  M  =  4;  // długość wzorca p
  zp = 65;  // kod pierwszego znaku alfabetu
  zk = 67;  // kod ostatniego znaku alfabetu

// Funkcja obliczająca hasz dla łańcucha x
//----------------------------------------
function h ( x : ansistring ) : integer;
var
  i, hx : integer;
begin
  hx := 0;
  for i := 1 to M do
    hx := 3 * hx + ( ord ( x [ i ] ) - 65 );
  h := hx;
end;

var
  s, p : ansistring;
  pp, i, Hp, Hs : integer;

begin
  randomize;

  // generujemy łańcuch s

  s := '';
  for i := 1 to N do
    s := s + chr ( zp + random ( zk - zp + 1 ) );

  // generujemy wzorzec

  p := '';
  for i := 1 to M do
    p := p + chr ( zp + random ( zk - zp + 1 ) );

  // wypisujemy wzorzec

  writeln ( p );

  // wypisujemy łańcuch

  writeln ( s );

  // obliczamy hasz wzorca

  Hp := h ( p );

  // obliczamy hasz okna wzorca

  Hs := h ( s );

  // szukamy pozycji wzorca w łańcuchu

  pp := 1; i := 1;

  while true do
  begin
    if( Hp = Hs ) and ( p = copy ( s, i, M ) ) then
    begin
       while pp < i do
       begin
         write ( ' ' ); inc ( pp );
       end;
       write ( '^' ); inc ( pp );
    end;
    inc ( i );
    if i = N - M + 2 then break;
    Hs := ( Hs- ( ord ( s [ i-1 ] )-65 )*27 )*3+ord ( s [ i+M-1 ] )-65;
  end;
  writeln;
end.
C++
// Wyszukiwanie wzorca algorytmem KR
// Data:  4.07.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N  = 79;  // długość łańcucha s
const int M  =  4;  // długość wzorca p
const int zp = 65;  // kod pierwszego znaku alfabetu
const int zk = 67;  // kod ostatniego znaku alfabetu

// Funkcja obliczająca hasz dla łańcucha x
//----------------------------------------
int h ( string & x )
{
  int i, hx;

  hx = 0;
  for( i = 0; i < M; i++ )
    hx = 3 * hx + ( x [ i ] - 65 );
  return hx;
}

int main( )
{

  string s, p;
  int pp, i, Hp, Hs;

  srand ( ( unsigned )time ( NULL ) );

  // generujemy łańcuch s

  s = "";
  for( i = 0; i < N; i++ )
    s += zp + rand( ) % ( zk - zp + 1 );

  // generujemy wzorzec p

  p = "";
  for( i = 0; i < M; i++ )
    p += zp + rand( ) % ( zk - zp + 1 );

  // wypisujemy wzorzec

  cout << p << endl;

  // wypisujemy łańcuch

  cout << s << endl;
  
  // obliczamy hasz wzorca

  Hp = h ( p );

  // obliczamy hasz okna wzorca

  Hs = h ( s );

  // szukamy pozycji wzorca w łańcuchu

  pp = i = 0;

  while( true )
  {
    if( ( Hp == Hs ) && ( p == s.substr ( i, M ) ) )
    {
      while( pp < i )
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
    }
    i++;
    if( i == N - M ) break;
    Hs = ( Hs - ( s [ i - 1 ] - 65 ) * 27 ) * 3 + s [ i + M - 1 ] - 65;
  }
  cout << endl;
  return 0;
}
Basic
' Wyszukiwanie wzorca algorytmem KR
' Data:  4.07.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Const N  = 79  ' długość łańcucha s
Const M  =  4  ' długość wzorca p
Const zp = 65  ' kod pierwszego znaku alfabetu
Const zk = 67  ' kod ostatniego znaku alfabetu

' Funkcja obliczająca hasz dla łańcucha x
'----------------------------------------
Function h ( Byref x As String ) As Integer

  Dim As Integer i, hx

  hx = 0
  For i = 1 To M
    hx = 3 * hx + Asc ( Mid ( x, i, 1 ) ) - 65
  Next
  h = hx
End Function

Dim As String s, p
Dim As Integer pp, i, Hp, Hs

Randomize

' generujemy łańcuch s

s = ""
For i = 1 To N: s += Chr ( zp + Cint ( Rnd * ( zk - zp ) ) ): Next

' generujemy wzorzec p

p = ""
For i = 1 To M: p += Chr ( zp + Cint ( Rnd * ( zk - zp ) ) ): Next

' wypisujemy wzorzec

Print p

' wypisujemy łańcuch

Print s

' obliczamy hasz wzorca

Hp = h ( p )

' obliczamy hasz okna wzorca

Hs = h ( s )

' szukamy pozycji wzorca w łańcuchu

pp = 1: i = 1

Do
  if( Hp = Hs ) And ( p = Mid ( s, i, M ) ) Then
    While pp < i
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
  End If
  i += 1
  If i = N - M + 2 Then Exit Do
  Hs = ( Hs- ( Asc ( Mid ( s, i-1, 1 ) )-65 )*27 )*3+Asc ( Mid ( s, i+M-1, 1 ) )-65
Loop
Print
End
Wynik:
BABC
CCABABABCBBBCAABCBCCAAAAACBABAABCABBBCCCCBCABACBBBBAABCBABCBACCACBBBABCBAAABBBA
     ^                                                 ^           ^
Wyszukiwanie wzorca algorytmem KR
(C)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.