Rabin-Karpův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. června 2021; kontroly vyžadují 3 úpravy .

Rabin-Karpův algoritmus je algoritmus pro vyhledávání řetězců , který hledá vzor, tj. podřetězec, v textu pomocí hash . V roce 1987 jej navrhli Michael Rabin a Richard Karp . [jeden]

Algoritmus se zřídka používá pro porovnávání jednoho vzoru, ale má značný teoretický význam a je velmi účinný při porovnávání více vzorů stejné délky. Pro text délky n a vzor délky m je jeho průměrná a nejlepší doba provedení O ( n ) při správné volbě hashovací funkce (viz níže), ale v nejhorším případě má účinnost O( nm ) , což je jeden z důvodů, proč není široce používán. U aplikací, kde jsou přijatelné falešně pozitivní výsledky vyhledávání, tj. kde některé nalezené výskyty vzoru nemusí ve skutečnosti odpovídat vzoru, Rabin-Karpův algoritmus běží v garantovaném čase O( n) a vhodnou volbou náhodné hašovací funkce (viz níže) lze pravděpodobnost chyby velmi snížit. Algoritmus má také jedinečnou vlastnost najít libovolný z daných k řetězců v průměru stejné délky (se správnou volbou hashovací funkce) v čase O( n ), bez ohledu na velikost k .

Jednou z nejjednodušších praktických aplikací Rabin-Karpova algoritmu je odhalování plagiátorství. Řekněme například, že student píše práci o Moby Dickovi . Vychytralý profesor najde různé zdrojové materiály Moby Dicka a automaticky z nich extrahuje seznam vět. Rabin-Karpův algoritmus pak může rychle najít příklady výskytů některých vět ze zdrojových materiálů v kontrolovaném článku. Aby byl algoritmus méně citlivý na malé rozdíly, lze detaily, jako jsou malá a velká písmena nebo interpunkci , ignorovat jejich odstraněním. Vzhledem k tomu, že počet hledaných řetězců, k , je velmi velký, stávají se obvyklé vyhledávací algoritmy s jedním řetězcem neefektivní.

Vyhledávání podřetězců pomocí posunu a konkurenčních algoritmů

Hlavním úkolem algoritmu je najít v textu délky n řetězec délky m , nazývaný vzor . Jeden z nejjednodušších algoritmů pro tento úkol jednoduše hledá podřetězec na všech možných místech:

1 funkce NaiveSearch( řetězec s[1..n], řetězec sub[1..m]) 2 pro i od 1 do n-m+1 3 pro j od 1 do m 4 pokud s[i+j-1] ≠ sub[j] 5 přejít na další iteraci vnější smyčky 6 návrat i 7 návrat nenalezen

Tento algoritmus funguje dobře v mnoha praktických případech, ale je zcela neefektivní, například při hledání řetězce 10 tisíc znaků „a“ následovaného „b“ v řetězci 10 milionů znaků „a“. V tomto případě ukazuje svou nejhorší dobu provedení Θ ( mn ).

Algoritmus Knuth-Morris-Pratt zkrátí tento čas na Θ( n ), přičemž použije předvýpočet jednou pro každý znak textu; Algoritmus Boyer-Moore nepřeskakuje pouze jeden znak, ale tolik, kolik je možné, aby bylo vyhledávání úspěšné, čímž se účinně snižuje počet iterací ve vnější smyčce, takže počet znaků, se kterými lze porovnávat, může být srovnatelný s n/m při nejlepším. Rabin-Karpův algoritmus se místo toho zaměřuje na zrychlení řádků 3-6, o čemž bude řeč v další části.

Použití hašování k nalezení podřetězců posunutím

Namísto použití chytřejšího přeskakování se Rabin-Karpův algoritmus snaží urychlit kontrolu ekvivalence vzoru s podřetězci v textu pomocí hashovací funkce . Hašovací funkce je funkce, která převádí každý řetězec na číselnou hodnotu nazývanou hašovací hodnota (hash) ; například můžeme mít hash řetězce „hello“ rovný 5. Algoritmus využívá toho, že pokud jsou dva řetězce stejné, pak jsou jejich hodnoty hash také stejné. Vše, co potřebujeme, je vypočítat hodnotu hash hledaného podřetězce a poté najít podřetězec se stejnou hodnotou hash.

S tím jsou však spojeny dva problémy. První je, že vzhledem k tomu, že existuje tolik různých řetězců, může dojít ke kolizi mezi dvěma různými řetězci - shoda jejich hashů. V takových případech je nutné zkontrolovat shodu samotných podřetězců znak po znaku, což zabere hodně času, pokud jsou tyto podřetězce dlouhé (tato kontrola není nutná, pokud vaše aplikace umožňuje falešné poplachy). S přiměřeně dobrými hashovacími funkcemi (viz níže) jsou kolize extrémně vzácné a průměrná doba vyhledávání je v důsledku toho krátká.

