Algorytm Karpa-Rabina

Z Wikipedii

Algorytm Karpa-Rabina jest algorytmem dopasowania wzorca - służy do lokalizowania w tekście określonego podciągu.

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 \larr h(x[1\ldots m])$

$Sy \larr h(y[1\ldots m])$

for $i \larr 1$ to

n - m

do

begin

if

S x = S y

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 \larr N(Sy, y[i], y[i+n])$

end

Spis treści

1 Zastosowanie
2 Różne algorytmy poszukiwania ruchomych podciągów
3 Użycie funkcji skrótu do zmiennego przeszukiwania podciągu
4 Funkcje skrótu będące w użyciu
5 Wielowzorcowe wyszukiwanie Rabina-Karpa

[edytuj] Zastosowanie

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 Robina-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. Ponieważ ilość ciągów przez nas poszukiwanych jest znaczna algorytmy pojedynczego wyszukiwania byłyby niepraktyczne.

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

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ą prekumputacji, 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.

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

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..n])
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.

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

Kluczem wydajności algorytmu Robina-Karpa 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.

[edytuj] Wielowzorcowe wyszukiwanie Rabina-Karpa

Algorytm Robina-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 poszukiwanemu.

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 z 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.

Soczewki kontaktowe z elektroniką

Opracowano prototyp nowoczesnych soczewek kontaktowych, w których wnętrzu zatopiony jest układ elektroniczny oraz diody LED. Jest to przysłowiowy "kamień milowy" dla dziedziny nauki, która zajmuje się miniaturyzacją układów scalonych, donosi "LaserFocusWorld".

Groźny detoks

Pewna Brytyjka doznała uszkodzeń mózgu po poddaniu się tzw. diecie "detoks", która wymagała picia dużych ilości płynów.

Pod lodami Arktyki 90 mld baryłek ropy

90 mld baryłek ropy i ilość gazu równa całym znanym jego zasobom w Rosji - na tyle oceniają amerykańscy eksperci rządowi zasoby Arktyki. Ich szacunki opisał w czwartek "Financial Times".

Twoje piersi tego nie lubią!

Kobiety, które noszą źle dobrane biustonosze, niszczą sobie piersi - alarmują naukowcy.

Odkryto "pogromcę plemników"

Mężczyźni, którzy codziennie spożywają produkty sojowe produkują mniej plemników, niż mężczyźni, którzy nie jedzą ich wcale - informuje pismo "Human Reproduction".

Linki: Strona g��wna

Encyklopedia