Hashfunktion

Proggen.org - Lernprojekt: Duplikatefinder
Benutzeravatar
Kerli
Beiträge: 1456
Registriert: So Jul 06, 2008 10:17 am
Wohnort: Österreich
Kontaktdaten:

Re: Hashfunktion

Beitrag von Kerli » Fr Mai 21, 2010 5:28 pm

cloidnerux hat geschrieben:Da die meisten noch keine SSD haben, gehen wir von einer HDD aus.
da hast du dann als maximalen Datendurchsatz von ~22Mbyte/s.
Das bedeutet, dass du beim Hashen von mehreren Gigabyte an Daten eben sehr viel Daten lesen musst, was eben sehr lange Dauern wird, bei 220GB ca 27h!!!
Wie kommst du denn auf 27h? Laut meiner Rechnung entspricht das einer Geschwindigkeit von 80GB/h (22*60*60/1024=> 77,3GB/h) weshalb man die 220GB in unter 3 Stunden bewältigen können sollte. Ich hab jetzt keine genauen Messungen, aber wie ich das letzte Mal meine externe Festplatte über USB komplett kopiert habe bin ich auf ca. 100GB/h gekommen...
cloidnerux hat geschrieben:Ich sehe eine große Möglichkeit einen eindeutigeren Hash aus der Dateigröße zu bauen, denn die Dateigröße bei "normalen" Dateien(Texte, Bilder) relativ Unterschiedlich.
Vielleicht nicht unbedingt aus der Größe einen Hash erstellen, aber wir könnten damit durchaus eine Vorauswahl treffen und nur Dateien mit einer ähnlichen Größe vergleichen.
cloidnerux hat geschrieben:Algorithmen
Was auch noch wichtig ist, ist zuerst einmal festzustellen um was für Dateien es sich handelt. Wir werden wohl kaum den Hash eines Videos mit dem eines Textes vergleichen...
"Make it idiot-proof and someone will invent an even better idiot." (programmers wisdom)

OpenGL Tutorials und vieles mehr rund ums Programmieren: http://www.tomprogs.at

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Fr Mai 21, 2010 6:43 pm

cloidnerux hat geschrieben:Da die meisten noch keine SSD haben, gehen wir von einer HDD aus.
da hast du dann als maximalen Datendurchsatz von ~22Mbyte/s.
Das bedeutet, dass du beim Hashen von mehreren Gigabyte an Daten eben sehr viel Daten lesen musst, was eben sehr lange Dauern wird, bei 220GB ca 27h!!!

Wie kommst du denn auf 27h? Laut meiner Rechnung entspricht das einer Geschwindigkeit von 80GB/h (22*60*60/1024=> 77,3GB/h) weshalb man die 220GB in unter 3 Stunden bewältigen können sollte. Ich hab jetzt keine genauen Messungen, aber wie ich das letzte Mal meine externe Festplatte über USB komplett kopiert habe bin ich auf ca. 100GB/h gekommen...
Ohh... Kommafehler. Aber selbst dann rentiert es nicht, ich will nicht 3h auf meine Duplikatprüfung warten ;)
Was auch noch wichtig ist, ist zuerst einmal festzustellen um was für Dateien es sich handelt. Wir werden wohl kaum den Hash eines Videos mit dem eines Textes vergleichen...
Das wäre schon über die Dateigröße gegeben.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Hashfunktion

Beitrag von Xin » Fr Mai 21, 2010 6:55 pm

cloidnerux hat geschrieben:Ohh... Kommafehler. Aber selbst dann rentiert es nicht, ich will nicht 3h auf meine Duplikatprüfung warten ;)
Wenn Du das Programm sinnvoll nutzen willst, wirst Du die Auswahl haben, 3 Stunden die Kiste laufen zu haben, während Du draußen bist oder TV guckst oder ein Vielfaches von drei Stunden Daten zu vergleichen, die eventuell identisch sein könnte, bzw. Daten zusammenzuführen, die eventuell identisch sein könnte - mal von den Daten abgesehen, die Du übersiehst.
cloidnerux hat geschrieben:
Was auch noch wichtig ist, ist zuerst einmal festzustellen um was für Dateien es sich handelt. Wir werden wohl kaum den Hash eines Videos mit dem eines Textes vergleichen...
Das wäre schon über die Dateigröße gegeben.
Ich sehe keinen Grund, warum man sich auf einen Hash-Wert beschränken muss. Die Dateigröße ist da genauso Teil der Identifikation wie selbstberechnete Hashwerte.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Fr Mai 21, 2010 7:43 pm

