Wyszukiwanie wzorca algorytmem Karpa-Rabina


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem

 

Problem

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


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 × 33 + 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 × 33 + 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.

Elementy 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 K08 ; sprawdzamy równość haszy
K07: Jeśli p = s[i:i+m], przetwarzaj i ; znaleziono wzorzec p w s na pozycji i-tej
K08: ii + 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 K06 ; kontynuujemy pętlę

 

Program

Ważne:

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 80 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 typie int, zrezygnowaliśmy z arytmetyki modulo.

 

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

program prg;

const
  N  = 80;  // 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

  write(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.
Code::Blocks
// Wyszukiwanie wzorca algorytmem KR
// Data:  4.07.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

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

using namespace std;

const int N  = 80;  // 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;
  
  // 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;
}
Free Basic
' Wyszukiwanie wzorca algorytmem KR
' Data:  4.07.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Const N  = 80  ' 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
CCABABABCBBBCAABCBCCAAAAACBABAABCABBBCCCCBCABACBBBBAABCBABCBACCACBBBABCBAAABBBAB
     ^                                                 ^           ^

 

Wyszukiwanie wzorca algorytmem KR
(C)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.