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

[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.

[Benmik]

Ich möchte deine Aufmerksamkeit auf xxHash richten, das ich mittlerweile statt MD5 verwende. Die Seite von Cyan4973 auf Github ist interessant, ich habe den Wrapper von YWtheGod (auch auf Github) genommen.
Ich fand es auch günstig, zunächst nur den Anfang zweier Dateien zu vergleichen, insbesondere bei sehr großen Dateien. Da unter Windows immer mindestens 256 KB eingelesen werden, lese und vergleiche ich zunächst einmal diese ersten 256 KB, was schon einmal so gut wie alle nicht gleichen Dateien aussieben sollte.
Bei mir sind Hardlinks ein Thema, weswegen ich auch mittels GetFileInformationByHandle die FileID ermittle und vergleiche.
Mir haben auch die Hinweise von Uwe Raabe und Andreas Hausladen sehr geholfen.

[himitsu]

Es geht hier doch garnicht um extreme Sicherheit,
es geht auch nicht um Vergleiche "ähnlicher" Dateien,
sondern nur um Ändernung jeweils einzelner Dateien mit sich selbst,
womit die Möglichkeit extrem selten vorkommender Hash-Kollisionen sehr unwahrscheinlich ist, vor allem, wenn niemand (Hacker und Co.) absichtlich die Datei gezielt und mit enormem Aufwand daraufhin ändert.

* das Archiv-Attribut
* Datum des letzten Schreibzugriffs
* und ansonsten sind doch immernoch MD5/SHA1/SHA256 ausreichend

System.Hash :
THashMD5 (128)
THashSHA1 (128)
THashSHA2 (224,256,384,512)
THashBobJenkins (32, verwendet Dlelphi für Listen)

[Delphi.Narium]

Hab' einfach mal wieder die KI meiner Wahl befragt:

Zitat von Frage:

Wie hoch ist die Wahrscheinlichkeit, dass es bei der Verwendung eines MD5-Hashes beim Vergleich von Dateien zu einer Kollision kommt, d. h., das zwei unterschieldiche Dateien über einen identischen MD5-Hash verfügen?

Zitat von Antwort:

Die Wahrscheinlichkeit einer Kollision bei der Verwendung von MD5-Hashes hängt von der Anzahl der eindeutigen Eingaben ab, die gehasht werden. MD5 erzeugt einen Hash-Wert von 128 Bit, was bedeutet, dass es 2^128 oder etwa 3.4 x 10^38 eindeutige Hash-Werte gibt.

Die Wahrscheinlichkeit einer Kollision kann mit der Geburtstagsparadoxon-Formel berechnet werden. Wenn wir n als die Anzahl der eindeutigen Eingaben und d als die Anzahl der möglichen Hash-Werte betrachten, dann ist die Wahrscheinlichkeit P einer Kollision gegeben durch:

P ≈ n^2 / 2d

Für MD5, wenn wir annehmen, dass wir etwa 2^64 eindeutige Eingaben hashen (eine große, aber realistische Anzahl), dann ist die Wahrscheinlichkeit einer Kollision:

P ≈ (2^64)^2 / 2 * 2^128 = 1 / 2^64

Das ist eine sehr kleine Wahrscheinlichkeit, aber es ist nicht null. In der Praxis sind Kollisionen mit MD5 bekannt und das Verfahren wird daher für sicherheitskritische Anwendungen nicht mehr empfohlen. Es ist jedoch immer noch weit verbreitet für weniger kritische Anwendungen wie die Überprüfung der Integrität von Dateien.

Bitte beachten Sie, dass diese Berechnung eine Vereinfachung ist und die tatsächliche Wahrscheinlichkeit aufgrund verschiedener Faktoren, einschließlich der spezifischen Eigenschaften des MD5-Algorithmus, abweichen kann. Es ist auch wichtig zu beachten, dass selbst eine sehr geringe Kollisionswahrscheinlichkeit in bestimmten Kontexten ein Sicherheitsrisiko darstellen kann.

Zitat von Frage:

Wie verändert sich bei einem Dateivergleich die Wahrscheinlichkeit einer MD5-Hash-Kollision, wenn zusätzlich noch die Dateigröße und das Datum der letzten Dateiänderung mit berücksichtigt werden?

Zitat von Antwort:

Die Berücksichtigung zusätzlicher Informationen wie Dateigröße und Datum der letzten Änderung kann die Wahrscheinlichkeit einer Kollision beim Vergleich von Dateien erheblich reduzieren.

Wenn zwei Dateien denselben MD5-Hash haben, aber unterschiedliche Größen oder Änderungsdaten, dann können wir sicher sein, dass es sich um unterschiedliche Dateien handelt, auch wenn der MD5-Hash identisch ist. In diesem Fall würde die Kollision beim MD5-Hash nicht zu einer falschen Übereinstimmung führen, da die zusätzlichen Informationen (Dateigröße und Änderungsdatum) die Unterschiede aufzeigen.

Es ist jedoch wichtig zu beachten, dass diese Methode nicht vollständig vor Kollisionen schützt. Es ist theoretisch möglich (wenn auch extrem unwahrscheinlich), dass zwei unterschiedliche Dateien denselben MD5-Hash, dieselbe Größe und dasselbe Änderungsdatum haben. Aber die Wahrscheinlichkeit dafür ist so gering, dass sie in der Praxis vernachlässigbar ist.

Insgesamt kann die Berücksichtigung von Dateigröße und Änderungsdatum bei der Verwendung von MD5-Hashes zur Dateivergleichung die Sicherheit erheblich verbessern. Es ist jedoch immer noch empfehlenswert, sicherere Hash-Funktionen wie SHA-256 zu verwenden, insbesondere für sicherheitskritische Anwendungen.

Zitat von Frage:

Es ist aber doch im Rahmen des Möglichen, dass zwei Dateien mit gleichem MD5-Hash und identischer Dateigröße, aber unterschiedlichen Änderungszeitpunkten identisch sind, z. B. weil eine Datei von einem Datenträger auf einen andern kopiert wurde oder nur ein Kopieren unter einem anderen Dateinamen oder in ein anderes Verzeichnis erfolgte. Wäre es in diesem Falle nicht zielführender zum Vergleich nur Dateigröße und erst bei identischer Dateigröße zusätzlich den MD5-Hash zu verwenden? Wie würde sich dadurch die Wahrscheinlichkeit eines Kollision der MD5-Hashs verändern?

Zitat von Antwort:

Sie haben absolut recht. In der Praxis ist es durchaus möglich, dass zwei Dateien mit demselben MD5-Hash und der gleichen Größe, aber unterschiedlichen Änderungsdaten tatsächlich identisch sind. Dies könnte der Fall sein, wenn eine Datei kopiert oder unter einem anderen Namen gespeichert wurde.

In solchen Fällen könnte es sinnvoll sein, zuerst die Dateigröße zu vergleichen und nur bei Übereinstimmung der Größe den MD5-Hash zu berechnen und zu vergleichen. Dies könnte die Effizienz des Vergleichsprozesses verbessern, insbesondere wenn eine große Anzahl von Dateien verglichen wird, da die Berechnung von Hashes rechenintensiv sein kann.

Was die Wahrscheinlichkeit einer Kollision betrifft, so würde sich diese nicht ändern, da die Wahrscheinlichkeit einer Kollision nur von der Anzahl der eindeutigen Eingaben und der Größe des Hash-Raums abhängt (bei MD5 sind das 2^128 mögliche Hashes). Die Reihenfolge, in der Sie die Größe und den Hash vergleichen, hat keinen Einfluss auf die Wahrscheinlichkeit einer Kollision. Es ändert jedoch die Wahrscheinlichkeit, dass eine Kollision zu einer falschen Übereinstimmung führt, da Dateien mit unterschiedlichen Größen bereits vor der Hash-Berechnung ausgeschlossen werden.

Es ist jedoch wichtig zu beachten, dass diese Methode immer noch nicht vollständig vor Kollisionen schützt. Es ist theoretisch möglich (wenn auch extrem unwahrscheinlich), dass zwei unterschiedliche Dateien denselben MD5-Hash und dieselbe Größe haben. Aber die Wahrscheinlichkeit dafür ist so gering, dass sie in der Praxis vernachlässigbar ist. Für sicherheitskritische Anwendungen wird daher empfohlen, sicherere Hash-Funktionen wie SHA-256 zu verwenden.

Mein Fazit:

Eine Tabelle mit Dateinamen, Dateigröße, MD5-Hash und den Änderungsdaten sollten für die gestellte Aufgabe ausreichend sein.

Das Erstellen einer Baumstruktur ist nicht erforderlich, es sei denn, man möchte es für die Anwender schön aussehen lassen. Dann reicht es aber aus die Baumstruktur nur für die Daten zu erstellen, die die Anwender auch zu Gesicht bekommen sollen und zwar erst dann, wenn die Daten zur Anzeige gebracht werden.

Mein Vorgehen wäre:

Rekursives Einlesen der Verzeichnisstruktur(en) und je Datei Pfad und Name, Dateigröße und Änderungsdaten in einer Tabelle speichern, dazu reichen FindFirst und FindNext mit TSearchRec aus.

In der so erstellten Tabelle alle Sätze suchen, bei denen die Dateigröße mehr als einmal vorkommt:

SQL-Code:

select * from tabelle a where exists (
  select 1 from tabelle b 
  where a.dateigroesse = b.dateigroesse
  group by b.dateigroesse having count(*) > 1
)
order by a.Dateigroesse;

Für die so ausgewählten Dateien den MD5-Hash berechnen und in der Tabelle speichern.

Anschließend die Dateien suchen lassen, bei denen die Kombination aus Dateigröße und MD5-Hash mehr als einmal vorkommen.

SQL-Code:

select * from tabelle a where exists (
  select 1 from tabelle b 
  where a.dateigroesse = b.dateigroesse
  and a.md5 = b.md5
  group by b.dateigroesse, b.md5 having count(*) > 1
)
order by a.Dateigroesse, a.md5;

Aus dem Ergebnis wird dann die Anzeige für die Anwender befüllt, egal ob als TreeView, ListView oder auch einfach nur in 'nem DBGrid.