Когда Shazam за пару секунд определяет трек в шумном кафе, он не слышит мелодию, не разбирает текст и даже не пытается «понять» музыку. Он делает нечто гораздо более изящное: превращает звук в набор координат на карте и ищет совпадения, как поисковик ищет слово в книжном указателе. На днях вышло интерактивное объяснение от PerThirtySix, которое отлично раскладывает этот трюк по полочкам — и мне захотелось пройтись по нему с техническими комментариями, потому что под капотом там красивая математика и одна очень правильная инженерная ленивость.
Сначала звук превращают в картинку
Микрофон в телефоне устроен примитивно и гениально одновременно: тонкая мембрана (диафрагма) тоньше человеческого волоса вибрирует от звуковых волн, эти колебания оцифровываются в waveform — последовательность чисел, описывающих давление воздуха в каждый момент времени. На стандартной частоте дискретизации 44 100 Гц (как на CD) телефон снимает 44 тысячи замеров в секунду.
Проблема: сам по себе waveform для распознавания бесполезен. Одна и та же песня, сыгранная громче, даёт совершенно другую форму сигнала. Две разные песни могут давать похожий waveform. Записи в разных акустических условиях — вообще катастрофа.
Поэтому алгоритм применяет к коротким кусочкам сигнала быстрое преобразование Фурье (Fast Fourier Transform, FFT). Идея FFT элегантна: любой сложный сигнал можно представить как сумму чистых синусоид разных частот и амплитуд. FFT берёт, скажем, 1024 отсчёта (это примерно 23 миллисекунды CD-качества) и отвечает на вопрос «какие чистые тона и с какой силой здесь присутствуют».
Почему «быстрое»? Наивный алгоритм (DFT) требует порядка N² операций — для миллионов отсчётов это смерть. FFT эксплуатирует симметрии в формуле и укладывается в ~N·log(N) операций. Разница колоссальная: вместо миллионов операций на кусочек — тысячи. Именно это позволяет гонять FFT сотни раз в секунду прямо на телефоне.
Если склеить результаты FFT по всем последовательным кусочкам, получится спектрограмма — картинка, где по горизонтали время, по вертикали частота, а яркость точки показывает амплитуду. Трёхмерные данные в двумерном представлении.
А потом большую часть картинки выбрасывают
Вот здесь начинается самое интересное. Спектрограмма для трёхминутной песни — это гигантский массив, и хранить его целиком для миллионов треков нереально. Алгоритм делает контринтуитивную вещь: выбрасывает почти всё.
Остаются только локальные максимумы — самые громкие пики в каждом районе спектрограммы. Получается «созвездие» (constellation map): разрежённая карта из редких точек, разбросанных по плоскости «время — частота».
И вот почему это гениально:
🎯 Фоновый шум в кафе размазан по всему спектру тонким слоем и практически никогда не создаёт самый громкий пик в конкретной области. Пики — это те частоты, которые «пробили» шум, и они останутся теми же самыми и в студийной записи, и в вашем записанном на айфон фрагменте.
🎯 Объём данных падает на порядки, а информативность почти не теряется — потому что именно пики несут «характер» записи.
🎯 Это объясняет, почему Shazam стабильно отказывается узнавать ваше напевание под душем. Он ищет отпечаток конкретной записи, а не мелодии. Ваш голос генерирует совершенно другие пики. Для напевания нужны ML-системы, которые работают поверх мелодии (Hum to Search у Google, например).
Соединяем точки — и получаем хеши
Одна точка «1200 Гц в момент X» сама по себе ничего не значит — такое есть в тысячах треков. Но пара точек уже гораздо уникальнее: «1200 Гц, а через 0.3 секунды 2400 Гц» — это почти отпечаток пальца.
Алгоритм делает это систематически. Каждый пик по очереди становится якорем (anchor). Вокруг якоря определяется целевая зона (target zone) — прямоугольник во времени и частоте. Якорь соединяется со всеми пиками в этой зоне, и из каждой пары генерируется хеш — короткая строка, которая однозначно кодирует три числа:
🔹 частота якоря
🔹 частота второй точки
🔹 интервал времени между ними
Один трёхминутный трек порождает тысячи таких хешей. База Shazam хранит десятки миллиардов записей вида «хеш → песня → время в песне».
Важная деталь: хеш — это не хеш в криптографическом смысле, а скорее компактный ключ-адрес. Одни и те же три числа всегда дают один и тот же ключ, и поэтому одинаковые куски звука в разных записях находят друг друга. Но из-за того, что отпечаток строится на точных частотах, каверы, ремиксы и живые исполнения матчатся плохо — это отпечаток конкретной записи, а не произведения.
Как найти совпадение в миллионах песен
Самый наивный подход — перебирать песни и проверять, есть ли в них нужные хеши. Это O(N) по количеству треков, и с ростом каталога становится всё хуже.
Shazam делает разворот на 180 градусов и использует инвертированный индекс — ту же структуру, что и поисковики, и что указатель в конце бумажной книги. Вместо «какая песня содержит эти хеши?» вопрос переформулируется как «какие песни содержат вот этот хеш?». Каждый хеш — это адрес, и по адресу лежит короткий список треков.
В результате поиск из O(N) превращается в практически O(1) — то есть время ответа почти не зависит от того, сколько песен в базе, 100 тысяч или 100 миллионов. Телефон не «прочёсывает» каталог, а прыгает прямо по нужным адресам.
Но и этого недостаточно. Популярный ритм ударных может давать один и тот же хеш в сотнях треков, и простое совпадение хешей даст ложные срабатывания. Поэтому финальный фильтр — тайминги. Если в вашем фрагменте хеши A и B стоят через 1.2 секунды, в песне-кандидате они тоже должны стоять через 1.2 секунды. Если набор временных разниц по многим парам хешей сходится к единому сдвигу — матч найден.
Ключевое наблюдение: вся эта схема построена на операциях, которые компьютеры делают очень хорошо — сравнение чисел и поиск по таблице. Никакого ML, никакого понимания музыки. Просто очень аккуратно выстроенная геометрия.
Что поменялось с 2003 года
Базовый алгоритм Shazam описан в классической статье Avery Wang 2003 года «An Industrial-Strength Audio Search Algorithm» — и суть не менялась два десятилетия. Но инфраструктура эволюционировала.
Классический Shazam отправляет отпечаток (не сам звук, кстати — это важно для приватности и трафика) на сервер, где живёт гигантская база из сотен миллионов треков. Матчинг происходит на сервере.
А есть on-device подходы — Apple Shazam в офлайне и Google Pixel Now Playing. Они работают совсем иначе:
⚡ На устройстве лежит компактная курируемая база популярных треков (десятки тысяч, не сотни миллионов).
⚡ Модель распознавания оптимизирована под мобильный железный бюджет. ⚡ База обновляется по геолокации: в Японии на устройство подтягиваются японские хиты, в США — американские. Это разумный компромисс: вероятность услышать в Токио топ-50 Oricon сильно выше, чем случайный трек из Спотифая.
⚡ Всё крутится в фоне пассивно, с минимальным расходом батареи, и ничего не уходит на серверы Google/Apple — большой плюс для приватности.
В научной работе Google по Now Playing описан нейросетевой подход: вместо классических хешей используется компактный эмбеддинг аудиофрагмента, который сравнивается с эмбеддингами треков в базе. Это устойчивее к искажениям, но принцип «выбрасываем всё лишнее, храним компактный отпечаток» сохраняется.
Почему это важно за пределами музыки
Алгоритм аудиоотпечатков (audio fingerprinting) давно вышел за рамки развлечений и работает в куда более серьёзных местах:
🎬 YouTube Content ID — тот же принцип, только для детектирования пиратского контента: аудио видео-загрузки прогоняется против базы правообладателей.
🏭 Промышленный мониторинг — станки и подшипники «звучат» по-разному в зависимости от состояния, и отпечаток аномального звука можно детектировать до того, как агрегат встанет. Здесь важно, что метод устойчив к постоянному фоновому шуму цеха.
🎙 Распознавание дикторов — та самая задача, которую я разбирал на хакатоне «Криптонита»: там тоже строятся эмбеддинги речи, и хотя это уже нейросетевое семейство методов, философия «убрать всё ненужное и оставить компактный отпечаток» та же.
📻 Мониторинг эфира — сервисы типа BMAT и Mediaguide круглосуточно слушают тысячи радиостанций по всему миру и считают ротации для обеспечения авторских выплат.
Что мне в этом нравится больше всего
Shazam — идеальный пример того, как правильно заданный вопрос решает задачу, которая в лоб кажется неподъёмной. Если задавать вопрос «как научить компьютер понимать музыку», вы упрётесь в десятилетия исследований. Если спросить «какие 20 координат на плоскости совпадают у этих двух фрагментов» — ответ помещается в несколько FFT и одну хеш-таблицу.
Как автор в статье на PerThirtySix хорошо формулирует: распознавание здесь — это упражнение в правильном игнорировании. Не в том, чтобы захватить всю информацию, а в том, чтобы понять, какую можно безопасно выбросить. Для инженера это урок, который стоит внутренне записать: отпечаток лучше полного описания, грубый инвариант лучше точной модели, и хорошая структура данных часто побеждает умный алгоритм.
Ну и отдельно — базовый патент Avery Wang подан в 2003 году, и его алгоритм до сих пор лежит в основе приложения, которое ежемесячно делает больше миллиарда запросов. Не уверен, что много software-решений выдерживают такой тест временем.
Источники
🔗 How The Heck Does Shazam Work? — PerThirtySix
🔗 An Industrial-Strength Audio Search Algorithm — Avery Wang, 2003
🔗 Now Playing: Continuous low-power music recognition — Google Research