Algorytm Karpa-Rabina

Algorytm Karpa-Rabina

Algorytm Karpa-Rabina to technika dopasowywania wzorca, która pozwala na znajdowanie określonego podciągu w danym tekście. Został opracowany w 1987 roku przez Michaela O. Rabina i Richarda Karpa.

Rozważmy wzorzec:

x[1…m]

(składający się z m znaków) oraz ciąg do przeszukania:

y[1…n]

(złożony z n znaków; przy czym n >= m). Problem polega na znalezieniu indeksu i, dla którego zachodzi równość:

y[i…i+m−1] = x[1…m].

W algorytmie Karpa-Rabina wykorzystywana jest funkcja mieszająca h. Algorytm przeszukuje wszystkie podciągi:

yi := y[i…i+m−1] dla i ∈ [1…n−m].

Bezpośrednie porównanie podciągu yi z x (które może być kosztowne) jest przeprowadzane tylko wtedy, gdy:

h(yi) = h(x).

Efektywność algorytmu zależy od konstrukcji funkcji mieszającej h – powinna istnieć funkcja N, która niskim kosztem wyznacza:

h(yi+1) na podstawie znanej już wartości h(yi).

W praktyce traktuje się tekst jako liczbę zapisaną w systemie o określonej podstawie (zwykle wykorzystując kody ASCII znaków).

Oczekiwana złożoność obliczeniowa to:

O(m + n).

Pseudokod (dane x, y, n, m):

Sx ← h(x[1…m])

Sy ← h(y[1…m])

for i ← 1 to n−m+1 do

begin

if Sx = Sy then

begin

porównaj ciąg x[1…m] z podciągiem y[i…i+m−1]

if wynik porównania prawdziwy then zwróć indeks i

end

Sy ← N(Sy, y[i+1], y[i+m])

end

Zastosowanie

Jednym z najprostszych zastosowań algorytmu Rabina-Karpa jest wykrywanie plagiatu. Przykładowo, gdy student pisze wypracowanie na temat „Pana Tadeusza”, profesor może porównać jego pracę z innymi opracowaniami na ten sam temat. Algorytm ten pozwala na identyfikację skopiowanych fragmentów. Aby przeciwdziałać próbą oszustwa przez niewielkie zmiany w tekście, algorytm może być skonfigurowany tak, aby ignorował szczegóły, takie jak znaki przestankowe, poprzez ich usunięcie lub wprowadzenie marginesu błędu przy porównywaniu skrótu tekstu ze wzorcem (ponieważ podobne ciągi znaków mają podobne skróty). W przypadku dużej liczby poszukiwanych ciągów, algorytmy pojedynczego wyszukiwania mogą być niepraktyczne.

Różne algorytmy poszukiwania ruchomych podciągów

Podstawowym celem algorytmu jest zlokalizowanie podciągu o długości m (wzoru) w tekście o długości n, na przykład odnalezienie słowa „zegar” w zdaniu: „Zegarmistrz wziął za naprawę 20 złotych.” Najprostszy algorytm realizuje to przez przeszukiwanie wszystkich możliwych podciągów.

1 function NaiveSearch(string s[1..n], string sub[1..m])

2 for i from 1 to n

3 for j from 1 to m

4 if s[i+j-1] ≠ sub[j]

5 jump to next iteration of outer loop

6 return i

7 return not found

Choć ten sposób działa w wielu przypadkach, w niektórych scenariuszach, np. przy poszukiwaniu tekstu składającego się z „b” oraz 10,000 „a” w ciągu składającym się z 10 milionów „a”, czas wykonania wynosi Θ(mn).

Algorytm Knutha-Pratta-Morrisa redukuje ten czas do Θ(n) dzięki prekomputacji, analizując każdy znak w tekście tylko raz. Algorytm Boyer-Moore’a przesuwa wskaźnik nie o 1, ale tak daleko, jak to możliwe, co zmniejsza liczbę iteracji w najlepszym przypadku do n/m. Algorytm Rabina-Karpa skupia się natomiast na przyspieszeniu działania linii kodu od 3 do 6.

Użycie funkcji skrótu do zmiennego przeszukiwania podciągu

Algorytm Rabina-Karpa wykorzystuje funkcję skrótu do przyspieszenia porównywania wzorca z podciągami w tekście. Funkcja skrótu przekształca każdy ciąg znaków na formę numeryczną – skrót (ang. hash). Algorytm opiera się na fakcie, że jeśli dwa teksty są równe, to ich skróty również muszą być równe. W przypadku odwrotnym, dwa różne teksty mogą mieć ten sam skrót, dlatego konieczne jest również porównanie tekstów.

