Hashfunktion

[Dirty Oerti]

Gleichzeitig sollte diese "Ignorierte Duplikateliste" einfach zu erreichen und leicht sortierbar sein (z.B. nach Suchdatum o.ä.)

[cloidnerux]

Um die DIskussion wieder zu sinnvolle Züge zu geben:
Algorithmen
Wir haben einmal einen noch unbekannten Hashalgorithmus, der die direkte Ähnlichkeit zweier Dateinen ermittelt, der aber NICHT die Komplette Datei auslesen sollte um den Hash zu bilden(Performance), Dateinamen nicht mit einbezieht und eindeutig ist(keine/wenige Kollisionen).
Dann haben wir eine Bild-Analyse Funktion, die es ermöglichen soll, BIlder mit gleichem Inhalt zu finden.
Implementation
Diese sollte man dann auch evt als gesonderte Feature behandeln, und z.B in einem Unterpunkt im Programm aufführen.
Dann haben wir noch die gewichtete Auflistung der Duplikate und ähnlichen Bilder, die sich merkt, welche Pfade und Dateien nicht als Duplikat angezeigt werden sollen, aber die Liste muss auch erreichbar sein um sie zu verändern.
Diese Auflistung sollte auch andere Faktoren mit einbeziehen, z.B Erstellungsdatum, Datum der Letzten Veränderung, Dateinmae, Endung, Charachterristika des Pfades, z.B "home/user/Documents/file.ext" wird wohl eher nicht das Duplikat von "/home/user/.temp/file.ext" sein, sondern eher Umgekehrt. In diesem Zusammenhang wäre eine Automatische vorselektion gut, was z.B dne Nutzer bei vielen gefundenen Duplikaten Arbeit erleichtert.

[Dirty Oerti]

Wir haben einmal einen noch unbekannten Hashalgorithmus, der die direkte Ähnlichkeit zweier Dateinen ermittelt, der aber NICHT die Komplette Datei auslesen sollte um den Hash zu bilden(Performance), Dateinamen nicht mit einbezieht und eindeutig ist(keine/wenige Kollisionen).

Wenn wir nicht die gesamte Datei auslesen, dann werden Kollisionen natürlich wahrscheinlicher.
Aber du hast schon Recht, eine Videodatei mit 5 GB zu hashen würde wahrscheinlich einfach zu lange dauern, wenn sie komplett ausgelesen werden muss.

Im Endeffekt können wir das aber erst sehen, wenn wir uns einen Algorithmus gewählt haben. Denn wenn es dieser zulässt, Dateien entsprechend schnell zu hashen, dann sollten wir die Dateien auch KOMPLETT einlesen.

Eventuell lässt sich das ja auf einzelne (Programm)Threads auslagern. Das wir einen allgemeinen Hash-Thread haben, der bei Bedarf (Dateigröße übersteigt ein gewisses Maximum) Kindprozesse startet, die sich dann nur auf diese Dateien beschränken.

Ich denke unser Hashalgorithmus muss nicht "Kryptographietauglich" sein, sprich es ist nicht sonderlich wichtig, dass aus dem Hashwert nicht auf den Dateiinhalt rückgeschlossen werden kann.
Wichtig ist wohl vorallem die Eindeutigkeit und die Performance.
Ich schau mal, was es da schon so an Algorithmen gibt ...

Dann haben wir eine Bild-Analyse Funktion, die es ermöglichen soll, BIlder mit gleichem Inhalt zu finden.

Diese sollte man dann auch evt als gesonderte Feature behandeln, und z.B in einem Unterpunkt im Programm aufführen.

Die wir ja auf jeden Fall als getrenntes Feature zur Hashfunktion sehen sollten.

Dann ist es möglich Dateiduplikate (identische Dateien) und auch Duplikate zu finden, die von ihrer binären Speicherung her zwar nicht identisch sind, von ihrem Inhalt her für den Benutzer aber schon.

[cloidnerux]

Im Endeffekt können wir das aber erst sehen, wenn wir uns einen Algorithmus gewählt haben. Denn wenn es dieser zulässt, Dateien entsprechend schnell zu hashen, dann sollten wir die Dateien auch KOMPLETT einlesen.

