20

My large (120gb) music collection contains many duplicate songs, and I've been trying to fingerprint tracks in the hopes of detecting duplicates. And since I'm a CS Major I'm very curious as to what is done out there? Nothing I do has nearly the accuracy of something like Shazam or Lala.com. How do they "hash" tracks? I have run a standard MD5 hash on all my files (26,000 files) and I found hundreds of equal hashes on different tracks, so that doesn't work.

I'm more interested in Lala.com since they work with full files, unlike Shazam, but I'm assuming both use a similar technique. Can anyone explain how to generate unique identifiers for music?

Matthieu Brucher
  • 21,634
  • 7
  • 38
  • 62
Niels Joubert
  • 342
  • 3
  • 8
  • 5
    You found hundreds of MD5 collisions? I think some security researchers would be interested to hear about that. MD5 is considered insecure at this point, but you still have to try pretty hard to construct two files with the same hash but different content. – keegan Jan 11 '11 at 03:25
  • Someone once wrote a nice paper summarizing the algorithm of Shazam's patent[1], but Shazam's lawyers had them take it down. I'm not convinced that writing such a paper would be patent infringement, but it takes too much time and money to prove otherwise so away it went. Reportedly the patent itself is quite readable in comparison to many patents, which go out of their way to be obscure. [1]: https://www.techdirt.com/articles/20100708/04230710128.shtml – Mark Ransom Jul 28 '16 at 21:25

4 Answers4

11

The seminal paper on audio fingerprinting is the work by Haitsma and Kalker in 2002-03. For each frame of audio, it preprocesses (differences across time frames and frequency bands) and then stores a binarized version of the frame's spectrum.

This procedure adds robustness. If the entire signal is shifted in time, it still works (at least, one can derive a lower bound on performance degradation). It is pretty robust to environmental noise. Since its inception, there have been many papers on low-level music similarity, so there is no single answer.

Do you have absolutely identical files, i.e., the signals are time aligned, bit depth is the same, sampling rate is the same? Then I would think a hash like MD5 should work. But if any of those parameters are changed, so will the hashes. In such an event, a procedure like the one mentioned earlier would work better.

Take a look at the ISMIR proceedings available free online. Fun stuff. http://www.ismir.net/

Steve Tjoa
  • 59,122
  • 18
  • 90
  • 101
  • Steve - thanks, that's exactly what I was looking for. I'll read the Haitsma and Kalker paper. The ISMIR proceesings looks like an awesome source. Yes, in my case, I have duplicate songs but they are at different bitrates, or in some cases I have a partial song and another full track, etc. – Niels Joubert Jan 18 '10 at 17:54
5

There are a lot of algorithms for acoustic fingerprinting. Some of the more popular ones are:

  1. AMG LASSO
  2. AudioID
  3. LibFooID

In fact libfooId is opensource , so you can check out its code in google-code!!

Suraj Chandran
  • 24,433
  • 12
  • 63
  • 94
  • Those were good, although the wikipedia references and musicbrainz references gave good theoretical info which I appreciate very much too!! – Niels Joubert Jan 14 '10 at 06:45
  • Unfortunately it looks like LibFooID is pretty much dead, and consists of the leftovers of a research project. – Niels Joubert Jan 24 '10 at 01:42
3

Take a look at he Acoustic Fingerprint page on Wikipedia. It has references for some papers as well as links to implementations (including the open source fdmf).

ars
  • 120,335
  • 23
  • 147
  • 134
0

After some more research (although this is not conclusive at all!), I happened across the wiki at MusicBrainz.org which details some of the approaches they use:

http://musicbrainz.org/doc/Audio_Fingerprint

http://musicbrainz.org/doc/How_PUIDs_Work

Niels Joubert
  • 342
  • 3
  • 8