Ich sehe keinen Grund, warum man sich auf einen Hash-Wert beschränken muss. Die Dateigröße ist da genauso Teil der Identifikation wie selbstberechnete Hashwerte.
Ich sehe den "Hashwert" als Identifiezierung an, der ausschlag gebend für den vergleich 2er Dateien ist. Am Ende muss unser Programm ja nur sagen können, ist es ein Duplikat oder nicht?
Natürlich könnten wir auch andere Faktoren mit einbeziehen, wie Name, Inhalt, Dateiinformationen, aber das Führt am Ende dazu, das wir nur noch Warscheinliche Duplikate finden, die wir dann entweder mit Direkter 1:1 Prüfung filtern müssen, doer dem Nutzer vorwerfen.
Nur müssen wir das ganze mehrstufig sehen:
Welchen sinn macht es, Hunderte Gigabyte an Daten einzulesen, zu Hashen und aus den 1M Datein dann vlt 1k Duplikate zu Finden, wenn wir nur mit 1 Information aus den 1M Dateien alle bis auf 2k Filtern können?
Jeder Nutzer freut sich, wenn die Prüfung schneller ist.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Hashfunktion

Beitrag von Xin » Fr Mai 21, 2010 7:54 pm

cloidnerux hat geschrieben:
Ich sehe keinen Grund, warum man sich auf einen Hash-Wert beschränken muss. Die Dateigröße ist da genauso Teil der Identifikation wie selbstberechnete Hashwerte.
Ich sehe den "Hashwert" als Identifiezierung an, der ausschlag gebend für den vergleich 2er Dateien ist. Am Ende muss unser Programm ja nur sagen können, ist es ein Duplikat oder nicht?
Für Sicherheit musst Du die Dateien grundsätzlich sowieso vergleichen.
Ein Hashwert kann nie Sicherheit bieten, sondern immer nur ein (möglichst starkes) Indiz.
cloidnerux hat geschrieben:Natürlich könnten wir auch andere Faktoren mit einbeziehen, wie Name, Inhalt, Dateiinformationen, aber das Führt am Ende dazu, das wir nur noch Warscheinliche Duplikate finden, die wir dann entweder mit Direkter 1:1 Prüfung filtern müssen, doer dem Nutzer vorwerfen.
So sieht es aus, und ich sehe zum Beispiel keinen Grund eine Datei mit 4GB Größe (DVD-Image?) zu hashen, wenn es genau eine Datei gibt, die diese Größe hat. Über den Hashwert kann man sich dann Gedanken machen, wenn diese Größe mehrfach auftritt und bis dahin ist die Dateigröße die billigste Art, zwei Dateien definitiv voneinander zu unterscheiden.
cloidnerux hat geschrieben:Nur müssen wir das ganze mehrstufig sehen:
Welchen sinn macht es, Hunderte Gigabyte an Daten einzulesen, zu Hashen und aus den 1M Datein dann vlt 1k Duplikate zu Finden, wenn wir nur mit 1 Information aus den 1M Dateien alle bis auf 2k Filtern können?
Jeder Nutzer freut sich, wenn die Prüfung schneller ist.
Nein, nicht alle. Andere freuen sich, wenn die Sache gründlich ist.
Des Weiteren ist das Problem umgekehrt: je weniger sicher die Sache ist, desto eher werden vermeindliche Duplikate erkannt. Und was meinst Du, was die Freude groß ist, wenn das vermeintliche Duplikat das einzige Original war?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Hashfunktion

Beitrag von Dirty Oerti » Sa Mai 22, 2010 10:12 am

Also ich fasse das mal etwas zusammen, in eine Art "Halbpseudo-Code" verpackt.

Code: Alles auswählen


typedef struct
{
   uint64 size;
   uint64 hash1;
   uint64 hash2;
   char* path;
   char* name;
} sFile;


