Optimaler Hash-Algorithmus und Strategie für Dateivergleiche, Verzeichnisbaum

[Rollo62]

Hallo zusammen,

ich möchte einen Verzeichnisbaum erstellen, welcher gleiche Dateien (PDF, JPG, PNG, ZIP, ...) eindeutig identifizieren kann und unabhängig vom Betriebssystem eingesetzt werden kann unter Windows, Linux (Web-Server), Macos, etc. den gleichen unverwechselbaren Fingerprint liefert.

Mein Favorit wäre MD5, weil es am schnellsten ist und weil die Aufgabe nicht sicherheitskiritisch ist.
Ich möchte nur möglichst schnell gleiche Dateien finden und zuordnen können, z.B. lokal und remote.

Andere Optionen wären:

Zitat:

Algorithmus____Vorteile_________________________Na chteile
MD5___________Schnell, breite Unterstützung_____Anfällig für Kollisionen, sicherheitskritisch bedenklich
SHA-1_________Weit verbreitet, sicherer_________Anfällig für spezielle Kollisionen, für viele Anwendungen bedenklich
SHA-256_______Hohe Sicherheit, Gute Leistung____Langsamer als vorherige, Hash-Länge 256 Bits kann zu lang werden
SHA-3_________Resistenter, Flexible Länge_______Kann langsamer sein als SHA-2
BLAKE2________Schnell, effizient, sicher_________Optionale variablere Hash-Länge, weniger verbreitet
...

Es geht um überschaubare Anzahl von Dateien, so 100K bis 1 Mio., wobei die Wahrscheinlichkeit von Kollisionen auch bei MD5 eher gering ist.
Bei einer Kollision müsste man dann zusätzlich prüfen, ob es eine echte Kollision ist, oder nicht.

Vielleicht ist die richtige Strategie dann MD5 - Kollision => Prüfe Datei binär.

Hat jemand Erfahrung mit solchen Verzeichnisbäumen und Dateivergleichen, geht es noch effizienter?

[Delphi.Narium]

Für sowas nehme ich immer zuerst die Dateigröße und bei gleicher Dateigröße dann MD5. Gleiche MD5 und unterschiedliche Dateigröße heißt auch unterschiedliche Dateien. Eine fehlerhafte Erkennung von Gleichheit ist mir bei dieser Kombination noch nicht untergekommen.

Und wenn es definierte Dateitypen sind, wie eben PDF, JPG, PNG, ZIP, dann kannst Du anhand der ersten paar Byte der Dateien bei identischer Dateigröße und identischer MD5 noch damit prüfen, ob auch identischer Dateityp.

Oder andersherum: Dateigröße, Dateityp aus den ersten paar Byte ermitteln. Wenn die übereinstimmen, dann noch MD5 (dürfte dann auch schneller sein, als Dateigröße, MD5 und dann erst den Dateityp) und wenn das dann alles gleich ist noch binären Vergleich auf Dateiebene.

Die Wahrscheinlichkeit dann noch eine fehlerhaft Erkennung der Dateigleichheit zu "erwischen" dürfte deutlich geringer sein, als ein Sechser im Lotto

[Rollo62]

Zitat von Delphi.Narium:

Für sowas nehme ich immer zuerst die Dateigröße und bei gleicher Dateigröße dann MD5. Gleiche MD5 und unterschiedliche Dateigröße heißt auch unterschiedliche Dateien. Eine fehlerhafte Erkennung von Gleichheit ist mir bei dieser Kombination noch nicht untergekommen.

Und wenn es definierte Dateitypen sind, wie eben PDF, JPG, PNG, ZIP, dann kannst Du anhand der ersten paar Byte der Dateien bei identischer Dateigröße und identischer MD5 noch damit prüfen, ob auch identischer Dateityp.

Oder andersherum: Dateigröße, Dateityp aus den ersten paar Byte ermitteln. Wenn die übereinstimmen, dann noch MD5 (dürfte dann auch schneller sein, als Dateigröße, MD5 und dann erst den Dateityp) und wenn das dann alles gleich ist noch binären Vergleich auf Dateiebene.

Die Wahrscheinlichkeit dann noch eine fehlerhaft Erkennung der Dateigleichheit zu "erwischen" dürfte deutlich geringer sein, als ein Sechser im Lotto

Ja, es geht erstmal nur um Binärdateien, also keine Textfiles mit Cr / CrLf Problem.

Der Dateivergleich ist eine Sache, aber nicht unbedingt mein Hauptproblem, sondern wie man das Ganze in eine optimale Dateistruktur giesst, also einen Folder/FileTree ähnlich dem Explorer zum Beispiel.

Ich sehe da möglicherweise zwei konkurrierende Pattern nebeneinander, einmal ein Dictionary für die Hashes um sehr schnell gleiche Dateien zu finden, und zum anderen z.B. eine TList als Baumstruktur, um die Files und Folderpfade abzubilden.

Das würde ich gerne ein eine einzige Klasse oder Struktur bauen, die alle Funktionen abdeckt, ohne große Fehlermöglichkeit und Redundanz.
Also Add/Get/Move/Delete (im Tree) aber auch Search (im Dictionary).

