Як працює аудіовідбиток: алгоритм Shazam

Shazam може розпізнати пісню за 10 секунд навколишнього звуку — попри фоновий шум, артефакти стиснення та фальшивий спів. Основна ідея — хешування спектрограми на основі орієнтирів — достатньо елегантна, щоб зрозуміти її повністю. Ось як це працює.

1. Звук як спектрограма

Необроблений аудіосигнал — це форма хвилі в часовій області: амплітуда відносно часу. Для розпізнавання музики порівняння в часовій області непрактичне: два записи однієї пісні дещо відрізняються таймінгом, гучністю, фоновим шумом і кодуванням.

Ключове розуміння — працювати в часово-частотній області. Спектрограма показує частотний вміст у часі — 2D-зображення, де вісь x — час, вісь y — частота, а яскравість кодує амплітуду. Пісня має характерний «відбиток» у цьому просторі, стійкий до багатьох спотворень.

Зокрема, положення піків (локальних максимумів енергії) на спектрограмі добре відтворювані. Той самий удар барабана на 200 Гц дасть пік приблизно в тому самому місці незалежно від налаштувань запису чи рівня гучності.

2. Короткочасне перетворення Фур'є

Короткочасне перетворення Фур'є (STFT) обчислює перетворення Фур'є над ковзним часовим вікном. Для кожного положення вікна t:

X[t, f] = Σₙ x[n] · w[n − t] · e^{−j2πfn/N}

Де x[n] — аудіосигнал, w[n] — віконна функція (Ганна, Геммінга), а N — розмір FFT. Типові параметри для музики:

Розмір вікна: 4096 відліків на 44 100 Гц → ~93 мс на кадр
Крок (hop): 1024 відліки → 75% перекриття між сусідніми кадрами
Частотна роздільність: 44100/4096 ≈ 10.77 Гц на бін

Спектрограма амплітуди — це |X[t, f]|. Зазвичай у логарифмічному масштабі та з логарифмічним рознесенням частот (шкала мел), щоб відповідати слуховому сприйняттю людини, але Shazam використовує лінійні частотні біни, розбиті на піддіапазони.

Стаття про Shazam: Wang, A.L. (2003). «An Industrial-Strength Audio Search Algorithm.» ISMIR 2003. Це оригінальний опублікований опис алгоритму.

3. Пошук орієнтирів (виявлення піків)

Орієнтири — це локальні максимуми на спектрограмі — точки (t, f), де енергія перевищує всіх сусідів у певному часово-частотному околі. Алгоритм:

Розбити вісь частот на смуги з логарифмічним рознесенням (наприклад, 6 смуг)
У кожній смузі та кожному часовому кадрі знайти бін із найбільшою енергією
Застосувати поріг: зберігати лише піки вище середньої енергії × деякий коефіцієнт
Застосувати обмеження мінімальної відстані: піки мають бути рознесені принаймні на Δt у часі та Δf за частотою

3-хвилинна пісня за цих налаштувань дає приблизно 1 000–2 000 орієнтирів — розріджене, але стабільне представлення. 10-секундний фрагмент запису дає ~100 орієнтирів, чого достатньо для надійного зіставлення.

Розрідженість критична: нам не потрібно зіставляти кожну частоту, лише виразні піки. Це робить алгоритм стійким до адитивного шуму, який рівномірно розподіляє енергію, піднімаючи рівень шуму, але суттєво не зсуваючи піки.

4. Комбінаторне хешування

Самих окремих піків недостатньо для розпізнавання. Той самий пік міг би траплятися в багатьох піснях. Підхід Shazam поєднує кожну якірну точку з кількома сусідніми цільовими точками в конічній зоні попереду в часі:

hash = (f_anchor, f_target, Δt) where Δt = t_target - t_anchor \in [1, FAN_OUT_WINDOW]

Для кожного якоря, якщо ми поєднуємо його з не більш ніж F = 15 цільовими піками в зоні, кожен якір породжує 15 хешів. За 1 500 орієнтирів у пісні це 22 500 хешів на пісню, що зберігаються в базі даних. Кожен хеш також зберігає абсолютний часовий зсув якоря: (hash → song_id, t_anchor).

