How does Shazam work?
Shazam is a cool app for the iPhone which identifies songs based on analyzing a 10 second snippet you record when you hear the song playing. It can find old or obscure songs and deal with noise, like when you are in a crowded restaurant and want to see what they are playing in the background. Gizmodo has a write up of how the app works and it basically creates a spectrogram of the song and then does a hash table lookup of the first few points to try and find a match. Check it out.
