Erkennung doppelter Dateien

Question

Ich würde gerne doppelte Dateien in einem Verzeichnisbaum erkennen. Wenn zwei identische Dateien gefunden werden, soll nur eines der Duplikate erhalten bleiben und die übrigen Duplikate sollen gelöscht werden, um Speicherplatz zu sparen.

Ein Duplikat ist eine Datei mit gleichem Inhalt, die sich in Dateinamen und Pfad unterscheiden kann.

Ich dachte an die Verwendung von Hash-Algorithmen für diesen Zweck, aber es besteht die Möglichkeit, dass verschiedene Dateien die gleichen Hashes haben, also brauche ich einen zusätzlichen Mechanismus, der mir sagt, dass die Dateien nicht die gleichen sind, obwohl die Hashes die gleichen sind, weil ich nicht zwei verschiedene Dateien löschen möchte.

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

Answer 1

Die Berechnung des Hashes macht Ihr Programm langsam. Es ist besser, wenn Sie auch Prüfen Sie die Dateigröße . Alle Dateiduplikate sollten die gleiche Dateigröße haben. Wenn sie dieselbe Dateigröße haben, wenden Sie die Hash-Prüfung an. Das macht Ihr Programm schnell.

Es kann mehr Schritte geben.

1. Prüfen Sie, ob Dateigröße ist gleich
2. Wenn Schritt 1 erfolgreich war, prüfen Sie, ob erster und letzter Bereich von Bytes (z.B. 100 Bytes) gleich sind
3. Wenn Schritt 2 erfolgreich war, prüfen Sie Dateityp ,
4. Wenn Schritt 3 erfolgreich war, prüfen Sie die endlich eine Raute

Je mehr Kriterien Sie hinzufügen, desto schneller wird es funktionieren und Sie können den letzten Ausweg vermeiden ( Hash ) auf diese Weise.

Answer 2

Das hängt von den Dateien ab, die Sie vergleichen wollen.

A) Das Worst-Case-Szenario ist:

1. Sie haben viele Dateien, die die gleiche Größe haben
2. Die Dateien sind sehr groß
3. Die Dateien sind sich sehr ähnlich und unterscheiden sich nur an einer kleinen zufälligen Stelle in der Datei

Zum Beispiel, wenn Sie hatten:

• 100x 2 MB große Dateien der gleichen Größe,
• Vergleich zueinander,
• mit Binärvergleich mit
• 50% Lesen der Datei (Wahrscheinlichkeit, ungleiche Bytes in der ersten Hälfte der Datei zu finden)

Dann hättest du das:

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

Wenn Sie jedoch das gleiche Szenario hätten, aber zunächst die Hashes der Dateien abgeleitet würden Sie:

• Lesen von 200 MB Daten von der Festplatte (in der Regel die langsamste Komponente in einem Computer) und Destillieren auf
• 1,6K im Speicher (mit MD5-Hashing - 16 Byte - Sicherheit ist nicht wichtig)
• und würde 2N*2MB für den endgültigen direkten Binärvergleich lesen, wobei N die Anzahl der gefundenen Duplikate ist.

Ich denke, dieses Worst-Case-Szenario ist nicht typisch Allerdings.

B) Das typische Szenario ist:

1. Die Dateien sind in der Regel unterschiedlich groß
2. Die Dateien unterscheiden sich höchstwahrscheinlich am Anfang der Datei - Das bedeutet, dass bei einem direkten Binärvergleich in der Regel nicht die gesamte Datei gelesen werden muss, wenn es sich um eine Vielzahl unterschiedlicher Dateien gleicher Größe handelt.

Zum Beispiel, wenn Sie hatten:

• Ein Ordner mit MP3-Dateien (sie sollten nicht zu groß werden - vielleicht nicht größer als 5 MB)
• 100 Dateien
• Größe zuerst prüfen
• höchstens 3 Dateien gleicher Größe (Duplikate oder nicht)
• mit Binärvergleich für Dateien der gleichen Größe
• 99 % der Wahrscheinlichkeit, dass sie nach 1 KBytes anders sind

Dann hättest du das:

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

Wenn Sie 100%ige Multiplikationen erwarten, ist Hashing nicht effizienter als ein direkter Binärvergleich. Wenn Sie <100% Multiplikationen erwarten, wäre Hashing weniger effizient als ein direkter Binärvergleich.

C) Wiederholter Vergleich

Dies ist die Ausnahme. Der Aufbau einer Hash+Länge+Pfad-Datenbank für alle Dateien wird wiederholte Vergleiche beschleunigen. Aber die Vorteile wären marginal. Anfangs müssen die Dateien zu 100 % gelesen und die Hash-Datenbank gespeichert werden. Die neue Datei muss zu 100 % gelesen und dann zur Datenbank hinzugefügt werden, und wenn sie übereinstimmt, ist immer noch ein direkter Binärvergleich als letzter Vergleichsschritt erforderlich (um Hash-Kollisionen auszuschließen). Selbst wenn die meisten Dateien unterschiedlich groß sind, kann eine neue Datei, die im Zielordner erstellt wird, mit einer bereits vorhandenen Datei übereinstimmen und so schnell vom direkten Vergleich ausgeschlossen werden.

Zum Schluss:

• Es sollten keine zusätzlichen Hashes verwendet werden (der ultimative Test - Binärvergleich - sollte immer der letzte Test sein)
• Der Binärvergleich ist beim ersten Durchlauf oft effizienter, wenn es viele Dateien unterschiedlicher Größe gibt.
• Der MP3-Vergleich funktioniert gut mit Längen- und nicht mit Binärvergleichen.

Answer 3

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

Fügen Sie einfach iterativ Elemente hinzu - wenn Ihre Implementierung feststellt, dass es ein Duplikat gibt, wird es nicht zum Hash-Set hinzugefügt. Sie wissen, dass es sich bei einem Element um ein Duplikat handelt, wenn die Größe der Menge nach dem Versuch, das Element hinzuzufügen, nicht geändert wurde.

Höchstwahrscheinlich gibt es bereits eine Implementierung für diese Art von Datenstruktur in Ihrer Sprache - zum Beispiel eine HashSet in Java und ungeordneter_satz in C++.

Answer 4

Wenn Sie einen Hash-Algorithmus wie SHA-1 oder besser noch SHA-256 oder höher verwenden, bezweifle ich wirklich, dass Sie für zwei verschiedene Dateien denselben Hash-Wert erhalten werden. SHA ist eine kryptografische Hash-Funktion und wird in Versionskontrollsystemen wie Git verwendet. Sie können sich also darauf verlassen, dass es seine Aufgabe erfüllen wird.

Wenn Sie dennoch zusätzliche Kontrollen durchführen möchten, können Sie diese beiden Schritte befolgen.
1) Analysieren Sie die Header - dies ist ein wirklich schwieriges Unterfangen, da verschiedene Formate unterschiedliche Headerlängen haben können
2) Führen Sie einige Sicherheitsprüfungen durch - Dateigröße, lesen Sie zufällige Dateipositionen und versuchen Sie zu prüfen, ob sie gleich sind.

Answer 5

Dies ist die typische Ausgabe einer md5sum:

0c9990e3d02f33d1ea2d63afb3f17c71

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

1/(decimal(0xfffffffffffffffffffffffffffffff)+1)

Wenn Sie die Dateigröße als zusätzlichen Test berücksichtigen, erhöht sich Ihre Gewissheit, dass beide Dateien passen. Sie können immer mehr Messungen hinzufügen, aber ein bitweiser Vergleich wird in einer solchen Debatte das letzte Wort haben. Für praktische Zwecke sollte md5sum ausreichend sein.