Impronta di Rabin
L'impronta di Rabin (Rabin fingerprint) è una funzione di rolling hash usata come fingerprint, definita tramite polinomi su un campo finito, proposta da Michael O. Rabin nel 1981.[1]
Definizione modifica
Dato un messaggio m di n-bit m0,...,mn-1, questo può essere interpretato come un polinomio di grado n-1 sul campo finito GF(2).
Dato un polinomio irriducibile di grado k in GF(2), la fingerprint di m è il resto della divisione di per su GF(2), che è un polinomio di grado al più k-1, ovvero un numero rappresentabile con k bit.
Applicazioni modifica
Molte implementazioni dell'algoritmo di Rabin-Karp usano internamente l'impronta di Rabin come rolling hash. Il Low Bandwidth Network Filesystem (LBFS) usa l'impronta di Rabin per la suddivisione dei dati in blocchi a grandezza variabile resistenti alla traslazione.[2]
Note modifica
- ^ Michael O. Rabin, Fingerprinting by Random Polynomials (PDF), Center for Research in Computing Technology, Harvard University, 1981. URL consultato il 22 marzo 2007.
- ^ Athicha Muthitacharoen, Benjie Chen, and David Mazières "A Low-bandwidth Network File System"
Collegamenti esterni modifica
- Andrei Z. Broder, Some applications of Rabin's fingerprinting method, 1993. URL consultato il 12 settembre 2011.
- David Andersen, Exploiting Similarity for Multi-Source Downloads using File Handprints, 2007. URL consultato il 12 aprile 2007.