Amprenta lui Rabin

Rabin Amprenta este o metodă de calcul al amprentei folosind polinoame care operează pe un câmp finit . A fost nominalizat de Michael O. Rabin .

Principiu

Dintr-un mesaj de n biți m 0 ..., m n-1 , acesta este tratat ca un polinom de grad n -1 peste câmpul finit GF (2) .

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

Se alege apoi un polinom ireductibil aleatoriu p (x) de grad k peste GF (2), iar amprenta mesajului m este definită ca restul diviziunii de peste peste GF (2), care poate fi văzută ca un polinom de grad k -1 sau ca număr de k biți. $r (x)$ $f (x)$ $p (x)$

Aplicații

Multe implementări ale algoritmului Rabin-Karp folosesc amprentele Rabin intern.

Fluxul redus de sistem de fișiere (LBFS) MIT utilizează amprente Rabin pentru a implementa offset rezistent la blocuri de dimensiuni variabile. Ideea este că sistemul de fișiere calculează suma de control a fiecărui bloc dintr-un fișier. Pentru a salva transferurile între client și server, sumele de verificare sunt comparate și sunt transferate doar blocurile pentru care sunt diferite.

O problemă cu această procesare este că o simplă inserare la începutul fișierului determină modificarea tuturor sumelor de verificare, dacă se utilizează blocuri de dimensiuni fixe (de exemplu, 4 kb ). Prin urmare, ideea este de a selecta blocuri în funcție de anumite proprietăți ale conținutului lor, mai degrabă decât în funcție de un offset specific. LBFS realizează acest lucru mutând o fereastră de 48 de octeți în fișier și calculând amprenta Rabin a fiecărei ferestre. Când cei 13 biți inferiori ai hashului sunt 0, LBFS numește acești 48 de octeți un punct de întrerupere, încetează blocul curent și pornește unul nou. Deoarece amprentele Rabin sunt pseudo-aleatorii , probabilitatea ca orice set de 48 de octeți să fie un punct de întrerupere este . Acest lucru are ca rezultat blocuri de dimensiuni variabile rezistente la deplasare. Orice funcție hash poate fi utilizată pentru a împărți un fișier lung în blocuri (atâta timp cât o funcție hash criptografică este apoi utilizată pentru a determina suma de verificare a fiecărui bloc): dar hash-ul lui Rabin este o funcție drop-down hash (en) eficientă, deoarece calculul regiunea de amprentă Rabin B poate reutiliza unele dintre calculele unei regiuni de amprentă Rabin a atâta timp cât regiunile a și B se suprapun. $2 ^ {- 13}$

Rețineți că această problemă este similară cu cea întâlnită de rsync .

Vezi și tu

W-shingling (ro)
Rolling hash (ro)

Referințe

Michael O. Rabin , Fingerprinting by Random Polynomials , Center for Research in Computing Technology, Harvard University, nouăsprezece optzeci și unu, PDF ( citiți online )
Athicha Muthitacharoen, Benjie Chen și David Mazières „Un sistem de fișiere de rețea cu lățime de bandă redusă”

linkuri externe

Andrei Z. Broder, Unele aplicații ale metodei de amprentă Rabin ,1993( citește online )
David Andersen, Exploatarea similarității pentru descărcări multi-sursă folosind amprente de fișiere ,2007( citește online )
Algoritmul de amprentă Rabin implementat în C