Wie funktioniert Shazam?

Gelegentlich nutze ich Shazam und bin jedesmal erstaunt darüber, wie gut die App Musik erkennt. Egal, ob im Auto, auf der Straße oder sonst wo, fast egal, wie laut die Nebengeräusche sind, Shazam erkennt die Titel mit hoher Wahrscheinlichkeit. Eigentlich war mir egal, wie das genau passiert, doch ein Artikel auf „The Universe of Discourse“ hat mich dann doch neugierig gemacht.

Und nach nur wenigen Klicks lese ich Avery Li-Chun Wangs Artikel („An Industrial-Strength Audio Search Algorithm„), der den Algorithmus, der Shazam erst funktionierten lässt, vorstellt. Schon im Exzerpt ist die Toleranz gegenüber Störgeräuschen erwähnt – und sie erklärt sich aus der Funktionsweise des Algorithmus von selbst:

We have developed and commercially deployed a flexible audio search engine. The algorithm is noise and distortion resistant, computationally efficient, and massively scalable, capable of quickly identifying a short segment of music captured through a cellphone microphone in the presence of foreground voices and other dominant noise, and through voice codec compression, out of a database of over a million tracks. The algorithm uses a combinatorially hashed time-frequency constellation analysis of the audio, yielding unusual properties such as transparency, in which multiple tracks mixed together may each be identified. Furthermore, for applications such as radio monitoring, search times on the order of a few milliseconds per query are attained, even on a massive music database.

Und wie funktioniert das nun? Eigentlich ziemlich einfach:

1. find the strongest frequencies in the music and times at which those frequencies happen
2. look at pairs (freq1,time1,freq2,time2)(freq1,time1,freq2,time2) and turn those into pairs into hashes (by subtracting time1time1 from time2time2)
3. look up those hashes in your database

Und das ist Shazam!