Комбінаторний простір величезний — 3 цілих значення, кожне в широкому діапазоні — тож колізії між різними піснями трапляються рідко. Точна ймовірність залежить від розміру хеш-простору; навіть із 20-бітними значеннями для кожного з трьох складників шанси на випадкову колізію становлять < 10⁻⁸ на пару.

function hashPair(f1, f2, dt) {
  // Упаковуємо три цілих числа в один 32-бітний хеш
  // f1, f2: індекси частотних бінів (0-511)
  // dt: різниця часу у кадрах (1-50)
  return ((f1 & 0x1FF) << 23) | ((f2 & 0x1FF) << 14) | (dt & 0x3FFF);
}

5. Пошук у базі даних і часова когерентність

Під час запиту обчислюємо ті самі ~100 орієнтирів із 10-секундного запису, генеруємо ~1 500 хешів і шукаємо кожен у хеш-таблиці. Кожен збіг повертає (song_id, stored_t_anchor).

Наївний підрахунок збігів на пісню працював би погано — хеші повторюються між піснями, хай і рідко. Ключ — це часова когерентність: якщо фрагмент запиту починається в момент t_q усередині пісні, то для кожного збіжного хеша зсув Δ = stored_t − query_t має бути сталим для всіх хешів, що належать цій пісні.

Побудуйте гістограму Δ для кожної пісні-кандидата. Правильна пісня дає різкий пік — багато хешів вирівнюються за тим самим зсувом, тоді як випадкові колізії розсіюються рівномірно. Перемагає пісня з найвищим, найвужчим піком:

score(song) = max_Δ { кількість хешів зі stored_t − query_t = Δ }

Оцінка вище порога (скажімо, 20+ збіжних хешів) приймається. На практиці база даних Shazam містить 11 мільйонів пісень. Їхній інженерний блог 2023 року зазначає, що середній час розпізнавання < 1 секунди, враховуючи мережеву затримку туди-назад.

6. Чому воно стійке до шуму

Адитивний шум: рівномірно піднімає спектральний рівень шуму; піки лишаються локальними максимумами, доки відношення сигнал/шум > ~−10 dB у відповідних частотних смугах.
Зміна гучності: виявлення піків використовує відносні пороги (без абсолютного масштабування амплітуди), тож тихий і гучний записи дають однакові піки.
Спотворення смугового фільтра: динаміки/мікрофони телефонів зрізають частоти <300 Гц і >8 кГц. Shazam використовує відбитки в діапазоні 300–2000 Гц, що цілком вкладається у смугу пропускання телефона.
Зміна темпу/висоти: алгоритм НЕ обробляє довільні зсуви висоти/темпу. (Для виявлення кавер-версій потрібні дорожчі алгоритми, як-от акустичні відбитки через глибоке навчання.)
Часткові записи: перевірка часової когерентності самовирівнюється — вам не потрібно знати, на яку частину пісні припадає запит.

7. Реалізація з Web Audio API

Вузол AnalyserNode з Web Audio API надає спектрограму в реальному часі безпосередньо у браузері:

const ctx = new AudioContext();
const analyser = ctx.createAnalyser();
analyser.fftSize = 4096;           // частотна роздільність
analyser.smoothingTimeConstant = 0; // без часового згладжування

const mic = await navigator.mediaDevices.getUserMedia({ audio: true });
const source = ctx.createMediaStreamSource(mic);
source.connect(analyser);

const bufLen = analyser.frequencyBinCount;  // 2048
const spectrum = new Float32Array(bufLen);

function captureFrame() {
  analyser.getFloatFrequencyData(spectrum);
  // spectrum[k] = амплітуда у dB для біна k
  // Частота біна k = k * sampleRate / fftSize
  return spectrum.slice();
}

// Збираємо кадри з кроком ~10 Гц, виявляємо піки, хешуємо пари
setInterval(() => {
  const frame = captureFrame();
  const peaks = detectPeaks(frame, /* поріг= */ -40 /* dB */);
  generateHashes(peaks);
}, 93 /* мс, відповідає кроку fftSize/sampleRate */);

Повна JS-реалізація (~300 рядків) може створювати аудіовідбиток локально та порівнювати його з попередньо побудованою хеш-картою. Існують відкриті еталонні реалізації у вигляді npm-пакетів (local-audio-fingerprint, fingerprint-js) для експериментів.