bool fillsFile(sFile& file)
{
   file.size = getSize(file);
   file.hash1 = hashFileStart(file);
   file.hash2 = hashFileEnd(file);
   return true;
}


bool equalsFile(sFile& a, sFile& b)
{
   if (a.size != b.size) return false;
   if (a.hash1 == b.hash1 && a.hash2 == b.hash2) return true;
   else return false;
}

So in etwa sieht ja das Ziel aus.
Dann brauchen wir noch eine Funktion, die die Dateihash-Werte berechnet (ich habe hier mal 2 Hashwerte angegeben, nur mal als Beispiel. Einer fürs Ende, einer für den Anfang. Wenn die Datei kleiner ist als eine gewisse Schranke sollte der 2. Wert natürlich nicht berechnet werden sondern mit dem 1. Werte die komplette Datei gehasht werden)

Dazu hatte ich mir schon ein paar Sachen angesehen und testweise auch mal Hash-Algorithmen verwendet.
Getestet habe ich bisher mit folgender Hashfunktion: http://de.wikipedia.org/wiki/FNV_%28Informatik%29

Den SourceCode hab ich mir dabei von Wikipedia geliehen (wie die beiden dort verwendeten Zahlen berechnet oder gewählt werden müssen steht da ja leider nicht)
und leicht modifiziert (damit er für mein Testprogramm direkt von der Standardeingabe liest, bis nichts mehr kommt)
Damit hab ich mal ein paar große Dateien (das größte, was ich im Moment gerade da hatte) gehasht und SO lange dauert das gar nicht:
daniel@GosigMus:~/Desktop/testhash$ cat ../ubuntu-10.04-server-i386.iso | time ./th
Erzeuge Hash aus Standardeingabe!
HASH = 16332320478266214823

5.04user 0.33system 0:05.42elapsed 98%CPU (0avgtext+0avgdata 4416maxresident)k
0inputs+0outputs (0major+327minor)pagefaults 0swaps

daniel@GosigMus:~/Desktop/testhash$ ls -la ../ | grep ubuntu
-rw------- 1 daniel daniel 700413952 2010-05-12 19:19 ubuntu-10.04-server-i386.iso
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » So Mai 23, 2010 11:24 am

Den SourceCode hab ich mir dabei von Wikipedia geliehen (wie die beiden dort verwendeten Zahlen berechnet oder gewählt werden müssen steht da ja leider nicht)
und leicht modifiziert (damit er für mein Testprogramm direkt von der Standardeingabe liest, bis nichts mehr kommt)
Damit hab ich mal ein paar große Dateien (das größte, was ich im Moment gerade da hatte) gehasht und SO lange dauert das gar nicht:
Die Parameter für das Hashing stehen im Link unterhalb der Wikipediaseite.
Es wäre eine Mögliche Implementation, die du Vorgeschlagen hast. Mal sehen ob wir daraus ein Funktionsfähiges Modul bekommen.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » So Mai 30, 2010 12:49 pm

Ich habe mich das Wochende etwas mit Edge-Detection beschäftigt, vorallem mit dem Laplace-, Sobel/Scharr-Filter.
Der erste Eindruck war: je größer das Bild desto länger dauert es. Bei einem 8Mpixel Bild von einer Kamera um die 40s, bei einem 1024*768 geht es immerhin in 2s.
Gut, wir suchen etwas um zwei Unterschiedlich gestaltete Bilder zu Vergleichen.
Dazu habe ich mal eben schnell ein kleinen Test gemacht. Das selbe Bild, aber jeweils nur noch halb so Groß.
Auf dem Bild sieht man oben die Orginalbilder, unten die von meinem Programm mit dem Laplace-Filter generierte Bild.
http://img88.imageshack.us/img88/2407/l ... ebniss.png
Man sieht, das bei abnemender Bildgröße es sträkere Kontratse gibt, wo die schrift vorher noch Bläulich war, ist sie jetzt Weiß.
Mal sehen was wir dann daraus machen können.

p.s: Testergebnisse nicht Aussagekräftig, da ich es unter C# im manged Code im Debug-Modus durchgeführt habe.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Hashfunktion