Auch wenn wir das in Kindprozesse einbauen, musst du folgendes berücksichtigen:
Eine "normale" HDD hat einen Datendurchsatz beim Lesen von ca <180Mbit/s, eine gute SSD <300Mbit/s
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!!!
Ich will den Nutzer sehen, der gerne 27h auf seine Duplikatprüfung warten will^^

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. Ich habe bei meinem auf 1024px*768px genormten Bildern keine mit doppelten Dateigrößen gefunden.

[Dirty Oerti]

bei 220GB ca 27h!!!

Ok, das ist zu lange.
Diesen Wert auf ca 1-2 Stunden zu drücken wäre, wie ich finde angemessen.

Über die Dateigröße ist es möglich, relativ sicher Hashs zu bilden die kollisionsfrei sein. Solange wir eben nicht kryptographische Hashs brauchen. Brauchen wir ja aber nicht, also sollte das ok sein.
Kleinere Dateien würde ich aber dennoch komplett hashen lassen, einfach um die Gefahr einer zufälligen Übereinstimmung der Teile der Datei, die gelesen werden zu vermeiden.
Bei größeren Dateien (ab ca 1 MB .. ? ) können wir ja dann Anfang, Ende und ein paar Zwischenpositionen hashen.
Wichtig ist halt nur, dass die Dateigröße entscheidend mit einfließt.

[cloidnerux]

Über die Dateigröße ist es möglich, relativ sicher Hashs zu bilden die kollisionsfrei sein. Solange wir eben nicht kryptographische Hashs brauchen. Brauchen wir ja aber nicht, also sollte das ok sein.
Kleinere Dateien würde ich aber dennoch komplett hashen lassen, einfach um die Gefahr einer zufälligen Übereinstimmung der Teile der Datei, die gelesen werden zu vermeiden.
Bei größeren Dateien (ab ca 1 MB .. ? ) können wir ja dann Anfang, Ende und ein paar Zwischenpositionen hashen.
Wichtig ist halt nur, dass die Dateigröße entscheidend mit einfließt.

Sehe ich auch so. Das größte Problem sind nämlich die kleinen Dateien. Bei einigen Bytes bis einigen kilobytes ist die Gefahr von Ähnlichkeit sehr hoch, da soclhe Dateien meistens als logs von Programmens, gespeicherte States oder Versionen von Mikrocontroller programmen seinen könnten
Hier wäre eine vollständiges Hashing sinnvoll und auch schnell möglich, nur muss hier auch wieder auf zusätzliche Parameter geachtet werden(Pfade, Namen, z.B Enumerationen) damit man nichts Essentiell löscht. Hier sollten wir in der Betaphase mal etwas Testen, nach welchen Kriterien, sich solche Dateien sicher ausschließen lassen.

[Dirty Oerti]

Sehe ich auch so. Das größte Problem sind nämlich die kleinen Dateien. Bei einigen Bytes bis einigen kilobytes ist die Gefahr von Ähnlichkeit sehr hoch, da soclhe Dateien meistens als logs von Programmens, gespeicherte States oder Versionen von Mikrocontroller programmen seinen könnten

Jup. Man denke nur an Readme Dateien oder sogar Lizenz Dateien, wobei letztere sich meist nur durch eine Zeile unterscheiden...

Worum wir uns auch Gedanken machen müssen ist folgendes:

Das Auffinden von Dateien aufgrund des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt

[cloidnerux]

Worum wir uns auch Gedanken machen müssen ist folgendes:

Das Auffinden von Dateien aufgrund des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt

Wer ist Patentinhaber? Und wie regeln das andere Duplikat-Finder Programme?

[Xin]

Worum wir uns auch Gedanken machen müssen ist folgendes:

Das Auffinden von Dateien aufgrund des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt

*lach*... das ist ja mal wieder typisch... Patente für Standardverfahren zu verteilen zeigt, dass die Leute keinen Plan haben.

Erstmal egal, aber ich werde mich darum kümmern müssen. Notfalls mal eine Rechtsanwalt aufsuchen. Notfalls darf ich nicht mehr in die USA einreisen, wenn ich nicht auf den elektrischen Stuhl will ;->

[Dirty Oerti]

Das steht ja erstmal nur auf Wikipedia. Ohne Quelle und nichts.
Ich mach mich da also mal auf die Suche ^^
US-Patente sind ja normalerweise online durchsuchbar ...