Bagaimana sebenarnya Shazam bekerja?

• Pengenalan musik dilakukan dengan mengubah getaran udara yang diterima mikrofon menjadi waveform, lalu memampatkannya menjadi spectrogram dan sejumlah kecil puncak frekuensi kuat untuk membuat sidik jari lagu
• Karena waveform mentah mudah berubah tergantung volume dan lingkungan pemutaran, waveform sulit dipakai sebagai dasar identifikasi; dengan menerapkan FFT pada potongan-potongan pendek, struktur frekuensi dari waktu ke waktu bisa ditampilkan sehingga perbandingan menjadi lebih stabil
• Puncak-puncak yang tersisa tidak dipakai sebagai titik tunggal, melainkan dipasangkan sebagai anchor dan target zone lalu diubah menjadi hash; kombinasi seperti ini berfungsi sebagai fingerprint hash yang cukup spesifik untuk membedakan rekaman tertentu
• Pencarian tidak membandingkan lagu satu per satu, melainkan memakai struktur hash-first yang langsung mencari berdasarkan hash sebagai kunci; pada tahap akhir sistem juga memeriksa apakah jarak waktu dari hash yang cocok ikut sesuai untuk meningkatkan keandalan
• Basis data skala besar berbasis server dan pendekatan on-device punya skala serta batasan yang berbeda, tetapi intinya sama: membuang sebagian besar informasi dan hanya menyisakan landmark peak agar lagu bisa ditemukan dengan cepat bahkan dari klip pendek dan berisik

---

Proses menafsirkan suara secara terbalik

• Mikrofon ponsel mengukur getaran udara dengan diafragma yang sangat tipis, lalu mengubahnya menjadi waveform, yaitu deretan angka yang merepresentasikan tekanan udara terhadap waktu
  • Gendang telinga manusia menerima gelombang tekanan yang sama, tetapi ponsel memperlakukannya bukan sebagai suara itu sendiri melainkan sebagai urutan angka
  • Suara yang masuk di-sampling puluhan ribu kali per detik, biasanya pada 44,100 Hz
• Mengidentifikasi lagu hanya dari waveform mentah itu sulit; lagu yang sama akan menghasilkan waveform yang sama sekali berbeda jika diputar lebih keras, dan lagu yang berbeda pun bisa memiliki waveform yang mirip
  • Karena waveform dari lagu yang sama juga bisa berubah jika lingkungan pemutaran berbeda, waveform itu sendiri tidak cocok dijadikan dasar identifikasi
• Untuk mengurangi masalah ini, waveform perlu dibagi menjadi potongan-potongan kecil lalu dikenai FFT agar bisa diuraikan frekuensi apa saja yang ada di setiap titik waktu
  • Jika dijadikan pertanyaan, ini setara dengan, "untuk membuat ulang potongan suara pendek ini, nada murni apa saja yang harus dijumlahkan?"
  • Jika hasil tiap potongan ditumpuk ke samping, terbentuklah spectrogram dengan sumbu waktu, sumbu frekuensi, dan sumbu kecerahan
• FFT memanfaatkan fakta bahwa waveform sekompleks apa pun bisa dinyatakan sebagai penjumlahan gelombang sinus dengan frekuensi, amplitudo, dan fase yang berbeda-beda
  • Sebagai contoh, jika memasukkan 1,024 sampel, FFT mengembalikan spektrum yang menunjukkan berapa banyak energi yang ada pada setiap frekuensi
  • Untuk setiap bin frekuensi, semua sampel dikalikan dengan gelombang sinus pada frekuensi itu lalu dijumlahkan; jika frekuensi tersebut memang ada dalam sinyal asli, jumlahnya akan besar, dan jika tidak, hasilnya akan saling meniadakan
• Inti FFT adalah kecepatannya; penguraian secara naif membutuhkan jutaan operasi per potongan, tetapi FFT memanfaatkan simetri matematis untuk menurunkannya menjadi sekitar n log n
  • Kecepatan seperti ini memungkinkan FFT dijalankan ratusan kali per detik bahkan di ponsel
  • Perangkat menggeser jendela ini terus-menerus di atas audio, menerapkan FFT ke setiap potongan, lalu menumpuk hasilnya menjadi spectrogram
• Contoh sederhana biasanya memakai suara sintetis yang hanya terdiri dari satu frekuensi murni agar mudah dipahami, tetapi musik nyata jauh lebih kompleks
  • Jika musik sungguhan atau humming dimasukkan ke mikrofon, spectrogram akan terlihat jauh lebih ramai, tetapi FFT tetap dapat menampilkan strukturnya secara real-time
  • Pada contoh di browser, seluruh audio diproses sepenuhnya di dalam browser, tanpa direkam atau dikirim ke luar

