Rolling hash

Un hash rulant (numit și hash recursiv sau sumă de verificare rulantă ) este o funcție hash care procesează intrarea printr-o fereastră glisantă pe intrare. Unele funcții hash permit calcularea foarte rapidă, actualizând rezultatul pe baza valorii hash din fereastra anterioară și pe baza valorilor adăugate și eliminate din fereastră la iterația curentă, similar cu calcularea unei medii mobile .

Toate funcțiile hash rulante au complexitate de calcul liniară în numărul de elemente, dar complexitatea în ceea ce privește lungimea k a ferestrei poate varia în funcție de algoritm. De exemplu, funcția hash rulantă a lui Rabin-Karp necesită înmulțirea a două numere întregi ale lui $k$ ${\ displaystyle k}$ $k$ bit, cu complexitate $O(k\log k2^{O(\log ^{*}k)})$ ${\ displaystyle O (k \ log k2 ^ {O (\ log ^ {*} k)})}$ ${\ displaystyle O (k \ log k2 ^ {O (\ log ^ {*} k)})}$ , ^{[1] în} timp ce hashul de n-gram cu polinoame ciclice poate fi calculat în timp liniar. ^[2]

Un hash rulant poate fi cel mult o funcție independentă de două până la două ^[2] sau o funcție de hash universal , dar nu poate fi un kak independent.

Rolling hash de la Rabin-Karp

Algoritmul Rabin-Karp folosește de obicei un hash de rulare foarte simplu, care folosește doar adunarea și multiplicarea:

$H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}$ ${\ displaystyle H = c_ {1} a ^ {k-1} + c_ {2} a ^ {k-2} + c_ {3} a ^ {k-3} + ... + c_ {k} a ^ {0}}$ ${\ displaystyle H = c_ {1} a ^ {k-1} + c_ {2} a ^ {k-2} + c_ {3} a ^ {k-3} + ... + c_ {k} a ^ {0}}$

unde este $la$ ${\ displaystyle a}$ $la$ este o constantă și $c_{1},...,c_{k}$ ${\ displaystyle c_ {1}, ..., c_ {k}}$ ${\ displaystyle c_ {1}, ..., c_ {k}}$ sunt caracterele introduse. Pentru a evita valorile imense ale $H.$ ${\ displaystyle H}$ $H.$ , toate calculele sunt modulo $n$ ${\ displaystyle n}$ $n$ . Alegerea $la$ ${\ displaystyle a}$ $la$ Și $n$ ${\ displaystyle n}$ $n$ este foarte important pentru eficacitatea hashului.

Adăugarea sau eliminarea caracterelor implică doar cei doi termeni extremi, în timp ce pentru a muta caracterele rămase la stânga, o multiplicare este suficientă pentru $la$ ${\ displaystyle a}$ $la$ , sau o diviziune pentru a trece la dreapta. Funcționând în aritmetică modulară, $la$ ${\ displaystyle a}$ $la$ se poate alege astfel încât să admită multiplicarea inversă $a^{-1}$ ${\ displaystyle a ^ {- 1}}$ $a ^ {{- 1}}$ , permițându-vă să vă deplasați la dreapta cu o multiplicare în loc de o diviziune.

Polinoame ciclice

Hashing-ul folosind polinoame ciclice ^[3] evită utilizarea înmulțirilor, înlocuindu-le cu schimbarea butoiului . Hash H este o valoare din interval $[0,2^{L})$ ${\ displaystyle [0,2 ^ {L})}$ ${\ displaystyle [0,2 ^ {L})}$ , definit ca

$H=s^{k-1}(h(c_{1}))\oplus s^{k-2}(h(c_{2}))\oplus \ldots \oplus s(h(c_{k-1}))\oplus h(c_{k})$ ${\ displaystyle H = s ^ {k-1} (h (c_ {1})) \ oplus s ^ {k-2} (h (c_ {2})) \ oplus \ ldots \ oplus s (h (c_ {k-1})) \ oplus h (c_ {k})}$ ${\ displaystyle H = s ^ {k-1} (h (c_ {1})) \ oplus s ^ {k-2} (h (c_ {2})) \ oplus \ ldots \ oplus s (h (c_ {k-1})) \ oplus h (c_ {k})}$

