Eindeutiger Vergleich für große Dateien gesucht

[mschaefer]

Sorry,

wahrscheinlich ist meine Ausdrucksweise vor Feierabend etwas Zeitoptimiert. Mit Variante x meine ich die ID für eindeutige Dateien. Kann sein das unter ID 5 nur eine Datei liegt, da andere ungleich sind und unter ID 7 zwei oder drei Dateien oder..., da diese gleich sind. Würde dazu neigen den Titel in "Eindeutiger Vergleich für große Dateien gesucht.." oder ähnlich umzubenennen. Die Theorie legt einfach weniger variable Dateistrukturen zugrunde als Du Sie hast und Du hast mit Deinem Beispiel deutlich gemacht, dass für vollständig gefüllte Dateien das Verfahren wenig geeignet ist.

Eigentlich denke ich auch nicht, dass der Binärvergleich wirklich soviel langsamer ist !

Grüße // Martin

[dahead]

kein problem,

Zitat:

Würde dazu neigen den Titel in Eindeutiger Vergleich für große Dateien gescuht.. oder ähnlich umzubenennen.

werde ich machen!

Die Theorie legt einfach weniger variable Dateistrukturen zugrunde als Du Sie hast und Du hast mit Deinem Beispieldeutlich gemacht, dass für vollständig gefüllte Dateien das Verfahren wenig geeignet ist. das ist richtig. in meinem beispiel-screenshot habe ich in meinem programm allerdings auch die option deaktiviert, die dateien vorher auf gleiche größe zu überprüfen. das habe ich nur getan, um feststellen zu können, ob auch dateien (beispielsweise 1 gb und größer) eindeutig identifiziert werden (das hätte ich eventuell noch erwähnen sollen).

da dies nicht der fall war, habe ich den thread hier überhaupt eröffnet.

wo du, WoGe und NicoDe recht habt ist, dass um eine datei eindeutig zu identifizieren ein binärer vergleich unabdingbar ist. diesen habe ich jetzt auch eingebaut.

ich prüfe die dateien allerdings immer noch vor dem überprüfen des binären inhalts auf gleiche checksummen, und davor auf gleiche dateigrößen. somit muss ich nicht jede einzelne datei binär überprüfen (wäre ja sinnlos, wenn die dateien unterschiedlich groß sind).

daher auch meine ursprungsfrage, welcher hash schneller als md5 ist.

also nochmals danke an alle für den hinweis und die hilfe!

[dahead]

ähm, wie benenne ich denn den thread um?

edit: hat sich erledigt, habs gefunden.

[Sharky]

Hai ihr lieben,

vor ab: Ich bin kein Kenner der gesamten "Hash-Systeme" (hier in der PP kenne ich nur einen der das angeblich kann)

Aber wenn ich das ganze richtig verstanden habe ist es doch so:
Eine MD5-Hash kennt maximal 2^128 Möglichkeiten