Beitrag von Xin » Mo Mai 31, 2010 9:40 pm

cloidnerux hat geschrieben:Ich habe mich das Wochende etwas mit Edge-Detection beschäftigt, vorallem mit dem Laplace-, Sobel/Scharr-Filter.
Der erste Eindruck war: je größer das Bild desto länger dauert es. Bei einem 8Mpixel Bild von einer Kamera um die 40s, bei einem 1024*768 geht es immerhin in 2s.
Erstaunlich. ;-)

Ich habe Dich hiermit für die Hash-Funktionen eingetragen. Zum einen glaube ich, dass Du in der letzten Zeit dich durchaus zu was Fähigem entwickelt hast und Du beschäftigst Dich ja schon damit ^^
cloidnerux hat geschrieben:Gut, wir suchen etwas um zwei Unterschiedlich gestaltete Bilder zu Vergleichen.
Dazu habe ich mal eben schnell ein kleinen Test gemacht. Das selbe Bild, aber jeweils nur noch halb so Groß.
Auf dem Bild sieht man oben die Orginalbilder, unten die von meinem Programm mit dem Laplace-Filter generierte Bild.
http://img88.imageshack.us/img88/2407/l ... ebniss.png
Man sieht, das bei abnemender Bildgröße es sträkere Kontratse gibt, wo die schrift vorher noch Bläulich war, ist sie jetzt Weiß.
Mal sehen was wir dann daraus machen können.
Ich stelle mir die Frage, was uns die Filter bringen? Sie vereinfachen das Bild, so dass sie nahezu Schwarz/Weiß sind. Ich würde mir erstmal einfach die Bildmap schnappen und relativ zur Größe mehrere Raster drüber legen, z.B. 3x3, 6x6, 12x12. Hier würde ich die Pixel in der Mitte eines Rasterquadrates stärker werten, damit Randverschiebungen bei unterschiedlichen Auflösungen das Ergebnis nicht zu stark verfälschen. Anschließend würde ich die Werte aufaddieren und wenn dieser Hashwert mit einem anderen Bild ähnlich ist (also nur geringfügig abweicht), dann sind sich auch die Bilder ähnlich - und zwar auch dann, wenn das Bild gedreht oder gespiegelt wurde.
cloidnerux hat geschrieben:p.s: Testergebnisse nicht Aussagekräftig, da ich es unter C# im manged Code im Debug-Modus durchgeführt habe.
Woher kommen die Filter?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Di Jun 01, 2010 5:40 am

Woher kommen die Filter?
Eigenentwicklung aus Wikipediaartikeln und ein bisschen C-Code zum Sobel-Filter.
Diese Fieler basieren alle auf dem selben Prinzip.
Man betrachtet immer 3*3 Pixel.
Nun Multipliziert man jeden Pixel mit einem für die Position vorgegeben Wert, addiert alle Produkte auf teilt sie durch einen vorgegebenen Wert.
Das ist beim Sobel/Scharr-Filter so, beim Laplace und noch bei einigen anderen.
Ich stelle mir die Frage, was uns die Filter bringen? Sie vereinfachen das Bild, so dass sie nahezu Schwarz/Weiß sind. Ich würde mir erstmal einfach die Bildmap schnappen und relativ zur Größe mehrere Raster drüber legen, z.B. 3x3, 6x6, 12x12. Hier würde ich die Pixel in der Mitte eines Rasterquadrates stärker werten, damit Randverschiebungen bei unterschiedlichen Auflösungen das Ergebnis nicht zu stark verfälschen. Anschließend würde ich die Werte aufaddieren und wenn dieser Hashwert mit einem anderen Bild ähnlich ist (also nur geringfügig abweicht), dann sind sich auch die Bilder ähnlich - und zwar auch dann, wenn das Bild gedreht oder gespiegelt wurde.
Das werde ich mir auch nochmal anschauen.
Was es bringen soll:
Kleinere Bilder, Gedrehte Bilder oder auch verfärbte Bilder haben alle ziemlich gleiche Kanten. Wenn wir also den hash der Kanten haben, so sollte man doch in der Lage sein, unterschiedliche Bilder eindeutig zuzuweisen.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Antworten