Duplikate von MP3-Files finden - Tags unterschiedlich
Sebastian Kaps
Ich suche eine Möglichkeit, aus einer fünfstelligen Anzahl von MP3-Files
alle Duplikate zu entfernen. Dabei kann es vorkommen, dass zwei Files
zwar identisch sind, aber unterschiedliche Namen und auch
unterschiedliche ID3 Tags haben können. Im Prinzip bräuchte ich sowas
wie ein md5sum, das auf den Audio-Teil der Files beschränkt ist.
Kennt jemand sowas?
--
Ciao, Sebastian
Andreas Kohlbach
Ich bin nicht sicher, ob der Header immer die selbe Größe in einem MP3
hat, auch wenn die Infos darin verschieden sind. Wenn ja, müsste die
Dateilänge identisch sein, wenn nur die ID3 Informationen sich
unterscheiden. Dann kann man mit "ls -l" arbeiten.
--
Andreas
Warum Linux? http://www.getgnulinux.org/ (Englisch)
Hans-J. Ude
>Ich suche eine Möglichkeit, aus einer fünfstelligen Anzahl von MP3-Files
>alle Duplikate zu entfernen. Dabei kann es vorkommen, dass zwei Files
Vergiss es. Z.B. 90.000 ist fünfstellig. Die Anzahl der Vergleiche bei
n Elementen ist n*(n-1)/2. Das macht ca. (9*10^4)^2 ~ 40*10^8 ~
4.000.000.000 Vergleiche. Dafür auf der Festplatte rumrödeln wie
verrückt, zigtausende Zwischenergebnisse berechnen und
zwischenspeichern. Und die Berechnung eines Zwischenergebnisses ist
kein Pappenspiel denn jedes File ist einige MB groß. Mit den
Unwägbarkeiten die Andreas erwähnt hat und wahrscheinlich noch Weitere
dazu. Vergiss es einfach.
Meine 2 Ct,
Hajü
Heiko Nocon
>Ich bin nicht sicher, ob der Header immer die selbe Größe in einem MP3
>hat
Nein, hat er nicht. Der "Header" (ID3V2.x) ist ein sehr komplexes
Gebilde mit variabler Struktur und Größe. Mit einfachen Kommandos ist da
nix zu wollen, das Ding muß von Code geparsed werden, der versteht, was
er da liest.
Allerdings wird selbst so ein Code das Problem des OP wahrscheinlich
nicht. Üblich ist nämlich auch noch ein mehr oder weniger großer
"Leerbereich" zwischen ID3-Teil und dem MPEG-Teil. Aber auch das ist
noch nicht alles. Nach dem eigentlichen Audioteil kann auch wieder mehr
oder weniger viel "Luft" kommen und danach noch die ollen V1-Tags. Tja
und last, but not least, können innerhalb der eigentlichen MPEG-Daten
prinzipiell auch noch fast beliebige andere Daten liegen, jedenfalls
solange sie nicht das Bitmuster eines MPEG-Audio-Headers enthalten.
Weil das alles so ist, braucht man einen ziemlich komplexen Parser, um
erstmal die reinen Audiodaten eines MP3-Files treffsicher auszufiltern.
Aber selbst, wenn der OP sowas hat, ist sein Problem noch nicht gelöst.
Es können z.B. identische Stücke vorkommen, die sich nur im Pegel
unterscheiden. Oder Stücke, die nahezu identisch sind, bloß etwas mehr
"Pause" vor oder hinter dem eigentlichen Stück mitschleppen oder bei
denen einzelne MPEG-Pakete durch irgendwelche Datenfehler beim Kopieren
mal ungültig geworden sind.
Fazit: Die Aufgabe ist mit primitiven Vergleichen auf Dateiebene nicht
sinnvoll zu lösen. Dafür muß man Mustererkennung auf den Inhalt
anwenden.
Andreas Pflug
> Sebastian Kaps <s...@sauerland.de> schrieb:
>
>>Ich suche eine Möglichkeit, aus einer fünfstelligen Anzahl von MP3-Files
>>alle Duplikate zu entfernen. Dabei kann es vorkommen, dass zwei Files
>
> Vergiss es. Z.B. 90.000 ist fünfstellig. Die Anzahl der Vergleiche bei
> n Elementen ist n*(n-1)/2. Das macht ca. (9*10^4)^2 ~ 40*10^8 ~
> 4.000.000.000 Vergleiche.
So schlimm ist es auch wieder nicht. Schließlich gibt es z. B.
Suchdienste wie Google, und die müssen sich in ihren
gigantischen Datenbanken u. a. auch um
Dublikate kümmern... Mein Vorschlag wäre folgender:
1) Berechne von jeder Datei die md5sum,
z. B. in der Art
for i in *.mp3; do echo "`cat $i|md5sum`, $i">>md5sums.txt; done
2) Lese die md5sum-Strings in ein Hash ein (z. B. in Perl).
Wenn dabei ein Hash-Eintrag schon belegt ist,
kannst Du sicherheitshalber noch mal die beiden
Dateien binär vergleichen, ansonsten hast Du ein
Dublikat gefunden.
Das ganze skaliert linear mit der Anzahl der Dateien
und sollte selbst bei 90000 Dateien maximal eine
bis wenige Minuten dauern.
MfG
Andreas
Roland Damm
Heiko Nocon schrub:
> Fazit: Die Aufgabe ist mit primitiven Vergleichen auf
> Dateiebene nicht sinnvoll zu lösen. Dafür muß man
> Mustererkennung auf den Inhalt anwenden.
Wenn man das dann noch bei Video-Dateien machen wollte....
Allerdings sind mp3s ja normalerweise nicht vollkommen sinnlos
benannt. Vielleicht hilft es ja sozusagen einer manuellen
Auswahl einen automatischen Dateinamensvergleich
vorauszuschicken. Also aus allen Paaren von Dateinamen die
(...such...) Levenshtein-Distanz auszurechnen. Dann kann man dem
menschlichen Sortierer wenigstens ähnlich klingende Dateien
(deren Namen) anzeigen und er soll dann beurteilen, ob sie
doppelt sind.
Frage: Wie errechnet man aus diesem Unterschied der Dateinamen
(Levenshtein-Distanz) ein sonnvolles Maß für die Ähnlichkeit?
Wie ähnlich sind sich danach die Namen 'test' und 'e' ? Die
Datei 'e' hat ja wohl große Ähnlichkeit mit quasi jedem anderen
Dateinamen, irgendwie muss man die Namenslänge noch vernünftig
mitverrechnen... Und man müsste vor der Auswertung alle
Dateinamen um Leerzeichen erleichtern, also '-', ' ', '_', am
einfachsten alles rausschmeißen. Alle Großbuchstaben klein
machen. Dennoch bleiben sich die Namen 'The Beatles...'
und 'Beatles, The...' ziemlich unähnlich.
CU Rollo
Andreas Pflug
Habe gerade noch mal gelesen, dass die ID3-Tags unterschiedlich
sein können, dann funktioniert das natürlich so nicht...
MfG
Andreas
Henning Paul
> 1) Berechne von jeder Datei die md5sum,
> z. B. in der Art
> for i in *.mp3; do echo "`cat $i|md5sum`, $i">>md5sums.txt; done
Wenn die Tags ignoriert werden sollen, dann doch lieber
for i in *.mp3; do echo "`mpg123 -s $i|md5sum`, $i">>md5sums.txt; done
oder?
Gruß
Henning
P.S.: Abgesehen davon ein UUOC.
Robert Grimm
> 1) Berechne von jeder Datei die md5sum,
> z. B. in der Art
> for i in *.mp3; do echo "`cat $i|md5sum`, $i">>md5sums.txt; done
Wenn der ID3tag unterschiedlich ist, dürfte die md5sum ebenfalls
Unterschiedlich sein.
Musicbrainz erstellt doch "Fingerabdrücke" von Musikdateien?
Vielleicht könnte
http://musicbrainz.org/doc/FindDuplicateMusicFiles
helfen.
> MfG
> Andreas
Rob
--
Paranoia ist ein Zustand erhöhter Bewusstheit.
Die meisten Menschen werden stärker verfolgt, als
sie es sich in ihren kühnsten Albträumen ausmalen.
-- Claude Steiner
Daniel Seuthe
shntool. Das enthält shnhash, welches einen MD5-Hash aus den Samples
berechnet (macht flac übrigens auch so). shnhash kann aber nur mit
WAV und FLAC-Dateien umgehen. Du mußt also die MP3-Dateien vorher
temporär umwandelt (sox musik.mp3 musik.wav && shnhash musik.wav)
Daniel
--
http://seuthe.org
Andreas Pflug
> Wenn die Tags ignoriert werden sollen, dann doch lieber
> for i in *.mp3; do echo "`mpg123 -s $i|md5sum`, $i">>md5sums.txt; done
> oder?
Das mit den Tags ist mir ja dann auch noch aufgefallen.
Deine Lösung sieht sehr vielversprechend aus!
MfG
Andreas
Henning Paul
Fingerprinting wäre aber wohl doch besser wie auch schon von Robert
vorgeschlagen, mittels MusicBrainz http://musicbrainz.org/ zum
Beispiel. Deren Software ist zwar eigentlich dafür gedacht, den
Fingerprint mit deren Server abzugleichen um den Tag füllen zu können,
in diesem Fall reichte es ja aber auch, die Fingerprints nur zu
vergleichen.
Gruß
Henning
Bernd Mayer
Hallo,
um doppelte Dateien zu suchen und zu entfernen verwende ich fdupes und
dupseek.
http://premium.caribe.net/~adrian2/fdupes.html
http://en.wikipedia.org/wiki/Fdupes
http://www.beautylabs.net/software/dupseek.html
Unterschiedliche Dateinamen sind dafür kein Problem da die Programme mit
md5sum arbeiten. Bei unterschiedlichen ID3 Tags habe ich auf die
Schnelle keine Lösung parat. Möglicherweise könnte man mit dd den Header
der Dateien entfernen und darauf den Dateivergleich loslassen.
Bernd Mayer
Hans-J. Ude
>Andreas Pflug <andrea...@gmx.de> wrote:
>> 1) Berechne von jeder Datei die md5sum,
>> z. B. in der Art
>> for i in *.mp3; do echo "`cat $i|md5sum`, $i">>md5sums.txt; done
>
>Wenn der ID3tag unterschiedlich ist, dürfte die md5sum ebenfalls
>Unterschiedlich sein.
>
>Musicbrainz erstellt doch "Fingerabdrücke" von Musikdateien?
>Vielleicht könnte
>http://musicbrainz.org/doc/FindDuplicateMusicFiles
>helfen.
Da stehen ja ein paar interessante Ansätze auf der Seite. Vielleicht
war ich mit meiner ersten Schätzung doch etwas pessimistisch, es war
ja auch schon verdammt spät. Aber auch dort steht "It can take hours
to complete for large collections, ...". Der OP könnte ja wenn er eine
Lösung gefunden und getestet hat ja mal verkünden wie viele Files
genau und wie lange es gedauert hat.
Das Aufnehmen der Fingerprints steigt etwa linear mit der Datenmenge
und die Anzahl der Vergleiche quadratisch, so viel ist jedenfalls
sicher.
Hajü
Henning Paul
> Robert Grimm <sp...@robgri.de> schrieb:
>>Musicbrainz erstellt doch "Fingerabdrücke" von Musikdateien?
>>Vielleicht könnte
>>http://musicbrainz.org/doc/FindDuplicateMusicFiles
>>helfen.
>
> Da stehen ja ein paar interessante Ansätze auf der Seite. Vielleicht
> war ich mit meiner ersten Schätzung doch etwas pessimistisch, es war
> ja auch schon verdammt spät. Aber auch dort steht "It can take hours
> to complete for large collections, ...". Der OP könnte ja wenn er eine
> Lösung gefunden und getestet hat ja mal verkünden wie viele Files
> genau und wie lange es gedauert hat.
libmusicbrainz kennt
| int trm_GenerateSignature (trm_t o, char *data, int size)
| void trm_ConvertSigToASCII (trm_t o, char sig[17],
| char ascii_sig[37])
das braucht dann auch keine Verbindung zum MusicBrainz-Server. Daraus
sollte sich mit ein paar Zeilen C was zusammenstöpseln lassen.
Gruß
Henning
Florian Diesch
> Das Aufnehmen der Fingerprints steigt etwa linear mit der Datenmenge
> und die Anzahl der Vergleiche quadratisch, so viel ist jedenfalls
> sicher.
Mit einer Hashtable geht das Vergleichen linear.
Florian
--
<http://www.florian-diesch.de/>
-----------------------------------------------------------------------
** Hi! I'm a signature virus! Copy me into your signature, please! **
-----------------------------------------------------------------------
Juergen Ilse
Heiko Nocon <Heiko...@gmx.net> wrote:
> Andreas Kohlbach wrote:
>>Ich bin nicht sicher, ob der Header immer die selbe Größe in einem MP3
>>hat
> Nein, hat er nicht. Der "Header" (ID3V2.x) ist ein sehr komplexes
> Gebilde mit variabler Struktur und Größe. Mit einfachen Kommandos ist da
> nix zu wollen, das Ding muß von Code geparsed werden, der versteht, was
> er da liest.
Dann koennte es sich moeglicherweise anbieten, die Datei ins "raw" oder "wav"
Format zu wandeln (jedenfalls etwas, was keinen Platz fuer solche "Metainfor-
mationen bietet) und darueber einen Hash zu bilden. Man muss dann nur die
Hashwerte mit den zugehoerighen Namen der MP3-Datei vorhalten (in einer Datei
oder einer datenbank), um dann daraus die Eintraege mit identischem Hashwert
zu ermitteln (wenn die Datei mit dem selben Programm und den selben Aufruf-
optionen in das entsprechende Format gewandelt wurde, sollten die raw- oder
wav-Dateien genau dann uebereinstimmen, wenn die MP3-Dateien bis auf den
Header identisch waren ...). Die konvertierten Dateien koennte man ja auch
gleich nach der Berechnung des Hashes wieder entsorgen (um Plattenplatz zu
sparen ...
Allerdings lassen sich damit natuerlich keine Doubletten erkennen, die zwar
annaehernd gleich klingen aber eben doch nicht wirklich gleich sind (z.B. mit
unterschiedlicher Software gerippte MP3-Dateien des selben Titels).
[...]
> Weil das alles so ist, braucht man einen ziemlich komplexen Parser, um
> erstmal die reinen Audiodaten eines MP3-Files treffsicher auszufiltern.
Daher mein (vielleicht auf den ersten Blick etwas absurd klingender)
Vorschlag, die Dateien zwecks "Hashbildung" in ein "weniger variables
Format" zu konvertieren (wobei natuerlich peinlich genau darauf zu achten
waere, dass fuer die Konvertierung immer die selbe Software mit identischen
Aufrufoptionen verwendet wird) ...
> Es können z.B. identische Stücke vorkommen, die sich nur im Pegel
> unterscheiden. Oder Stücke, die nahezu identisch sind, bloß etwas mehr
> "Pause" vor oder hinter dem eigentlichen Stück mitschleppen oder bei
> denen einzelne MPEG-Pakete durch irgendwelche Datenfehler beim Kopieren
> mal ungültig geworden sind.
Die wird man prinzipiell nur mittels "anhoeren und fuer gleich befinden"
heraussuchen koennen, fuer eine "automatisierte Loesung" wuerde ich in
diesem Fall ziemlich schwarz sehen ...
Tschuess,
Juergen Ilse (jue...@usenet-verwaltung.de)
--
Ein Domainname (auch wenn er Teil einer Mailadresse ist) ist nur ein Name,
nicht mehr und nicht weniger ...
Florian Diesch
Hans-J. Ude
>Hans-J. Ude <ne...@s237965939.online.de> wrote:
>
>
>> Das Aufnehmen der Fingerprints steigt etwa linear mit der Datenmenge
>> und die Anzahl der Vergleiche quadratisch, so viel ist jedenfalls
>> sicher.
>
>Mit einer Hashtable geht das Vergleichen linear.
Um *ein* Element mit dem Rest zu vergleichen. Der OP will aber alle(n)
mit allen anderen(n-1) vergleichen. x = n*(n-1)/2 also quadratisch.
Der Faktor 1/2 kommt daher dass wenn ich A,B verglichen habe, dann
brauche ich nicht mehr B,A.
Hajü
Florian Diesch
> Florian Diesch <die...@spamfence.net> schrieb:
>
>>Hans-J. Ude <ne...@s237965939.online.de> wrote:
>>
>>
>>> Das Aufnehmen der Fingerprints steigt etwa linear mit der Datenmenge
>>> und die Anzahl der Vergleiche quadratisch, so viel ist jedenfalls
>>> sicher.
>>
>>Mit einer Hashtable geht das Vergleichen linear.
>
> Um *ein* Element mit dem Rest zu vergleichen. Der OP will aber alle(n)
> mit allen anderen(n-1) vergleichen. x = n*(n-1)/2 also quadratisch.
Er will Duplikate finden, dafür reicht es zu schauen, ob bereits ein
Eintrag für den jeweiligen Fingerprint vorhanden ist, was bei einer
Hashtabelle in O(1) geht.
Juergen Ilse
Normalerweiose wuerde man IMHO auch nicht die Dateien vergleichen, sondern
ueber die Dateien einen Hash bilden (z.B. MD5 oder SHA1) und dann die Hashes
vergleichen ... Dann faellt die Hash-Berechnung nur einmal an (was bei 90000
Dateien schon ein ziemlicher Aufwand sein koennte, aber irgendwo noch im
Bereich des machbaren bleibt) und dann 4000000000 Vergleiche von Hashwerten
verbleiben (was vermutlich nicht wesentlich mehr Aufwand ist als die vorherige
Brechnung der Hashwerte, eher deutlich weniger ...).
Da aber das "extrahieren der audio-daten aus MP3-Dateien" eher eine "unueb-
liche Aufgabe" darstellt, koennte man ggfs. auf die Konvertierung der Dateien
in ein anderes Dateiformat zwecks Hash-Bildung zurueckgreifen (siehe meinen
anderen Beitrag).
Andreas Pflug
>>Mit einer Hashtable geht das Vergleichen linear.
>
> Um *ein* Element mit dem Rest zu vergleichen. Der OP will aber alle(n)
> mit allen anderen(n-1) vergleichen. x = n*(n-1)/2 also quadratisch.
> Der Faktor 1/2 kommt daher dass wenn ich A,B verglichen habe, dann
> brauche ich nicht mehr B,A.
>
> Hajü
Nein, das geht trotzdem linear. In perl legt man z. B.
ein Hash an mit
my %H;
Dieses wird in etwa nach dem folgenden Verfahren mit
Einträgen befüllt.
if($H{$md5string}) { print "Dublette: $(filename) <--> $H{$md5string}\n"; }
$H{$md5string} = $filename;
($md5string und $filename wurden vorher z. B. aus der in anderen
Beiträgen erwähnten md5sum.txt - Datei herausextrahiert, das ganze
innerhalb einer Schleife über alle Zeilen dieser Datei)
Für jeden Wert in $md5string wird also zuerst geprüft,
ob bereits ein Hash-Eintrag existiert (und im Falle eines Falles
die Dublette gemeldet).
Andernfalls wird der Hash-Eintrag neu angelegt.
Der Vergleich über alle n*(n-1)/2 Paare entfällt, weil durch
die Hashfunktion der Vergleich jeweils auf die wenigen Elemente
reduziert wird, die denselben Hashwert haben.
Somit steigt der Aufwand annähernd linear mit der
Anzahl der Elemente.
MfG
Andreas
Hans-J. Ude
>Hans-J. Ude <ne...@s237965939.online.de> wrote:
>
>> Florian Diesch <die...@spamfence.net> schrieb:
>>
>>>Hans-J. Ude <ne...@s237965939.online.de> wrote:
>>>
>>>
>>>> Das Aufnehmen der Fingerprints steigt etwa linear mit der Datenmenge
>>>> und die Anzahl der Vergleiche quadratisch, so viel ist jedenfalls
>>>> sicher.
>>>
>>>Mit einer Hashtable geht das Vergleichen linear.
>>
>> Um *ein* Element mit dem Rest zu vergleichen. Der OP will aber alle(n)
>> mit allen anderen(n-1) vergleichen. x = n*(n-1)/2 also quadratisch.
>
>Er will Duplikate finden, dafür reicht es zu schauen, ob bereits ein
>Eintrag für den jeweiligen Fingerprint vorhanden ist, was bei einer
>Hashtabelle in O(1) geht.
Hmm... sollte ich mich wohl mal etwas mit beschäftigen. Ich bin eher
Techniker, diesen Datenbank Kram habe ich wo's geht immer vermieden.
Ich hab mal auf die Schnelle im Wiki nachgeschaut aber das brauchen
wir hier jetzt nicht zu vertiefen.
Gruß,
Hajü
Sebastian Kaps
> [...]
Danke erstmal für die bisherigen Antworten! Ich konnte sie erstmal nur
überfliegen, aber ein paar interessante Ansätze sind dabei.
Um das Problem mal ein wenig einzuschränken: Die Duplikate, die ich
finden will stammen mit hoher Wahrscheinlichkeit jeweils vom selben
Ursprungsfile ab. Es geht also nicht darum, z.B. Files mit verändertem
Pegel als Duplikat zu entlarven.
Ich habe etliche alte MP3s aus der Zeit als ID3 noch nicht so verbreitet
war, wo dann im Titel-Tag plötzlich sowas wie "Tracknummer - Artist -
Song" steht. Später wurden diese Files dann mit Hilfe diverser Tools
richtig getaggt, mit hoher Wahrscheinlichkeit umbenannt und anschließend
mit einem Cover versehen. Dabei sind wohl irgendwie einige Duplikate
entstanden, so dass nun das originale File und das "aufgeräumte" File
weiterhin existieren.
--
Ciao, Sebastian
Hans-J. Ude
>Danke erstmal für die bisherigen Antworten! Ich konnte sie erstmal nur
>überfliegen, aber ein paar interessante Ansätze sind dabei.
>Um das Problem mal ein wenig einzuschränken: Die Duplikate, die ich
>finden will stammen mit hoher Wahrscheinlichkeit jeweils vom selben
>Ursprungsfile ab. Es geht also nicht darum, z.B. Files mit verändertem
Du hast in deinem ersten Posting nur geschrieben 5-stellig. Wie viele
sind's denn so grob über'n Daumen, eher 10.000 oder eher 90.000?
Hajü
Heiko Nocon
>Um das Problem mal ein wenig einzuschränken: Die Duplikate, die ich
>finden will stammen mit hoher Wahrscheinlichkeit jeweils vom selben
>Ursprungsfile ab.
Unter diese Randbedingung ist es der von Jürgen Ilse bereits skizzierte
Ansatz der Richtige.
for each file in MP3-files do
-Konvertiere aktuelles File mit immer demselben Programm in eine
temporäre Datei im RAW-Format (also eigentlich ohne jedes Format)
-Bilde über das temporäre File einen Hash
-Merke dir den Hash der Tempdatei und den zugehörigen Dateinamen der
Quelle
-Lösche die temporäre Datei
end;
Sortiere Hashliste by Hash;
Scanne sortierte Liste, gib Dateinamen der Quellen bei Mehrfachvorkommen
aus;
Bernd Hohmann
>> Um *ein* Element mit dem Rest zu vergleichen. Der OP will aber alle(n)
>> mit allen anderen(n-1) vergleichen. x = n*(n-1)/2 also quadratisch.
>> Der Faktor 1/2 kommt daher dass wenn ich A,B verglichen habe, dann
>> brauche ich nicht mehr B,A.
[...]
> Dieses wird in etwa nach dem folgenden Verfahren mit
> Einträgen befüllt.
>
> if($H{$md5string}) { print "Dublette: $(filename) <--> $H{$md5string}\n"; }
> $H{$md5string} = $filename;
Tschuldigung dass ich mich da vorsichtig einmische:
1) Zwischendatei "MD5" + "Dateiname"
2) Sortieren nach Spalte 1
3) Datei durchlesen
4) Findet kein Gruppenwechsel in Spalte 1 statt hast Du eine Doublette
Aufwand: je nach Sorter. Quicksort: n*log(n) oder so.
Bernd
--
Well, there's egg and bacon; egg sausage and bacon; egg and
nos...@spamonly.de ; egg bacon and spam; egg bacon sausage
and kuc...@spamonly.net ; spam bacon sausage and spam;spam
egg spam spam bacon and nos...@nixwill.de ; spam sausage
Florian Diesch
> Florian Diesch <die...@spamfence.net> schrieb:
>
>>Hans-J. Ude <ne...@s237965939.online.de> wrote:
>>
>>> Florian Diesch <die...@spamfence.net> schrieb:
>>>
>>>>Hans-J. Ude <ne...@s237965939.online.de> wrote:
>>>>
>>>>
>>>>> Das Aufnehmen der Fingerprints steigt etwa linear mit der Datenmenge
>>>>> und die Anzahl der Vergleiche quadratisch, so viel ist jedenfalls
>>>>> sicher.
>>>>
>>>>Mit einer Hashtable geht das Vergleichen linear.
>>>
>>> Um *ein* Element mit dem Rest zu vergleichen. Der OP will aber alle(n)
>>> mit allen anderen(n-1) vergleichen. x = n*(n-1)/2 also quadratisch.
>>
>>Er will Duplikate finden, dafür reicht es zu schauen, ob bereits ein
>>Eintrag für den jeweiligen Fingerprint vorhanden ist, was bei einer
>>Hashtabelle in O(1) geht.
>
> Hmm... sollte ich mich wohl mal etwas mit beschäftigen. Ich bin eher
> Techniker, diesen Datenbank Kram habe ich wo's geht immer vermieden.
Damit werden üblicherweise die assoziativen Arrays in vielen
modernen Programmiersprachen implementiert.
Ohne Hashtable könnte man auch die Liste der Fingerprints sortieren
und dann der Reihe nach durchgehen - damit hat man immerhin n*log n
statt n^2, und es lässt sich in der Shell sehr einfach auch mit sort
und uniq machen.
Sebastian Kaps
> Allerdings sind mp3s ja normalerweise nicht vollkommen sinnlos
> benannt. Vielleicht hilft es ja sozusagen einer manuellen
Teilweise leider doch. Zumindest wenn man Track01.mp3 nicht als
hinreichend sinnvoll betrachtet ;-)
--
Ciao, Sebastian
Sebastian Kaps
> Dann koennte es sich moeglicherweise anbieten, die Datei ins "raw" oder "wav"
> Format zu wandeln (jedenfalls etwas, was keinen Platz fuer solche "Metainfor-
> mationen bietet) und darueber einen Hash zu bilden.
Ja, so was ähnliches hatte ich auch schon gedacht. Evtl. einfach mpg123
(oder was man da aktuell nimmt) in md5sum reinpipen und jeweils den Pfad
zum Hash merken.
> Allerdings lassen sich damit natuerlich keine Doubletten erkennen, die zwar
> annaehernd gleich klingen aber eben doch nicht wirklich gleich sind (z.B. mit
> unterschiedlicher Software gerippte MP3-Dateien des selben Titels).
Solche Fälle schließe ich erstmal aus. Es geht in erster Linie nur um
Dateien, die sich nur im Namen und in den Tags unterscheiden.
--
Ciao, Sebastian
Sebastian Kaps
> Wenn die Tags ignoriert werden sollen, dann doch lieber
> for i in *.mp3; do echo "`mpg123 -s $i|md5sum`, $i">>md5sums.txt; done
> oder?
Das sieht gut aus. Ich werd's mal ausprobieren.
--
Ciao, Sebastian
Sebastian Kaps
> Vergiss es. Z.B. 90.000 ist fünfstellig.
Es geht um weniger als 20.000 Files. Einen Hashwert für jede Datei zu
speichern sollte kein Problem sein und die entsprechenden Daten dürften
ins RAM passen. Die 200 Mio Vergleiche sollten dann relativ schnell zu
machen sein.
--
Ciao, Sebastian
Bernd Hohmann
>> Dann koennte es sich moeglicherweise anbieten, die Datei ins "raw" oder "wav"
>> Format zu wandeln (jedenfalls etwas, was keinen Platz fuer solche "Metainfor-
>> mationen bietet) und darueber einen Hash zu bilden.
>
> Ja, so was ähnliches hatte ich auch schon gedacht. Evtl. einfach mpg123
> (oder was man da aktuell nimmt) in md5sum reinpipen und jeweils den Pfad
> zum Hash merken.
Wäre eine Variante.
Wobei ich Anmerken möchte dass es manchen Konvertern ziemlich egal ist,
ob sie den MP3-Tag korrekt weggeschnippelt bekommen und im Zweifel vorne
und hinten abschneiden (da ist bei CD-Rips immer etwas Luft). Dann ist
MD5 fürn Hintern.
Probieren geht über Studieren, schreib uns mal wie das Abenteuer
ausgegangen ist.
Sebastian Kaps
> Fingerprinting wäre aber wohl doch besser wie auch schon von Robert
> vorgeschlagen, mittels MusicBrainz http://musicbrainz.org/ zum
> Beispiel.
Hm, ich bin mir nicht sicher. Gibt es davon eigentlich schon ein
Commandline-Tool für Linux? Das letzte Mal als ich mir das angesehen
habe, gab's da nur so ein komisches "Teil" für Windows...
Abgesehen davon dürfte so ein Fingerprint zu unscharf sein und auch
nur ähnliche Dateien als gleich betrachten. Zum identifizieren von
unbekannten Files mag das eine gute Lösung sein, aber imho nicht, um
Duplikate zu finden (zumindest sähe ich da keinen Vorteil zu md5sum,
wenn man die Header ignoriert).
--
Ciao, Sebastian
Sebastian Kaps
> shntool. Das enthält shnhash, welches einen MD5-Hash aus den Samples
> berechnet (macht flac übrigens auch so). shnhash kann aber nur mit
> WAV und FLAC-Dateien umgehen. Du mußt also die MP3-Dateien vorher
> temporär umwandelt (sox musik.mp3 musik.wav && shnhash musik.wav)
Das klingt auch vielversprechend, danke. Allerdings kann es wohl nicht
von stdin lesen, was ein Vorteil für mpg123 mit md5sum wäre. Dann würde
die ganze Platten-I/O wegfallen.
--
Ciao, Sebastian
Sebastian Kaps
> Du hast in deinem ersten Posting nur geschrieben 5-stellig. Wie viele
> sind's denn so grob über'n Daumen, eher 10.000 oder eher 90.000?
Weniger als 20.000. Also zu viele, um irgendwelchen Listen per Hand
durchzugehen aber noch berechenbar ;-)
--
Ciao, Sebastian
Sebastian Kaps
Das klingt von der Beschreibung genau nach dem was ich suche. Ich werd's
mal testen. Danke!
--
Ciao, Sebastian
Roland Damm
Juergen Ilse schrub:
Irgendwie geht es aber: Es gibt so einen Handy-Service, da kann
man anrufen, ein unbekanntes Musikstück einfach 40 Sekunden lang
ins Handy dudeln lassen und bekommt ein paar Sekunden später per
SMS Titel, Interpret und so mitgeteilt.
Aber trivial ist das sicher nicht...
CU Rollo
Juergen Schroeder
Sebastian Kaps <s...@sauerland.de> wrote:
> Um das Problem mal ein wenig einzuschränken: Die Duplikate, die ich
> finden will stammen mit hoher Wahrscheinlichkeit jeweils vom selben
> Ursprungsfile ab. Es geht also nicht darum, z.B. Files mit verändertem
> Pegel als Duplikat zu entlarven.
das vereinfacht die Sache doch.
> Ich habe etliche alte MP3s aus der Zeit als ID3 noch nicht so verbreitet
> war, wo dann im Titel-Tag plötzlich sowas wie "Tracknummer - Artist -
> Song" steht. Später wurden diese Files dann mit Hilfe diverser Tools
> richtig getaggt, mit hoher Wahrscheinlichkeit umbenannt und anschließend
> mit einem Cover versehen. Dabei sind wohl irgendwie einige Duplikate
Wenn man mittels script die Tags ID3V2 in V1 wandelt und die V2 wegschmeisst
braucht man nur die Dateilängen anzusehen.
(Ich hätte zur Not ein Perl-Script dazu. Mein alter Wohnzimmer-MP3-PC mit
LCD-dev hat ein altes gepatchtes mpg123 was nur die ID3V1 im Display
anzeigt, daher verwende ich auch nur V1.)
Jürgen
Sebastian Kaps
> Wenn man mittels script die Tags ID3V2 in V1 wandelt und die V2 wegschmeisst
> braucht man nur die Dateilängen anzusehen.
Hehe, ok. Aber ich wollte nur Duplikate finden und nicht die gesamte
Sammlung schrotten ;-)
--
Ciao, Sebastian
Daniel Seuthe
Na ja, so temporäres Zeug landet bei mir immer in /tmp und das ist ein
extra tmpfs-Dateisystem. Notwendige Plattenaktivitäten halten sich
damit in Grenzen.
Aber ansonsten funktioniert die Variante mit mpg123 und md5sum auch gut. Es
erzeugt auch den gleichen Hash-Wert wie shnhash.
Daniel
--
http://seuthe.org
Torben Keil
> [...]
> > Im Prinzip bräuchte ich sowas
> wie ein md5sum, das auf den Audio-Teil der Files beschränkt ist.
> Kennt jemand sowas?
Du hast Glück, daß Du in einer Linux-Group gefragt hast. Hier ein recht
schnell arbeitender Lösungsansatz von mir:
list=`find /home/torben/musik/free/ -name "*mp3"`; i=0; for name in $list;
do fileList[$i]=`dd bs=512 skip=2 count=16 if=$name 2>/dev/null | md5sum`;
fileList[$i]="`echo ${fileList[$i]} | cut -b-32`:${name}"; i=`expr $i + 1`;
done; list2nd=`for a in \`seq 1 1 $i\`; do echo ${fileList[$a]} | sort;
done`; chsum="00"; for a in `seq 1 1 $i`; do chsumNew=`echo $list2nd |
cut -d " " -f $a | cut -b-32`; if [ "$chsum" != "$chsumNew" ]; then
chsum="$chsumNew"; else echo $list2nd | cut -d " " -f $a; fi; done
Aber Achtung: Diese Routine springt bei Leerzeichen im Dateinamen im
Vieleck. Vielleicht hat da ja jemand eine bessere Lösung als ich.
Ansonsten zur Funktion dieses Einzeilers:
Ich gehe davon aus, daß ich nicht die gesamte MP3-Datei lesen muss, um sie
von einer anderen unterscheiden zu können. Also überspringe ich mit skip
die ersten 4x512 Bytes um dann auch nur 8k zu lesen. Davon lasse mich mir
via md5sum eine Checksumme errechnen und in einer Liste speichern.
Wenn alle Files in der Liste vorhanden sind, dann lasse ich sie mir via sort
sortieren. Später brauche ich nur noch nachzuschauen, ob in der Liste die
identische Checksummen vorkommen und die nachfolgenden identischen
Checksummen samt Dateinamen ausgeben.
Viel Spaß beim Ausprobieren,
Gruß Torben
Torben Keil
Der Skip-Wert ist zu niedrig: Ändere den Skip-Wert von 2 auf 11.
Dann funktioniert diese Routine nur noch mit Dateien von mindestens
13.5kBytes Größe.
Gruß,
Torben
Hier der neue Einzeiler:
list=`find /home/torben/musik/musicals/ -name "*mp3"`; i=0; for name in
$list; do fileList[$i]=`dd bs=512 skip=10 count=16 if=$name 2>/dev/null |
René van Bevern
Hallo Torben,
> Ansonsten zur Funktion dieses Einzeilers:
> Ich gehe davon aus, daß ich nicht die gesamte MP3-Datei lesen muss, um sie
> von einer anderen unterscheiden zu können. Also überspringe ich mit skip
> die ersten 4x512 Bytes um dann auch nur 8k zu lesen.
Das versagt aber, wenn die MP3-Dateien Header mit unterschiedlicher
Länge haben, was afaik bei ID3v2 durchaus der Fall sein kann. Also
eins.mp3: headerheader|xxxxxxx
zwei.mp3: headhead|xxxxxxx
René
Torben Keil
> [...]
> Das versagt aber, wenn die MP3-Dateien Header mit unterschiedlicher
> Länge haben, was afaik bei ID3v2 durchaus der Fall sein kann. Also
>
> eins.mp3: headerheader|xxxxxxx
> zwei.mp3: headhead|xxxxxxx
Okay, hier mein verbessertes Skript. Im Gegensatz zu dem vorherigen
geposteten Skript, lese ich einfach nur das erste MB ein und pipe es durch
mpg123, welches mir die Audiodaten als RAW ausgeben soll (=> verwirft
einfach die Header :). Diese RAW-Daten werden wiederum mit md5sum zu einer
Checksumme verarbeitet. Der Rest des Skriptes arbeitet wie vorher auch
schon beschrieben.
list=`find /home/torben/musik/free/ -name "*mp3"`; i=0; for name in $list;
do fileList[$i]=`dd bs=512 count=20 if=$name 2>/dev/null | mpg123 -s -
md5sum`;
fileList[$i]="`echo ${fileList[$i]} | cut -b-32`:${name}"; i=`expr $i + 1`;
done; list2nd=`for a in \`seq 1 1 $i\`; do echo ${fileList[$a]} | sort;
done`; chsum="00"; for a in `seq 1 1 $i`; do chsumNew=`echo $list2nd |
cut -d " " -f $a | cut -b-32`; if [ "$chsum" != "$chsumNew" ]; then
chsum="$chsumNew"; else echo $list2nd | cut -d " " -f $a; fi; done
> René
Gruß,
Torben
Florian Diesch
Spricht eigentlich irgendwas dagegen, sowas ordentlich zu formatieren?
Oder es so zu schreiben, dass es auch mit Leerzeichen in Dateinamen
funktioniert?
Sieghard Schicktanz
Du schriebst am Mon, 16 Feb 2009 15:55:15 +0100:
> > 1`; done; list2nd=`for a in \`seq 1 1 $i\`; do echo ${fileList[$a]} |
> > sort; done`; chsum="00"; for a in `seq 1 1 $i`; do chsumNew=`echo
...
> Spricht eigentlich irgendwas dagegen, sowas ordentlich zu formatieren?
> Oder es so zu schreiben, dass es auch mit Leerzeichen in Dateinamen
> funktioniert?
Die dafür aufzuwendende Mühe vielleicht, etwas ansehnlich und für
Randerscheinungen funktionsfähig zu machen, das im eigentlichen Kern seiner
Funktion prinzipiell nicht gehen kann?
--
(Weitergabe von Adressdaten, Telefonnummern u.ä. ohne Zustimmung
nicht gestattet, ebenso Zusendung von Werbung oder ähnlichem)
-----------------------------------------------------------
Mit freundlichen Grüßen, S. Schicktanz
-----------------------------------------------------------
Florian Diesch
> Hallo Florian,
>
> Du schriebst am Mon, 16 Feb 2009 15:55:15 +0100:
>
>> > 1`; done; list2nd=`for a in \`seq 1 1 $i\`; do echo ${fileList[$a]} |
>> > sort; done`; chsum="00"; for a in `seq 1 1 $i`; do chsumNew=`echo
> ...
>> Spricht eigentlich irgendwas dagegen, sowas ordentlich zu formatieren?
>> Oder es so zu schreiben, dass es auch mit Leerzeichen in Dateinamen
>> funktioniert?
>
> Die dafür aufzuwendende Mühe vielleicht, etwas ansehnlich und für
> Randerscheinungen funktionsfähig zu machen, das im eigentlichen Kern seiner
> Funktion prinzipiell nicht gehen kann?
Wenn man schon eine Idee hat, kann man die doch auch halbwegs
brauchbar präsentieren.
Michael Müller
> Florian Diesch schrieb:
>
>> http://www.w140.com/audio/
>
> Das klingt von der Beschreibung genau nach dem was ich suche. Ich werd's
> mal testen. Danke!
Ich hab das jetzt mal auf meine Sammlung losgelassen.
Erste Tests waren ganz nett; da hatte ich von einer Band einige Alben
und ein paar Duplikate (aus anderer Quelle) in einen Ordner geworfen und
fdmf drauf losgelassen. Hat soweit auch halbwegs funktioniert.
Der ganze Spaß auf meiner gesamten Sammlung bringt dann allerdings
primär "Fehlalarme".
Michael
Florian Diesch
Gut zu wissen, ich hatte es bisher nur für einzelne Interpreten
benutzt, und da hat es brauchbar funktioniert.
Florian
--
<http://www.florian-diesch.de/>
Sebastian Biallas
> Irgendwie geht es aber: Es gibt so einen Handy-Service, da kann
> man anrufen, ein unbekanntes Musikstück einfach 40 Sekunden lang
> ins Handy dudeln lassen und bekommt ein paar Sekunden später per
> SMS Titel, Interpret und so mitgeteilt.
Musicbrainz kann einen Fingerabdruck erstellen.
--
Gruß,
Sebastian
Manuel Reimer
> Dann koennte es sich moeglicherweise anbieten, die Datei ins "raw" oder
> "wav" Format zu wandeln (jedenfalls etwas, was keinen Platz fuer solche
Schneller wäre es, wenn man den Meta-Informations-Kram einfach wegfallen
lässt. Ich habe mich zwar länger nicht mit MP3 befasst, aber ich soweit
ich mich erinnere, war der ID3-Kram ziemlich leicht zu finden, zu
parsen, und somit auch zu entfernen.
Das bereinigte MP3 dann zum Bilden der MD5-Summe nehmen.
Ich würde das in Perl umsetzen. Mit einem Hash-Array. Hash-Index ist die
MD5-Checksumme und Hash-Werte sind dann entsprechend die Pfade. So kann
das Script bei jedem neu errechneten MD5-Wert gleich feststellen, ob
schon eine Datei mit diesem Wert im Array vorhanden ist, und diese
entweder irgendwie loggen oder gleich das Duplikat löschen.
Das wird aber nur bei *echten* Duplikaten funktionieren! Wird das
gleiche MP3 zum Beispiel in verschiedenen Bitraten erstellt, dann ist
das kein Duplikat mehr! Das Problem hat man aber auch, wenn man vorher
nach WAV oder RAW geht.
CU
Manuel
--
www.jetzt-abwaehlen.de Wählen gehen 2009! Ein Aufruf etwas zu ändern.
Der Mensch erfand Maschinen, um sich damit die Arbeit zu erleichtern.
Nur leider hat er vergessen, rechtzeitig damit aufzuhören...
Beiträge mit *X-No-Html Header* kann ich weder lesen, noch beantworten!