Rabin-Karp algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 13.6.2021 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Rabin-Karp- algoritmi on merkkijonohakualgoritmi , joka etsii tekstistä kuviota, eli alimerkkijonoa, käyttämällä hajautustoimintoa . Sen suunnittelivat vuonna 1987 Michael Rabin ja Richard Karp . [yksi]

Algoritmia käytetään harvoin yksittäisen kuvion sovittamiseen, mutta sillä on huomattava teoreettinen merkitys ja se on erittäin tehokas useiden samanpituisten kuvioiden sovittamisessa. Tekstille, jonka pituus on n ja kuvion, jonka pituus on m , sen keskimääräinen ja paras suoritusaika on O ( n ) oikealla hash-funktion valinnalla (katso alla), mutta pahimmassa tapauksessa sen hyötysuhde on O( nm ) , mikä on yksi syistä, miksi sitä ei käytetä laajasti. Sovelluksissa, joissa haun väärät positiiviset tulokset ovat hyväksyttäviä, ts. joissa jotkin kuvion löydetyt esiintymät eivät välttämättä vastaa kuviota, Rabin-Karp-algoritmi suoritetaan taatussa ajassa O( n) ja sopivalla satunnaistetun hash-funktion valinnalla (katso alla), virheen todennäköisyys voidaan tehdä hyvin pieneksi. Algoritmilla on myös ainutlaatuinen ominaisuus löytää mikä tahansa annetuista k samanpituisesta merkkijonosta keskimäärin (oikealla hash-funktiolla) O( n ) ajassa riippumatta k :n koosta .

Yksi Rabin-Karp-algoritmin yksinkertaisimmista käytännön sovelluksista on plagioinnin havaitseminen. Oletetaan esimerkiksi, että opiskelija kirjoittaa artikkelia Moby Dickistä . Huijaava professori löytää erilaisia Moby Dick -lähdemateriaaleja ja poimii automaattisesti luettelon näiden materiaalien lauseista. Sitten Rabin-Karp-algoritmi löytää nopeasti esimerkkejä joidenkin lauseiden esiintymisestä tarkistettavan artikkelin lähdemateriaaleista. Jotta algoritmi olisi vähemmän herkkä pienille eroille, yksityiskohdat, kuten kirjainkoko tai välimerkit, voidaan jättää huomiotta poistamalla ne. Koska etsimiemme merkkijonojen määrä, k , on erittäin suuri, tavalliset yhden merkkijonon hakualgoritmit tulevat tehottomiksi.

Alimerkkijonohaku siirrolla ja kilpailevilla algoritmeilla

Algoritmin päätehtävänä on löytää n pituisesta tekstistä merkkijono , jonka pituus on m . Yksi tämän tehtävän yksinkertaisimmista algoritmeista etsii vain osamerkkijonoa kaikista mahdollisista paikoista:

1 funktio NaiveSearch( merkkijono s[1..n], merkkijono ali[1..m]) 2 i : lle 1 - n-m+1 3 j : lle 1 - m 4 jos s[i+j-1] ≠ sub[j] 5 siirtyy ulomman silmukan seuraavaan iteraatioon 6 paluu i 7 paluuta ei löydy

Tämä algoritmi toimii hyvin monissa käytännön tapauksissa, mutta on täysin tehoton, esimerkiksi kun etsitään 10 000 "a"-merkkistä merkkijonoa, jota seuraa "b" 10 miljoonan "a"-merkin merkkijonossa. Tässä tapauksessa se näyttää huonoimman suoritusaikansa Θ ( mn ).

Knuth-Morris-Pratt-algoritmi vähentää tämän ajan arvoon Θ( n ) käyttämällä esilaskentaa kerran jokaiselle tekstin merkille; Boyer-Moore-algoritmi ei ohita vain yhtä merkkiä, vaan niin monta kuin on mahdollista, jotta haku onnistuisi, mikä vähentää tehokkaasti iteraatioiden määrää ulkosilmukan läpi, joten vertailtavien merkkien määrä voi olla verrattavissa n/m :iin. parhaimmillaan. Rabin-Karp-algoritmi keskittyy sen sijaan linjojen 3-6 nopeuttamiseen, josta keskustellaan seuraavassa osiossa.

