Hashfunktion

Proggen.org - Lernprojekt: Duplikatefinder
Benutzeravatar
cloidnerux
Moderator
Beiträge: 3083
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Hashfunktion

Beitrag von cloidnerux » Mo Mai 17, 2010 5:23 pm

Da über den Hash einer Datei eventuelle Duplikate gefunden werden sollen, kann sich der Hash nach Folgenden Werten Richten:
-Größe der Datei
-Binärer Inhalt der Datei
-Name
-Endung
-Pfad
-Weitere Dateiinformationen(Besitzer, Erstellungsdatum, Bearbeitungsdatum)
Da aber im Zusammenhang mit Duplikaten folgende Effekte auftreten können:
-Unabsichtliche Kopien die dann automatisch "Kopie von ..." oder "<Name>(X)" genannt werden.
-Verschiedene Daten und Besitzer(Unter Linux in einen Allgemeinen ordner Kopiert)
Ist ein die Bildung eines sinnvollen Hashs nur noch über Größenangaben, Inhalt und Endungen möglich.
Wobei aber beachtet werden muss, das es bei dem Duplikatfinder womöglich 1.000.000 Datein Indexiert werden müssen es unmöglich ist, den Kompletten Inahlt zu Hashen, da dies den Indexierungsforgang erheblich verlangsamen würde.
Jetzt werden ntürlich viele MD5 vorschalgen, was auch nicht schlecht wäre, nur wollen wir hier etwas lernen.
ich versuche heute abend noch ein kleines Demo-Programm zusammenhacken, um meine Idee zu einem hash-Algortihmus zu testen.
Redundanz macht wiederholen unnötig.
quod erat expectandum

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

Re: Hashfunktion

Beitrag von Xin » Mo Mai 17, 2010 6:33 pm

cloidnerux hat geschrieben:Ist ein die Bildung eines sinnvollen Hashs nur noch über Größenangaben, Inhalt und Endungen möglich.
Ich denke, wir werden eine Datenbank aufbauen, wo Name (inkl. Endung), Größe und Hash drin verzeichnet sind.
cloidnerux hat geschrieben:Wobei aber beachtet werden muss, das es bei dem Duplikatfinder womöglich 1.000.000 Datein Indexiert werden müssen es unmöglich ist, den Kompletten Inahlt zu Hashen, da dies den Indexierungsforgang erheblich verlangsamen würde.
Guter Punkt. Hier sollte es also vielleicht zwei Punkte geben: Einen Hash über bestimmte Stellen im File oder - wer Zeit hat - einen Hash über die komplette Datei.
cloidnerux hat geschrieben:Jetzt werden ntürlich viele MD5 vorschalgen, was auch nicht schlecht wäre, nur wollen wir hier etwas lernen.
ich versuche heute abend noch ein kleines Demo-Programm zusammenhacken, um meine Idee zu einem hash-Algortihmus zu testen.
Dani93s Idee mit dem Hashs aus der Qt-Library fand ich auch ganz witzig. Allerdings muss ich auch sagen, dass wir kein Projekt brauchen, dass nur Funktionen von irgendwelchen DLLs ruft. Dann könnten wir direkt Java programmieren ^^

Wer kann, soll also auch ruhig mal seinen Kopf benutzen. Von daher fände ich es auch interessant, den Algorithmus zum Durchschreiten der Verzeichnisse nicht einer Plattformunabhängigen DLL anzuvertrauen, sondern plattformunabhängig selbst zu schreiben.
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 » Mo Mai 17, 2010 7:37 pm

Die Hashs müssen denke ich vorallem auf den Inhalt spezifiziert werden.
Sprich eine Text-Datei wird anders gehasht als eine Bild oder Audiodatei.

Bei einer Textdatei kann man mit normalen Hashverfahren arbeiten, das ist gut dokumentiert und sollte nicht schwer zu implementieren sein.
So einen "Rohdaten-Hash" könnte man auch auf die Bilder/Audio/Video-Dateien (ZIP, doc, pdf, ...) anwenden, das ermöglicht dem Duplikatfinder aber nur EXAKT gleiche Dateien zu finden.

Als Konsequenz daraus ist zu sehen, dass wir zum einen eine Möglichkeit haben müssen, unterschiedliche Dateien am besten ohne die simple Verwendung der Dateierweiterung einen eindeutigen Dateityp zuweisen zu können.

