How Shazam works: audio fingerprinting

Hold up a phone in a noisy café, and a few seconds later it names the song playing: one of millions, from a recording made through a small microphone, with people talking over it. Shazam launched in the UK in 2002 (you dialled a number and held your phone up to the music, and got the answer by text message), and its method was published the next year by Avery Wang, one of its founders. It’s surprisingly simple, and surprisingly hard to fool. This page builds it, step by step, and then lets it listen.

There’s no copyrighted music here: the library is the site’s own, made by other pages (the trackers page’s tune, the SID page’s, some phrases on the synth page’s synth, the guitar, and a spoken sentence), and you can add your own.

It leans on:

The Fourier transform, and the spectrogram from wavelets: the frequencies in each short stretch of sound.
Finding signals below the noise, for correlation: comparing a signal with a pattern.

1 · Why not compare the sound itself?

The obvious way to find a recording in a library is to compare it with every song: slide it along each one, sample by sample, and see where it lines up, as the finding-signals page does with a known pulse. Two things go wrong.

It’s slow. Everything on this page works at 8,000 samples a second, so a 5-second recording is 40,000 samples. Sliding it along a 3-minute song means trying 1.44 million positions, each 40,000 multiplications: 58 billion for one song, and a library has millions.

And it’s fragile. A waveform’s exact shape depends on everything: the phases of its harmonics, the room, the speaker, the microphone. A recording can sound just like the song and look nothing like it.

30 ms of the trackers page’s tune (grey), and the same moment recorded (blue). Their correlation is 1 when they’re identical and near 0 when they have nothing in common. Through a phone’s small speaker, which takes away the bass and the top, it falls to −0.09: no better than an unrelated sound, though you’d recognise the song at once. With noise as loud as the music it’s 0.71; played 1% fast, −0.04.

What survives a small speaker, a noisy room and a cheap microphone? Not the waveform. It’s which frequencies are loudest, and when.

2 · The peaks that survive

A spectrogram shows a sound’s frequencies over time: cut the sound into short frames, overlapping, and take the Fourier transform of each. Here, frames are 64 ms long, one every 16 ms, and the frequencies run up to 4 kHz in steps of 15.6 Hz. The bright spots are the music’s loudest moments at particular frequencies: a note’s strong harmonics, a drum’s hit.

The method keeps only those peaks: points louder than everything near them, within a box about 250 Hz tall and 200 ms wide, and then only the strongest 30 or so in every second. The rest of the spectrogram is thrown away. That’s the trick. Noise and a small speaker change a great deal, but the loudest points mostly stay the loudest: noise fills in the quiet areas around them.

A recording’s spectrogram, 6 seconds of it, with its peaks (pink dots) and the clean song’s peaks (rings). With noise as loud as the music, through a phone’s speaker, 42% of the SID tune’s peaks are still found (within a frame and a frequency step). That doesn’t sound like many, but it’s enough, as the next sections show. Turn the noise down and watch the dots return to their rings.

3 · Constellations, and pairs of peaks

The peaks alone, without the spectrogram, look like stars in the sky, and Wang called them a constellation map. A song is its constellation. To find one in a library, the recording’s constellation has to be found inside one of the songs’.

A single peak isn’t much to search for: it’s one of 256 frequencies, and any song has thousands of peaks at each. So peaks are paired. Each peak is an anchor, paired with a few of the peaks that follow it in a target zone (from 16 to 640 ms later, and within 940 Hz). Each pair makes a hash: a number made from the anchor’s frequency, the other peak’s frequency, and the time between them. Here that’s 22 bits, a little over 4 million possible hashes, so a hash is far more specific than a peak. It also doesn’t depend on when the pair happens, only on its shape, so the same hash comes out wherever in the song the recording starts.

The peaks of 4 seconds of a synth arpeggio (from the synth page’s synth). Move the anchor: its target zone is shaded, and lines join it to the peaks it’s paired with (up to 6). Each pair’s hash is listed below. Across the library, there are about 29 peaks and 158 hashes a second.

The price of pairing: a hash survives only if both of its peaks do. If 42% of peaks survive, roughly one hash in six does. But there are so many of them that a few seconds still leaves plenty.

4 · Finding the song

Fingerprinting the library means working out every song’s hashes, and keeping an index: for each hash, the songs it occurs in, and where. A recording is fingerprinted the same way, and each of its hashes is looked up. That’s fast: one look-up per hash, however big the library is.

Most hashes match somewhere: in a big library, a 22-bit number turns up by chance in many songs. What gives the right song away is time. For each match, take the time of the hash in the song, minus its time in the recording: the offset. In the right song, every true match gives the same offset, where in the song the recording started. Chance matches give offsets all over the place. So for each song, count the matches at each offset, and the song’s score is the biggest count. Plotted with the recording’s time across and the song’s time up, the true matches make a straight diagonal line.

Choose a song and a stretch of it, then spoil it. Top: every hash from the recording that matched in the best-scoring song: the true matches line up (blue), the chance ones don’t (grey). Bottom: every song’s score. With 5-second recordings through a phone’s speaker (three from each song), the right song wins clearly every time with noise as loud as the music, and 18 times in 19 with the noise 5 dB louder than the music. With 10 seconds, it’s right every time even then.

When a song repeats itself (a chorus, or this library’s pieces, which mostly play twice), a recording matches in more than one place. It’s still the right song; only the offset is in doubt.

5 · Try it

Play something from the library (on this device’s speaker, or from the page on another device), and let it listen through the microphone for up to 8 seconds. You can add your own music to the library too: it stays in your browser.

The library, with a button to play each one, from a random point. Press Listen while it plays. The result is drawn as above: the matching hashes, and every song’s score. A clear winner has a score well above the rest; the page says it isn’t sure when the best is less than twice the next.

6 · What it can’t do

The hashes record exact frequencies and exact times. That’s what makes them so specific, and it’s also their limit. Play a recording a little faster, and every frequency goes up and every gap gets shorter, so the hashes change:

Recording sped up by	Found (5 s, through a phone’s speaker)
0.5%	19 times in 19
1%	17 in 19
2%	14 in 19
3%	5 in 19

So this method finds this recording of a song, not the song. A live performance, a cover, or someone humming the tune has different frequencies and timing, and doesn’t match. Recognising a hummed tune needs a different approach, matching the melody’s shape (up a bit, down a lot) rather than exact notes, and it’s much less precise.

Summary

Comparing waveforms fails: a small speaker or a cheap microphone changes the waveform completely while the song still sounds the same.
A spectrogram’s loudest peaks survive noise and filtering. Keeping only the strongest few dozen a second gives the song’s constellation map.
Pairs of peaks make hashes (two frequencies and a gap in time): specific enough to search for, and the same wherever in the song the recording starts.
An index finds every place each hash occurs. The right song is the one where many matches agree on one offset: a straight line of matches.
It finds a recording, not a song: speeding it up by a few percent, or playing it live, changes the hashes.