ShazamMulţi dintre noi folosim serviciul de identificare muzicală Shazam atunci când auzim cântece necunoscute ori al căror titlu ne scapă pe moment. În definitiv, este destul de simplu să deblocăm telefonul inteligent, să deschidem o aplicaţie şi să lămurim misterul muzical în numai câteva secunde. Dar cum anume reuşeşte aplicaţia Shazam să ne ofere informaţiile dorite atât de rapid?

 



Există un serviciu foarte popular numit Shazam, care înregistrează un fragment muzical scurt şi identifică melodia din care face parte secvenţa înregistrată. Poate fi utilizat în mai multe feluri, dar unul dintre cele mai comode este instalarea aplicaţiei gratuite cu acelaşi nume pe telefoanele inteligente. E suficient să apăsaţi butonul "tag now", să ţineţi microfonul telefonului aproape de boxe şi de cele mai multe ori aplicaţia va reuşi identificarea cântecului şi va oferi informaţii despre artist, alături de un link către o pagină de unde poate fi achiziţionat albumul din care face parte melodia auzită.

Remarcabil este faptul că serviciul funcţionează şi pentru cântece foarte puţin cunoscute, chiar şi în prezenţa unui zgomot deranjant de fundal. Am reuşit să îl utilizez cu succes chiar şi în interiorul unor cafenele şi restaurante aglomerate.

Aşa că am fost curios să aflu cum funcţionează şi, din fericire, există un document scris de către unul dintre creatorii serviciului care tocmai asta explică. Bineînţeles că anumite detalii nu sunt acolo, dar ideea de bază este că aplicaţia funcţionează utilizând amprentarea muzicii pe baza spectrogramei asociate (spectrograma este o reprezentare vizuală a spectrului de frecvenţe conţinute într-un semnal sonor ori de altă natură, reprezentare realizată pe măsură ce frecvenţa variază în timp ori în funcţie de altă mărime variabilă - n.tr.).



Iată paşii de bază:

1. Înainte de toate, trebuie spus că serviciul Shazam a amprentat şi amprentează un catalog impresionant de melodii şi stochează amprentele respective într-o bază de date proprie.

2. Un utilizator "etichetează" (operaţia amintită anterior: "tag now") un cântec auzit, operaţie în urma căreia se creează amprenta unui fragment de 10 secunde din melodie.

3. Aplicaţia Shazam încarcă pe serverele proprii amprenta, iar la nivelul serverelor are loc o căutare pentru depistarea unei amprente similare în baza proprie de date.

4. Dacă este descoperită o potrivire, informaţiile despre cântecul respectiv sunt returnate către utilizator, iar în caz contrat este returnată o eroare.


Iată cum decurge procedura de amprentare:

Ne putem gândi la orice fragment muzical ca la un grafic timp-frecvenţă care poartă numele de spectrogramă. Pe o axă avem timpul, pe alta frecvenţa, iar pe o a treia intensitatea. Fiecare punct de pe graficul respectiv reprezintă intensitatea unei frecvenţe date la un anumit moment de timp. Presupunând că reprezentăm timpul pe axa x şi frecvenţa pe axa y, o linie orizontală ar reprezenta un ton continuu, curat şi o linie verticală ar reprezenta o explozie instantanee de zgomot alb. Iată, ca exemplu, cum ar putea fi reprezentat un cântec prin intermediul unei asemenea spectrograme:

grafic shazam
Spectrograma unui fragment dintr-un cântec cu intensităţile de vârf marcate cu roşu.
Wang, Avery Li-Chun. Un superalgoritm (industrial-strength) de căutare a informaţiei audio. Shazam Entertainment, 2003. Fig. 1A,B.

Algoritmul Shazam amprentează un cântec generând acest grafic tridimensional şi identificând frecvenţele asociate "intensităţilor de vârf." Pentru fiecare dintre aceste puncte de maxim sunt reţinute frecvenţele şi timpul trecut de la începutul melodiei. Bazat pe exemplele din documentul anterior menţionat, estimez că e vorba de aproximativ 3 astfel de puncte pe secundă. [Update: cineva menţionează faptul că în implementarea proprie a avut nevoie de în jur de 30 de puncte/sec.]. Aşadar, un exemplu de amprentă a unei mostre de 10 secunde ar putea fi:

hash shazam


Shazam construieşte catalogul propriu de amprente sub forma unei tabele hash (tabelele hash reprezintă structuri de date în cadrul cărora se asociază anumite chei valorilor anumitor indicatori - n.tr.), cheia fiind frecvenţa. Atunci când Shazam primeşte o amprentă similară celei de mai sus, foloseşte prima cheie (în acest caz 823.44), şi caută melodiile similare. Tabela lor hash ar putea arăta ca mai jos:

hash shazam


Câteva detalii suplimentare: nu este marcat un singur punct în cadrul spectrogramei, ci mai degrabă o pereche de puncte: "intensitatea de vârf" plus un al doilea "punct ancoră". Astfel că cheia nu este o frecvenţă unică, ci este calculată prin intermediul unei funcţii hash (o funcţie hash reprezintă o funcţie prin intermediul căreia se asociază datelor digitale de dimensiuni variabile date digitale de dimensiuni fixe - n.tr.) calculată pe baza frecvenţelor ambelor puncte. Asta duce la mai puţine coliziuni de hash-uri (adică situaţii în care mostrei îi corespund mai multe intrări în baza de date dpdv al hash-ului), fapt care creşte viteza de căutare în catalog cu câteva ordine de mărime. Se pot spune multe lucruri interesante despre procedura de calcul al acestui hash, dar nu mă voi referi la ele aici, aşa că puteţi accesa linkurile din acest paragraf dacă sunteţi interesaţi.]

Grafic Shazam
Graficul de sus: melodiile şi mostrele au multe potriviri de frecvenţe, dar acestea nu se aliniază în timp, astfel că nu vorbim de o potrivire. Graficul de jos: potrivirile de frecvenţe se petrec la acelaşi momente de timp, astfel că între melodie şi mostră se identifică o potrivire.
Wang, Avery Li-Chun. Un superalgoritm (industrial-strength) de căutare a informaţiei audio. Shazam Entertainment, 2003. Fig. 2B.

Dacă pentru un anumit cântec apare o potrivire de mai multe ori (bazat pe exemplele din document cred că este nevoie de aproximativ o potrivire de frecvenţă în fiecare secundă), algoritmul verifică dacă aceste frecvenţe corespund în timp. Creatorii au implementat o modalitate foarte inteligentă pentru a face asta. Se creează un al doilea grafic de potriviri de frecvenţă, pe o axă având timpul trecut de la începutul melodiei la care apar acele frecvenţe, iar pe cealaltă axă timpul la care acele frecvenţe apar în cadrul mostrei prelucrate. Dacă există o relaţie temporală între aceste seturi de puncte, atunci acestea se vor alinia pe o linie diagonală. Se foloseşte o altă metodă de procesare a semnalului pentru a găsi această linie şi dacă există cu un anumit grad de certitudine, atunci este raportată o potrivire.

Traducere după How Shazam Works To Identify (Nearly) Every Song You Throw At It.