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 (siehe Diskussionsseite) ) 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 grep(1):

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

-f FILE, --file=FILE
  Obtain  patterns  from  FILE, one per line.  The empty file contains 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 Hardlinks oder Symlinks erzeugt werden.