Zum anderen brauchen wir pro Dateityp (den wir anfangs unterstützen wollen) einen Weg um Hashs zu bilden, die am besten eine variable (und vom Benutzer einstellbare) Toleranz haben.

Bei Texten ist das wie schon angesprochen "simpel", die Toleranz ist auch in vielen Algorithmen implementierbar.
Bei Bildern haben wir das Problem das hier viel mehr "Variablen" zu berücksichtigen sind:

Das Bild könnte:
* Skaliert
* Gedreht (und zwar nicht nur in 90° Schritten)
* Gespiegel
* Eingefärbt
* Auf Schwarzweiß reduziert
* Nachträglich geschärft
* mit einem kleinen Titel versehen
* oder (ganz fies) auch zurechtgeschnitten sein
und noch andere Eigenheiten aufweisen.
Und im Prinzip muss es dem Benutzer freistehen, in wie weit diese Unterschiede toleriert werden oder nicht. Denn bei einer Suche interessieren ihn/sie womöglich nur die "echten" Kopien, bei der nächsten auch die aufgebesserten Kopien seiner/ihrer Urlaubsfotos.

Wir müssen also eine Möglichkeit finden, einen Hashwert aus Bildern zu berechnen der obiges mit berücksichtigt.
Um die Geometrischen Aspekte abzudecken ist mir folgende Idee gekommen:

Zuerst wird das Zentrum des Bildes gesucht.
Den Wert des Pixels nimmt man als ersten Datenwert und erstellt daraus einen ersten Hash.
Den zweiten Datenwert kann man dann durch Multiplikation aller Pixelwerte des Kreises erhalten, der den "Zentrumspixel" umgibt. Auch daraus berechnet man einen Hash.
Und so kann man sich vom Zentrum immer weiter an die Ränder des Bildes vorarbeiten (wie mit den Ecken verfahren wird ist noch mal eine Angelegenheit für sich)
Man erhält pro Kreis um das Zentrum also einen Hashwert, und all diese Hashwerte für sich ergeben ein recht gutes Profil des Bildes. (Bei dem Rotation und Spiegelung schonmal keine Rolle mehr spielen)
Reduziert man das Verfahren auf (z.B.) 100 Kreise mit gleichem Abstand zum Zentrum, dann kann man das Bild schon sehr gut identifizieren, selbst wenn es skaliert wurde.
Auf eine ähnliche Weise müsste es auch möglich sein, zurechtgeschnittene Bilder zu erkennen.

Wichtig und das A und O bei dieser Angelegenheit ist nunmal, wie die Toleranzwerte eingestellt werden.

Audiodateien sind dann noch einmal eine Klasse für sich. Hier gibt es ja schon Verfahren, um einen Fingerabdruck der Audiodatei zu erstellen.
Da müsste man sich halt mal angucken, wie das gemacht wird.

Videodateien sind dann wohl die absolute Krönung des Ganzen.
Hierbei könnte man ein kombiniertes Verfahren aus obigen anwenden und "Bildvergleiche" mit Einzelbildern durchführen.

Gepackte Dateien müssten wohl entpackt werden und die enthaltenen Dateien verglichen werden...

Bei doc/pdf müsste auch entsprechend Text- und Bilddaten extrahiert werden.

So, soweit erstmal was mir spontan einfiel :)
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: 3083
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Mo Mai 17, 2010 8:06 pm

Jetzt muss man mal Aufwand mit Nutzen vergleichen:
Ich hab in meiner "kleinen" Bildersammlung ca 2000 Bilder.
Alle so im 1 - 8 Megapixel bereich.
Wenn du pro Bild 100msess Brauchst, bedeutet das, dass du >3 Min brauchts, nur um alle Bilder zu Hashen.
Dann liegt das Problem auch im Hashvergleich:
Ist in der Prüfung 1 Pixel unterschiedlich, wie verändert sich der Hash?
Wie willst du Prüfen ob ein Bild gleich, ähnlich oder verändert ist?
Wie würde der Hashwert aussehen.
Bei Videos wäre es sogar noch schlimmer mit der Frameanalyse. Du hättest da einen Datenoverheap, der nihct nötig ist, denn Videos editiert man meistens nicht oder hat einen guten Grund sein Video verändert zu speichern.
Auch der reine Content-Hash verlangt viel ab. Wie viel Zeit würde es wohl dauern, meine 229GB Dateien einzeln vollständig zu hashen?
Auch stellt sich die Frage, in wie ferne "Gleiche" Inhalte sich in der Binären Speicherung unterschdeiden.
Redundanz macht wiederholen unnötig.
quod erat expectandum

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

