Bearbeiten von „Doubletten finden“

Ver größere Archive von z.B. Multimedia-Daten wie etwa Musik oder Fotos hat, kommt früher oder später an den Punkt, Doubletten finden zu müssen, die sich im Laufe der Zeit entwickelt haben. Gemeint sind hier Bit-identische Dateiinhalte unter verschiedenen Namen und/oder in verschiedenen Verzeichnissen.

== Ansatz ==
Das Tool [[md5]] bzw unter Linux [[md5sum]] kann aus einer Liste von angegebenen Dateien eine Ausgabeliste erzeugen, wo jede Datei mit ihrer md5-Summe dargestellt wird.

; Ausgabebeispiel von md5 -r:
 e3f7bb147a9810a8f1730c79ea776bb1 ./Musik/Interpret 1/Album 1/Interpret 1 - Titel 1.mp3
 a283f7ee42d067645bff9b090ad2db05 ./Musik/Interpret 1/Album 1/Interpret 1 - Titel 2.mp3
 e7cbc5c42bf1d6c0d0411a14d749acd7 ./Musik/Interpret 2/Album 1/Interpret 2 - Titel 1.mp3
 c03d58aa8f3679c52d8a7a6e9202156c ./Musik/Interpret 2/Album 1/Interpret 2 - Titel 2.mp3

Irgendwo auf der Platte liegen vielleicht noch Kopien herum, die schon sortiert wurden, aber von der (unsortierten) Quelle nicht entfernt wurden, z.B.

 e3f7bb147a9810a8f1730c79ea776bb1 ./Musik/unsortiert/Interpret_1%20-%20Titel_1.mp3
 c03d58aa8f3679c52d8a7a6e9202156c ./Musik/unsortiert/titel%202.mp3

Auf den ersten Blick könnte man aufgrund von Erfahrung und schnellem Erkennen von typischen Mustern erkennen, dass die erste und letzte Datei aus der Gesamtliste nochmal als Doublette in /unsortiert/ liegt, auch ohne die md5-Summen zu kennen. Das menschliche Gehirn ist aber nicht in der Lage, diese Erkennung auf einer sehr großen Liste von Dateien systematisch durchzuführen. Dazu sind Rechner besser geeignet. Allerdings ist es sehr schwer einen Algorithmus zu definieren, der anhand der Dateinamen eine solche Suche durchführt, denn dazu müsste man diesem Algorithmus menschliche (Un)Intelligenz zufügen. Computer mögen Zahlen und daher wird nicht anhand der Dateinamen verglichen, sondern anhand der Inhalte.

;Nachteil:
Der große Nachteil dieser Methode ist: man findet nur echte Kopien. Hat man beispielsweise einen Titel mit verschiedenen Bitraten vorliegen oder wurden in manchen Dateien irgendwelche Metainformationen verändert, so liegt keine bitidentische Kopie mehr vor und der Rechner kann es nicht erkennen.

;Exkurs:
Um dieses Problem systematisch zu lösen, müsste sich der Computer die Musik "anhören" und analysieren, wie deckungsgleich bestimmte Aufnahmen sind um dann mit einer Wahrscheinlichkeit angeben zu können, wie "identisch" die Aufnahmen sind. In der Realität würde man eine ganze Reihe von Parametern (Abspieldauer, Dynamik, Takt, Klangfarben und Frequenzspektren (Instrumente), ... ), definieren, die einzeln analysiert werden und die man dann zahlenmäßig auf Ähnlichkeit prüft. Mustererkennung.  Dies ist nicht Gegenstand dieses Artikels.

Analog dazu versucht man beispielsweise durch automatische Auswertung von Einzelbildern aus Videokameras einzelne Personen aus Menschenmengen zu identifizieren, etwa bekannte Hooligans im Fußballstadion oder Leute mit einem "Terroristen-Gesicht".

== Werkzeug benutzen ==
=== Liste erstellen ===
'''md5 -r''' unter BSD ({{FIXME|Parameter für md5sum  unter Linux}}) erzeugen die benötigte Liste, mit '''find''' listet man alle zu durchsuchenden Dateien.

 $ find /pfad/zur/Musik/ -name "*.mp3" -exec md5 -r {} \+ | sed -e 's, ,|,' > md5_alle.out