Příklad algoritmu (zdrojový kód aplikace):

1 funkce RabinKarp( řetězec s[1..n], řetězec sub[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 pro i od 1 do (n-m+1) 5 pokud hs = hsub 6 pokud s[i..i+m-1] = sub 7 návrat i 8 hs := hash(s[i+1..i +m]) 9 návrat nenalezen

Spuštění řádků 2, 3 a 6 vyžaduje čas . Řádky 2 a 3 se však provedou pouze jednou a řádek 6 se provede pouze tehdy, když se hodnoty hash shodují, což se stává zřídka. Řádek 5 se provede jednou, ale vždy trvá konstantní čas. $\Omega (m)$ $n$

Druhým problémem je přepočet hash. Naivně přepočítat hašovací hodnotu podřetězce s[i+1..i+m]zabere čas , a protože se to děje v každé smyčce, algoritmus stráví čas , což je stejné jako u většiny jednoduchých algoritmů. Řešením tohoto problému je předpokládat, že proměnná již obsahuje hash hodnotu podřetězce . Pokud jej použijete k výpočtu další hodnoty hash v konstantním čase, pak je problém vyřešen. $O(m)$ $\Omega (mn)$ hss[i..i+m-1]

Toho je dosaženo použitím toho, co je známé jako kruhový hash . Nejjednodušším příkladem kruhového hashu je přidat hodnoty každého následujícího znaku do podřetězce a poté pomocí tohoto vzorce vypočítat každou následující hash hodnotu v pevně stanoveném čase:

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

Takový vzorec nezaručuje, že ke kolizím nedojde často, a je opravdu snadné zajistit, že ve většině aplikací se při jeho použití bude výraz na řádku 6 provádět častěji než při použití jiných, „chytřejších“ “ring hash funkce.

Všimněte si, že pokud máme velkou smůlu nebo máme velmi špatnou hashovací funkci, jako je konstantní funkce (hash=const), je velmi pravděpodobné, že se řádek 6 provede jednou, tj. při každé iteraci cyklu. Protože to zabere čas , zabere to čas i samotný algoritmus . $n$ $\Omega (m)$ $\Omega (mn)$

Použitá hashovací funkce

Klíči k výkonu Rabin-Karpova algoritmu jsou nízká pravděpodobnost kolizí a efektivní výpočet hash hodnoty po sobě jdoucích podřetězců textu. Rabin a Karp [1] navrhli použít takzvaný polynomiální hash (ačkoli jakýkoli jiný kruhový hash by také fungoval). Pro danou šablonu je takový hash definován takto: $p[1..m]$

hash(p[1..m])=\left(\sum _{i=1}^{m}p[i]x^{mi}\right){\bmod {q)),

kde je nějaké prvočíslo a je číslo od do . Hodnoty hash po sobě jdoucích podřetězců a pro polynomiální hash se počítají následovně (všimněte si, že kvůli účinnosti se číslo počítá před hlavní vyhledávací procedurou Rabin-Karp): $q$ $X$ $0$ $q-1$ $s[i..i+m-1]$ $s[i+1..i+m]$ $x^{m-1}{\bmod {q))$

hash(s[i+1..i+m])=\left((hash(s[i..i+m-1])-s[i]\cdot x^{m-1} )\cdot x+s[i+m]\right){\bmod {q))

Necháme například libovolně a máme text "abracadabra" a hledáme vzor délky 3. Z hash podřetězce "abr" (předchozí podřetězec) můžeme vypočítat hash podřetězce "bra" odečtením čísla přidaného pro první písmeno 'a' od "abr", tj. ( - ASCII pro 'a'), vynásobením základem a nakonec přidáním posledního čísla pro "podprsenku", tj . Abyste se vyhnuli přetečení celého čísla, ve většině implementací musíte po každé z těchto čtyř operací (násobení ve výpočtu je samostatná operace) vzít výsledek modulo . $x=101$ $q$ $97\times 101^{2}$ $97$ $101$ $97\times 101^{0}=97$ $97\times 101^{2}$ $q$

Rabin a Karp dokázali, že pokud je (tedy pevné) a prvočíslo je vybráno náhodně z rozsahu , pak pravděpodobnost kolize při hledání vzoru v textu délky nepřesáhne . Ale taková hašovací funkce má dvě významné nevýhody: za prvé, algoritmus pro výběr náhodného prvočísla je značně těžkopádný, a zadruhé, modulární aritmetika takový haš v praxi velmi zpomaluje (všimněte si, že veškerá aritmetika ve vzorci pro haše po sobě jdoucích podřetězců musí být modulo , to znamená, že převzetí modulu bude provedeno čtyřikrát). $x=2$ $X$ $q$ $[2..n^{3}]$ $n$ $O(1/n)$ $q$

Moderní modifikace polynomiálního hashu navržená Ditzfelbingerem et al [2] tyto nedostatky nemá. Rozdíl v této volbě je v tom, že prvočíslo je pevné a číslo je náhodně vybráno z rozsahu od do před spuštěním algoritmu ( nemusí být prvočíslo vůbec). Bylo prokázáno [2] , že u takové hashovací funkce pravděpodobnost kolize při hledání vzoru v řetězci pro některé nepřekročí , za přirozené podmínky, že pro všechny . Pro urychlení modulární aritmetiky můžete zvolit mocninu dvě mínus jedna (takzvaná Mersennova prvočísla ): pro 32bitové stroje se nejlépe hodí , pro 64bitové stroje - ; modulo pro takové hodnoty se vypočítá pomocí rychlých bitových operací [3] . Další možnou volbou jsou hodnoty nebo , pro které existují také rychlé algoritmy pro převzetí zbytku dělení [4] (rozsah přijatelných hodnot je mírně zúžen). Můžete si vybrat pouze jednou při spuštění programu a poté jej použít ve všech hashích. $q$ $X$ $0$ $q-1$ $X$ $s[1..n]$ $q>n^{c}$ $c>2$ $1/n^{c-2}$ $0\leq s[i]<q$ $i=1,2,\ldots ,n$ $q$ $q=2^{31}-1$ $q=2^{61}-1$ $q$ $q$ $q=2^{32}-5$ $q=2^{64}-59$ $q$ $X$ $X$

Mylné představy o polynomiálních hashích

Ještě jednou poznamenáváme, že záruky absence kolizí, které poskytuje polynomiální hash, jsou velmi silné: i když někdo, kdo ví, ale neví , konkrétně vybere vzor a řetězec délky pro hledání tak, aby Rabin-Karpův algoritmus s polynomiálním hashem dává co nejvíce kolizí , každopádně pro některé (tedy pro dostatečně velký a ne supervelký ) a pokud je vybrán opravdu náhodně, pravděpodobnost byť jen jedné kolize nebude větší než , že je, velmi malý. K tomu je důležitý výsledek, kterým je prvočíslo. Běžnou chybou je například předpokládat nebo (to znamená vůbec nepoužívat modulární aritmetiku); příklad řetězce, ve kterém lze najít mnoho polynomiálních kolizí hash pro takový , a bez ohledu na výběr čísla , je Morse-Thue sekvence . [5] $q$ $X$ $n$ $q>n^{c}$ $c>2$ $q$ $n$ $X$ $1/n^{c-2}$ $q$ $q=2^{32}$ $q=2^{64}$ ${\displaystyle q=2^{k))$ $X$

Oblíbená je následující interpretace polynomiálního hashe: každý řetězec je reprezentován číslem se základem a toto číslo se pak vezme modulo . Taková interpretace nepřidává jasnost povaze účinnosti daného hashe, zatímco interpretace polynomického hashe jako správného polynomu s koeficienty rovnými hodnotám symbolů vede jednoduše k důkazu nízké pravděpodobnosti. kolize s náhodným výběrem [2] : zvažte dva různé řetězce a ; polynomiální hash těchto řetězců jsou stejné tehdy a jen tehdy , když ; ale z Bezoutovy věty vyplývá, že polynom stupně , který není identický s nulou v oboru zbytků modulo ( volí se jednoduše, právě proto, aby se prstenec zbytků změnil v pole) má nanejvýš kořeny, což znamená, že pravděpodobnost kolize nepřekročí ani při náhodném výběru ; tedy pokud u některých nepřekročí pravděpodobnost srážky dvou různých řetězců délky (tedy zejména pravděpodobnost chyby při hledání vzoru v řetězci). $X$ $q$ $X$ $p_{1}[1..m]$ $p_{2}[1..m]$ $\sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{mi}\equiv 0{\pmod {q))$ ${\displaystyle \sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{mi))$ $m-1$ $q$ $q$ $m-1$ $p_{1}$ $p_{2}$ $X$ $(m-1)/q$ $q>n^{c}\geq m^{c}$ $c>1$ $m$ ${\displaystyle (m-1)/q<n/q<1/n^{c-1))$ $1/n^{c-2}$

Někdy je také možné narazit na doporučení použít prvočíslo jako , ale zjevně kromě empirických pozorování na některých velmi omezených množstvích dat už taková rada není podložená. $X$

Rabin-Karp a hledání mnoha exemplářů

Kvůli pomalému chování v nejhorším případě je algoritmus Rabin–Karp horší než algoritmus Knuth–Morris–Pratt , algoritmus Boyer–Moore a další algoritmy rychlého vyhledávání řetězců . Rabin-Karpův algoritmus však lze použít k nalezení sady vzorků v lineárním čase v nejlepším případě a v kvadratickém čase v nejhorším případě; i když i zde prohrává v nejhorším případě s algoritmem Aho-Korasik , který má lineární dobu běhu.

Pokud chceme v daném textu najít jakýkoli vzor z velké množiny, řekněme, k vzorů s pevnou délkou, můžeme modifikovat Rabin-Karpův algoritmus použitím hashovací tabulky nebo jakékoli jiné datové struktury , abychom zkontrolovali, že hash daný řetězec patří do sady hash. vzorové hodnoty, které hledáme:

function RabinKarpSet( řetězec s[ 1..n ], množina řetězců subs, m) { set hsubs := pro každý sub v subs

\varno nic

hsubs := hsubs {hash(sub[1..m])}

\pohár

hs := hash(s[1..m]) for i od 1 do (n-m+1) if hs ∈ hsubs if s[i..i+m-1] = řetězec z subs s hash hs return i hs := hash(s[i+1..i+m]) návrat nenalezen }

Jiné algoritmy mohou hledat jeden vzorek v O( n ) čase, a proto je lze použít k hledání k vzorků v O( nk ) čase. Naproti tomu výše uvedená varianta Rabin-Karpova algoritmu dokáže najít všech k vzorků v očekávaném čase O( n + k ), protože hashovací tabulka používaná k testování případu, kdy se hash podřetězce rovná hash kterýkoli ze vzorků používá čas O(1). V praxi může být tato možnost často výhodnější z důvodu relativní snadnosti implementace a rychlosti provozu před algoritmem Aho-Korasik .

Viz také

Poznámky

↑ 1 2 Rabin, Karp, 1987 .
↑ 1 2 3 Dietzfelbinger, Gil, Matias, Pippinger, 1992 .
↑ SE Anderson. Trochu šmrncovní hacky. Archivováno 1. června 2020 na Wayback Machine
↑ Krovetz, Rogaway, 2000 .
↑ Pachocki, Radoszewski, 2013 .

Literatura

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algorithms: construction and analysis = Introduction to Algorithms / ed. S. N. Triguba ; za. z angličtiny. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2. vyd. - M. : Williams, 2005. - 801 s. — ISBN 5-8459-0857-4 .
Rabin MO , Karp RM Efektivní algoritmy náhodného porovnávání vzorů // IBM Journal of Research and Development . - IBM, 1987. - T. 31 , č. 2 . — S. 249–260 . - doi : 10.1147/rd.312.0249 .
Dietzfelbinger M., Gil J., Matias Y., Pippenger N. Polynomiální hašovací funkce jsou spolehlivé // Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP'92) . — London, UK: Springer-Verlag, 1992. — s. 235–246 . - doi : 10.1007/3-540-55719-9_77 .
Krovetz T., Rogaway P. Rychlé univerzální hashování s malými klíči a bez předběžného zpracování: konstrukce PolyR // Sborník příspěvků z mezinárodní konference o informační bezpečnosti a kryptologii. - Berlín, Německo: Springer-Verlag, 2000. - s. 73–89 . - doi : 10.1007/3-540-45247-8_7 .
Pachocki J., Radoszewski J. Kde používat a jak nepoužívat hašování polynomiálních řetězců // Olympiády v informatice. - Vilnus, Litva: Vilnus University, 2013. - V. 7 . — S. 90–100 .

Struny
Míry podobnosti řetězců	Vzdálenost Damerau - Loewenstein Levenshteinská vzdálenost Hammingova vzdálenost Podobnost Jaro-Winkler
Hledání podřetězců	Boyer-Mooreův algoritmus Algoritmus Boyer-Moore-Horspool Knuth-Morris-Prattův algoritmus Rabin-Karpův algoritmus funkce předpony Z-funkce Algoritmus Aho - Korasik
palindromy	palindromový strom Manažerův algoritmus
Sekvenční zarovnání	Algoritmus Needleman-Wunsha Smith-Watermanův algoritmus
Struktury přípon	Pole přípon Přípona automat příponový strom předponový strom
jiný	rozebrat Shoda vzorů Největší společná podsekvence Největší společný podřetězec