Rabin-Karp algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. juni 2021; checks kræver 3 redigeringer .

Rabin-Karp- algoritmen er en strengsøgningsalgoritme , der leder efter et mønster, dvs. en understreng, i en tekst ved hjælp af hashing . Den blev designet i 1987 af Michael Rabin og Richard Karp . [en]

Algoritmen bruges sjældent til enkeltmønstermatchning, men er af betydelig teoretisk betydning og er meget effektiv til at matche flere mønstre af samme længde. For en tekst af længden n og et mønster af længden m er dens gennemsnitlige og bedste udførelsestid O ( n ) med det rigtige valg af hashfunktion (se nedenfor), men i værste tilfælde har den en effektivitet på O( nm ) , hvilket er en af grundene til, at det ikke er meget brugt. For applikationer, hvor falske positive søgeresultater er acceptable, dvs. hvor nogle af de fundne forekomster af et mønster muligvis ikke matcher mønsteret, kører Rabin-Karp-algoritmen i en garanteret tid på O( n )) og med et passende valg af randomiseret hashfunktion (se nedenfor), kan sandsynligheden for fejl gøres meget lille. Algoritmen har også en unik funktion til at finde enhver af de givne k strenge af samme længde i gennemsnit (med det rigtige valg af hashfunktion) i O( n ) tid, uanset størrelsen på k .

En af de enkleste praktiske anvendelser af Rabin-Karp-algoritmen er at opdage plagiat. Lad os for eksempel sige, at en studerende skriver en opgave om Moby Dick . Den besnærende professor finder forskellige Moby Dick -kildemateriale og udtrækker automatisk en liste over sætninger i disse materialer. Så kan Rabin-Karp-algoritmen hurtigt finde eksempler på forekomster af nogle sætninger fra kildematerialerne i artiklen, der kontrolleres. For at gøre algoritmen mindre følsom over for små forskelle kan detaljer som store og små bogstaver eller tegnsætning ignoreres ved at fjerne dem. Da antallet af strenge, vi leder efter, k , er meget stort, bliver de sædvanlige enkeltstrengssøgningsalgoritmer ineffektive.

Understrengssøgning efter skift og konkurrerende algoritmer

Algoritmens hovedopgave er at finde en streng med længden m , kaldet mønster , i en tekst med længden n . En af de enkleste algoritmer til denne opgave leder simpelthen efter understrengen alle mulige steder:

1 funktion NaiveSearch( streng s[1..n], streng sub[1..m]) 2 for i fra 1 til n-m+1 3 for j fra 1 til m 4 hvis s[i+j-1] ≠ sub[j] 5 gå til næste iteration af den ydre sløjfe 6 return i 7 return ikke fundet

Denne algoritme fungerer godt i mange praktiske tilfælde, men er fuldstændig ineffektiv, for eksempel til at finde en streng på 10 tusind "a"-tegn efterfulgt af "b" i en streng på 10 millioner "a"-tegn. I dette tilfælde viser den sin dårligste udførelsestid Θ ( mn ).

Knuth-Morris-Pratt-algoritmen reducerer denne tid til Θ( n ), ved at bruge forberegningen én gang for hvert tegn i teksten; Boyer-Moore-algoritmen springer ikke kun ét tegn over, men så mange som det maksimale muligt for at søgningen lykkes, hvilket effektivt reducerer antallet af iterationer gennem den ydre sløjfe, så antallet af tegn, der skal sammenlignes med, kan sammenlignes med n/m i bedste fald. Rabin-Karp-algoritmen fokuserer i stedet på at fremskynde linje 3-6, hvilket vil blive diskuteret i næste afsnit.

Brug af hashing til at finde understrenge ved at flytte

I stedet for at bruge smartere spring, forsøger Rabin-Karp-algoritmen at fremskynde mønsterækvivalenskontrollen med understrenge i teksten ved hjælp af en hash-funktion . En hash-funktion er en funktion, der konverterer hver streng til en numerisk værdi kaldet en hash-værdi (hash) ; for eksempel kan vi have hashen af strengen "hello" lig med 5. Algoritmen bruger det faktum, at hvis to strenge er ens, så er deres hashværdier også de samme. Alt, hvad vi behøver, er således at beregne hashværdien af den søgte understreng og derefter finde understrengen med samme hashværdi.