1 function RabinKarp(string s[1..n], string sub[1..m])

2 hsub := hash(sub[1..m])

3 hs := hash(s[1..m])

4 for i from 1 to n

5 if hs = hsub

6 if s[i..i+m-1] = sub

7 return i

8 hs := hash(s[i+1..i+m])

9 return not found

Linie 2, 3, 6 i 8 wymagają Ω(m) czasu każda. Jednak linie 2 i 3 są realizowane tylko raz, a linia 6 uruchamiana jest wyłącznie w przypadku równości skrótów. Linia 5 wykonuje się n razy, ale zajmuje stały czas. Złożoność algorytmu może być negatywnie wpływana przez linię 8.

Jeśli wyliczymy skrót dla podciągu s[i+1…i+m] w sposób naiwny, zajmie to Ω(m) czasu, co oznacza, że ogólna złożoność algorytmu wyniesie Ω(mn). Kluczem jest wyliczenie aktualnego skrótu na podstawie skrótu z poprzedniej iteracji, co realizuje algorytm postępującego skrótu.

Najprostsza wersja tego algorytmu wyznacza wartość każdego znaku w podciągu, a następnie oblicza skrót według wzoru:

hs[i+1…i+m] = hs[i…i+m−1] − s[i] + s[i+m].

Ta funkcja skrótu nie ma jednak równomiernego rozkładu, co powoduje, że linia 6 jest wykonywana znacznie częściej w porównaniu do bardziej zaawansowanych algorytmów.

Funkcje skrótu będące w użyciu

Wydajność algorytmu Karpa-Rabina zależy od efektywnego obliczania wartości skrótu kolejnych podciągów tekstu. Jednym z efektywnych algorytmów postępującego skrótu traktuje podciągi jako liczby w systemie o określonej podstawie, zazwyczaj będącej dużą liczbą pierwszą. Na przykład dla podciągu „hi” wartość skrótu wynosi 104 * 101^1 + 105 * 101^0 = 10609 (gdzie kody ASCII dla h i i to odpowiednio 104 oraz 105). Główną zaletą tego sposobu hashowania jest możliwość wyznaczenia wartości skrótu kolejnego podciągu na podstawie wartości poprzedniego podciągu, wykonując stałą liczbę operacji niezależnych od długości tego podciągu.

Wielowzorcowe wyszukiwanie Rabina-Karpa

Algorytm Rabina-Karpa jest mniej efektywny w wyszukiwaniu pojedynczego wzorca w porównaniu do algorytmów takich jak Knutha-Morrisa-Pratta czy Boyer’a-Moore’a, ponieważ jest najwolniejszy w przypadku pesymistycznego ułożenia ciągu. Jednak w kontekście wielowzorcowego wyszukiwania nie ma sobie równych. Aby wyszukać w tekście wielokrotnie powtarzający się wzorzec, wystarczy stworzyć uproszczoną wersję algorytmu Rabina-Karpa, wykorzystującą filtr Blooma do sprawdzania, czy skrót analizowanego podciągu jest równy skrótowi poszukiwanego podciągu.

function RabinKarpSet(string s[1..n], set of string subs, m) {

set hsubs := emptySet

for each sub in subs

insert hash(sub[1..m]) into hsubs

hs := hash(s[1..m])

for i from 1 to n

if hs ∈ hsubs

if s[i..i+m-1] = a substring with hash hs

return i

hs := hash(s[i+1..i+m])

return not found

}

W tym przykładzie zakłada się, że wszystkie podciągi mają narzuconą długość m, ale można to z łatwością zmienić. Porównujemy obecną wartość skrótu z wartościami skrótów wszystkich podciągów jednocześnie, a następnie porównujemy znalezione pary ze wszystkimi podciągami o danej wartości skrótu.

Inne algorytmy, przy wyszukiwaniu pojedynczego wzorca, mają złożoność czasową O(n), a dla wielokrotnie (k razy) powtarzającego się wzorca O(n*k). W przeciwieństwie do algorytmu Rabina-Karpa, który wyszukuje k wzorów w czasie O(n+k), ponieważ sprawdzenie, czy skrót podciągu jest równy skrótowi wzorca, zajmuje O(1) czasu.

Linki zewnętrzne

Richard M. Karp, Michael O. Rabin. Efficient randomized pattern-matching algorithms. „IBM Journal of Research and Development”. 31 (2), marzec 1987. brak numeru strony

Karp-Rabin algorithm na stronie EXACT STRING MATCHING ALGORITHMS