Algorytm Karpa-Rabina

Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca – służy do lokalizowania w tekście określonego podciągu. Został stworzony w 1987 roku przez Michaela O. Rabina i Richarda Karpa.

Dany jest wzorzec $x[1\ldots m]$ (złożony z $m$ znaków) oraz przeszukiwany ciąg $y[1\ldots n]$ (złożony z $n$ znaków; $n>=m$ ). Problem dopasowania wzorca polega na znalezieniu takiego indeksu $i,$ dla którego $y[i\ldots i+m-1]=x[1\ldots m].$

W algorytmie Karpa-Rabina wykorzystuje się funkcję mieszającą $h.$ Przeglądane są wszystkie podciągi $y_{i}:=y[i\ldots i+m-1]$ dla $i\in [1\ldots n-m],$ ale bezpośrednie porównania podciągu $y_{i}$ z $x$ (które jest bardzo kosztowne) ma miejsce tylko wtedy, gdy $h(y_{i})=h(x).$

O efektywności algorytmu decyduje konstrukcja funkcji mieszającej $h$ – powinna istnieć funkcja $N$ która niskim kosztem wyznacza $h(y_{i+1})$ na podstawie znanej już wartości $h(y_{i}).$ W praktyce, traktuje się tekst jako liczbę zapisaną w systemie o określonej podstawie (najczęściej biorąc jako wartości cyfr kody ASCII znaków).

Oczekiwana złożoność obliczeniowa jest rzędu $O(m+n).$

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

Sx\leftarrow h(x[1\ldots m])

Sy\leftarrow h(y[1\ldots m])

for $i\leftarrow 1$ to $n-m+1$ do

begin

if $Sx=Sy$ then

begin

porównaj ciąg $x[1\ldots m]$ z podciągiem $y[i\ldots i+m-1]$

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

end

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

end

Zastosowanie edytuj

Jednym z najprostszych praktycznych zastosowań algorytmu Rabina-Karpa jest wykrywanie plagiatu. Powiedzmy, na przykład, że student pisze wypracowanie na temat Pana Tadeusza. Profesor mógłby wyszukać opracowania na ten sam temat i automatycznie porównać je z zawartością wypracowania. Za pomocą algorytmu Rabina-Karpa można wykazać, z którego opracowania zostało skopiowane dane zdanie. Aby zapobiec oszukaniu systemu poprzez niewielkie przeróbki tekstu algorytm może zostać ustawiony tak, aby ignorował detale, takie jak znaki przestankowe, poprzez ich uprzednie usunięcie lub wprowadzenie marginesu błędu przy porównywaniu skrótu przeszukiwanego tekstu ze wzorcem (ponieważ podobne ciągi znaków mają podobne skróty). Ponieważ liczba ciągów przez nas poszukiwanych jest znaczna algorytmy pojedynczego wyszukiwania byłyby niepraktyczne.

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

Podstawowym zadaniem algorytmu jest znalezienie podciągu długości m, nazywanego wzorem, wbudowanego w tekst o długość n; na przykład znajdując wyraz „zegar” w zdaniu „Zegarmistrz wziął za naprawę 20 złotych.” Najprostszy algorytm wykonujący to zadanie po prostu wyszukuje podciągi na wszystkie możliwe sposoby.

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

Taka praca algorytmu jest dobra w wielu praktycznych przypadkach, ale w pewnych przykładach, takich jak szukanie tekstu składającego się z „b” i 10,000 „a” w tekście z 10 milionów „a”, owocuje wystąpieniem pesymistycznego czasu przebiegu równego Θ(mn).

Algorytm Knutha-Pratta-Morrisa zmniejsza ten czas do Θ(n) za pomocą prekomputacji, czyli badania każdego znaku w tekście tylko raz. Algorytm skoku Boyer-Moore’a przesuwa wskaźnik nie o 1 miejsce, ale tak dużo jak tylko to możliwe, ponieważ wskaźnik przesuwa się o tyle miejsc ile znalazło elementów zgodnych z wzorem licząc od początku wzoru, skutecznie zmniejszając liczbę powtórzeń zewnętrznej pętli, w najlepszym przypadku liczba ta może być rzędu n/m. Algorytm Rabina-Karpa skupia się zamiast tego przyspieszeniu działania linii kodu od 3 do 6, co będzie rozważane w następnych paragrafach.

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