Der er dog to problemer forbundet med dette. Den første er, at da der er så mange forskellige strenge, kan der opstå en kollision mellem to forskellige strenge - sammenfaldet af deres hashes. I sådanne tilfælde er det nødvendigt at kontrollere matchningen af selve understrengene tegn for tegn, hvilket tager meget tid, hvis disse understrenge er lange (dette tjek er ikke nødvendigt, hvis din applikation tillader falske positiver). Med rimelig gode hash-funktioner (se nedenfor) er kollisioner ekstremt sjældne, og den gennemsnitlige opslagstid er kort som følge heraf.

Algoritmeeksempel (applikationskildekode):

1 funktion RabinKarp( streng s[1..n], streng sub[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 for i fra 1 til (n-m+1) 5 hvis hs = hsub 6 hvis s[i..i+m-1] = sub 7 returner i 8 hs := hash(s[i+1..i) +m]) 9 retur ikke fundet

Linje 2, 3 og 6 tager hver tid at udføre . Linje 2 og 3 udføres dog kun én gang, og linje 6 udføres kun, når hashværdierne matcher, hvilket sker sjældent. Linje 5 udføres én gang, men tager altid konstant tid. $\Omega (m)$ $n$

Det andet problem er hash-genberegning. s[i+1..i+m]Det tager tid at genberegne hashværdien af en understreng naivt , og da dette gøres i hver sløjfe, vil algoritmen bruge tid , hvilket er det samme, som de fleste simple algoritmer bruger. Løsningen på dette problem er at antage, at variablen allerede indeholder understrengens hashværdi . Hvis du bruger det til at beregne den næste hashværdi i konstant tid, så er problemet løst. $O(m)$ $\Omega (mn)$ hss[i..i+m-1]

Dette opnås ved at bruge det, der er kendt som en ringhash . Det enkleste eksempel på en ring-hash er at tilføje værdierne af hvert efterfølgende tegn i en understreng og derefter bruge denne formel til at beregne hver efterfølgende hash-værdi i en fast tidsperiode:

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

En sådan formel giver ingen garanti for, at kollisioner ikke vil forekomme ofte, og det er virkelig nemt at sikre sig, at i de fleste applikationer, når du bruger den, vil udtrykket i linje 6 blive udført oftere, end når du bruger andre, mere "smarte" ” ringhash-funktioner.

Bemærk, at hvis vi er meget uheldige eller har en meget dårlig hash-funktion, såsom en konstant funktion (hash=const), vil linje 6 med stor sandsynlighed blive udført én gang, dvs. ved hver iteration af løkken. Da det tager tid , vil selve algoritmen tage tid . $n$ $\Omega (m)$ $\Omega (mn)$

Den anvendte hash-funktion

Nøglerne til ydeevnen af Rabin-Karp-algoritmen er den lave sandsynlighed for kollisioner og den effektive beregning af hashværdien af successive understrenge af tekst. Rabin og Karp [1] foreslog at bruge en såkaldt polynomial hash (selvom enhver anden ringhash også ville fungere). For en given skabelon er en sådan hash defineret som følger: $p[1..m]$

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

hvor er et eller andet primtal, og er et tal fra til . Hashværdierne for på hinanden følgende understrenge og for en polynomiel hash beregnes som følger (bemærk, at for effektivitetens skyld tælles tallet før Rabin-Karps hovedsøgningsprocedure): $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))

Lad for eksempel vilkårligt , og vi har teksten "abracadabra" og leder efter et mønster med længde 3. Vi kan beregne hashen af understrengen "bra" ud fra hashen af understrengen "abr" (forrige understreng) ved at subtrahere tallet tilføjet for det første bogstav 'a' fra "abr", dvs. ( -ASCII for 'a'), gange med grundtallet og til sidst tilføje det sidste tal for "bra", dvs. For at undgå heltalsoverløb skal du i de fleste implementeringer, efter hver af disse fire operationer (multiplikation i beregningen er en separat operation), tage resultatet modulo . $x=101$ $q$ $97\times 101^{2}$ $97$ $101$ $97\times 101^{0}=97$ $97\times 101^{2}$ $q$

