Gördülő hash

Rolling hash ( eng.  rolling hash , ring hash is ) egy hash függvény , amely egy bizonyos ablakon belül dolgozza fel a bemenetet. Az eltolt ablak hash értékének lekérése ilyen függvényekben olcsó művelet. Az érték újraszámításához csak az előző hash értékét, az ablakon kívül maradt bemeneti adatok és az ablakba került adatok értékét kell ismerni. Más szóval, ha a sorozat hash-je , akkor az "eltolt" sorozat hash-je egy könnyen kiszámítható függvény segítségével szerezhető meg .

A hash gyors "eltolásának" képessége bizonyos korlátozásokat támaszt az elméleti garanciákra vonatkozóan. Konkrétan kimutatták [1] , hogy a gyűrűs hash családok nem lehetnek 3-függetlenek ; maximum - univerzális vagy 2-független . A legtöbb alkalmazáshoz azonban az univerzális (még hozzávetőleges) is elegendő.

A gyűrűkivonat egy részstring keresésére szolgál a Rabin-Karp algoritmusban, N-gramm hash-ek kiszámítására a szövegben [2] , valamint az rsync programban a bináris fájlok összehasonlítására (az Adler-32 gyűrűs verziót használják ). .

Polinom hash

A Rabin-Karp algoritmus gyakran használ egy egyszerű polinomi gyűrű hash-t, amely szorzási és összeadási műveleteken alapul [3] [4] :

.

Az önkényes pontosságú egész aritmetika használatának elkerülése érdekében a maradékgyűrűs aritmetika modulo , amely egy gépszóba belefér . Az állandók megválasztása nagyon fontos a minőségi hash eléréséhez. A hash eredeti változatában azt feltételezték, hogy véletlenszerűen kiválasztott prímszámnak kell lennie, és . [3] Mivel azonban a véletlen prímszám kiválasztásának algoritmusa nem olyan egyszerű, inkább olyan hash-változatot használnak, amelyben rögzített prímszám, de véletlenszerűen választják ki a tartományból . Dietzfelbinger és munkatársai [4] kimutatták, hogy a hashnek ez a változata ugyanazokkal az elméleti jellemzőkkel rendelkezik, mint az eredeti változat. Különösen annak a valószínűsége, hogy két különböző karakterlánc és és hash- je nem haladja meg a , if és tartományból származó egész számokat , és valóban véletlenszerűen kerül kiválasztásra.

A régi bemeneti szimbólumok eltávolítása és újak hozzáadása a képlet első vagy utolsó tagjának összeadásával vagy kivonásával történik (modulo ). Egy tag eltávolításához egy előre kiszámított érték kerül tárolásra . Az ablak eltolása a teljes polinom szorzásával vagy osztásával történik (ha egyszerű, akkor a maradékgyűrűben osztás helyett lehet reciprokkal is szorozni). A gyakorlatban a legkényelmesebb a 32, illetve 64 bites gépszavak feltételezése vagy esetében (ezek az úgynevezett Mersenne-prímek ). Ilyen esetben a modulo művelet számos számítógépen végrehajtható gyors bitenkénti eltolási és összeadási műveletekkel [5] . Egy másik lehetséges választás a vagy értékek , amelyekhez szintén vannak gyors algoritmusok az osztás hátralevő részének felvételére (ebben az esetben az elfogadható értékek tartománya kissé szűkül) [6] . Általános tévhit a hinni . Vannak olyan karakterlánc-családok, amelyeken a c hash mindig sok ütközést produkál , függetlenül attól, hogy melyiket választottuk . [7] Ezek és a további megvalósítási részletek, valamint a polinomiális hash elméleti elemzése megtalálható a Rabin-Karp algoritmusról szóló cikkben .

Polinom hash GF(2 L ) felett

Ez a hash hasonlít egy normál polinomi hash-hez, de az összes számítás a végső mezőben történik . Általában 64-re van állítva. A mezőelemek számok . Az összeadás a mezőben a bitenkénti kizárólagos „vagy” művelettel , a szorzás pedig a művelettel történik , amely először nem transzferálhatóan megszorozza az -t a -val, majd az eredmény „nem transzferálható” osztásának maradékát veszi fel. valamilyen kiválasztott fix elemmel (itt a nem átvihető osztás a nem transzferálható szorzásra fordított művelet). Az elemet úgy kell megválasztani, hogy és egy irreducibilis polinom legyen a mező felett (a mezőt gyakran úgy tekintik, mint a mező feletti polinomok halmazát, egy tetszőleges fokszámú irreducibilis polinomot ). Például felteheti a [8] -ot . Ezután a hash kiszámítása a következőképpen történik [4] :

,

ahol a hash inicializálási szakaszában véletlenszerűen kiválasztott szám a tartományból , és a hol ismétlődő rövid jelölése . Az algebra alaptételével kimutatható , hogy két különböző hosszúságú húr hash ütközésének valószínűsége nem haladja meg a . Kimutatták [8] , hogy a modern Intel és AMD processzorokon a hash-hez szükséges mezőn belüli összes aritmetika hatékonyan kiszámítható a CLMUL kiterjesztés utasításaival .