Zamiast dążyć do bardziej wyrafinowanego przeskakiwania, algorytm Rabina-Karpa przyspiesza porównywanie szukanego wzorca do podciągów w tekście za pomocą funkcji skrótu. Funkcja skrótu przerabia każdy ciąg liter na postać numeryczną nazywaną skrótem (ang. hash). Algorytm Rabina-Karpa wykorzystuje fakt, że jeżeli dwa teksty są równe, ich skróty też są równe. Implikacja odwrotna nie zachodzi jednak – dla dwóch różnych tekstów mogą się zdarzyć dwa równe skróty. Trzeba zatem porównać także teksty, jeśli wartości skrótów są równe:

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że linie 2 i 3 są wykonane tylko raz a linia 6 jest uruchamiana tylko gdy wartości skrótu są równe. Linia 5 jest wykonywana n razy, ale wymaga stałego czasu. Więc jedynym punktem mogącym negatywnie wpłynąć na złożoność algorytmu jest linia 8.

Jeśli wyliczymy w sposób naiwny wartość skrótu dla podciągu s[i+1...i+m], zajmie to Ω(m) czasu, a ponieważ linia ta jest wykonywana przy każdym obiegu pętli, cały algorytm będzie miał złożoność czasową Ω(mn), czyli tyle ile najmniej wydajne algorytmy naiwne. Sztuczka polega na wyliczeniu aktualnego skrótu na podstawie skrótu wyliczonego w poprzednim obiegu pętli. Do tego służy algorytm postępującego skrótu.

Najprostsza wersja działa według takiej zasady: wyznacza się wartość każdego znaku w podciągu, następnie wylicza się skrót według wzoru

hs[i+1\dots i+m]=hs[i\dots i+m-1]-s[i]+s[i+m]

Ta prosta funkcja skrótu ma niestety niezbyt równomierny rozkład, co powoduje, że linia 6 jest wykonywana o wiele częściej niż w innych bardziej wyrafinowanych algorytmach postępującego skrótu.

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

Kluczem wydajności algorytmu Karpa-Rabina jest efektywne wyliczanie wartości skrótu kolejnych podciągów tekstu. Jeden z wydajnych algorytmów postępującego skrótu traktuje podciągi jako numery o pewnej bazie. Bazą zazwyczaj jest jakaś duża liczba pierwsza. Np.: dla podciągu „hi” wartość skrótu wynosi 104 * 101^1 + 105 * 101^0 = 10609 (kod ASCII dla h wynosi 104, a dla i – 105). Główną zaletą takiego sposobu hashowania jest możliwość wyznaczenia wartości skrótu kolejnego podciągu na podstawie podciągu poprzedniego poprzez wykonanie stałej liczby operacji niezależnej od długości tego podciągu.

Wielowzorcowe wyszukiwanie Rabina-Karpa edytuj

Algorytm Rabina-Karpa jest gorszy w wyszukiwaniu pojedynczego wzorca od algorytmów takich jak Knutha-Morrisa-Pratta czy Boyer’a-Moore’a, ponieważ jest najwolniejszy w przypadku pesymistycznego ułożenia ciągu. Jednak nie ma sobie równych przy wyszukiwaniu wielowzorcowym. Jeżeli chcemy wyszukać w tekście wielokrotnie powtarzający się wzorzec, wystarczy stworzyć prostą wersję algorytmu Rabina-Karpa używającą filtru Blooma do sprawdzania czy skrót sprawdzanego podciągu jest równy skrótowi podciągu przez nas poszukiwanego.

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 przykładzie tym zakładamy, że wszystkie podciągi mają narzuconą długość m, jednak można to wyeliminować. Po prostu 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 wyszuka k wzorów w czasie O(n+k) ponieważ sprawdzenie czy skrót podciągu jest równy skrótowi wzorca zabiera O(1) czasu.

Linki zewnętrzne edytuj

Richard M. Karp, Michael O. Rabin. Efficient randomized pattern-matching algorithms. „IBM Journal of Research and Development”. 31 (2), marzec 1987.
Karp-Rabin algorithm na stronie EXACT STRING MATCHING ALGORITHMS (ang.)