unde este $s$ ${\ displaystyle s}$ $s$ este o rotație ciclică de un bit spre stânga (ex. $s(10011)=00111$ ${\ displaystyle s (10011) = 00111}$ ${\ displaystyle s (10011) = 00111}$ ), $\oplus$ ${\ displaystyle \ oplus}$ $\ oplus$ denotă xor , $h$ ${\ displaystyle h}$ $h$ este o funcție care mapează caractere la numere întregi din interval $[0,2^{L})$ ${\ displaystyle [0,2 ^ {L})}$ ${\ displaystyle [0,2 ^ {L})}$ .

Având în vedere noul personaj $c_{k+1}$ ${\ displaystyle c_ {k + 1}}$ ${\ displaystyle c_ {k + 1}}$ pentru a adăuga la fereastră, $c_{1}$ ${\ displaystyle c_ {1}}$ $c_1$ caracterul de eliminat, e $H_{t}$ ${\ displaystyle H_ {t}}$ ${\ displaystyle H_ {t}}$ valoarea hashului din iterația anterioară, noua valoare $H_{t+1}$ ${\ displaystyle H_ {t + 1}}$ ${\ displaystyle H_ {t + 1}}$ are ca.

$H_{t+1}=s(H_{t})\oplus s^{k}(h(c_{1}))\oplus h(c_{k+1})$ ${\ displaystyle H_ {t + 1} = s (H_ {t}) \ oplus s ^ {k} (h (c_ {1})) \ oplus h (c_ {k + 1})}$ ${\ displaystyle H_ {t + 1} = s (H_ {t}) \ oplus s ^ {k} (h (c_ {1})) \ oplus h (c_ {k + 1})}$ .

Aplicații

Funcțiile de rulare hash sunt utilizate pentru a crea divizări dinamice pe baza conținutului unui flux de date sau fișier. Acest lucru este util, de exemplu, pentru a transfera numai părțile modificate ale unui fișier, în cazul în care o împărțire statică a fișierului nu ar fi adecvată, deoarece adăugarea unui singur octet la începutul fișierului ar afecta toate porțiunile. O abordare simplă constă în calcularea hashului rulant al datelor și, stabilirea ca limite a secțiunilor punctelor în care corespunde unui anumit model (de exemplu, cei N biți cel mai puțin semnificativi sunt nuli). În acest fel, o modificare a fișierului va afecta secțiunea curentă și posibil următoarea, dar nu și restul. Când limitele secțiunilor au fost determinate, secțiunile sunt hash pentru a determina care dintre ele au fost modificate și care trebuie transmise. ^[4]

Programe precum gzip (cu opțiunea --rsyncable ) și rsyncrypto împart datele folosind o sumă plutitoare ca hash. ^[5]

Notă

^ M. Fürer, Faster integer multiplication, în: STOC '07, 2007, pp. 57-66.
^ ^a ^b Daniel Lemire, Owen Kaser: Hash-ul recursiv n-gram este independent în perechi, în cel mai bun caz, Computer Speech & Language 24 (4), paginile 698-710, 2010. arXiv: 0705.4676
^ Jonathan D. Cohen, Funcții Hashing recursive pentru n-Grams ^{[ link rupt ]} , ACM Trans. Inf. Syst. 15 (3), 1997
^ Adam Horvath, Rabin Karp rolling hash - bucăți de dimensiuni dinamice bazate pe conținut hash , blog.teamleadnet.com , 24 octombrie 2012.
^ "Rsyncrypto Algorithm" Arhivat 15 august 2016 la Internet Archive.

Elemente conexe

Amprenta lui Rabin

linkuri externe

MIT 6.006: Introducere în algoritmi 2011 - Note de curs - Rolling Hash

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] M. Fürer, Faster integer multiplication, în: STOC '07, 2007, pp. 57-66.

[lemirekaser-2] Daniel Lemire, Owen Kaser: Hash-ul recursiv n-gram este independent în perechi, în cel mai bun caz, Computer Speech & Language 24 (4), paginile 698-710, 2010. arXiv: 0705.4676

[3] Jonathan D. Cohen, Funcții Hashing recursive pentru n-Grams ^{[ link rupt ]} , ACM Trans. Inf. Syst. 15 (3), 1997

[4] Adam Horvath, Rabin Karp rolling hash - bucăți de dimensiuni dinamice bazate pe conținut hash , blog.teamleadnet.com , 24 octombrie 2012.

[5] "Rsyncrypto Algorithm" Arhivat 15 august 2016 la Internet Archive.

[1] în

[2]

[3]

[4]

[5]