Wenn ich nun den MD5-Hash von allen [b8-Bit[/b] "Zeichen" ermittele habe ich per Definition nur 2^8 Mögliche Kombinationen.

Es gibt also nur eine berenzte Menge von Möglichkeiten. Die Auswahl von diesen ist Abhängig von der Menge der Eingangsmöglichkeiten?`

Wenn ich nun mehrere Dateien vergleichen möchte reicht es wenn ich ich von jeder Datei die ersten 2^128 Bit vergleiche.
Danach muss ich, bei einer Anzahl von 2^128 Datein, immer einen gleichdn Hash wert bekommen.

Aber ich kann nicht verstehen das dies bei Dateien ab einer bestimmten Größe häufer passiert als bei anderen?

Naja, wie schon gesagt: Der Profi für diese Fragen ist Hagen (sagt er )

Wenn ich eben total daneben war -> Sorry

[Chewie]

Zitat von mschaefer:

Eigentlich denke ich auch nicht, dass der Binärvergleich wirklich soviel langsamer ist !

Wenn du nur 2 Dateien miteinander vergleichst, ist ein Binärvergleich wahrscheinlich schneller. Aber sobald eine Datei mit mehreren anderen und diese wiederum untereinander verglichen werden sollen, geht ein Hashwertvergleich schneller, da dieser ja pro Datei nur einmal berechnet werden muss.

[bigg]

Nochmal ein Link:
http://www.galileocomputing.de/openb...sel_24_003.htm

@dahead: MD4 ist nochmal schneller

[Flocke]

@Sharky: ja das war ein bisschen Unsinn

2^N (z.B. 2^128) bedeutet, dass es genau so viele unterschiedliche Hashwerte gibt. Da es aber mehr als 2^N unterschiedliche Dateien gibt, nämlich unendlich viele, müssen bei 2^N+1 ja mindestens 2 Dateien den gleichen Hashwert haben.

So ein Vergleich über Hashwerte ist also immer nur eine notwendige Bedingung und keine hinreichende. Das bedeutet:

1. Wenn zwei Dateien einen unterschiedlichen Hashwert besitzen, dann haben sie auch einen unterschiedlichen Inhalt.

2. Wenn zwei Dateien den gleichen Hashwert haben, dann können sie gleich sein. Um es wirklich zu überprüfen, muss man die Dateien Bit für Bit vergleichen.

Und das gilt für jeden Hashcode! Egal ob MD5 oder SHA-1 oder was weiß ich.

[bigg]

@dahead:

Die Dateien die angeblich bei dir im Screenshot doppelt sind,
sehen für mich eher aus, als könnten sie nicht geöffnet werden

Zugriff auf Datei verweigert. *plonk*
Der markierte Hash ist eigentlich ein Initalisierungs-Wert,
das heißt ein Leer-String ergibt den gleichen Hash.

Prüf das mal mit FileDup

[negaH]

Es wurde ja schon alles relevante gesagt, aber trotzdem mal in komprimierter Form

1.) mit Hash's ermittelt man ob zwei gehashte Dateien gleich sein könnten, zu 100% sicher kann man sich aber erst sein wenn man sie binär Bit für Bit vergleicht

2.) da man also im Worstcase Bit für Bit zwei Dateien vergleichen muß wäre es dumpfsinnig NICHT die Dateigrößen auf Gleichheit als Indiz zu benutzen. Ergo: die Dateigröße sollte als erstes und primäres Unterscheidungsmerkmal herangezugen werden.

3.) der Performance Vorteil ergibt sich aus dem Arbeitsaufwand. Zuerst vergleicht man jeweils 32Bit mit 32Bit Dateigröße. Falls dort Gleichheit herrschen sollte vergleicht man 128Bit mit 128Bit Hashwert. Und erst bei Gleichheit vergleicht man nun die Dateien Bit für Bit. Das macht also 1/(2^32 * 2^128)=(1/2^160) an Trefferquote das man zwei Dateien auch wirklich binär vergleichen muß. Versuche mal 1/2^160 auszurechnen und überlege dir wie lange es dauert einen 160Bit Zähler der in die Sekunde 256 mal inkrementiert wird zum überlaufen zu bringen. (2^260 / 2^8) = 2^152 Sekunden ~ 180000000000000000000000000000000000000 Jahre !!) Man sieht das 160 Bit = 2^160 eine enorm große Zahl darstellt und somit die Wahrscheinlichkeit für zwei gleiche Hashwerte zu unterschiedlichen Dateien in der Realität sehr sehr gering sein wird, aber eben nicht unmöglich ist. In fakt gibt es theoretisch Unendlich-(2^160) viele Dateien die alle den gleichen Hashwert erzeugen müssen. Davon sind aber fast Undenlich viele Dateien unendliche Bits groß. D.h. die größte Masse an Dateien mit gleichem Hashwert sind so rießig groß das sie auf keinen Rechner gespeichert werden können.

4.) die so gesammelten Dateigrößen + Hashwerte sollten in einer datenbank sortiert gespeichert werden. Bei sagen wir mal 1024 so gesammelten Dateien in der DB benötigt man im Worstcase nur 12 Vergleiche von Dateigrößen + Hashwerten

5.) der Hashwert wird über die komplette Datei gezogen, NICHT nur über die ersten Bytes der Datei

6.) Da der hashwert nur 128 oder 256 Bits groß ist bedeutet das das zb. mit 1Mb großen Dateien exakt 2^(1Mb-256) Dateien gibt die den gleichen Hashwert erzeugen aber binär komplett unterschiedlich sind. Der Hash einer Datei, wie auch jede andere Prüfsumme ist also kein eineindeutiges Indiz für den Vergleich auf Gleichheit ! Sondern eher nur ein Indiz für Ungleichheit wenn die Hashwerte sich unterscheiden. Um so wichtiger ist es das man über die komplette Datei hasht.

7.) somit garantiert eine Hashfunktion das sie einen anderen Wert erzeugt wenn die Datei sich nur um 1 Bit unterscheidet. Sie garantiert aber nicht das zwei gleiche Hashwerte auch zweimal die gleiche Datei darstellt.

8.) Performancetechnisch sind die Hashfunktionen heutzutage schneller als jede Form eines direkten Binären Vergleiches. D.h. die Benutzung einer Hashfunktion ist absolut richtig wenn man einen performanten Vergleich erzielen möchte. Denn man produziert von einer neuen Datei nur einmal den Hash und vergleicht diesen dann mit 1000'enden anderen Hashwerten + Dateigrößen in der Datenbank. Das ist bei weitem viel weniger an Speicherzugriffen als alle diese Dateien binär bit für bit mit der neuen Datei zu vergleichen.

9.) ein 256Bit Algo. hat zwar viel weniger Redundanz als ein 128 Bit Algo, dafür sind die 256 Bit Algos durch die Bank weg aber auch langsammer, die Hashwerte benötigen 2x mehr an Speicherplatz und die Wahrscheinlichkeiten für Kollisionen mit unseren heutigen Dateien ist aber nicht um 2^128 vergleichbar größer. Ich würde also für so eine Aufgabe absolut den 128Bit MD4 Algo empfehlen. Er ist immer noch der schnellste seiner Art.

10.) bei einer solchen Aufgabe ist es wichtig sich darüber zu informieren wie die Wahrscheinlichkeiten der unterschiedlich auftretenden Dateien verteilen. Beispiel: in der DB sind 65535 Dateien gespeichert. Davon werden maximal aber nur 1-2 % auch die gleiche Dateigröße besitzen und davon hat KEINE den gleichen Hashwert. Wird nun eine neue Datei eingefügt so wird diese mit max. 1-2% der gespeicherten Dateigrößen übereinstimmmen und von diesen 2% wird mit sehr sehr geringer Wahscheinlichkeit 1 Datensatz den gleichen Hashwert besitzen.
Mit einer 128 Bit Hashfunktion kann man mal unsauber eine Pi*Daumen Abschätzung machen -> falls 2^128 Datensätze, also 2^128 verschiedene Dateien in der DB gespeichert würden so ist die wahrscheinlichkeit 100/(2^32) Prozent das man 1 Datensatz findet der mit dem neuen Datensatz übereinstimmen wird. Die 2^32 ist die Dateigröße die ebenfalls berücksichtigt werden sollte. Für diese riesige Datenbank von 2^128 Dateien heist dies das das Program sich eher auf eine hoch optimierte Datenbanksuche konzentrieren sollte da der eigentliche Dateivergleich sich in der Gesamtperformance fast garnicht auswirken wird.

Fazit: nehme MD4 mit 128Bit Hashwerten + Dateigröße in DB auf. Konzentriere dich darauf die richtige "Datenbank" zu finden statt sich mit der "besten" Hashfunktion Zeit zu vergeuden. In der Gesamtperformance wird es garantiert nicht die Hashfunktion sein die die meiste Zeit verbrauchen wird, eher die Suche in der DB.

Gruß Hagen

[dahead]

@bigg:

ich habe die im screenshot gezeigten dateien mit deinem programm mal getestet und er zeigt mir in der tat eine andere md5 checksumme an. also muss es wohl richtig sein, dass ich bei meinem test darauf keinen zugriff bekommen hatte (ich frage mich allerdings noch warum, muss ich noch prüfen).

was anderes: ich habe mir deinen source-code mal angesehen und festgestellt (evtl. auch übersehen, korrigier mich falls ich falsch liege), dass dein programm relativ zügig arbeitet. ich beziehe mich mal auf folgenden source auszug (hoffe das macht dir nichts aus):

Delphi-Quellcode:

Filter_FileSize;
FastScan;
Filter_ShortMD5;
LowScan;
Filter_LongMD5;

du prüfst die dateien allerdings nicht inhaltlich byte per byte, oder? (ich habe zumindest keine solche funktion auf die schnelle gefunden.)

edit: achja, danke für den link. der war auch sehr aufschlussreich. darin steht u.a. dass sha langsamer als md5 ist. bzw. auch, dass für md4 (mittlerweile auch für md5) kollisionen entdeckt wurden. dazu habe ich auch noch das hier gefunden: http://eprint.iacr.org/2004/199

@negaH:

vielen dank für deine mühe hier nochmal alles gründlich zusammenzufassen!

in der tat benötigt mein programm nicht die meißte zeit damit, den hash zu ermitteln. das geht auch bei md5 relativ zügig. das einzige zeit-problem ist der byte pro byte vergleich der kompletten filestreams.