Semakin sedikit, semakin kuat sidik jarinya

• Sistem tidak menyimpan seluruh spectrogram, melainkan hanya menyisakan puncak-puncak terbesar dan memampatkannya menjadi sparse point set
  • Dengan membuang sinyal yang lemah dan hanya menyisakan titik-titik terkuat, yang tertinggal adalah landmark yang penting secara akustik
• Alasan membuang sebagian besar data ini adalah karena menyimpan dan mencari seluruh spectrogram terlalu lambat bahkan untuk komputer
  • Semakin tinggi ambang batasnya, semakin banyak sinyal samar yang hilang, dan hanya puncak besar yang bertahan
• Pendekatan ini meningkatkan ketahanan terhadap noise
  • Noise latar menambahkan energi rendah ke seluruh spectrogram, tetapi biasanya tidak sampai menciptakan puncak terkuat pada area tertentu
  • Landmark yang tersisa adalah frekuensi dominan yang berhasil menonjol menembus noise
• Sebagai gantinya, pendekatan sidik jari ini cenderung berkinerja lebih buruk ketika lagu dinyanyikan langsung oleh pengguna
  • Bahkan jika dinyanyikan dengan sangat baik, hash yang dihasilkan kemungkinan besar akan berbeda dari lagu aslinya
  • Karena itu, sistem berbasis machine learning yang lebih baru menangani humming dan nyanyian berdasarkan melodi, bukan frekuensi yang persis sama

Menghubungkan titik untuk membuat hash

• Satu titik saja punya daya pembeda yang rendah, tetapi kombinasi dua titik jauh lebih kecil kemungkinannya terjadi secara kebetulan sehingga cocok dipakai sebagai fingerprint hash
  • Sebagai contoh, satu frekuensi 1,200 Hz pada suatu waktu bisa muncul di ribuan lagu, tetapi kombinasi 2,400 Hz yang muncul 0,3 detik setelah 1,200 Hz jauh lebih spesifik
• Algoritme mengambil setiap puncak secara bergiliran sebagai anchor, lalu menetapkan target zone di sebelah kanannya yang memiliki rentang waktu dan frekuensi, kemudian memasangkannya dengan semua puncak di dalam area itu
  • Setiap pasangan membentuk hash pendek dari tiga angka: dua frekuensi dan selisih waktunya
• Hash bekerja sebagai kode singkat yang selalu menghasilkan nilai yang sama untuk input yang sama, tetapi menghasilkan nilai yang benar-benar berbeda jika inputnya berubah sedikit saja
  • Sistem ala Shazam memang punya mekanisme untuk menangani variasi kecil, tetapi pada dasarnya hash dibuat dari frekuensi dan timing yang presisi
• Akibatnya, hash ini lebih mirip sidik jari dari rekaman tertentu daripada dari lagunya secara abstrak
  • Itulah sebabnya cover atau remix lebih sulit dicocokkan
• Bahkan dari satu lagu berdurasi 3 menit, ribuan fingerprint hash seperti ini bisa dibuat, dan basis data menyimpannya semua
  • Ponsel membawa sejumlah kecil hash yang diperoleh dari klip 5 detik, sementara basis data membawa jutaan hash yang diambil dari sejumlah besar lagu, lalu masuk ke tahap pencocokan

Menemukan kecocokan yang tepat

• Setiap hash dipakai semacam alamat; untuk setiap hash yang didapat dari klip, sistem langsung melihat tabel besar untuk menemukan lagu yang memiliki hash tersebut
  • Jadi, alih-alih memeriksa lagu satu per satu, sistem mengakses langsung dengan hash sebagai kunci
• Pendekatan intuitif song-first harus memeriksa semua lagu satu per satu dan melihat apakah ada hash yang tumpang tindih, sehingga semakin lambat ketika jumlah lagu bertambah
  • Teks aslinya menyatakan ini sebagai waktu O(N)
  • Basis data contoh dan daftar hash dari klip 5 detik dipakai untuk memvisualisasikan ketidakefisienan ini
• Komputer bisa membalik pendekatan ini dengan cara hash-first
  • Untuk setiap hash, sistem langsung menanyakan, "lagu mana saja yang mengandung hash ini?"
  • Ini dianalogikan seperti indeks di bagian belakang buku: alih-alih membaca semua halaman lagi, kita langsung menuju entri kata tertentu
