Rolling hash

Da Wikipedia, l'enciclopedia libera.

Un rolling hash (chiamato anche hash ricorsivo o rolling checksum) è una funzione hash che processa l'input tramite una finestra scorrevole sull'input stesso. Alcune funzioni hash permettono il calcolo molto rapido, aggiornando il risultato in base al valore dell'hash nella finestra precedente e in base ai valori aggiunto e rimosso dalla finestra all'iterazione corrente, in maniera analoga al calcolo di una media mobile.

Tutte le funzioni di rolling hash hanno complessità computazionale lineare nel numero di elementi, ma la complessità rispetto alla lunghezza k della finestra può variare a seconda dell'algoritmo. Ad esempio la funzione rolling hash di Rabin-Karp richiede la moltiplicazione di due interi di bit, con complessità ,[1] mentre l'hash di n-gram con polinomi ciclici può essere calcolato in tempo lineare.[2]

Un rolling hash può essere al più una funzione due-a-due indipendente[2] o una funzione hash universale, ma non può essere k-a-k indipendente.

Rolling hash di Rabin-Karp[modifica | modifica wikitesto]

L'algoritmo di Rabin-Karp usa solitamente un rolling hash molto semplice, che impiega solo addizioni e moltiplicazioni:

dove è una costante e sono i caratteri in input. Per evitare valori enormi di , tutti i calcoli sono modulo . La scelta di e è molto importante per l'efficacia dell'hashing.

L'aggiunta o rimozione di caratteri coinvolge solo i due termini estremi, mentre per spostare a sinistra i rimanenti caratteri è sufficiente una moltiplicazione per , oppure una divisione per spostare a destra. Operando in aritmetica modulare, può essere scelto tale da ammettere inverso moltiplicativo , permettendo di eseguire lo spostamento a destra con una moltiplicazione invece che una divisione.

Polinomi ciclici[modifica | modifica wikitesto]

L'hashing tramite polinomi ciclici[3] evita l'uso di moltiplicazioni, sostituendole con barrel shift. L'hash H è un valore nell'intervallo , definito come

dove è una rotazione ciclica di un bit a sinistra (es. ), denota lo xor, è una funzione che mappa caratteri a interi nell'intervallo .

Dati il nuovo carattere da aggiungere alla finestra, il carattere da rimuovere, e il valore dell'hash all'iterazione precedente, il nuovo valore è ottenuto come

.

Applicazioni[modifica | modifica wikitesto]

Le funzioni rolling hash sono usate per creare suddivisioni dinamiche basate sul contenuto di un flusso dati o un file. Ciò è utile ad esempio per trasferire solo le parti modificate di un file, laddove una suddivisione statica del file non sarebbe adeguata in quanto l'aggiunta anche di un singolo byte all'inizio del file influirebbe su tutte le porzioni. Un semplice approccio consiste nel calcolare il rolling hash dei dati e, fissando come limiti delle sezioni i punti dove esso corrisponde ad un certo pattern (es. gli N bit meno significativi sono nulli). In questo modo, un cambiamento al file influirà sulla sezione corrente ed eventualmente sulla successiva, ma non sulle restanti. Quando i limiti delle sezioni sono stati determinati, le sezioni vengono comparate tramite hash per determinare quali sono state modificate e necessitano di essere trasmesse.[4]

Programmi come gzip (con l'opzione --rsyncable) e rsyncrypto suddividono i dati usando come hash una somma mobile.[5]

Note[modifica | modifica wikitesto]

  1. ^ M. Fürer, Faster integer multiplication, in: STOC ’07, 2007, pp. 57–66.
  2. ^ a b Daniel Lemire, Owen Kaser: Recursive n-gram hashing is pairwise independent, at best, Computer Speech & Language 24 (4), pages 698-710, 2010. arXiv:0705.4676
  3. ^ Jonathan D. Cohen, Recursive Hashing Functions for n-Grams[collegamento interrotto], ACM Trans. Inf. Syst. 15 (3), 1997
  4. ^ Adam Horvath, Rabin Karp rolling hash - dynamic sized chunks based on hashed content, su blog.teamleadnet.com, 24 ottobre 2012.
  5. ^ "Rsyncrypto Algorithm".

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica