I recently replaced my old blackberry to an android phone.
One of the apps that i downloaded was "Shazam".
If you are not familiar with it, download it now, it's pretty cool.
What it does is very simple, it recognizes songs. So, just play a song on the radio and click on Shazam.
It will practically instantly detect the song playing on that radio.
It works so well, I've tried to think how the heck it works.
I came up with all sort of algorithms they might have used, Neural networks, Clustering algorithms, etc...
And then I came across this blog post:
How-shazam-works
Genius.
I thought that they had a AI that clustered and classified similar patterns.
But using a fingerprint algorithm is actually much much simpler and better.
A fingerprint algorithm doesn't look for "similar" patterns, it looks for an EXACT pattern.Think of it as a hash-table, naturally it's O(1) when looking for a key.
So if you can build an enormous hash-table that keys are the hash-code of the song's fingerprint, voila! you got a O(1) song recognition system.
Downside:
You cannot hum a song to it. Cause it can only recognize exact patterns.
You cannot find similar songs (songs that have a general similar beat or instruments playing), again cause it uses an exact search algorithm.
Still, it is pretty amazing when you use it.
