Die Erkennung von doppelten Dateien

Question

Ich möchte doppelte Dateien in einem Verzeichnisbaum erkennen. Wenn zwei identische Dateien gefunden werden, wird nur eines der Duplikate erhalten und die verbleibenden Duplikate werden gelöscht, um Speicherplatz zu sparen.

Doppelte Dateien sind Dateien mit demselben Inhalt, die sich in Dateinamen und Pfad unterscheiden können.

Ich habe daran gedacht, Hash-Algorithmen für diesen Zweck zu verwenden, aber es besteht die Möglichkeit, dass verschiedene Dateien dieselben Hashes haben. Daher benötige ich einen zusätzlichen Mechanismus, der mir mitteilt, dass die Dateien nicht gleich sind, auch wenn die Hashes gleich sind, da ich nicht zwei verschiedene Dateien löschen möchte.

Welchen zusätzlichen schnellen und zuverlässigen Mechanismus würden Sie verwenden?

Answer 1

Das Berechnen des Hashs verlangsamt Ihr Programm. Es ist besser, auch die Dateigröße zu überprüfen. Alle doppelten Dateien sollten dieselbe Dateigröße haben. Wenn sie dieselbe Dateigröße teilen, wenden Sie die Hash-Prüfung an. Dadurch wird Ihr Programm schneller ausgeführt.

Es können weitere Schritte folgen.

1. Überprüfen Sie, ob die Dateigröße gleich ist
2. Wenn Schritt 1 bestanden ist, überprüfen Sie, ob die ersten und letzten Bytebereiche (sagen wir 100 Byte) gleich sind
3. Wenn Schritt 2 bestanden ist, überprüfen Sie den Dateityp,
4. Wenn Schritt 3 bestanden ist, überprüfen Sie am Ende den Hash

Je mehr Kriterien Sie hinzufügen, desto schneller wird es funktionieren, und Sie können so das letzte Mittel (Hash) vermeiden.

Answer 2

Es würde von den Dateien abhängen, die Sie vergleichen.

A) Das schlimmste Szenario ist:

1. Sie haben viele Dateien, die die gleiche Größe haben
2. Die Dateien sind sehr groß
3. Die Dateien sind sehr ähnlich, mit Unterschieden, die an einer engen zufälligen Stelle in der Datei gefunden werden

Zum Beispiel, wenn Sie hätten:

• 100x 2MB Dateien derselben Größe,
• Vergleich miteinander,
• mit binärem Vergleich unter Verwendung von
• 50% Dateilesen (Wahrscheinlichkeit, ein ungleiches Byte in der ersten Hälfte der Datei zu finden)

Dann hätten Sie:

• 10.000 Vergleiche von
• 1MB, was gleichbedeutend ist mit
• insgesamt 10GB zu lesenden Daten.

Wenn Sie jedoch dasselbe Szenario haben, aber die Hashes der Dateien zuerst ableiten, würden Sie:

• 200MB Daten von der Festplatte lesen (typischerweise das langsamste Komponente in einem Computer), die sich destillieren zu
• 1,6K im Speicher (unter Verwendung von MD5-Hashing - 16 Byte - Sicherheit ist nicht wichtig)
• und würden 2N*2MB für den endgültigen direkten binären Vergleich lesen, wobei N die Anzahl der gefundenen Duplikate ist.

Ich denke, dieses schlimmste Szenario ist nicht typisch jedoch.

B) Das typische Szenario ist:

1. Dateien haben normalerweise verschiedene Größen
2. Die Dateien unterscheiden sich höchstwahrscheinlich nahe dem Anfang der Datei - dies bedeutet, dass beim direkten binären Vergleich in der Regel nicht die gesamte Datei bei den meisten sich unterscheidenden Dateien derselben Größe gelesen wird.

Zum Beispiel, wenn Sie hätten:

• Einen Ordner mit MP3-Dateien (sie werden nicht zu groß - vielleicht nicht größer als 5MB)
• 100 Dateien
• zuerst die Größe überprüfen
• höchstens 3 Dateien derselben Größe (Duplikate oder nicht)
• binärer Vergleich für Dateien derselben Größe verwenden
• zu 99% wahrscheinlich, dass sie sich nach 1KByte unterscheiden

Dann hätten Sie:

