Rullaava hash

Rolling hash ( eng. rolling hash , myös ring hash ) on hash-funktio , joka käsittelee syötteen tietyssä ikkunassa. Hajautusarvon saaminen siirretylle ikkunalle tällaisissa funktioissa on halpa toimenpide. Arvon uudelleen laskemiseksi sinun tarvitsee vain tietää edellinen hash-arvo, ikkunan ulkopuolelle jääneiden syöttötietojen arvo ja ikkunaan pudonneiden tietojen arvo. Toisin sanoen, jos on sekvenssin tiiviste , niin "siirretyn" sekvenssin tiiviste voidaan saada käyttämällä helposti laskettavaa funktiota . $x=h(a_{1}a_{2}\cdots a_{n})$ ${\displaystyle a_{1}a_{2}\cdots a_{n))$ $h(a_{2}a_{3}\cdots a_{n}a_{n+1})$ ${\displaystyle a_{2}a_{3}\cdots a_{n}a_{n+1))$ $f(x,a_{1},a_{n+1})$

Mahdollisuus nopeasti "siirtää" hashia asettaa joitain rajoituksia teoreettisille takuille. Erityisesti on osoitettu [1] , että rengastiivisteiden perheet eivät voi olla 3-riippumattomia ; maksimi - universaali tai 2-riippumaton . Useimmissa sovelluksissa universaalisuus (jopa likimääräinen) on kuitenkin riittävä.

Ring hashia käytetään etsimään alimerkkijonoa Rabin-Karp- algoritmissa , laskemaan N- grammien tiivisteitä tekstistä [2] ja myös rsync -ohjelmassa vertailemaan binääritiedostoja (käytetään adler-32 rengasversiota ) .

Polynomi hash

Rabin - Karp-algoritmi käyttää usein yksinkertaista polynomirengastiivistettä, joka perustuu kerto- ja yhteenlaskuoperaatioihin [3] [4] :

h(a_{1}a_{2}\cdots a_{n})=(a_{1}x^{n-1}+a_{2}x^{n-2}+a_{3} x^{n-3}+\cdots +a_{n}x^{0}){\bmod {q}}

Mielivaltaisen tarkkuuden kokonaislukuaritmeettisen käytön välttämiseksi käytetään jäännösrengasaritmetiikkaa modulo , joka sopii yhteen konesanaan . Vakioiden valinta on erittäin tärkeä laadukkaan tiivisteen saamiseksi. Hajautuksen alkuperäisessä versiossa oletettiin, että sen pitäisi olla satunnaisesti valittu alkuluku ja . [3] Mutta koska algoritmi satunnaisen alkuluvun valitsemiseksi ei ole niin yksinkertainen, he käyttävät mieluummin hash-varianttia, jossa on kiinteä alkuluku, mutta joka valitaan satunnaisesti alueelta . Dietzfelbinger ym. [4] osoittivat, että tällä hash-versiolla on samat teoreettiset ominaisuudet kuin alkuperäisellä. Erityisesti todennäköisyys, että kahden eri merkkijonon ja ja hajautusarvot eivät ylitä , if ja ovat kokonaislukuja alueelta , ja valitaan todella satunnaisesti. $q$ $x$ $q$ $q$ $x=2$ $q$ $x$ $\{0,1,\ldots ,q-1\}$ ${\displaystyle a_{1}a_{2}\cdots a_{n))$ ${\displaystyle b_{1}b_{2}\cdots b_{n))$ $1/n^{c}$ $a_{1},\ldots ,a_{n}$ ${\displaystyle b_{1},\ldots ,b_{n))$ ${\näyttötyyli [0,q)}$ $q>n^{c+1}$ $x$

Vanhojen syöttösymbolien poistaminen ja uusien lisääminen tehdään lisäämällä tai vähentämällä kaavan ensimmäinen tai viimeinen termi (modulo ). Jäsenen poistamiseksi tallennetaan ennalta laskettu arvo . Ikkunaa siirretään kertomalla koko polynomi tai jakamalla ( jos se on yksinkertainen, niin jäännösrenkaassa on mahdollista kertoa käänteisluvulla jakamisen sijaan). Käytännössä on kätevintä olettaa 32- ja 64-bittisiä konesanoja (nämä ovat ns. Mersennen alkulukuja ). Siinä tapauksessa modulo-operaatio voidaan suorittaa monilla tietokoneilla käyttämällä nopeita bittikohtaisia siirto- ja summaustoimintoja [5] . Toinen mahdollinen vaihtoehto on arvot tai , joille on olemassa myös nopeita algoritmeja jaon loppuosan ottamiseksi (tässä tapauksessa hyväksyttävien arvojen alue on hieman kaventunut) [6] . Yleinen väärinkäsitys on uskoa . On olemassa merkkijonoperheitä, joissa hash c tuottaa aina monia törmäyksiä valinnasta riippumatta . [7] Nämä ja muut toteutusyksityiskohdat ja polynomin hashin teoreettinen analyysi löytyvät Rabin-Karp-algoritmia käsittelevästä julkaisusta . $q$ $a_{1}x^{n-1}$ $x^{n-1}{\bmod {q))$ $h(a_{1}a_{2}\cdots a_{n})$ $x$ $x$ $q$ $q=2^{31}-1$ $q=2^{61}-1$ $q=2^{32}-5$ $q=2^{64}-59$ $q$ $x$ $q=2^{32}$ ${\displaystyle q=2^{L))$ $L$

