Finden von Dateiduplikaten

[Uwke1337]

Hall ocih habe eine Aufgabe bekommen, verstehe diese aber leider nic. Ichb in neu in Sachen Programmierung und woltle Fragen ob jemand vielleicht eine Lösung bzw. einen Lösungsansatz parat hat.

Hier die Aufgabe.

Finden von Dateiduplikaten

Problembeschreibung

In einem vorzugebenden Verzeichnis sollen alle Dateiduplikate gefunden werden. Die Suche nach identischen Dateien soll dabei möglichst optimal ablaufen. Bei der Analyse lassen sich über eine entsprechende Option folgenden vorgeben:

• Zu ignorierende Unterverzeichnisse

• Zu ignorierende Dateitypen

• Zu ignorierende Dateien anhand eines vorzugebenden Anteils am Dateinamen

Beachten Sie, dass Dateien zwar identisch sein können, aber verschiedene Namen haben können!

Auszugeben ist:

• Name und Verzeichnis einer Datei

• Anzahl der Duplikate

• Name und Verzeichnis für jedes Duplikat

Wenn eine Datei als Duplikat einer anderen erkannt wurde, dann wird diese hier nicht ausgegeben.

Aufgaben:

Zerlegen Sie das Problem in Teilprobleme (mindestens 4)! Definieren Sie die Teilprobleme und legen Sie die Schnittstellen fest!

Lösen Sie die Teilprobleme und stellen Sie sie als Struktogramm, Programmablaufplan, Pseudocode oder echtem Sourcecode (mit Kommentaren) dar!

Denken Sie bei den gewählten oder entworfenen Algorithmen über Alternativen nach! Stellen Sie für einen Algorithmus diese Alternative dar und bewerten Sie diese!

Erläutern Sie den Begriff der Rekursion!

Wie lassen sich Dateien miteinander vergleichen! Erklären Sie ein mögliches Verfahren!

Stellen Sie die Gesamtlösung vor!

ich eien Antwort würde ich mich sehr freuen

mfg uwke

[Klotzkopp]

Was genau verstehst du denn an dieser Aufgabe nicht?

[Uwke1337]

ich verstehe nicht wie ich es umsetzen kann diese Aufgabe in z.B ein Strukturgramm zu bringen da ich wie gesagt sogut wie 0 ahnung vom Programmieren habe

Ich finde weder einen Ansatz noch weiß ich wie ich das Problem in Teilprobleme Zerlege und woher ich die Festzulegenden Schnittstellen bekomme.

[Klotzkopp]

ich verstehe nicht wie ich es umsetzen kann diese Aufgabe in z.B ein Strukturgramm zu bringen da ich wie gesagt sogut wie 0 ahnung vom Programmieren habe

Dann solltest du dir eine einfachere Aufgabe suchen. An dieser wirst du dir die Zähne ausbeißen.

[Uwke1337]

naja es ist ja ncih so das ich mir die Aufgabe ausgesucht habe ich habe sie von meinen Chef bekommen und soll sie dann Präsentieren deshalb wäre ein wenig hilef echt nett

[Klotzkopp]

naja es ist ja ncih so das ich mir die Aufgabe ausgesucht habe ich habe sie von meinen Chef bekommen

Kann es sein, dass das grundsätzliche Problem ist, dass dein dein Chef nicht weiß, dass du "sogut wie 0 ahnung vom Programmieren" hast?

Einem Anfänger sollte man so eine Aufgabe nämlich nicht geben.

Mit "ein wenig hilef" würdest du auch nicht weit kommen, wenn du bei dieser Aufgabe komplett ratlos bist.

[Uwke1337]

schade...

ok trotzdem danke!

[flashpixx]

Ich finde für einen Anfänger auch zu schwer, für mich hört es sich wie ein Übungszettel aus der Vorlesung Informatik an.

Ich gebe aber trotzdem einmal den Hinweis auf den Befehl "find" und "md5" unter Unix und folgendes Bsp Kommando: find . -name '*.java' -exec md5 \{\} \;

HTH Phil

[Jan Jansen]

Die Umsetzung der Aufgabe ist eventuell zu schwer, sich den grundsätzlichen Ablauf vorzustellen aber nicht.

Geh in deinen Dateimanager, mach ein Verzeichnis auf und versuch festzustellen ob es in dem Verzeichnis Duplikate gibt. Schreib zur Hilfe jeden deiner Schritte auf und versuch wenn möglich ähnliche Schritte in eine Gruppe zusammenzufassen.