• Höchstens 33 Fälle, in denen die Länge in 3 Dateisätzen gleich ist
• Parallelles binäres Lesen von 3 Dateien (oder mehr ist möglich) gleichzeitig in 4K-Blöcken
• Bei 0% gefundenen Duplikaten - 33 * 3 * 4K von Lesedateien = 396KB an Festplattenlesevorgängen
• Bei 100% gefundenen Duplikaten = 33 * 3 * N, wobei N die Dateigröße ist (~5MB) = ~495MB

Wenn Sie 100% Duplikate erwarten, wäre das Hashing nicht effizienter als der direkte binäre Vergleich. Da Sie jedoch <100% Duplikate erwarten sollten, wäre das Hashing weniger effizient als der direkte binäre Vergleich.

C) Wiederholter Vergleich

Dies ist die Ausnahme. Der Aufbau einer Hash+Längen+Pfad-Datenbank für alle Dateien beschleunigt wiederholte Vergleiche. Aber die Vorteile wären marginal. Es würde anfänglich 100% Lesen der Dateien erfordern und die Speicherung der Hash-Datenbank. Die neue Datei müsste zuerst zu 100% gelesen und zur Datenbank hinzugefügt werden, und wenn sie übereinstimmt, wäre immer noch der direkte binäre Vergleich als abschließender Vergleichsschritt erforderlich (um Kollisionen bei den Hashes auszuschließen). Selbst wenn die meisten Dateien unterschiedliche Größen haben, kann bei Erstellung einer neuen Datei im Zielordner diese möglicherweise die Größe einer vorhandenen Datei haben und schnell vom direkten Vergleich ausgeschlossen werden.

Zusammenfassend:

• Es sollten keine zusätzlichen Hashes verwendet werden (der ultimative Test - binärer Vergleich - sollte immer der letzte Test sein)
• Der binäre Vergleich ist oft effizienter beim ersten Durchlauf, wenn es viele Dateien mit unterschiedlichen Größen gibt
• MP3-Vergleiche funktionieren gut mit Längen- und dann binärem Vergleich.

Answer 3

Die Hash-Lösung ist in Ordnung - Sie müssen nur eine der Kollisionsmechanismen für den Umgang mit 2 Elementen durchführen, die auf denselben Wert gehasht sind. [chaining oder offene Adressierung].

Fügen Sie einfach iterativ Elemente hinzu - wenn Ihre Implementierung feststellt, dass es ein Duplikat gibt, wird es nicht dem Hash-Set hinzugefügt. Sie erkennen ein Element als Duplikat, wenn die Größe des Sets sich nach dem Versuch, das Element hinzuzufügen, nicht geändert hat.

Es ist sehr wahrscheinlich, dass es bereits Implementierungen für diese Art von Datenstruktur in Ihrer Sprache gibt - zum Beispiel ein HashSet in Java und unordered_set in C++.

Answer 4

Wenn Sie einen Hash-Algorithmus wie SHA-1 oder noch besser SHA-256 oder höher verwenden, bezweifle ich wirklich, dass Sie denselben Hash-Wert für zwei verschiedene Dateien erhalten. SHA ist eine kryptografische Hash-Funktion und wird in Versionskontrollsystemen wie Git verwendet. Sie können also sicher sein, dass sie die Aufgabe für Sie erledigen wird.

Aber wenn Sie trotzdem zusätzliche Überprüfungen wünschen, können Sie diese zwei Schritte befolgen.
1) Interpretieren Sie die Header - dies ist ein wirklich schwieriges Nuss zu knacken, da verschiedene Formate unterschiedliche Headerlängen haben können.
2) Führen Sie einige Plausibilitätsprüfungen durch - Dateigröße, lesen Sie zufällige Dateipositionen und versuchen Sie zu überprüfen, ob sie gleich sind.

Answer 5

Dies ist die typische Ausgabe einer md5sum:

0c9990e3d02f33d1ea2d63afb3f17c71

Wenn Sie keine absichtlich gefälschten Dateien befürchten müssen, ist die Wahrscheinlichkeit, dass eine zweite zufällige Datei übereinstimmt

1/(Dezimalwert(0xfffffffffffffffffffffffffffffff)+1)

Wenn Sie die Dateigröße als zusätzlichen Test berücksichtigen, steigt Ihre Sicherheit, dass beide Dateien passen. Sie könnten mehr und mehr Messungen hinzufügen, aber ein bitweiser Vergleich wird das letzte Wort in einer solchen Debatte sein. Für praktische Zwecke sollte md5sum ausreichen.