Re: Hashfunktion

Beitrag von Dirty Oerti » Mo Mai 17, 2010 10:23 pm

Videos bearbeitet man nicht? Das wäre mir neu :-P

Dass du, wenn du deine komplette Musik/Bilder/Videosammlung durchsuchen lässt bei einem solchen Verfahren auf eine ordentliche Zeitdauer kommst ist ja wohl klar.
Aber man muss das auch mal realistisch sehen:
Es wird uns kaum möglich sein (ich denke sogar dass es mit den aktuellen technischen Möglichkeiten auf HomePCs unmöglich ist) eine so große Sammlung an Daten in so kurzer Zeit (weniger als 3 Minuten) komplett durchsuchen zu können.
Das muss man ja auch nicht.
Ich denke kaum, dass man Dedupe als "Dateibrowser" im eigentlichen Sinne benutzen kann wenn solche Vergleiche wie ich oben angesprochen habe gewünscht sind.
Deshalb sollten solche Vergleiche möglichst optional sein.

Es sollte also vom Benutzer abhängen, wie genau er seine Duplikatsuche gestalten will.
Möchte der Benutzer genauere Werte, dann muss er auch eine längere Bearbeitungsdauer in Kauf nehmen.
(3 Minuten sind ja wohl nichts wenn man diesen Arbeitsaufwand mal genau betrachtet. Da wären 30 und mehr Minuten schonmal Minimum)

Hängt hat alles davon ab, wie genau man es machen will (Wenn du aus jedem deiner 2000 Bilder nur sagen wir 40 -50 Werte entnimmst dann schaffst du das locker schneller als 3 Minuten, vorrausgesetzt die Festplatte macht mit. Dann bekommst du aber eben nicht unbedingt genaue Werte)

Deswegen sage ich ja: Es kommt auf den Toleranzbereich an.

Übrigens: Das mit dem "Bildhash" ist mal nur eine erste Idee. Da gibt es sicherlich noch Besseres. Bis jetzt ist mir aber noch nichts eingefallen.
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
Kerli
Beiträge: 1456
Registriert: So Jul 06, 2008 10:17 am
Wohnort: Österreich
Kontaktdaten:

Re: Hashfunktion

Beitrag von Kerli » Mo Mai 17, 2010 10:35 pm

Nur einmal so als kleiner Einwurf. Ich würde irgendwie von dem Begriff Hash weggehen, da es dabei mehr um eine eindeutige Identifikation und nicht um ein Matchin mit Toleranz geht. Deshalb würde ich es eher als zb. Featureextraktion oder Merkmalsbestimmung bezeichnen.

Bei einem Bild wäre es zum Beispiel einen gute Idee das Bild auf eine einheitliche Größe zu bringen, dann in ein Schwarz-Weiß Bild konvertieren und anschließend einen Kantendetektion durchführen. Dannach kann man über die Differenz der Pixelwerte über das gesamte Bild schon etwas über die Ähnlichkeit aussagen. Für unterschiedliche Laufzeiten bzw. Genauigkeit kann man dann ja zum Beispiel die Bildgröße verändern.

Zu gedrehten/zugeschnittenen Bildern. Sollen die wirklich als Duplikate erkannt werden? Drehungen in 90° Schritten und Spiegelungen lass ich mir ja noch einreden, aber alles andere würde ich nicht mehr als Duplikat bezeichnen...
"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
Xin
nur zu Besuch hier
Beiträge: 8486
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Hashfunktion

Beitrag von Xin » Mo Mai 17, 2010 10:49 pm

Kerli hat geschrieben:Nur einmal so als kleiner Einwurf. Ich würde irgendwie von dem Begriff Hash weggehen, da es dabei mehr um eine eindeutige Identifikation und nicht um ein Matchin mit Toleranz geht. Deshalb würde ich es eher als zb. Featureextraktion oder Merkmalsbestimmung bezeichnen.
Dateien sollen zunächst eindeutig Identifiziert werden.