Wenn du das gemacht hast, schreib die Schritte hier ins Forum, dann hilft dir sicher jemand weiter.

[flashpixx]

@Jan: Das ist eine gute Idee. Also erst einmal "händisch" den Ablauf durch zu führen. Also Dateimanager, Dateien anschauen usw. und evtl kann man dann das ganze in einzelne Struktogramme zerlegen

Phil

[AndiE]

Ich denke, im Prinzip ist das gar nicht so schwer. Ich würde einfach einen Zettel nehmen, und einen Datenflußplan zeichnen. Ein Kreis stellt die Festpaltte dar, ein Trapez die Tastatur, ein Dreieck den Bildschirm und ein Rechteck das Programm. Das wären die beteiligten Komponenten. Dann erfolgt "algorithmisches Denken", wie arbeiten die teile zusammen?

1. Daten von Tastatur einlesen

2. Dateinamen von Festplatte lesen

3. Duplikate suchen

4. Duplikate ausgeben.

Das sind vier Teile. Erste Aufgabe gelöst. Ohne Ahnung von Programmieren zu haben.

[speedi]

Dateien haben einen HashCode. Anhand dieses Hashs kannst du Dateien ziemlich performant vergleichen.

Zuerst legst du dir eine Liste an, in welcher du die Pfade und die dazugehörigen Hashes speichern kannst.

Nun startest du eine Schleife (for-Schleife, maximalwert = anzahl der Dateien im Verzeichnis).

In der Schleife überprüfst du ob der hash der Datei mit der Nummer (zähler) im Verzeichnis mit einem Hash in der Liste übereinstimmt. Wenn ja, gibst die Datei als doppelte Datei aus, wenn nicht fügst du die Datei mit Pfad und Hash in deine Liste.

Wenn du 100% sicher sein willst, dass die Dateien wirklich übereinstimmen und nicht nur zufällig den gleichen Hash haben kannst du die Dateien auch nochmal genau vergleichen indem du Byte für Byte einliest und vergleichst.

Das ganze noch in ein Struktogramm zu bringen sollte nicht das größte Problem sein. Soll das ganze auch am ende programmiert werden? Wenn ja in welcher Sprache?

HINWEIS:

Diese Lösung berücksichtigt keine Unterordner. Um Unterordner ebenfalls zu überprüfen müsste man das Problem rekursiv lösen.

Bearbeitet 14. Januar 2009 von speedi

[flashpixx]

Dateien haben einen HashCode. Anhand dieses Hashs kannst du Dateien ziemlich performant vergleichen.

Full Ack

Zuerst legst du dir eine Liste an, in welcher du die Pfade und die dazugehörigen Hashes speichern kannst.

Nun startest du eine Schleife (for-Schleife, maximalwert = anzahl der Dateien im Verzeichnis).

In der Schleife überprüfst du ob der hash der Datei mit der Nummer (zähler) im Verzeichnis mit einem Hash in der Liste übereinstimmt. Wenn ja, gibst die Datei als doppelte Datei aus, wenn nicht fügst du die Datei mit Pfad und Hash in deine Liste.

Überlege einmal was das für ein Algorithmus ist: Wenn ich n Dateien habe, muss ich für jedes n die Liste n-1 durchlaufen => O(n^2)

Ich würde hier zu der Struktur eine Hashmap (o.ä.) raten, bei der ich beim Einfügen direkt prüfe, ob ein identischer Hash schon vorliegt, wenn ja, ist die Datei mehrfach, wenn ein, den Hash inkl Pfad einfügen

Nach Erzeugung der Hashmap kann ich sie einfach, da ich mit Keys-Values erzeugt habe, direkt auslesen und die Dateien z.B. kopieren usw.

Ein Problem hat man allerdings beim Hashing, möchte man z.B. diese Art auf Bilder anwenden und auch Duplikate finden, die sich z.B. nur in de Bildgröße oder Qualität unterscheiden, dann wird das Hashing nicht funktionieren, da ich hier eine Bildanalyse durchführen muss. (Abgesehen von identischen Hashcodes für unterschiedliche Dateien)

Phil

[Jan Jansen]

Die Lösung über Hash-Werte ist nicht effizient und vor allem nicht pädagogisch. Wie einzelne Schritte (der Vergleich einer Datei) technisch gelöst werden ist für das Verständnis des Grundproblems erstmal unwichtig.

Mein 2. Hinweis wäre:

