Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
ProblemW łańcuchu s należy 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 ( 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.
Kolejne pozycje wystąpień wzorca w łańcuchu.
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 |
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ę |
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, 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 ^ ^ ^ |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 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.