आखिर Shazam काम कैसे करता है?

• संगीत पहचान में माइक्रोफ़ोन द्वारा प्राप्त हवा के कंपन को waveform में बदलकर, फिर उसे spectrogram और कुछ मज़बूत frequency peaks में compress करके गाने का fingerprint बनाया जाता है
• raw waveform volume और playback environment के अनुसार आसानी से बदल जाता है, इसलिए उसे पहचान के मानदंड के रूप में इस्तेमाल करना कठिन है; छोटे-छोटे हिस्सों पर FFT लागू करके समय के अनुसार frequency structure को सामने लाना पड़ता है, तभी stable comparison संभव होता है
• बची हुई peaks को एकल बिंदु की तरह नहीं बल्कि anchor और target zone की जोड़ी के रूप में बांधकर hash बनाया जाता है, और ऐसे संयोजन किसी खास recording को अलग पहचानने लायक विशिष्ट fingerprint hash की तरह काम करते हैं
• खोज में गानों को एक-एक करके compare नहीं किया जाता, बल्कि hash को key बनाकर सीधे खोजने वाली hash-first संरचना इस्तेमाल होती है; अंत में matched hashes के time gap भी मिलते हैं या नहीं, यह जांचकर reliability बढ़ाई जाती है
• server-based बड़े database और on-device तरीके scale और constraints में अलग होते हैं, लेकिन मूल बात यह है कि ज़्यादातर जानकारी फेंककर सिर्फ landmark peaks छोड़े जाते हैं, ताकि छोटे और noisy clip से भी गाना जल्दी खोजा जा सके

---

आवाज़ को उल्टा समझने की प्रक्रिया

• फ़ोन का माइक्रोफ़ोन बहुत पतले diaphragm से हवा के कंपन को मापता है, और उसे समय के अनुसार वायु-दाब को दिखाने वाली संख्या-श्रृंखला यानी waveform में बदलकर store करता है
  • कान का eardrum भी यही pressure wave पाता है, लेकिन फ़ोन इसे आवाज़ के रूप में नहीं बल्कि number sequence के रूप में संभालता है
  • आने वाली आवाज़ को प्रति सेकंड कई दसियों हज़ार बार sample किया जाता है, और आम तौर पर 44,100 Hz इस्तेमाल होता है
• सिर्फ raw waveform से गाने की पहचान करना कठिन है; वही गाना अगर ज़्यादा तेज़ बजाया जाए तो waveform बिल्कुल अलग बन सकता है, और अलग-अलग गाने भी कभी-कभी मिलते-जुलते waveform बना सकते हैं
  • playback environment बदलने पर भी एक ही गाने का waveform बदल सकता है, इसलिए waveform अपने-आप में पहचान का सही आधार नहीं है
• इस समस्या को कम करने के लिए waveform को छोटे टुकड़ों में बांटकर उन पर FFT लागू करना पड़ता है, ताकि हर क्षण पर कौन-कौन सी frequencies मौजूद हैं, यह अलग करके देखा जा सके
  • सवाल की तरह कहें तो यह ऐसा है: "इस छोटे sound chunk को दोबारा बनाने के लिए कौन-कौन से pure tones जोड़ने होंगे?"
  • हर chunk के result को बगल में जमाने पर समय-अक्ष, frequency-अक्ष और brightness-अक्ष वाला spectrogram बनता है
• FFT इस बात का फायदा उठाता है कि कोई भी जटिल waveform अलग-अलग frequency, amplitude और phase वाली sine waves के योग से व्यक्त किया जा सकता है
  • उदाहरण के लिए, 1,024 samples देने पर यह ऐसा spectrum लौटाता है जो दिखाता है कि हर frequency में कितनी energy है
  • हर frequency bin पर सभी samples को उस frequency की sine wave से गुणा करके जोड़ा जाता है; अगर वह frequency वास्तव में signal में मौजूद हो, तो योग बड़ा होता है, नहीं तो वह cancel हो जाता है
• FFT की असली ताकत इसकी speed है; सीधी-सादी decomposition में हर chunk पर लाखों operations लग सकते हैं, लेकिन FFT mathematical symmetry का उपयोग करके इसे लगभग n log n स्तर तक घटा देता है
  • यही speed इसे फ़ोन पर भी प्रति सेकंड सैकड़ों बार चलाने लायक बनाती है
  • device इस window को audio पर लगातार आगे बढ़ाता है, हर chunk पर FFT लागू करता है, और results को जमा करके spectrogram बनाता है