Hajautustoiminnolla alimerkkijonojen etsiminen siirtämällä

Älykkäämmän ohituksen sijaan Rabin-Karp-algoritmi yrittää nopeuttaa kuvion vastaavuuden tarkistusta tekstin osamerkkijonoilla käyttämällä hash-funktiota . Hajautusfunktio on funktio, joka muuntaa jokaisen merkkijonon numeeriseksi arvoksi, jota kutsutaan hash-arvoksi (hash) ; esimerkiksi merkkijonon "hello" hash voi olla yhtä suuri kuin 5. Algoritmi käyttää sitä tosiasiaa, että jos kaksi merkkijonoa ovat samat, niin myös niiden hash-arvot ovat samat. Siksi meidän tarvitsee vain laskea haetun osamerkkijonon hajautusarvo ja löytää sitten alimerkkijono, jolla on sama hash-arvo.

Tähän liittyy kuitenkin kaksi ongelmaa. Ensimmäinen on se, että koska erilaisia merkkijonoja on niin paljon, kahden eri merkkijonon välillä voi tapahtua törmäys - niiden hajautusten yhteensattuma. Tällaisissa tapauksissa on tarpeen tarkistaa itse alimerkkijonojen yhteensopivuus merkki merkiltä, mikä vie paljon aikaa, jos nämä osajonot ovat pitkiä (tämä tarkistus ei ole tarpeen, jos sovelluksesi sallii vääriä positiivisia tuloksia). Kohtuullisen hyvillä hash-funktioilla (katso alla) törmäykset ovat erittäin harvinaisia, ja keskimääräinen hakuaika on tämän seurauksena lyhyt.

Algoritmiesimerkki (sovelluksen lähdekoodi):

1 funktio RabinKarp( merkkijono s[1..n], merkkijono ala[1..m]) 2 hsub := hash(sub[1..m]) 3 hs := hash(s[1..m]) 4 i : lle arvosta 1 arvoon (n-m+1) 5 , jos hs = hsub 6 , jos s[i..i+m-1] = ali 7 palauttaa i 8 hs := hash(s[i+1..i +m]) 9 paluuta ei löydy

Rivien 2, 3 ja 6 suorittaminen vie aikaa . Rivit 2 ja 3 suoritetaan kuitenkin vain kerran, ja rivi 6 suoritetaan vain, kun hash-arvot täsmäävät, mitä tapahtuu harvoin. Rivi 5 suoritetaan kerran, mutta se vie aina vakioajan. $\Omega (m)$ $n$

Toinen ongelma on hash-uudelleenlaskenta. Osamerkkijonon hash-arvon naiivi uudelleen laskeminen s[i+1..i+m]vie aikaa , ja koska tämä tehdään jokaisessa silmukassa, algoritmi käyttää aikaa , joka on sama kuin useimmat yksinkertaiset algoritmit. Ratkaisu tähän ongelmaan on olettaa, että muuttuja sisältää jo alimerkkijonon hash-arvon . Jos käytät sitä seuraavan hajautusarvon laskemiseen vakioajassa, ongelma on ratkaistu. $O(m)$ $\Omega (min)$ hss[i..i+m-1]

Tämä saavutetaan käyttämällä niin kutsuttua rengashajautetta . Yksinkertaisin esimerkki rengastiivisteestä on lisätä jokaisen myöhemmän merkin arvot osamerkkijonoon ja sitten käyttää tätä kaavaa laskeaksesi jokaisen seuraavan hajautusarvon tietyssä ajassa:

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

Tällainen kaava ei anna mitään takeita siitä, ettei törmäyksiä tapahdu usein, ja on todella helppo varmistaa, että useimmissa sovelluksissa sitä käytettäessä rivin 6 lauseke suoritetaan useammin kuin käytettäessä muita, "älykkäämpiä" ” ring hash -toiminnot.