Rabin og Karp beviste, at hvis (det vil sige fast) og et primtal er valgt tilfældigt fra området , så overstiger sandsynligheden for en kollision, når man søger efter et mønster i en tekst af længde , ikke . Men sådan en hashfunktion har to væsentlige ulemper: For det første er algoritmen til at vælge et tilfældigt primtal ret besværlig, og for det andet gør modulær aritmetik en sådan hash meget langsom i praksis (bemærk, at al aritmetik i formlen for hashes af successive delstrenge skal være modulo , det vil sige at tage modulet udføres fire gange). $x=2$ $x$ $q$ $[2..n^{3}]$ $n$ $O(1/n)$ $q$

Den moderne modifikation af polynomiets hash foreslået af Ditzfelbinger et al. [2] har ikke disse mangler. Forskellen på denne mulighed er, at primtallet er fast, og tallet er tilfældigt udvalgt fra intervallet fra til før algoritmen starter (det behøver slet ikke at være primtal). Det er blevet bevist [2] at for en sådan hashfunktion overstiger sandsynligheden for en kollision ved søgning efter et mønster i en streng for nogle ikke , under den naturlige betingelse, at for alle . For at fremskynde modulær aritmetik , kan du vælge lig med en potens på to minus en (de såkaldte Mersenne-primtal ): til 32-bit maskiner er det bedst egnet , til 64-bit maskiner - ; modulo for sådanne værdier beregnes ved hjælp af hurtige bitvise operationer [3] . Et andet muligt valg er værdierne eller , for hvilke der også er hurtige algoritmer til at tage resten af divisionen med [4] (rækken af acceptable værdier er en smule indsnævret). Du kan kun vælge én gang i starten af programmet, og derefter bruge det i alle hashes. $q$ $x$ $0$ $q-1$ $x$ $s[1..n]$ ${\displaystyle 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$

Misforståelser om polynomielle hashes

Endnu en gang bemærker vi, at garantierne for fravær af kollisioner givet af polynomiets hash er meget stærke: selv hvis nogen, der ved, men ikke ved , specifikt vil vælge mønsteret og længdestrengen til søgningen, så Rabin-Karp-algoritmen med et polynomium giver hash så mange kollisioner som muligt , alligevel for nogle (det vil sige for en tilstrækkelig stor og ikke super-stor ), og hvis den er valgt virkelig tilfældigt, vil sandsynligheden for selv en kollision ikke være mere end , at er meget lille. For at opnå dette er resultatet vigtigt, som er et primtal. For eksempel er en almindelig fejltagelse at antage eller (det vil sige slet ikke bruge modulær aritmetik); et eksempel på en streng, hvor man kan finde mange polynomielle hash-kollisioner for sådanne , og uanset valg af tal , er Morse-Thue-sekvensen . [5] $q$ $x$ $n$ ${\displaystyle q>n^{c))$ $c>2$ $q$ $n$ $x$ $1/n^{c-2}$ $q$ $q=2^{32}$ $q=2^{64}$ ${\displaystyle q=2^{k))$ $x$

Følgende fortolkning af et polynomisk hash er populært: hver streng er repræsenteret af et tal med en base , og så tages dette tal modulo . En sådan fortolkning tilføjer ikke klarhed til arten af effektiviteten af en given hash, mens fortolkningen af en polynomiel hash som et egentligt polynomium med koefficienter svarende til værdierne af symbolerne ganske enkelt fører til beviset for en lav sandsynlighed af en kollision med et tilfældigt valg [2] : overvej to forskellige strenge og ; polynomiets hashes for disse strenge er ens, hvis og kun hvis ; men det følger af Bezouts sætning , at et gradspolynomium , der ikke er identisk med nul i feltet af rester modulo ( det er valgt simpelt, netop at forvandle ringen af rester til et felt) højst har rødder, hvilket betyder, at sandsynligheden af en kollision ikke overstiger selv med et tilfældigt valg ; derfor, hvis for nogle , sandsynligheden for en kollision af to forskellige strenge af længde ikke overstiger (derfor, i særdeleshed, sandsynligheden for en fejl for at søge efter et mønster i en streng). $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$ ${\displaystyle q>n^{c}\geq m^{c))$ $c>1$ $m$ ${\displaystyle (m-1)/q<n/q<1/n^{c-1))$ $1/n^{c-2}$

Det er også nogle gange muligt at støde på en anbefaling om at bruge et primtal som , men tilsyneladende, bortset fra empiriske observationer på nogle meget begrænsede mængder data, er sådanne råd ikke længere underbygget. $x$

Rabin-Karp og søgningen efter mange eksemplarer

På grund af sin langsomme worst-case-adfærd er Rabin-Karp- algoritmen værre end Knuth-Morris-Pratt- algoritmen , Boyer-Moore-algoritmen og andre hurtige strengsøgningsalgoritmer . Rabin-Karp-algoritmen kan dog bruges til at finde et sæt prøver i lineær tid i bedste fald og kvadratisk tid på det sværeste for at opnå worst case; selvom den også her taber i værste fald til Aho-Korasik-algoritmen , som har en lineær køretid.

Hvis vi ønsker at finde et hvilket som helst mønster i en given tekst fra et stort sæt af f.eks. k faste mønstre af samme længde, kan vi modificere Rabin-Karp-algoritmen ved at bruge en hash-tabel eller en hvilken som helst anden datastruktur for at kontrollere, at hashen af en givne streng tilhører hashsættet. Eksempelværdier vi leder efter:

function RabinKarpSet( string s[1..n], sæt af strengsubs , m) { sæt hsubs := for hver sub i subs

\varnothing

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

\kop

hs := hash(s[1..m]) for i fra 1 til (n-m+1) hvis hs ∈ hsubs hvis s[i..i+m-1] = streng fra subs med hash hs returnerer i hs := hash(s[i+1..i+m]) retur ikke fundet }

Andre algoritmer kan søge efter en enkelt prøve på O( n ) tid, og de kan derfor bruges til at søge efter k prøver på O( nk ) tid. I modsætning hertil kan varianten af Rabin-Karp-algoritmen ovenfor finde alle k samples i den forventede tid O( n + k ), fordi hash-tabellen bruges til at teste for det tilfælde, hvor hashen af en understreng er lig med hashen af enhver af prøverne bruger O(1) tid. I praksis kan denne mulighed ofte være at foretrække frem for Aho-Korasik-algoritmen på grund af den relative lette implementering og betjeningshastighed .

Se også

Noter

↑ 1 2 Rabin, Karp, 1987 .
↑ 1 2 3 Dietzfelbinger, Gil, Matias, Pippinger, 1992 .
↑ SE Anderson. Lidt snodige hacks. Arkiveret 1. juni 2020 på Wayback Machine
↑ Krovetz, Rogaway, 2000 .
↑ Pachocki, Radoszewski, 2013 .

Litteratur

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / red. S. N. Triguba ; om. fra engelsk. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2. udg. - M. : Williams, 2005. - 801 s. — ISBN 5-8459-0857-4 .
Rabin MO , Karp RM Effektive randomiserede mønstertilpasningsalgoritmer // IBM Journal of Research and Development . - IBM, 1987. - T. 31 , nr. 2 . — S. 249–260 . - doi : 10.1147/rd.312.0249 .
Dietzfelbinger M., Gil J., Matias Y., Pippenger N. Polynomiske hash-funktioner er pålidelige // 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. Hurtig universel hashing med små nøgler og ingen forbehandling: PolyR-konstruktionen // Proceedings of the International Conference on Information Security and Cryptology. - Berlin, Tyskland: Springer-Verlag, 2000. - s. 73–89 . - doi : 10.1007/3-540-45247-8_7 .
Pachocki J., Radoszewski J. Hvor skal man bruge og hvordan man ikke bruger polynomial strenghashing // Olympiads in Informatics. - Vilnus, Litauen: Vilnus Universitet, 2013. - V. 7 . — S. 90–100 .

Strenge
String lighedsmål	Afstand fra Damerau til Loewenstein Levenshtein afstand Hammerafstand Jaro-Winkler lighed
Understrengssøgning	Boyer-Moore algoritme Boyer-Moore-Horspool algoritme Knuth-Morris-Pratt algoritme Rabin-Karp algoritme præfiks funktion Z-funktion Algoritme Aho - Korasik
palindromer	palindrom træ Manakers algoritme
Sekvensjustering	Needleman-Wunsha algoritme Smith-Waterman algoritme
Suffiksstrukturer	Suffiks array Suffiks automat suffiks træ præfiks træ
Andet	parsing Mønster matchende Største fælles efterfølger Største fælles understreng