• एक simple example में सिर्फ एक pure frequency वाला synthetic tone समझने में मदद करता है, लेकिन असली संगीत इससे कहीं अधिक जटिल होता है
  • असली music या humming को microphone से लेने पर spectrogram कहीं ज़्यादा बिखरा हुआ दिखता है, फिर भी FFT उसके भीतर की structure को real time में सामने ले आता है
  • browser example में सारा audio browser के अंदर ही process होता है; न recording होती है, न बाहर भेजा जाता है

जितना कम, उतना मज़बूत fingerprint

• system पूरा spectrogram store नहीं करता, बल्कि सिर्फ सबसे बड़े peaks छोड़कर उसे sparse point set में compress करता है
  • कमजोर signal हटाकर सिर्फ सबसे मज़बूत बिंदु रखने से acoustic रूप से महत्वपूर्ण landmark ही बचते हैं
• अधिकांश data फेंकने की वजह यह है कि पूरे spectrogram को store और search करना computer के लिए भी बहुत धीमा होता है
  • threshold जितना ऊँचा रखा जाएगा, उतने ही हल्के signal गायब होंगे और सिर्फ बड़े peaks बचेंगे
• यह तरीका noise tolerance बढ़ाता है
  • background noise spectrogram के पूरे हिस्से में कम energy जोड़ता है, लेकिन आम तौर पर किसी खास region का सबसे बड़ा peak नहीं बना पाता
  • जो landmark बचते हैं, वे noise के बीच से उभरने वाली dominant frequencies होती हैं
• लेकिन इस fingerprinting तरीके में गाना खुद गाकर input देने पर performance गिर सकती है
  • बहुत अच्छा गाने पर भी original track से अलग hash बनने की संभावना रहती है
  • इसलिए नए machine learning-based systems exact frequency के बजाय melody के आधार पर humming और singing को handle करते हैं

बिंदुओं को जोड़कर hash बनाना

• सिर्फ एक point में पर्याप्त भेद-क्षमता नहीं होती, लेकिन दो points का संयोजन कहीं कम संयोगवश होता है, इसलिए वह fingerprint hash के लिए ज़्यादा उपयुक्त है
  • उदाहरण के लिए, किसी समय पर 1,200 Hz अकेला हजारों गानों में आ सकता है, लेकिन 1,200 Hz के 0.3 सेकंड बाद 2,400 Hz आने वाला संयोजन कहीं अधिक specific होता है
• algorithm हर peak को बारी-बारी से anchor मानता है, और उसके दाईं ओर समय और frequency की सीमा वाला target zone तय करके उसके भीतर के सभी peaks से जोड़ी बनाता है
  • हर pair दो frequencies और time difference, यानी कुल तीन numbers से एक छोटा hash बनाता है
• hash एक छोटे code की तरह काम करता है जो एक ही input पर हमेशा वही result देता है, और input में थोड़े से बदलाव पर पूरी तरह अलग value दे देता है
  • Shazam जैसे systems छोटे बदलावों को संभालने की कुछ व्यवस्था रखते हैं, लेकिन मूल रूप से hash exact frequency और timing से बनता है
• नतीजे में यह hash गाने से ज़्यादा किसी खास recording के fingerprint की तरह काम करता है
  • इसलिए cover या remix को match करना ज़्यादा कठिन हो जाता है
• 3 मिनट के एक गाने से भी ऐसे हजारों fingerprint hashes बनाए जा सकते हैं, और database इन्हें सभी store करता है
  • फ़ोन 5 सेकंड के clip से मिले थोड़े से hashes लेकर आता है, जबकि database विशाल संख्या में गानों से निकाले गए लाखों hashes लेकर matching चरण में जाता है

सटीक match कैसे मिलता है

• हर hash एक तरह के address की तरह काम करता है, और system clip से मिले हर hash के लिए विशाल table में सीधे lookup करके उस hash वाले गाने ढूंढता है
  • गानों को एक-एक करके scan करने के बजाय hash को ही key बनाकर access किया जाता है