• Pendekatan ini membuat lookup nyaris mendekati O(1)
  • Baik lagunya 100 maupun 100 juta, waktu prosesnya kira-kira tetap serupa
  • Karena jumlah hash yang mungkin sangat besar, bahkan jika ada jutaan lagu, tiap alamat biasanya hanya berisi sedikit entri
• Tidak cukup hanya berbagi hash yang sama; verifikasi terakhir dilakukan pada jarak waktu
  • Sebagai contoh, jika 17403C dan 19A998 berjarak 1,2 detik di dalam klip, maka pada lagu kandidat yang cocok kedua hash itu juga harus muncul dengan jarak 1,2 detik
  • Kecocokan baru dianggap sangat andal jika selisih waktu antar-hash yang cocok saling sejajar dan jumlahnya juga cukup banyak
• Keseluruhan sistem dirancang agar sesuai dengan jenis pekerjaan yang sangat dikuasai komputer
  • Strukturnya berpusat pada perbandingan angka dan lookup alamat
  • Karena itu, bahkan terhadap jutaan lagu, seluruh pencarian selesai dalam jauh kurang dari 1 detik

Pendekatan yang lebih modern

• Banyak layanan pengenalan lagu seperti Shazam mengirim klip audio ke server lalu melakukan pencocokan pada basis data sidik jari besar yang ada di server
  • Struktur ini dipakai karena basis datanya sangat besar, terus berubah, dan pencariannya memerlukan sumber daya komputasi yang cukup besar
• Sebaliknya, pengenalan on-device Apple dan Now Playing di Google Pixel berjalan sepenuhnya secara lokal di dalam ponsel
  • Mereka memakai basis data yang lebih kecil dan terseleksi, serta model yang dioptimalkan
  • Alih-alih mengejar cakupan penuh, pendekatan ini memilih kecepatan dan juga dapat mencakup metode machine learning yang lebih canggih yang lebih tahan terhadap noise dan perubahan audio
• Pendekatan on-device lebih cepat dan bisa bekerja tanpa koneksi internet, tetapi ada batasan bahwa basis data lagu yang bisa dicocokkan jauh lebih kecil
  • Pembaruan lagu baru juga umumnya lebih lambat
  • Saat perpindahan lokasi terdeteksi, perangkat mungkin perlu mengambil ulang data baru
• Perbedaan lagu populer per wilayah juga memengaruhi komposisi data on-device
  • Lagu hit di Jepang bisa berbeda dari lagu hit di Amerika Serikat
• Baik pencocokan dilakukan di server maupun di dalam perangkat, teknik intinya sama
  • Dengan membuang sebagian besar informasi dan hanya menyisakan sedikit landmark peak, klip 5 detik yang direkam di kafe berisik pun bisa diubah menjadi sekumpulan koordinat yang cukup presisi untuk menunjuk satu lagu di antara jutaan lagu
  • Inti pengenalan ini bukan sekadar mendengar banyak hal, melainkan membuang dengan tepat apa yang harus diabaikan

Makalah yang menjadi landasan

• Sebagian besar isi tulisan ini didasarkan pada makalah Avery Wang tahun 2003, An Industrial-Strength Audio Search Algorithm
  • Jika ingin melihat pemrosesan sinyal dan desain sistemnya lebih dalam, makalah itu adalah titik awal yang paling langsung
• Alur keseluruhannya bergerak dari transformasi waveform, pemilihan puncak, hash pasangan puncak, lookup indeks terbalik, hingga verifikasi penyelarasan waktu
  • Rangkaian langkah inilah yang memungkinkan identifikasi lagu secara cepat bahkan dari klip yang pendek dan berisik

[GN⁺]

Komentar Hacker News

• Ada baiknya melihat materi terkait Shazam juga Ada makalah aslinya di https://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf, dan kalau benar-benar tertarik, presentasi YouTube dari penulisnya juga layak dicari https://news.ycombinator.com/item?id=18069968 berisi tulisan dari karyawan Shazam, https://news.ycombinator.com/item?id=38538996 memuat penjelasan yang diakui oleh salah satu pendiri, dan https://news.ycombinator.com/item?id=41127726 punya reproduksi algoritmenya dalam Go Pada akhirnya, untuk ML pun sering kali nilai data lebih besar daripada kode itu sendiri