Huomaa, että jos olemme erittäin epäonnisia tai meillä on erittäin huono hash-funktio, kuten vakiofunktio (hash=const), rivi 6 suoritetaan hyvin todennäköisesti kerran, eli silmukan jokaisessa iteraatiossa. Koska se vie aikaa , algoritmi itsessään vie aikaa . $n$ $\Omega (m)$ $\Omega (min)$

Hash-funktiota käytettiin

Rabin-Karp-algoritmin suorituskyvyn avaimet ovat törmäysten alhainen todennäköisyys ja peräkkäisten tekstin osamerkkijonojen hash-arvon tehokas laskenta. Rabin ja Karp [1] ehdottivat ns. polynomitiivisteen käyttöä (vaikka mikä tahansa muu rengas hash toimisi myös). Tietylle mallille tällainen hash määritellään seuraavasti: $p[1..m]$

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

missä on jokin alkuluku, ja on numero alkaen . Peräkkäisten osamerkkijonojen ja polynomin hajautusarvot lasketaan seuraavasti (huomaa, että tehokkuuden vuoksi luku lasketaan ennen Rabin-Karp-päähakumenettelyä): $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))

Esimerkiksi anna , mielivaltaisesti, ja meillä on teksti "abrakadabra" ja etsimme kuviota, jonka pituus on 3. Voimme laskea alimerkkijonon "bra" tiivisteen alimerkkijonon "abr" (edellinen osamerkkijono) tiivistearvosta vähennetään ensimmäiselle kirjaimelle a lisätty numero "abr":sta, eli ( - ASCII tarkoittaa 'a'), kerrotaan perusluvulla ja lisätään lopuksi viimeinen numero "bralle", eli . Kokonaislukujen ylivuodon välttämiseksi useimmissa toteutuksissa jokaisen näistä neljästä operaatiosta (kertominen laskennassa on erillinen operaatio) on otettava tulos modulo . $x=101$ $q$ $97\times 101^{2}$ $97$ $101$ $97\times 101^{0}=97$ $97\times 101^{2}$ $q$

Rabin ja Karp osoittivat, että jos (eli kiinteä) ja alkuluku valitaan satunnaisesti alueelta , niin törmäyksen todennäköisyys haettaessa kuviota pituisesta tekstistä ei ylitä . Mutta tällaisella tiivistefunktiolla on kaksi merkittävää haittaa: ensinnäkin algoritmi satunnaisalkuluvun valitsemiseksi on melko hankala, ja toiseksi modulaarinen aritmetiikka tekee tällaisesta hashista käytännössä erittäin hidasta (huomaa, että kaikki aritmetiikka peräkkäisten osamerkkijonojen hajautuskaavassa täytyy olla modulo , eli moduulin ottaminen suoritetaan neljä kertaa). $x=2$ $x$ $q$ $[2..n^{3}]$ $n$ $O(1/n)$ $q$

Ditzfelbingerin ym. [2] ehdottamassa nykyaikaisessa polynomitiivisteen modifikaatiossa ei ole näitä puutteita. Tämän vaihtoehdon erona on, että alkuluku on kiinteä, ja luku valitaan satunnaisesti alueelta - ennen algoritmin käynnistymistä (sen ei tarvitse olla alkuluku ollenkaan). On todistettu [2] , että tällaiselle hash-funktiolle törmäyksen todennäköisyys, kun etsitään merkkijonosta kaavaa joidenkin kohdalla ei ylitä :tä luonnollisessa tilanteessa, että kaikille . Modulaarista aritmetiikkaa nopeuttaaksesi voit valita potenssiksi kaksi miinus yksi (ns. Mersennen alkuluvut ): 32-bittisille koneille se sopii parhaiten , 64-bittisille koneille - ; modulo tällaisille arvoille lasketaan käyttämällä nopeita bittikohtaisia operaatioita [3] . Toinen mahdollinen vaihtoehto on arvot tai , joille on olemassa myös nopeita algoritmeja jaon [4] :llä jäljellä olevan osan ottamiseksi (hyväksyttyjen arvojen alue on hieman kaventunut). Voit valita vain kerran ohjelman alussa ja käyttää sitä sitten kaikissa tiivisteissä. $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$

