Rabinův–Karpův algoritmus

Rabin–Karpův algoritmus je v informatice jedním z algoritmů pro vyhledávání textu. Vytvořili ho Michael O. Rabin a Richard M. Karp v roce 1987. Algoritmus hledá řadu vzorků najednou a používá k tomu hašovací funkci. Pro text délky n a p vzorků společné délky m je jeho průměrná a nejlepší složitost O(n+m) v prostoru O(p) a jeho nejhorší složitost je O(nm).

Praktické využití Rabinova-Karpova algoritmu je odhalování plagiátorství. Vzhledem k množství hledaných řetězců jsou algoritmy, které vyhledávají jeden řetězec, nepraktické.

Použití hašovací funkce

Klíčem k výkonu Rabinova-Karpova algoritmu je efektivní výpočet vrácených hodnot hašovací funkce u podřetězců v textu. Jedna populární a efektivní hašovací funkce považuje každý podřetězec jako číslo nějakého základu obvykle velikosti prvočísla. Například když máme podřetězec "hi" a základ je 101, tak bude vrácená hodnota 104 × 101¹ + 105 × 101⁰ = 10609 (v ASCII je za 'h' 104 a za 'i' je 105).

Příklad Rabinova-Karpova algoritmu

Pokud chceme najít některé z velkých čísel k s pevnou délkou vzorků v textu, můžeme vytvořit jednoduchou variantu Rabinova-Karpova algoritmu použitím Bloomova filtru.

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-m+1
         if hs ∈ hsubs and s[i..i+m-1] ∈ subs
             return i
         hs := hash(s[i+1..i+m])
     return not found

Předpokládáme, že všechny podřetězce mají pevnou délku m.

Reference

V tomto článku byl použit překlad textu z článku Rabin–Karp algorithm na anglické Wikipedii.