Es gibt vielleicht eine ganz andere, offensichtliche Lösung, aber im Moment sehe ich den Wald vor Bäumen nicht.
Klar, es ist wohl schon Freitag, daran muss es liegen

[Stevie]

Egal welchen Algo du nimmst, Hauptsache ist, dass du nicht die Implementierung in der RTL nutzt

[Rollo62]

Ja, selbst das würde mir erstmal reichen.
Aber ja, Spring4D sollte es schon sein

Gibt es denn da eine gute Collection, welche Tree mit Dictionary/Map von Haus aus sauber abbildet?

Ich könnte natürlich nur eine Dictionary verwenden und darin irgendwie den Pfad mit speichern und mich irgendwie durchhangeln.
Gefühlt erscheint mir das aber erstmal nicht besonders effizient, für die Verwaltung einer Baumstruktur.

Oder ist das Ganze etwa besser mit JSON-Nodes zu erreichen?

[Delphi.Narium]

Die Daten bilde ich immer in 'ner Datenbanktabelle ab, ggfls. auch "nur" 'ne Memorytable. Da bekomme ich immer "für umsonst" die entsprechenden Möglichkeiten für die Auswahl nach welchen Kriterien auch immer und muss nicht erst eine wie auch immer geartete Struktur "erfinden" und alle für die Selektion, Auswertungen, ... nötigen Algorithmen implementieren. (Je Datei eine Zeile in der Tabelle.)

Die Optik wird dann aus den selektierten Daten gebildet.

Aber vermutlich gehen wir hier grundsätzlich unterschiedlich an die Problemlösung heran. JSon, XML, Collctions, ... sind mir hier gedanklich und aufwandstechnisch viel zu kompliziert. Das liegt vermutlich auch daran, dass ich nur Delphi 7 hab' und bei mir fast jede Anwendung irgendwann bei der Datenhaltung in 'ne Datenbankanwendung "ausartet" (meist mit KBMemtable) und nichts davon (seit ca. einem Jahrzehnt) im professionellen Bereich zum Einsatz kommt.

[Michael II]

Ich würde auch Parameter, welche rasch zu gewinnen sind früh auswerten und jene, welche Kosten verursachen erst spät. Der Informationsgehalt der verschiedenen Parameter muss natürlich mitberücksichtigt werden.

Du hast für viele Dateien mehrere Parameter (Dateigrösse, MD5, SHA256..., nennen wir sie mal alle Hashes, obschon das für gewisse Typen genau genommen nicht zutrifft) Werte gewonnen und willst wissen, ob eine weitere Datei bereits vorhanden ist? Eventuell ist es ratsam vorher gewisse (Nicht Hash konforme wie Dateigrösse) Parameter p1,p2,... zu einem Parameter p zu hashen und dann... => Bloom Filter bietet sich an.


Du suchst OS übergreifend. Dennoch der Link für Windows auf LINQ

[Rollo62]

Zitat von Delphi.Narium:

Die Daten bilde ich immer in 'ner Datenbanktabelle ab

Interessant, das ist auch eine Möglickeit.
Ich bin bisher davon ausgegangen, dass es wohl zu langsam wäre, aber stimmt, das muss es ja gar nicht.
Wie verwaltest Du denn da die Baumstruktur, mit selbst-referenzierten Keys in einer Tabelle?
Vielleicht hast Du dafür schon eine optimale SQL-Struktur gefunden, Baumstrukturen in einer DB sind etwas problematisch.

Mit FDMemTable könnte das schon ziemlich performant sein, vielleicht sogar mit sqlite, was noch weitere Vorteile hätte.

Was mich bisher nicht auf den Gedanken gebracht hat, war, das ich sowas wie ein Einlesen aller Verzeichnisse oder
ein Hinzufügen von Verzeichnissen einbauen möchte.
Mit Unterverzeichnissen und Dateien, da könnte eine DB etwas schwächeln, gegenüber einen optimierten Speicherliste mit Hash-Option.

Eigentlich wollte ich die Struktur immer on-the.fly laden, und dabei auf Änderungen prüfen,
aber ja, eine permanente DB würde das regelmäßige Einladen sparen.

Zitat von Michael II:

Ich würde auch Parameter, welche rasch zu gewinnen sind früh auswerten und jene, welche Kosten verursachen erst spät. Der Informationsgehalt der verschiedenen Parameter muss natürlich mitberücksichtigt werden.

Ja, ich möchte beim Einlesen möglichst schnell auf Änderungen Prüfen, bzw. Vergleichen ob sich Lokale und Remote-Verzeichnisse geändert haben.
Danke für die Vorschläge mit den zusätzlichen Parametern, aber im Moment reichen mir die JA/NEIN Aussagen zu Files welche geändert wurden, völlig aus.
Zusätzlich dazu wäre dann noch entsprechend der letzte Zuugriff interessant, aber optional.