Prüfe ob man wirklich immer jede Datei mit jeder anderen vergleichen muss. Gibt es Konstellationen wo sehr viele Dateien in einem Verzeichnis sind, wo man am Ende aber keine der Dateien genauer prüfen (in irgendeiner Weise öffnen) muss?

[flashpixx]

Die Lösung über Hash-Werte ist nicht effizient und vor allem nicht pädagogisch.

Was wäre effizienter?

Prüfe ob man wirklich immer jede Datei mit jeder anderen vergleichen muss. Gibt es Konstellationen wo sehr viele Dateien in einem Verzeichnis sind, wo man am Ende aber keine der Dateien genauer prüfen (in irgendeiner Weise öffnen) muss?

Nach welchen Kriterien arbeitest Du. Dateinamen o.ä. sind sehr schlechte Kriterien.

Phil

[Jan Jansen]

Für die Lösung muss man etwas mit dem Dateimanager spielen. Mit der richtigen Einstellung kann man in vielen Fällen auf "einen Blick" sehen ob sich Duplikate im Verzeichnis befinden (Unterverzeichnisse läßt man erstmal weg)

[AndiE]

Ich sag mal:

Sind die Dateilängen verschieden, sind auch immer die Dateien verschieden. Ist die Dateilängen gleich muß die Datei durchlaufen werden. Sie müssen nicht gleich sein

[Kadauz]

Ich hätte jetzt aber auch einen Hash vorgeschlagen. Performant und simpel.

Ob das jetzt pädagogisch sinnvoll ist, darüber lässt sich streiten...

[Klotzkopp]

Die Verwendung eines Hash ist aus Performance-Sicht weder grundsätzlich gut noch grundsätzlich schlecht.

Um einen Hash überhaupt zu erstellen, müssen die Dateien komplett eingelesen werden. Das sollte also überhaupt nur dann erfolgen, wenn andere, schneller zu prüfende Kriterien (z.B. Dateigröße) eine mögliche Übereinstimmung ergeben.

Aber selbst dann ist ein Hash nicht unbedingt angebracht. Wenn man z.B. nur zwei Kandidaten für eine Übereinstimmung hat, ist es wesentlich effizienter, einfach nur beide Dateien einzulesen und beim ersten gefundenen Unterschied abzubrechen. Man darf auch nicht vergessen, dass ein gleicher Hash nicht automatisch bedeutet, dass der Dateiinhalt gleich ist. Wenn man also Hashes benutzt, und dabei Duplikate findet, muss man diese Dateien dann nochmal auf "konventionelle" Weise vergleichen.

Wenn man natürlich Hashinformationen bereits vorliegen hat, sei es aus dem Dateisystem oder aus der Datei selbst, sollte man diese auch benutzen. Aber auch hier muss man zuletzt immer noch Byte für Byte vergleichen.

[flashpixx]

Ich gehe davon aus, dass der Begriff "Hash" bekannt ist und impliziert das Kollisionen auftreten können.

@Klotzkopp: Es kommt sicherlich einmal auf die Datenmenge und das gewünschte Ergebnis an. Wenn ich z.B. nur die Daten des Dateisystems nehme (Dateigröße, zugeordnetes Programm, Datum usw), dann kann ich z.B. auch ein Clusterverfahren verwenden, um Blöcke zu bilden, so dass z.B. nur MP3s mit MP3s verglichen werden. Wenn man z.B. dann innerhalb des Clustern z.B. noch einmal nach identischer Dateigröße cluster, dann minimiere ich die möglichen Vergleiche. Ich denke an "Komplexität" kann man hier viel optimieren.

Es geht aber hier wohl um ein Anfängerproblem, so dass ein einfacher Hash sinnvoll abgelegt zu dem gewünschten Ergebnis führt

Phil

[Guybrush Threepwood]

Ich würde dafür auch keinen Hash nehmen weil der einfach keinen Vorteil bringt. Es sei denn der wäre aus irgendeinem Grund schon vorhanden, aber das alle "Dateien einen hash haben" wäre mir neu bzw. das man da einfach dran kommt.

Auch am Dateiende kann man es imho nicht unbedingt fest machen denn manchmal wird ja für Backups einfach ein .bak drangehangen oder so und dann hat man evtl. 2 Dateien die gleich sind aber unterschiedliche Endungen haben.

Letzten Endes kommt man um einen Zeichenweisen vergleich nicht drum herum wenn man zwei Dateien mit der gleichen Größe findet. Da aber wohl nur wichtig ist ob zwei Dateien unterschiedlich sind kann man den ja beim ersten Unterschied abbrechen.