Väärinkäsityksiä polynomitiivisteistä

Jälleen kerran toteamme, että polynomin hajautusarvon takaamat törmäysten puuttumisen takeet ovat erittäin vahvat: vaikka joku tietäen, mutta ei tietäisi , valitsee erityisesti haun mallin ja pituuden, jotta Rabin-Karp-algoritmi polynomihajautus antaa niin monta törmäystä kuin mahdollista, joka tapauksessa joillekin (eli riittävän suurelle eikä super-suurelle ) ja jos se valitaan todella satunnaisesti, ei edes yhden törmäyksen todennäköisyys ole suurempi kuin , että on hyvin pieni. Tämän saavuttamiseksi tulos on tärkeä, joka on alkuluku. Esimerkiksi yleinen virhe on olettaa tai (eli olla käyttämättä modulaarista aritmetiikkaa ollenkaan); esimerkki merkkijonosta, josta löytyy monia polynomitiivistetörmäyksiä sellaisille , ja riippumatta luvun valinnasta , on Morse-Thue-sekvenssi . [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$

Seuraava polynomin hajautustulkinta on suosittu: jokaista merkkijonoa edustaa luku, jonka kanta on , ja sitten tämä luku otetaan modulo . Tällainen tulkinta ei lisää selkeyttä tietyn tiivisteen tehokkuuden luonteeseen, kun taas polynomin tiivisteen tulkinta oikeaksi polynomiksi , jonka kertoimet ovat yhtä suuria kuin symbolien arvot, johtaa yksinkertaisesti todisteeseen alhaisesta todennäköisyydestä. törmäyksestä satunnaisen valinnan kanssa [2] : harkitse kahta eri merkkijonoa ja ; näiden merkkijonojen polynomitiivisteet ovat yhtä suuret, jos ja vain jos ; mutta Bezoutin lauseesta seuraa, että astepolynomilla , joka ei ole identtinen nollan kanssa jäännösten kentässä modulo ( se valitaan yksinkertaiseksi, nimenomaan jäännösrenkaan muuttamiseksi kenttään), on enintään juuret, mikä tarkoittaa, että todennäköisyys törmäys ei ylitä edes satunnaisella valinnalla ; siksi, jos joillekin , kahden eri pituisen merkkijonon törmäyksen todennäköisyys ei ylitä (siis erityisesti virheen todennäköisyys haettaessa merkkijonoa kuviota). $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$ ${\näyttötyyli (m-1)/q}$ ${\displaystyle q>n^{c}\geq m^{c))$ $c>1$ $m$ ${\näyttötyyli (m-1)/q<n/q<1/n^{c-1))$ $1/n^{c-2}$

Joskus on myös mahdollista törmätä suositukseen käyttää alkulukua , mutta ilmeisesti, lukuun ottamatta empiirisiä havaintoja, jotka koskevat joitakin hyvin rajoitettuja tietomääriä, tällainen neuvo ei ole enää perusteltu. $x$

Rabin-Karp ja monien yksilöiden etsiminen

Hitaan pahimman tapauksen käyttäytymisensä vuoksi Rabin-Karp- algoritmi on huonompi kuin Knuth-Morris-Pratt- algoritmi , Boyer-Moore-algoritmi ja muut nopeat merkkijonohakualgoritmit . Rabin-Karp-algoritmia voidaan kuitenkin käyttää näytteiden joukon löytämiseen parhaimmillaan lineaarisessa ajassa ja vaikeimmin saavutettavissa olevassa neliössä pahimmassa tapauksessa; vaikka tässäkin se häviää pahimmassa tapauksessa Aho-Korasik-algoritmille , jolla on lineaarinen käyntiaika.

Jos haluamme löytää minkä tahansa kuvion tietystä tekstistä suuresta joukosta esimerkiksi k kiinteää samanpituista kuviota, voimme muokata Rabin-Karp-algoritmia käyttämällä hash-taulukkoa tai mitä tahansa muuta tietorakennetta tarkistaaksemme, että annettu merkkijono kuuluu hash-joukkoon. Etsimme näytearvot:

function RabinKarpSet( merkkijono s[1..n], merkkijonon alaosien joukko , m) { set hsubs : = kullekin alaosalle

\varno mitään

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

\kuppi

hs := hash(s[1..m]) i : lle arvosta 1 arvoon (n-m+1) , jos hs ∈ hsubs jos s[i..i+m-1] = merkkijono alaosista, joissa on hash hs palauttaa i hs := hash(s[i+1..i+m]) palautusta ei löydy }

Muut algoritmit voivat etsiä yhtä näytettä O( n ) ajassa, ja siten niitä voidaan käyttää k näytettä etsimään O( n k ) ajassa. Sitä vastoin yllä oleva Rabin-Karp-algoritmin muunnelma voi löytää kaikki k näytettä odotetussa ajassa O( n + k ), koska hash-taulukossa testataan tapausta, jossa alimerkkijonon hash on yhtä suuri kuin mikä tahansa näyte käyttää O(1)-aikaa. Käytännössä suhteellisen helpon toteutuksen ja toiminnan nopeuden vuoksi tämä vaihtoehto voi usein olla parempi kuin Aho-Korasik-algoritmi .

Katso myös

Muistiinpanot

↑ 1 2 Rabin, Karp, 1987 .
↑ 1 2 3 Dietzfelbinger, Gil, Matias, Pippinger, 1992 .
↑ SE Anderson. Hieman hämmentäviä hakkereita. Arkistoitu 1. kesäkuuta 2020 Wayback Machinessa
↑ Krovetz, Rogaway, 2000 .
↑ Pachocki, Radoszewski, 2013 .

Kirjallisuus

Kormen T. H. , Leyzerson C. E. , Rivest R. L. , Stein K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / toim. S. N. Triguba ; per. englannista. I. V. Krasikov , N. A. Orekhov ,N. Romanov - 2. painos - M .: Williams, 2005. - 801 s. — ISBN 5-8459-0857-4 .
Rabin MO , Karp RM Tehokkaat satunnaistetut kuvionsovitusalgoritmit // IBM Journal of Research and Development . - IBM, 1987. - T. 31 , nro 2 . — S. 249–260 . - doi : 10.1147/rd.312.0249 .
Dietzfelbinger M., Gil J., Matias Y., Pippenger N. Polynomiset hajautusfunktiot ovat luotettavia // Proceedings of the 19th International Colloquium on Automata, Languages ja Programming (ICALP'92) . — Lontoo, UK: Springer-Verlag, 1992. — s. 235–246 . - doi : 10.1007/3-540-55719-9_77 .
Krovetz T., Rogaway P. Nopea yleinen hajautus pienillä avaimilla ja ilman esikäsittelyä: PolyR-rakenne // Kansainvälisen tietoturva- ja kryptologiakonferenssin julkaisut. - Berliini, Saksa: Springer-Verlag, 2000. - s. 73–89 . - doi : 10.1007/3-540-45247-8_7 .
Pachocki J., Radoszewski J. Missä käytetään ja miten ei käytetä polynomimerkkijonohajausta // Informatiikan olympialaiset. - Vilnus, Liettua: Vilnuksen yliopisto, 2013. - V. 7 . — S. 90–100 .

jouset
Merkkijonojen samankaltaisuusmitat	Etäisyys Damerausta Loewensteiniin Levenshtein etäisyys Hammingin etäisyys Jaro-Winkler yhtäläisyydet
Alimerkkijonohaku	Boyer-Mooren algoritmi Boyer-Moore-Horspool-algoritmi Knuth-Morris-Pratt-algoritmi Rabin-Karp algoritmi etuliitetoiminto Z-toiminto Algoritmi Aho - Korasik
palindromit	palindromipuu Manakerin algoritmi
Jakson tasaus	Needleman-Wunsha-algoritmi Smith-Waterman-algoritmi
Suffiksirakenteet	Suffiksitaulukko Suffiksiautomaatti suffiksi puu etuliite puu
muu	jäsentäminen Kuvioiden yhteensopivuus Suurin yhteinen osasarja Suurin yhteinen osamerkkijono