Cesko.wiki Rabinův–Karpův algoritmus
Author
Albert FloresRabin-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. +more Například když máme podřetězec "hi" a základ je 101, tak bude vrácená hodnota 104 × 1011 + 105 × 1010 = 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. +morem]) 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.