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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie wzorca algorytmem Karpa-Rabina

SPIS TREŚCI W KONSERWACJI
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 (n2). W algorytmie Karpa-Rabina postępujemy nieco inaczej. Najpierw odwzorowujemy poszukiwany wzorzec p w liczbę całkowitą Hp 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ą Hs. Porównujemy ze sobą liczby Hp i Hs. 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ę Hs porównujemy z haszem wzorca Hp. 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 × 34 + 1 × 3 3 + 1 × 32 + 0 × 31 + 1 × 30) 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 = 34 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 × 34 + 1 × 3 3 + 0 × 32 + 1 × 31 + 1 × 30) 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
Hp  :  hasz wzorca
Hs  :  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: Hp ← h (p) obliczamy hasz wzorca
K04: Hs ← h (s [0:m]) obliczamy hasz okna
K05: i ← 0 ustawiamy pozycję okna
K06: Jeśli Hs ≠ Hp,
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 Hs
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 × 33 + c × 32 + c × 31 + c × 30,
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 <ctime>

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(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
©2024 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.