• सहज लगने वाला song-first तरीका हर गाने को अलग-अलग जांचकर hash overlap देखता है, इसलिए गानों की संख्या बढ़ने के साथ यह धीमा होता जाता है
  • लेख इसे O(N) time के रूप में बताता है
  • उदाहरण database और 5-second clip hash list से इस inefficiency को visualise किया गया है
• computer इसे उलटकर hash-first तरीके से process कर सकता है
  • हर hash के लिए यह सीधे पूछता है: "किन गानों में यह hash मौजूद है?"
  • इसे किताब के पीछे वाले index की तरह समझाया गया है, जहाँ हर page दोबारा पढ़ने के बजाय किसी खास शब्द की entry पर सीधे जाया जाता है
• यह approach lookup को लगभग O(1) के करीब ले आती है
  • गाने 100 हों या 10 करोड़, processing लगभग समान समय में हो सकती है
  • संभव hashes की संख्या इतनी अधिक होती है कि लाखों गाने होने पर भी हर address पर आम तौर पर सिर्फ कुछ ही entries होती हैं
• सिर्फ एक जैसे hash मिल जाना काफी नहीं होता; अंतिम verification time gap पर होती है
  • उदाहरण के लिए, अगर clip में 17403C और 19A998 के बीच 1.2 सेकंड का अंतर है, तो matching candidate song में भी वही दो hashes 1.2 सेकंड के अंतर पर आने चाहिए
  • matched hashes के time differences आपस में align हों और उनकी संख्या भी पर्याप्त हो, तभी match को high confidence माना जाता है
• पूरा system ऐसे tasks के हिसाब से बनाया गया है जिनमें computer खास तौर पर अच्छा होता है
  • number comparison और address lookup इस संरचना के केंद्र में हैं
  • इसलिए लाखों गानों के खिलाफ भी पूरा lookup 1 सेकंड से बहुत कम समय में पूरा हो जाता है

और आधुनिक approaches

• Shazam जैसे कई song recognition services audio clip को server पर भेजते हैं, और server पर मौजूद बड़े fingerprint database में matching करते हैं
  • database बहुत बड़ा होता है, लगातार बदलता रहता है, और search के लिए काफ़ी compute resources चाहिए होते हैं, इसलिए यह संरचना अपनाई जाती है
• इसके उलट Apple की on-device recognition और Google Pixel का Now Playing सब कुछ फ़ोन के अंदर local रूप से चलाते हैं
  • वे छोटे और curated database तथा optimized models का उपयोग करते हैं
  • पूरी व्यापकता के बजाय speed को प्राथमिकता दी जाती है, और noise तथा audio variation के प्रति अधिक मज़बूत sophisticated machine learning approaches भी शामिल होती हैं
• on-device तरीका ज़्यादा तेज़ है और internet connection के बिना भी काम करता है, लेकिन इसकी सीमा यह है कि match किए जा सकने वाले गानों का database बहुत छोटा होता है
  • नए गाने जोड़ने में भी आम तौर पर अधिक समय लग सकता है
  • location change detect होने पर नया data फिर से लाना पड़ सकता है
• अलग-अलग क्षेत्रों के लोकप्रिय गानों का फर्क on-device data composition को भी प्रभावित करता है
  • जापान के hit songs और अमेरिका के hit songs अलग हो सकते हैं
• चाहे matching server पर हो या device के अंदर, मूल तकनीक लगभग वही रहती है
  • ज़्यादातर जानकारी हटाकर सिर्फ कुछ landmark peaks छोड़ दिए जाएँ, तो शोरगुल वाले cafe में रिकॉर्ड किए गए 5-second clip को भी ऐसी precise coordinates की series में बदला जा सकता है जो लाखों गानों में से एक को पहचान सके
  • पहचान का मूल बहुत कुछ सुनना नहीं, बल्कि क्या अनदेखा करना है इसे सही-सही हटाना है

आधार बना शोध-पत्र

• लेख का बड़ा हिस्सा Avery Wang के 2003 के शोध-पत्र An Industrial-Strength Audio Search Algorithm पर आधारित है
  • signal processing और system design को और गहराई से समझना हो, तो वही paper सीधा शुरुआती बिंदु बनता है
• पूरा flow waveform conversion, peak selection, peak-pair hashing, inverted-index lookup, और time-alignment verification से होकर गुजरता है
  • यही चरण मिलकर छोटे और noisy clip से भी तेज़ी से गाना पहचानना संभव बनाते हैं