Polynomi hash yli GF(2 L )

Tämä hash on samanlainen kuin tavallinen polynomitiiviste, mutta kaikki sen laskelmat suoritetaan viimeisessä kentässä . Yleensä asetetaan arvoon 64. Kenttäelementit ovat numeroita . Kentän yhteenlasku toteutetaan käyttämällä bittikohtaista poissulkevaa "tai" -toimintoa ja kertolasku suoritetaan operaatiolla , joka ensin ei-siirrettävästi kertoo : llä ja ottaa sitten loppuosan tuloksen "ei-siirrettävästä" jaosta. jollakin valitulla kiinteällä elementillä (tässä ei-siirrettävä jako on operaatio käänteinen ei-siirrettävälle kertolaskulle). Elementti on valittava siten, että ja on pelkistymätön polynomi kentän yli (kenttää pidetään usein kentän yli olevien polynomien joukkona modulo mielivaltaisen asteisen redusoitumattoman polynomin joukoksi ). Voit esimerkiksi laittaa [8] . Sitten hash lasketaan seuraavasti [4] : $\mathrm {GF} (2^{L})$ $L$ $0,1,\ldots ,2^{L}-1$ $\oplus$ $a\star b$ $a$ $b$ ${\displaystyle q\in \{2^{L},2^{L}+1,\ldots ,2^{L+1}-1\))$ $q=2^{i_{1}}+2^{i_{2}}+\cdots +2^{i_{k}}$ $L=i_{1}>i_{2}>\cdots >i_{k}\geq 0$ $x^{i_{1}}+x^{i_{2}}+\cdots +x^{i_{0}}$ $GF(2)$ $\mathrm {GF} (2^{L})$ ${\mathrm {GF}}(2)$ $L$ $q=2^{64}+2^{4}+2^{3}+2+1$

h(a_{1}a_{2}\cdots a_{n})=(a_{1}\star x^{n-1})\oplus (a_{2}\star x^{n- 2})\oplus \cdots \oplus (a_{n-1}\star x)\oplus a_{n}

jossa on satunnaisesti valittu luku tiivisteen alustusvaiheessa alueelta , ja se on lyhyt merkintä missä toistuvia kertoja. Algebran peruslauseen avulla voidaan osoittaa, että kahden eripituisen merkkijonon tiivistystörmäyksen todennäköisyys ei ylitä . On osoitettu [8] , että nykyaikaisissa Intel- ja AMD -prosessoreissa kaikki hajautusarvon edellyttämä kentän aritmetiikka voidaan laskea tehokkaasti käyttämällä CLMUL -laajennuksen ohjeita . $x$ $\{0,1,\ldots ,2^{L}-1\}$ $x^{m}$ $x\star x\star \cdots \star x$ $x$ $m$ $n$ $n/2^{L}$ $\mathrm {GF} (2^{L})$

Hash syklisten polynomien mukaan (Buzhash)

Olkoon jokin hash, joka yhdistää tiivistetyn merkkijonon merkit -bittisiksi numeroiksi (yleensä tai ). Hajautus syklisten polynomien avulla määritellään seuraavasti [2] : $h'$ $a_{1},\ldots ,a_{n}$ $L$ $L=32$ $L=64$

