Wie findet man alle Dateien mit gleichem Inhalt?

Question

Dies ist ein Interviewfrage : "Finde in einem Verzeichnis mit vielen Dateien die Dateien, die den gleichen Inhalt haben". Ich würde vorschlagen, eine Hash-Funktion zu verwenden, um Hash-Werte der Dateiinhalte zu erzeugen und nur die Dateien mit den gleichen Hash-Werten zu vergleichen. Ist das sinnvoll?

Die nächste Frage ist, wie man die Hash-Funktion auswählt. Würden Sie SHA-1 für diesen Zweck verwenden?

Answer 1

Ich würde den Hash lieber als zweiten Schritt verwenden. Die Sortierung des Verzeichnisses nach Dateigröße und der Hash und der Vergleich nur bei doppelten Größen kann das Suchuniversum im allgemeinen Fall erheblich verbessern.

Answer 2

Wie die meisten Fragen im Vorstellungsgespräch soll sie eher ein Gespräch anregen als eine einzige Antwort geben.

Bei sehr wenigen Dateien kann es schneller sein, einfach einen Byte-für-Byte-Vergleich durchzuführen, bis man auf Bytes stößt, die nicht übereinstimmen (vorausgesetzt, sie stimmen überein). Wenn es viele Dateien gibt, kann es schneller sein, Hashes zu berechnen, da Sie nicht auf der Festplatte herumwandern müssen, um Stücke aus mehreren Dateien einzulesen. Dieser Prozess kann beschleunigt werden, indem man sich immer größere Teile jeder Datei schnappt, während man sich durch die Dateien arbeitet, um mögliche Übereinstimmungen zu beseitigen. hEs kann auch notwendig sein, das Problem auf mehrere Server zu verteilen, wenn es genügend Dateien gibt.

Ich würde mit einer viel schnelleren und einfacheren Hash-Funktion als SHA-1 beginnen. SHA-1 ist kryptografisch sicher, was in diesem Fall nicht unbedingt erforderlich ist. In meinen informellen Tests ist Adler 32 zum Beispiel 2-3 Mal schneller. Sie könnten auch einen noch schwächeren Vermutungstest verwenden und dann alle Dateien, die übereinstimmen, erneut testen. Diese Entscheidung hängt auch vom Verhältnis zwischen IO-Bandbreite und CPU-Leistung ab. Wenn Sie eine leistungsfähigere CPU haben, sollten Sie einen spezifischeren Hash verwenden, um sich das erneute Einlesen von Dateien bei nachfolgenden Tests zu ersparen; wenn Sie eine schnellere IO haben, kann das erneute Einlesen billiger sein, als unnötig teure Hashes durchzuführen.

Eine weitere interessante Idee wäre die Anwendung von Heuristiken auf die Dateien während der Verarbeitung, um die optimale Methode auf der Grundlage der Dateigröße, der Geschwindigkeit des Computers und der Entropie der Datei zu bestimmen.

Answer 3

Ja, der vorgeschlagene Ansatz ist vernünftig und SHA-1 oder MD5 sind für diese Aufgabe ausreichend. Hier ist eine detaillierte Analyse für dasselbe Szenario und hier ist eine Frage speziell zur Verwendung von MD5 . Vergessen Sie nicht, dass Sie eine Hash-Funktion so schnell wie möglich benötigen.

Answer 4

Ja, Hashing ist das erste, was mir einfällt. Für Ihre spezielle Aufgabe müssen Sie die schnellste verfügbare Hash-Funktion verwenden. Adler32 würde funktionieren. Kollisionen sind in Ihrem Fall kein Problem, Sie brauchen also keine kryptografisch starke Funktion.