Kivonat ciklikus polinomokkal (Buzhash)

Legyen  valami hash, amely a kivonatolt karakterlánc karaktereit -bites számokká képezi le (általában vagy ). A ciklikus polinomok általi hash a következőképpen definiálható [2] :

ahol  egy bitenkénti exkluzív "vagy" művelet , és egy  bitszám bitenkénti ciklikus eltolása balra. Könnyen kimutatható, hogy ez a hash kör alakú:

Ennek a hashnek az a fő előnye, hogy csak a sok modern számítógépen elérhető gyors bitenkénti műveleteket használja. A hash minősége közvetlenül függ a függvény kiválasztásától . Lemire és Cacer [1] bebizonyította, hogy ha egy függvényt véletlenszerűen választunk ki független hash-függvények családjából , akkor annak a valószínűsége, hogy két különböző hosszúságú karakterlánc hash-je illeszkedik , nem haladja meg a -t . Ez bizonyos korlátozásokat ír elő azon feladatok körében, amelyekben ez a hash használható. Először is, a hashálható karakterláncok hosszának kisebbnek kell lennie, mint . Általános célú kivonatoló algoritmusoknál ez a feltétel gondot jelenthet, de például a -grams kivonatnál , ahol általában nem haladja meg a 16-ot, természetes az ilyen megszorítás ( -gram esetén a szöveg egyes tokenjei játsszák a szereplők szerepe). Másodszor, bizonyos esetekben a független funkciók családjának kiválasztása is problémát jelenthet. Egy bájtos ábécé esetében a 256 különböző véletlen bites számból álló táblázat által kódolt függvénycsalád rendelkezik függetlenségi tulajdonsággal (a függvény kiválasztása a táblázat kitöltése). A -gramok kivonatolásánál különböző véletlenszerű -bit számokat rendelhetünk a különböző tokenekhez (általában az ilyen feladatokban a különböző tokenek száma viszonylag kicsi), és egy ilyen hash függvénycsaládnak megvan a függetlensége is.

Rabin hash

Ez a hash csak abban a speciális esetben alkalmazható, amikor a kivonatolt karakterlánc karakterei a 0 és az 1. A hash lényege, hogy a bemeneti karakterláncot polinomként tekintsük a mező felett , és maga a hash veszi az osztás maradéka egy véletlenszerűen kiválasztott hash-sel az inicializálási szakaszban irreducibilis fokú a mező felett . Ez lényegében ugyanaz az eljárás, mint a CRC -ben . Tekintsük részletesebben.

Egy karakterlánc kivonatolásának eredménye egy bitsorozat . A számot egyszerűen [9] választjuk , és elég nagyot, de úgy, hogy a sorozat egy gépszóba beleférjen (általában take vagy [9] ). Legyen valamilyen irreducibilis fokszámú polinom a mező felett . Jelölje a megfelelő számmal bitreprezentációval . A hash függvényt úgy definiáljuk, mint egy bitenkénti reprezentációval rendelkező számot úgy, hogy a polinom a polinom polinommal való osztásának maradéka , azaz .

A meglehetősen zavaros definíció ellenére a Rabin hash meglehetősen könnyen megvalósítható (ha már találtunk egy irreducibilis polinomot). A számítások egy ilyen egyszerű megfigyelésen alapulnak: ha egy bitreprezentált szám polinomot kódol , akkor a szám polinomot kódol , ahol azt a műveletet jelöli , hogy az egy bitet bitenként balra toljuk , és a legkisebb jelentőségű bitet nullára cseréljük ( nem tévesztendő össze a fent meghatározott ciklikus eltolással!). Legyen , és  a bit reprezentációja . Ezután a következőképpen számítják ki:

ha ha

A hash kör alakú. Legyen és  a bit reprezentációja . A hash kiszámítása a következőképpen történik [9] :

ha ha

ahol  egy olyan bitszám, amelynek bitjei megfelelnek a polinomnak . A számot a rendszer előre kiszámítja egy hosszúságú karakterlánc hashének inicializálása során .

A fő nehézség egy irreducibilis fokú polinom véletlenszerű kiválasztása . Rabin [9] egy hatékony algoritmust írt le erre, és bebizonyította, hogy két különböző hosszúságú karakterlánc véletlenszerű választással történő hash ütközésének valószínűsége nem haladja meg a -t .

Vegye figyelembe, hogy ezt a hash-t gyakran összekeverik egy polinomiális hash-sel, a hasonló hatókör, a polinomok figyelembevétele és a közös szerző miatt.

Linkek

Jegyzetek

  1. 12 Lemire , Kaser, 2010 .
  2. 12 Cohen , 1997 .
  3. 1 2 Rabin, Karp, 1987 .
  4. 1 2 3 Dietzfelbinger, Gil, Matias, Pippinger, 1992 .
  5. SE Anderson. Kicsit pörgős hackek. Archiválva 2020. június 1-én a Wayback Machine -nél
  6. Krovetz, Rogaway, 2000 .
  7. Pachocki, Radoszewski, 2013 .
  8. 12 Lemire , Kaser, 2016 .
  9. 1 2 3 4 Rabin, 1981 .

Irodalom