Bilder bekommen eine zusätzliche Sonderbehandlung.
Kerli hat geschrieben:Bei einem Bild wäre es zum Beispiel einen gute Idee das Bild auf eine einheitliche Größe zu bringen, dann in ein Schwarz-Weiß Bild konvertieren und anschließend einen Kantendetektion durchführen. Dannach kann man über die Differenz der Pixelwerte über das gesamte Bild schon etwas über die Ähnlichkeit aussagen. Für unterschiedliche Laufzeiten bzw. Genauigkeit kann man dann ja zum Beispiel die Bildgröße verändern.
Gefällt mir.
Kerli hat geschrieben:Zu gedrehten/zugeschnittenen Bildern. Sollen die wirklich als Duplikate erkannt werden? Drehungen in 90° Schritten und Spiegelungen lass ich mir ja noch einreden, aber alles andere würde ich nicht mehr als Duplikat bezeichnen...
Mir geht es auch nur um gedrehte oder gespiegelte Bilder.... mal nicht übertreiben.

Es geht mir vorrangig um Fotos, die gedreht wurden.
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 » Di Mai 18, 2010 1:54 pm

Ich nenne das nun einfach mal Hashs, weil ich es so gewohnt bin. Soweit ich weiß (bzw das Buch über Algorithmen, dass wir in der Schulbibliothek haben) gibt es auch "Hashverfahren" mit Toleranzzonen.
Xin hat geschrieben:Gefällt mir.
Mir nicht.
Bzw ich sehe darin einen Nachteil.

Wenn wir die Bilder erst konvertieren, dann brauchen wir zunächst mal zusätzlichen Speicher. Bei vielen Bildern geht das dann eventuell in einen Bereich, der nicht mehr vertretbar ist.
Außerdem haben wir dann das Problem, dass wir WIRKLICH ein Bild komplett (PIXEL für PIXEL sozusagen) bearbeiten müssen, während bei meinem Vorschlag nur einzelne Pixel betrachtet werden müssen.
Deshalb wird eine Konvertierung mit anschließender Kantenerkennung um einiges mehr an Ressourcen abverlangen als meine mal grob skizzierte Methode.
Ein Vorteil wäre allerdings, dass dadurch mit Sicherheit genauere Ergebnisse geliefert werden.
Xin hat geschrieben:Mir geht es auch nur um gedrehte oder gespiegelte Bilder.... mal nicht übertreiben.
Naja, es geht ja erstmal darum mal zu sammeln, womit das Programm so konfrontiert werden könnte.
Wie weit man dass dann ausbaut ist eben zum einen eine Frage unseres "Könnens", zum anderen eine Frage des Nutzens.

Das Fotos (auch Urlaubsfotos) nur in 90° Schritten gedreht werden ist außerdem eine Utopie.
Häufiger Anwendungszweck von Bildbearbeitungsprogrammen ist es, die Fotos gerade zu drehen, wenn man beim Fotografieren die Hand nicht ruhig hatte (als gerade richten gegen den Horizont)
Das zu erkennen (dabei wird es sich wohl meistens um Drehungen um +/- 10° handeln mit anschließendem Zuschneiden) dürfte aber wirklich eine Herausforderung sein...
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: 3083
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Hashfunktion

Beitrag von cloidnerux » Di Mai 18, 2010 2:04 pm

Dedupe soll vorrangig Diplikate finden, dabei wird es sich in dne meisten fällen um direkte Duplikate handeln, die man hashen kann.
Die Funktion, Bilder auf ähnlichkeit zu Prüfen ist nur erstmal ein Extra, aus meiner sicht.
Dann muss zusätzlich noch überlegt werden, nach welchen Kriterien die Dateien dann zum Löschen ausgewählt werden.
Redundanz macht wiederholen unnötig.
quod erat expectandum

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

Re: Hashfunktion

Beitrag von Xin » Di Mai 18, 2010 2:25 pm

cloidnerux hat geschrieben:Dann muss zusätzlich noch überlegt werden, nach welchen Kriterien die Dateien dann zum Löschen ausgewählt werden.
Vorschau => Pfad angabe => User sagt, welches gelöscht wird oder springt zum nächsten. Idealerweise sollten solche Duplikate gemerkt werden, die der User nicht löschen will (Backups z.B.) und entsprechend sollte er dann auch nicht mehr genervt werden.
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.

Antworten