• Dugaan terbaru saya justru ke arah mungkin tidak sama sekali Untuk musik pop umumnya cocok, tetapi saya beberapa kali mencoba Shazam untuk beberapa musik synth yang lumayan bagus yang diputar saat jeda kompetisi seluncur es, dan tidak satu pun terdeteksi dengan benar Bisa jadi itu lagu yang belum dirilis atau musik yang sangat niche, tetapi bisa juga memang Shazam gagal besar di situ

• Ini jelas teknologi satu keluarga yang juga dipakai untuk ACR di TV Namun reputasi Shazam di internet jauh lebih baik, tampaknya karena ia menghormati niat dan persetujuan pengguna Kalau implementasi serupa di TV dilakukan tanpa datanya hanya berakhir untuk penjualan iklan, mungkin bisa ada bentuk yang benar-benar menguntungkan konsumen

  • Kalau nilai yang ditawarkan pada akhirnya cuma memberi tahu judul acara atau film yang sedang diputar, rasanya itu tidak jauh berbeda dari info yang sudah muncul saat menekan tombol jeda

• Tulisan ini mungkin salah satu materi terbaik untuk menjelaskan secara visual algoritme audio fingerprinting asli dari makalah Shazam 2003 Meski begitu, saya juga merasa pada titik tertentu mereka mungkin sudah beralih ke model ML

• Ada algoritme bernama DTW(dynamic time warping) yang sering diabaikan Insting saya mengatakan Shazam mungkin juga memakai ini sampai tingkat tertentu

  • Dulu saya pernah memakai DTW untuk melacak bot di situs media sosial tertentu Bot cenderung bergerombol dalam perilakunya, jadi DTW cocok untuk menyelaraskan pola perilaku berulang yang tertunda secara halus

• Mengenali rekaman yang sama tidak terlalu sulit Kalau rekamannya sama, progresi akor dan timing bisa berulang dengan sangat presisi, jadi teknologi pengenalan seperti ini sudah ada jauh lebih dari 10 tahun lalu Sebaliknya, mengenali lagu yang sama dari rekaman berbeda seperti versi cover jauh lebih sulit Audible Magic mengklaim di https://www.audiblemagic.com/2024/02/07/identifying-cover-songs-live-performances-ai-clones-and-more/ bahwa mereka bisa mengenali berbagai versi pertunjukan dari lagu yang sama bahkan sampai parodi, yang tentu saja memakai AI dan komputasi yang lebih besar

  • Ungkapan tidak terlalu sulit itu menyederhanakan terlalu banyak hal Pada level masyarakat secara keseluruhan, ini mungkin terlihat seperti teknologi sederhana yang sudah lama terselesaikan, tetapi jika seorang pengembang diminta membuatnya sendiri tanpa mencari jawabannya, saya rasa tidak banyak yang benar-benar bisa melakukannya
  • Ini setidaknya cerita yang sudah lebih dari 20 tahun Dulu saat saya menjadi konsultan untuk Gracenote, saya ingat pernah melihat bagaimana hal itu bekerja
  • Kalau begitu, bukankah cukup menghapus informasi timing saja?

• Saya sempat berpikir, oh topik ini lagi, lalu ternyata SCP Domain ini terlihat agak mencurigakan Untuk analisis yang lebih lengkap daripada tulisan CameronMacLeod tahun 2022, ada https://news.ycombinator.com/item?id=38531428, dan tulisan Slate tahun 2009 ada di https://news.ycombinator.com/item?id=893353

  • Dalam konteks ini saya kurang paham apa itu SCP Secure copy yang biasa saya tahu jelas tidak cocok Meski begitu, terima kasih untuk tautannya, saya sudah lama penasaran dengan pertanyaan di judul tetapi belum pernah menggali serius, jadi saya berniat membaca ketiganya
  • Meski begitu, elemen interaktif di tulisan ini cukup keren

• Harus saya tambahkan ke daftar proyek saya Dinosaur game, tetapi alih-alih melompat dengan input tombol, akan lucu kalau dibuat melompat dengan suara kokok ayam

• Saya penasaran apakah ada cara untuk mencegah aplikasi seperti Shazam mendeteksi sesuatu Mungkin dengan mencampurkan noise atau teknik lain

  • Kecuali noise itu lebih keras daripada aslinya pada frekuensi dominan tertentu, saya rasa akan sulit Ada contoh juga di tulisan itu, algoritme ini pada dasarnya hanya menyisakan puncak frekuensi dan membuang hampir semua yang lain agar pencarian cepat
  • Produser atau DJ biasanya menyelesaikan masalah ini dengan tidak merilisnya sama sekali atau baru merilisnya jauh belakangan

• Pada 1986 saya pernah mencoba ini sebagai proyek sains dengan Apple ][c