Rabin-Fingerprint

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Rabin Fingerprint)
Wechseln zu: Navigation, Suche

Der Rabin Fingerprint ist ein Verfahren zur Berechnung eines Fingerprints. Es wurde von Michael O. Rabin vorgeschlagen.[1]

Methode[Bearbeiten]

Es werden zur Berechnung ein Eingabe-Polynom A(x) und ein Schlüssel P(x), beide aus \mathbb{Z}_2[x], benötigt. Die Fingerprintfunktion f ist als f(A)(x) = A(x) \mod P(x) definiert.

Verwendung[Bearbeiten]

Besonders geeignet ist der Rabin-Fingerprint beim Einsatz zur Erkennung von identischen oder ähnlichen Abschnitten in unterschiedlichen Dateien, d. h. zur Erkennung von Redundanz. Diese kann dann zum Beispiel zur Optimierung von Dateitransferprozessen oder bei der Archivierung von Daten genutzt werden. So benutzt etwa das am Massachusetts Institute of Technology entwickelte Dateisystem LBFS (Low-Bandwidth File System) den Rabin-Fingerprint.[2]

Einzelnachweise[Bearbeiten]

  1.  Michael O. Rabin: Fingerprinting by Random Polynomials. Center for Research in Computing Technology, Harvard University, 1981 (PDF-Datei; 465 KB, abgerufen am 9. Dezember 2014).
  2. Purushottam Kulkarni, Fred Douglis, Jason D. LaVoie, John M. Tracey: Redundancy Elimination Within Large Collections of Files. In: USENIX Annual Technical Conference, General Track. 12. Mai 2004, S. 59-72, abgerufen am 21. Februar 2015 (englisch).