h(a_{1}a_{2}\cdots a_{n})=s^{n-1}(h'(a_{1}))\oplus s^{n-2}(h' (a_{2}))\oplus \cdots \oplus s(h'(a_{n-1}))\oplus h'(a_{n}),

jossa on bittikohtaisesti poissulkeva "tai" -operaatio ja operaatio bittiluvun syklisestä siirrosta bitti kerrallaan vasemmalle. On helppo osoittaa, että tämä hash on pyöreä: $\oplus$ $s^{i}(x)$ $L$ $x$ $i$

h(a_{2}a_{3}\ldots a_{n+1})=s(h(a_{1}a_{2}\ldots a_{n}))\oplus s^{n} (h'(a_{1}))\oplus h'(a_{n+1}).

Tämän hashin tärkein etu on, että se käyttää vain nopeita bittikohtaisia toimintoja, jotka ovat saatavilla monissa nykyaikaisissa tietokoneissa. Hajautuksen laatu riippuu suoraan funktion valinnasta . Lemire ja Cacer [1] osoittivat, että jos funktio valitaan satunnaisesti riippumattomien tiivistefunktioiden perheestä , niin kahden eripituisen merkkijonon tiivisteiden yhteensopivuuden todennäköisyys ei ylitä . Tämä asettaa tiettyjä rajoituksia tehtäville, joissa tätä tiivistettä voidaan käyttää. Ensinnäkin tiivistettävien merkkijonojen pituuden on oltava pienempi kuin . Yleiskäyttöisissä hajautusalgoritmeissa tämä ehto voi olla ongelma, mutta esimerkiksi hajautusalgoritmissa -grams , jossa ei yleensä ylitä 16, tällainen rajoitus on luonnollinen ( -grammien tapauksessa tekstin yksittäiset merkit toistavat hahmojen rooli). Toiseksi itsenäisten toimintojen perheen valinta voi myös olla ongelma joissain tapauksissa. Tavuaakkostossa funktioperheellä, joka on koodattu 256 eri satunnaisbittiluvun taulukolla, on riippumattomuusominaisuus (funktion valinta on taulukon täyttäminen). Hashing -grammeja varten voit antaa eri tokeneille erilaisia satunnaisia -bittinumeroita (yleensä eri merkkien määrä tällaisissa ongelmissa on suhteellisen pieni), ja tällaisella hash-funktioiden perheellä on myös itsenäisyyden ominaisuus. $h'$ $h'$ $n$ $1/2^{L-n+1}$ $L$ $n$ $n$ $n$ $h'$ $h'$ $L$ $n$ $L$ $h'$

Rabinin hash

Tämä tiiviste on sovellettavissa vain siinä erikoistapauksessa, jossa tiivistetyn merkkijonon merkit ovat numerot 0 ja 1. Hajautuksen ideana on tarkastella syötemerkkijonoa polynomina kentän päällä ja itse hash ottaa loput jaosta satunnaisesti valitulla hashilla alustusvaiheessa redusoitumaton astepolynomi kentän yli . Tämä on pohjimmiltaan sama menettely kuin CRC :ssä . Tarkastellaanpa sitä tarkemmin. ${\displaystyle a_{1}a_{2}\cdots a_{n))$ ${\displaystyle a_{1}a_{2}\cdots a_{n))$ $A(x)=a_{1}x^{n-1}\oplus a_{2}x^{n-2}\oplus \cdots \oplus a_{n-1}x\oplus a_{n }x^{0}$ ${\mathrm {GF}}(2)$ $Kirves)$ $P(x)$ $L$ ${\mathrm {GF}}(2)$

Merkkijonon hajautustulos on bittijono . Numero valitaan yksinkertainen [9] ja riittävän suuri, mutta niin, että sekvenssi mahtuu yhteen konesanaan (yleensä ota tai [9] ). Olkoon jokin redusoitumaton astepolynomi kentän yli . Merkitään vastaavalla numerolla bittimuodolla . Hash-funktio määritellään luvuksi, jolla on bittimuotoinen esitys siten, että polynomi on polynomin polynomilla jakamisen jäännös , eli . ${\displaystyle a_{1}a_{2}\cdots a_{n))$ ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0))$ $L$ ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0))$ $L=31$ $L=61$ ${\displaystyle P(x)=p_{L}x^{L}\oplus p_{L-1}x^{L-1}\oplus \cdots \oplus p_{1}x\oplus p_{0))$ $L$ ${\mathrm {GF}}(2)$ $s$ ${\displaystyle p_{L}p_{L-1}\cdots p_{0))$ $h(a_{1}a_{2}\cdots a_{n})$ $b_{L-1}b_{L-2}\cdots b_{0},$ $B(x)=b_{L-1}x^{L-1}\oplus b_{L-2}x^{L-2}\oplus \cdots \oplus b_{1}x\oplus b_ {0}$ $A(x)=a_{1}x^{n-1}\oplus a_{2}x^{n-2}\oplus \cdots \oplus a_{n-1}x\oplus a_{n }$ $P(x)$ $B(x)=A(x){\bmod {P))(x)$