Weiterhin war mein Gedanke, dass diese Struktur dan auch gleich das Navigieren in den Dateien übernehmen kann.
Also eine Klasse für Verzeichnisstruktur mit Navigation und schneller Hash-Suche.

Womöglich ist aber auch eine Trennung beider "Concerns" sinnvoller, gefühlt würde ich momentan aber eher alles in eine Baumstruktur packen,
um nicht noch viel Redundanz und Komplexität beim Aufrufer reinzubekommen.
Ausserdem wäre eine zentrale Klasse sicher fehlertoleranter auszulegen als zwei separate, die sich überschneiden können.

[Kas Ob.]

Hi,

Sorry if i am missing the subject,

I would like to suggest to skip any multi parameters, and use concatenation, example: MD5 could be more than enough and as "Delphi.Narium" mentioned use the file size this will make collision probability a lot smaller, but prefix the hash with the (aligned to 4 byte by zeros) size like this :
the MD5 hash for "This is MD5" = f6eda1d8b4b2dba89938db14285cf78a
Length("This is MD5") = 11 then your custom hash will be
0000000bf6eda1d8b4b2dba89938db14285cf78a

The advantage here :
1) removing the need for multiple parameters.
2) reduce the collision chance.
3) in its binary (non hex format) it can be used in Trees or DBs .. with only 20 bytes length.
4) if you have files size that need 64bit then use the lower 32bit only and it will be fine, this doesn't affect the collision chance, if there is too many big files then use 5 bytes for the file size, but this really not needed.
5) and as Stefan did point, use an optimized implementation for MD5.

[Delphi.Narium]

Also ganz kurz (oder eher doch etwas lang geworden ):

Es gibt eine Komponente für das rekursive Einlesen der Dateien. Je Datei wird ein Ereignis OnFile ausgelöst. In dem Ereignis wir der Dateiname an eine Komponenten übergeben, die die Datei liest und Dateigröße, MD5, Dateityp (sofern ermittelbar), ... in Attributen zurückgibt.
Danach wir für jede Datei genau ein Datensatz in der Tabelle (egal ob Datenbank oder Memorytable) angelegt (Spalten: einfach alle Werte, die ich im späteren Verlauf benötige(n könnte). Per AutoInc wird ein eindeutiger technischer Schlüssel festgelegt, mit dem kann man dann jederzeit jede Datei eindeutig identifizieren, ginge zwar auch über den vollständigen Dateinamen (der immer 'nen eindeutigen Index hat) ist per AutoInc aber einfacher zu handhaben, da ggfls. auch mal das Tag-Attribut einer Komponente ausreichen kann, um den Schlüssel jederzeit zur Verfügung zu haben.

Damit ist die Datenhaltung erledigt. Und sofern ich 'ne Datenbank nutze, muss ich auch nicht immer alle Daten im Arbeitsspeicher haben, sondern nur das, was ich gerade für 'ne Auswertung auch benötige.

Auswertungen erfolgen über SQL oder Filter, je nach dem, was Datenbank oder Memorytable gerade unterstützen.

Da mich für gewöhnlich nur die Dubletten interessieren, komme ich mit 'nem Select MD5 from tabelle having count(*) > 1 aus. Alles was da dann vorkommt, kann per Filter oder Select in weiteren Abfrage (oder etwas komplexeren SQLs) ausgewählt werden. Und nur aus dem so erstellten Ergebnis wird dann die Anzeige zusammengebaut. Für 'nen Tree muss man dann ggfls. die Pfadangabe am PathDelimiter aufbröseln, um den Baum optisch korrekt zu erstellen. Aber die ganze Baumstruktur für 'ne Million Dateien aufzubauen, nur um dann festzustellen, dass ich eventuell irgendwo 'ne Dublette haben könnte (oder eben auch keine), ist mir zu aufwändig.
Sind die Zeitstempel der Datei mit in der Tabelle, kann ich so auch auf Dateiänderungen prüfen und die entsprechenden Werte in der Tabelle ändern. Ist 'ne Datei schon in der Tabelle, muss ich nicht bei jedem Prüfvorgang alles neu einlesen, sondern nur das Neue oder das Veränderte. Das kann dann (je nach Datenmenge und Datenträgergeschwindigkeit) das eine oder andere Kaffeezwangspäuschen obsolet machen.

Kommt alles in 'ne Datenbanktabelle, muss ich aber auch ab und an mal prüfen, ob's das, was in der Tabelle steht, im realen Leben noch gibt und nicht inzwischen gelöscht wurde. Spätestens bei Auswertungen, die Dubletten erkannt haben, muss man dann noch mal auf die Existenz der Dateien prüfen, um nicht z. B. umbenannte Dateien mit altem und neuem Dateinamen als Dubletten zu identifizieren.

Es ist also nicht ganz banal, aber vermutlich einfacher, als mit komplexen Baumstrukturen im Arbeitsspeicher zu hantieren.

In kurz:

Einmal alles in 'ne Datenbanktabelle und dann per SQL auswerten. Wenn es dann tatsächlich was zu prüfendes, sprich Dubletten, gibt, kann man sich um eine entsprechende Optik kümmern.