Rolling hash

Un rolling hash (chiamato anche hash ricorsivo o rolling checksum) è una funzione di 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 $k$ bit, con complessità $O(k\log k2^{O(\log ^{*}k)})$, mentre l'hash di n-gram con polinomi ciclici può essere calcolato in tempo lineare.

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

Rolling hash di Rabin-Karp

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

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

dove $a$ è una costante e $c_{1},...,c_{k}$ sono i caratteri in input. Per evitare valori enormi di $H$, tutti i calcoli sono modulo $n$. La scelta di $a$ e $n$ è 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 $a$, oppure una divisione per spostare a destra. Operando in aritmetica modulare, $a$ può essere scelto tale da ammettere inverso moltiplicativo $a^{-1}$, permettendo di eseguire lo spostamento a destra con una moltiplicazione invece che una divisione.

Polinomi ciclici

L'hashing tramite polinomi ciclici evita l'uso di moltiplicazioni, sostituendole con barrel shift. L'hash H è un valore nell'intervallo $[0,2^{L})$, definito come

$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})$

dove $s$ è una rotazione ciclica di un bit a sinistra (es. $s(10011)=00111$), $\oplus$ denota lo xor, $h$ è una funzione che mappa caratteri a interi nell'intervallo $[0,2^{L})$.

Dati il nuovo carattere $c_{k+1}$ da aggiungere alla finestra, $c_{1}$ il carattere da rimuovere, e $H_{t}$ il valore dell'hash all'iterazione precedente, il nuovo valore $H_{t+1}$è ottenuto come

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

Applicazioni

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.

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

Voci correlate

• Impronta di Rabin

Collegamenti esterni

• MIT 6.006: Introduction to Algorithms 2011- Lecture Notes - Rolling Hash