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

Dato un messaggio m di n-bit m₀,...,m_n-1, questo può essere interpretato come un polinomio di grado n-1 sul campo finito GF(2).

${\displaystyle f(x)=m_{0}+m_{1}x+\ldots +m_{n-1}x^{n-1}}$

Dato un polinomio irriducibile ${\displaystyle p(x)}$ di grado k in GF(2), la fingerprint di m è il resto ${\displaystyle r(x)}$ della divisione di ${\displaystyle f(x)}$ per ${\displaystyle p(x)}$ su GF(2), che è un polinomio di grado al più k-1, ovvero un numero rappresentabile con k bit.

Applicazioni

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

1. Michael O. Rabin, Fingerprinting by Random Polynomials (PDF), Center for Research in Computing Technology, Harvard University, 1981. URL consultato il 22 marzo 2007.
2. Athicha Muthitacharoen, Benjie Chen, and David Mazières "A Low-bandwidth Network File System"

Collegamenti esterni

• 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.