File Duplicat Finder

Ser's !

Nein, aber ich find' die Aufgabe ganz reizvoll.
Im Prinzip trivial, aber wenn's effizient werden soll recht challenging.

Versuche daher atm sowas zu designen/implementieren, sollte morgen fertig werden. (command line only, win32)

Mfg, LB

Meinst du auch, dass es doppelte Files trotz völlig unterschiedlichem Dateinamen findet? Müsste eigentlich recht effektiv gehen indem man zuerst die Filesize vergleicht und dann den Inhalt. Problem seh ich da beim abspeichern von über 100000 filesizes, dürfte ein etwas großen RAM Bedarf haben ;-).
[edit]
wie immer, google und fertig?
http://noclone.net/
http://www.efsoftware.com/dm/e.htm
http://www.xtrimsoft.com/downloads/freeware.htm
[/edit]
mfg Oliver

Sind aber alle nicht wirklich Freeware. (höchstens free trial, und das ist dann auf 100 Files oder so beschränkt)
Schon gar ned opensource.

Effizenz-Problem ist dieses: (bei meinem Ansatz)
( Das ist eher grundsätzlich algorithmischer Natur, sonst würd ich's nicht beschreiben, denn bei der Umsetzung sind der Ineffizenz keine Grenzen gesetzt :>)

Zuerst bilde ich Äquivalenzklassen bezüglich Filesize.
Solche mit einem Element werden natürlich nicht weiter betrachtet.

Speicher ist hier kein Problem.
Für 1000000 Files -> 8 Byte * 10^5=0.8MB.
Tatsächlich muß natürlich auch der Filename+Pfad gespeichert werden, da gibts ein Limit von knapp unter 300 Bytes (das kommt vom Windows-Kernel)
Also worst case braucht Filesize+Filename ca 300 Bytes.
Das ergibt bei 10^5 Files ca 29MB Speicherbedarf.
Das ist zwar nicht wenig, aber auch kein großes Problem.
Tatsächlich brauch ich bei meiner HD, ca 300.0000 Files, 10MB Speicher dafür.

Das geht soweit ratz fatz

Aber dann ?

Innerhalb der Äquivalenzklassen echter Byte-for-Byte Vergleich.
Soweit ist das die selbe "Idee" die Zentor kurz beschrieben hat.

Jetzt kommt das Problem:
IMHO läßt sich's nicht vermeiden innerhalb einer Äquivlanezklasse bzgl Filesize "alle mit allen" zu vergleichen.
Hat eine Klasse n Elemente, n^2/2 Vergleiche.
Es kann natürlich innerhalb einer Äquivalnzklasse bzgl Filesize max n/2 neue Äquivelnzklassen bzgl Echter Identitent geben.
Also sein z.b 100 riesen Files a 1GB mit selber Filesize auf der HD, die tatächlich 50 Paare von identischen FIles sind.
Dann muß 5000*1GB geladen werden
Das dauert vermutlich eine halbe Ewigkeit.
Nichteinaml ansatzweise Chance die alle im RAM zu halten.

Auch wenn das eher unwahrscheinliche worst-case Szenarien sind, die große Frage ist halt ob's da Bessers gibt, das vorallem den quadratischen Aufwand vermeidet.

Falls da jemand schlaue Ideen hat -> feel free

wie wärs, wenn du für files innerhalb einer äquivalenzklasse bzgl Filesize die hashsumme berechnest und _diese_ fürs vergleichen heranziehst.

Danke

Die Idee hatte ich auch schon, und wieder verworfen.
Grund: Hashsummen sind so designed, daß jedes Bit, das unterschiedlich ist, die Hashsumme maximal verändern soll.
Das heißt aber auch, daß jedes Bit eingelesen werden muß.
Genauso wie beim simplen Byte vergleich.
Aber es kommt bei den Hashsummen noch ein wenig MEHR Rechenaufwand dazu.

[EDIT]
Letzlich hast recht, (eventuell doch eine gute Idee), es verringert ja das n, das quadratisch eingeht mit linearem Aufwand.
[/EDIT]

Zu bedenken ist, wenn Du auf Nummer sicher gehen willst, dann kommst Du um einen echten Byte-for-Byte Vergleich nicht herum. Mit einer Hash-Summe kannst Du zwar definitiv sagen, dass zwei Files unterschiedlich sind, nicht jedoch, dass sie tatsächlich übereinstimmen (dürfte in der Praxis aber eher weniger relevant sein).
Zur Effizienzsteigerung könntest Du ja so vorgehen, dass Du für große Files aus einer großen Äquivalenzklasse (also viele Dateien gleicher Größe) nur mal eine Hash-Summe für die ersten x Bytes bildest und dann miteinander vergleichst - wenn Du "Glück" hast, dann fällt vielleicht schon ein Teil weg - dann für den nächsten Block, ...

@LB .. ich bin deswegen auf Hashsums gekommen, da du dir dann "byte für byte"-vergleiche mit allen files untereinander ersparen würdest.

du könntest in dein programm noch eine option einbaun, die beim vergleichen nur dateien selben typs/endung untereinander vergleicht, wodurch der rechnenaufwand sicher beträchtlich sinken würde.

mas..

Zitat

Mit einer Hash-Summe kannst Du zwar definitiv sagen, dass zwei Files unterschiedlich sind, nicht jedoch, dass sie tatsächlich übereinstimmen (dürfte in der Praxis aber eher weniger relevant sein).

bedeutet das dann etwa bei passwörtern, die als hashsum gespeichert werden, dass es für eine hashsum mehrere zutreffende passwörter geben kann?
*grübel*

ich habe zwar keine Ahnung vom Thema, aber
1. eine Abwandlung von mas' idee wär einstellen zu können, ob zb nur jedes 2., 5., oder 10. byte verglichen werden soll.
2. kann das Programm ja bei den files, von denen es glaubt sie seien gleich erstens einen exakten vergleich machen, und zweitens den user fragen, ob er mit dem löschen des duplikates einverstanden ist.
Und sowieso müsste es die Frage stellen, weil man ja sagen muss, welche Datei (in welchem Ordner) gelöscht werden soll.

Zitat

1. eine Abwandlung von mas' idee wär einstellen zu können, ob zb nur jedes 2., 5., oder 10. byte verglichen werden soll.

das wäre gefährlich.. wenn man das macht, weiß man mit sicherheit nicht, ob die files wirklich identisch sind oder nicht.
das wäre so, wie wenn man ein fahndungsfoto aushängt, indem nur steht.. "gesuchter ist jeansträger, farbe blau". und sonst keine angaben.
um rechenzeit zu sparen (und trotzdem schnell zum erfolg zu kommen) sollte man den kreis der "verdächtigen" schon von anfang an so gut wie möglich eingrenzen.

@Wings: Ja, das bedeutet es für Passwörter

Ist ja auch klar, wenn sie kollisionsfrei wären, könnte man ALLE Daten beliebiger(!) Größe in eindeutigerweise auf die meist nur ein paar Bytes geringe Hashsum-Größe abbilden. (z.b 16 Bytes MD5, 4 Bytes CRC32)
Das kann grundsätzlich nicht gehen.
Bei kryptographischen Hashsums (z.b MD5) , ist es aber extrem schwer - by design - zwei msgs mit der selben hashsum zu berechen(!). Zufällige Kollision sollten möglichst unwahrscheinlich ein.
Defakto sicher ist es "eher schon" - Passwörter mit guten hashsum Algorithmen zu speichern. Kommt natürlich drauf an, wie sicher man es braucht.

Beispiel für eine "Attacke"

[EDIT]
da war wer schneller
[/EDIT]

Falls noch Bedarf besteht... basiert auf einer Art rekursivem Bucket-Sort mit ein paar Abkürzungen und schmutzigen Tricks. Kompiliert und läuft unter Linux auf x86, obs portabel ist weiß ich nicht.

Nur fürs Protokoll, das von mir oben genannte in 2s per Google gesuchte:
http://www.xtrimsoft.com/downloads/freeware.htm
erledigt alles was ihr hier geschrieben habt und ist Freeware...
mfg Oliver

jeuneS2
thx :thumb:

Dein Lösungsansatz interessiert mich natürlich ...
Aber aus dem Sourcecode schlau zu werden ist ein bissi challenging :shinner:

Funktioniert das etwa so ?

Eine Datei wird als eine einzige "Riesenzahl" (bzw Riesenschlüssel) angesehen, alle zu unterschuchenden Datein werden mit einem Radix-sort ähnlichem Ding sortiert ?
Dann einfach die mit Mehrfachvorkommen ausgeben.

Scheint jedenfalls eine clevere und effiziente Lösung zu sein :thumb:

Randbemerkung die vermutlich unter "feel free to improve" fällt: funktionierts auch mit files über 31/32 bit filesize ?

Mfg, LB

Zitat von Lord Binary

Dein Lösungsansatz interessiert mich natürlich ...
Aber aus dem Sourcecode schlau zu werden ist ein bissi challenging :shinner:

Funktioniert das etwa so ?

Eine Datei wird als eine einzige "Riesenzahl" (bzw Riesenschlüssel) angesehen, alle zu unterschuchenden Datein werden mit einem Radix-sort ähnlichem Ding sortiert ?
Dann einfach die mit Mehrfachvorkommen ausgeben.

Scheint jedenfalls eine clevere und effiziente Lösung zu sein :thumb:

Randbemerkung die vermutlich unter "feel free to improve" fällt: funktionierts auch mit files über 31/32 bit filesize ?

Mfg, LB

Alles anzeigen

Jo, der Sourcecode is halt so wie es sich in C gehört: jenseits jeder Lesbarkeit

So funktionierts: es wird von allen Dateien das erste Word eingelesen, mit dem als Index werden die Dateien in eine Tabelle eingetragen (->classify()). Indizes mit nur einer Datei werden gestrichen (->cleanup_table()) und die restlichen Indizes der Tabelle werden rekursiv weiter gelesen und in Tabellen einsortiert (->find_duplicates()). "EOF" hat einen eigenen Index in der Tabelle, wenn sich dort mehrere Einträge finden, hat man Duplikate gefunden.
Dazu kommen noch Optimierungen wie dass das ganze nicht rekursiv sondern iterativ passiert, wenn nur noch ein Index in einer Tabelle übrig ist, dass das Lesen der Dateien gepuffert erfolgt (->read_chunk(), ->add_file()) usw.

Ich hab oben eine neue Version angefügt, Dateigrößen über 4GB sollten jetzt funktionieren; die maximale Anzahl der Dateien die verglichen werden können liegt irgendwo unter 4 Millionen. Die neue Version ist außerdem merklich schneller und schafft den 2.6.10er Kernel-Sourcetree in ca. 1 1/2 Minuten, wobei die effektive Rechenzeit bei unter 3 Sekunden liegt.

Danke für die Erklärung, jetzt ist's (mir) vollständig klar

Theoretisch könnte man sogar die Rekursion völlig loswerden.
Natürlich nicht im Sinne von: jede Rekursion kann iterativ hingeschrieben/aufgelöst werden.
Stichwort:Forward Radix Sort with Groups (Seite 4).

Bringt aber vermutlich wenig bis gar nix.

Denn Disc-I/O ist hier das entscheidende Bottleneck.
Die wesentliche Optimierung ist daher, daß Indizes mit nur einem Eintrag nicht weiter verfolgt werden.
Die gibt's genauso bei dieser Variante. (und nicht mehr)
Ob die reine CPU Zeit jetzt 3 Sek oder 1.78 Sek ist, ist wohl schnurz.

Jedefalls dürfte Deine Lösung ziemlich optimal sein :thumb:

[EDIT]
btw: verglichen damit sind hashsummen-basierende Methoden dermassen mies, das es sich gar nicht lohnt, sie auch nur optional anzubieten.
Abgesehen davon, daß sie nicht 100% exakt sein können,
muß man jedes Bit jeder Datei einlesen.
[/EDIT]

Zitat von Lord Binary

Denn Disc-I/O ist hier das entscheidende Bottleneck.
Die wesentliche Optimierung ist daher, daß Indizes mit nur einem Eintrag nicht weiter verfolgt werden.
Die gibt's genauso bei dieser Variante. (und nicht mehr)
Ob die reine CPU Zeit jetzt 3 Sek oder 1.78 Sek ist, ist wohl schnurz.

Jedefalls dürfte Deine Lösung ziemlich optimal sein :thumb:

Dein Lob freut mich

Den Punkt der Performance muss ich allerdings ergänzen: die Optimierung des Tabellenzugriffs (mittels struct access_pair) ist nicht unerheblich, weil die Tabellen recht groß sind und sich eine normale lineare Suche deutlich bemerkbar macht (da hält dann sogar NFS vom Durchsatz locker mit). Zur I/O-Performance sein noch angemerkt, dass sich durch eine größere Anzahl gleichzeitig geöffneter Dateien auch noch einiges gewinnen ließe; da leider garantierterweise nur 16 Dateien (incl. stdio, stderr und stdin) gleichzeitig geöffnet sein können, hab ich die Sache aber nicht ausgereizt (Fehlermeldungen gibts auf meinem System erst ab ca. 1000 Dateien, theoretischerweise könnte es aber schon an der 17. scheitern).