Melko hämmentävästä määritelmästä huolimatta Rabin-hash on melko helppo toteuttaa (jos redusoitumaton polynomi on jo löydetty). Laskelmat perustuvat tällaiseen yksinkertaiseen havaintoon: jos luku , jossa on bittiesitys, koodaa polynomin , niin luku koodaa polynomin , jossa tarkoittaa operaatiota , jossa numero yksi bitti siirretään bittittäin vasemmalle siten, että vähiten merkitsevä bitti korvataan nollalla ( ei pidä sekoittaa edellä määriteltyyn sykliseen siirtoon!). Antaa , ja olla bitin esitys . Sitten se lasketaan seuraavasti: $P(x)$ $b$ ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0))$ $B(x)=b_{L-1}x^{L-1}\oplus b_{L-2}x^{L-2}\oplus \cdots \oplus b_{1}x\oplus b_ {0}$ $\mathop {sh} (b)$ $x\cdot B(x)$ $\mathop {sh} (b)$ $b$ $s$ $b=h(a_{1}a_{2}\cdots a_{i})$ ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0))$ $b$ $h(a_{1}a_{2}\cdots a_{i}a_{i+1})$

\mathop {sh} (b)\oplus a_{i+1},

jos

b_{L-1}=0,

\mathop {sh} (b)\oplus p\oplus a_{i+1},

jos

b_{L-1}=1.

Hash on pyöreä. Antaa ja olla bitin esitys . Hash lasketaan seuraavasti [9] : $b=h(a_{1}a_{2}\cdots a_{n})$ ${\displaystyle b_{L-1}b_{L-2}\cdots b_{0))$ $b$ $h(a_{2}a_{3}\cdots a_{n}a_{n+1})$

\mathop {sh} (b)\oplus a_{n}\oplus (a_{1}\cdot c),

jos

b_{L-1}=0,

\mathop {sh} (b)\oplus p\oplus a_{n}\oplus (a_{1}\cdot c),

jos

b_{L-1}=1,

jossa on bittiluku, jonka bittiesitys vastaa polynomia . Luku lasketaan etukäteen alustattaessa pituisen merkkijonon tiivistettä . $c$ $L$ $x^{n}{\bmod {P}}(x)$ $c$ $n$

Suurin vaikeus on valita satunnaisesti redusoitumaton astepolynomi . Rabin [9] kuvasi tehokkaan algoritmin tämän tekemiseen ja osoitti, että kahden eripituisen merkkijonon hash-törmäyksen todennäköisyys satunnaisella valinnalla ei ylitä . $P(x)$ $L$ $n$ $P(x)$ $n/2^{L}$

Huomaa, että tämä hash sekoitetaan usein polynomitiivisteeseen samanlaisen laajuuden, polynomien huomioimisen ja yhteisen tekijän vuoksi.

Linkit

ngramhashing on ilmainen C++-toteutus useille rengashajautustoiminnoille
rollinghashjava — Apache-lisenssillä lisensoitujen rullaavien hash-toimintojen Java-toteutus

Muistiinpanot

↑ 12 Lemire , Kaser, 2010 .
↑ 12 Cohen , 1997 .
↑ 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 .
↑ 12. Lemire , Kaser, 2016 .
↑ 1 2 3 4 Rabin, 1981 .

Kirjallisuus

Cohen JD Rekursiiviset hajautusfunktiot n-grammille // ACM Transactions on Information Systems . - New York, USA: ACM, 1997. - V. 15 , nro 3 . — S. 291–320 . - doi : 10.1145/256163.256168 .
Dietzfelbinger M., Gil J., Matias Y., Pippenger N. Polynomiset hajautusfunktiot ovat luotettavia // Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP'92). - Berliini, Saksa: 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 .
Lemire D., Kaser O. Rekursiivinen n-grammien hajautus on parhaimmillaan pareittain riippumatonta // Journal Computer Speech and Language. - Lontoo, Iso-Britannia: Academic Press Ltd., 2010. - V. 24 , nro 4 . — S. 698–710 . - doi : 10.1016/j.csl.2009.12.001 .
Lemire D., Kaser O. Nopeampi 64-bittinen yleinen hajautus käyttämällä kantamattomia kertolaskuja // Journal of Cryptographic Engineering. - Berliini, Saksa: Springer-Verlag, 2016. - V. 6 , nro 3 . — S. 171–185 . - doi : 10.1007/s13389-015-0110-5 .
Rabin M. O. Sormenjäljet satunnaisten polynomien avulla // Tekninen raportti TR-CSE-03-01. - Center for Research in Computing Technology, Harvard University, 1981. - P. 1-14 . Arkistoitu alkuperäisestä 29. huhtikuuta 2018.
Rabin M. O. , Karp R. M. Tehokkaat satunnaistetut mallinsovitusalgoritmit // IBM Journal of Research and Development . - IBM, 1987. - T. 31 , nro 2 . — S. 249–260 . - doi : 10.1147/rd.312.0249 .
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 .