ergibt die Datei ''md5_alle.out'', die etwa so aussieht:
 e3f7bb147a9810a8f1730c79ea776bb1|/pfad/zur/Musik/unsortiert/Interpret_1%20-%20Titel_1.mp3
 c03d58aa8f3679c52d8a7a6e9202156c|/pfad/zur/Musik/unsortiert/titel%202.mp3
 e3f7bb147a9810a8f1730c79ea776bb1|/pfad/zur/Musik/Interpret 1/Album 1/Interpret 1 - Titel 1.mp3
 a283f7ee42d067645bff9b090ad2db05|/pfad/zur/Musik/Interpret 1/Album 1/Interpret 1 - Titel 2.mp3
 e7cbc5c42bf1d6c0d0411a14d749acd7|/pfad/zur/Musik/Interpret 2/Album 1/Interpret 2 - Titel 1.mp3
 c03d58aa8f3679c52d8a7a6e9202156c|/pfad/zur/Musik/Interpret 2/Album 1/Interpret 2 - Titel 2.mp3

=== Doubletten filtern ===
Das Gespann '''sort|uniq -d''' liefert eine einfache Liste aller doppelt vorkommenden Zeilen(!) aus dem Eingabestrom. 
Da wir uns aber nur für die doppelt vorkommenden md5-Summen interessieren, die jeweils am Zeilenanfang stehen, 
schneiden wir die gesamte Pfad/Dateiangabe (hinter |) ab, das macht '''cut'''.

 $ < md5_alle.out cut -f 1 -d "|" | sort | uniq -d > md5_dbl.out

Die Datei ''md5_dbl.out'' ergibt folgenden Inhalt:
 e3f7bb147a9810a8f1730c79ea776bb1
 c03d58aa8f3679c52d8a7a6e9202156c

Wie wir aus diesen Zahlen jetzt wieder die Pfade/Dateinamen erhalten und zwar alle Doubletten, zeigen wir Euch nach der nächsten Maus.

=== Doubletten auflisten ===
Aus der Liste ''md5_alle.out'', die ganz am Anfang generiert wurde und der Liste mit allen doppelt vorkommenden md5-Summen erzeugen wir eine menschenlesbare Liste mit allen Doppelt vorkommenden Dateinamen. Dabei hilft uns '''grep'''

 $ grep -F -f md5_dbl.out md5_alle.out | sort > md5_dbl_files.out

aus {{man|freebsd|1|grep}}:

       -F, --fixed-strings
              Interpret  PATTERN as a list of fixed strings, separated by new-
              lines, any of which is to be matched.

       -f FILE, --file=FILE
              Obtain  patterns  from  FILE, one per line.  The empty file con-
              tains zero patterns, and therefore matches nothing.

==== Performance ====
Mit -F geht es einfach nur sehr viel schneller, da die Suchstrings, die mittels -f zeilenweise eingelesen werden, nicht als [[Regular Expression]] interpretiert werden. Die Suche nach "fixed strings" ist deutlich schneller.

Angenommen man hat ein sehr umfangreiches Foto-Archiv mit z.B. 10.000 Bilddateien und findet 1.000 Doubletten, dann müssen hier 10.000.000 Vergleiche durchgeführt werden und da macht sich die Verwendung von -F deutlich bemerkbar.

==== Ausgabe ====
Obige Befehlsliste ergibt für unser kleines Beispiel folgenden Output:

 c03d58aa8f3679c52d8a7a6e9202156c|/pfad/zur/Musik/Interpret 2/Album 1/Interpret 2 - Titel 2.mp3
 c03d58aa8f3679c52d8a7a6e9202156c|/pfad/zur/Musik/unsortiert/titel%202.mp3
 e3f7bb147a9810a8f1730c79ea776bb1|/pfad/zur/Musik/Interpret 1/Album 1/Interpret 1 - Titel 1.mp3
 e3f7bb147a9810a8f1730c79ea776bb1|/pfad/zur/Musik/unsortiert/Interpret_1%20-%20Titel_1.mp3

==== Weitere Schritte ====
Anhand dieser Ausgabe kann man relativ schnell entscheiden, welche Dateien gelöscht werden können.
Falls es nur um Platzersparnis geht, die Dateien aber an beiden Orten verbleiben sollen, können ersatzweise auch [[Hardlink]]s oder [[Symlink]]s erzeugt werden.


[[Kategorie:Anwendungsbeispiel]]