Вы сидите в кофейне. Включается песня, название которой вертится на языке, но вспомнить его вы никак не можете. Вы достаёте телефон, нажимаете на кнопку, и приложение за несколько секунд определяет композицию.

Как, прослушав всего несколько секунд музыки в шумном помещении, телефон мгновенно может найти её среди миллионов песен?

Можно подумать, что телефон слушает мелодию или распознаёт текст, но это не так. На самом деле, всё гораздо хитрее.

Реверс-инжиниринг звука

В микрофоне телефона есть очень тонкая мембрана (диафрагма), измеряющая вызываемые звуком колебания воздуха. Эти колебания преобразуются в электрический сигнал, оцифровываемый в волновую форму: последовательность чисел, описывающую давление воздуха в каждый момент времени.

Это похоже на то, как наши барабанные перепонки улавливают те же волны давления, но мозг превращает их в звук, а телефон — в последовательность чисел.

Сама волновая форма не очень полезна для идентификации композиций. Повышение громкости песни создаст совершенно иную волновую форму, хотя сама песня остаётся той же. Две разные песни могут генерировать очень похожие волновые формы, а одна и та же песня, проигрываемая в разных пространствах, может генерировать разные.

Хитрость заключается в том, чтобы преобразовать волновую форму в более полезное для компьютера представление. Телефон выполняет с небольшими фрагментами волновой формы математическую операцию — быстрое преобразование Фурье (БПФ, или Fast Fourier Transform, FFT). Каждый фрагмент преобразуется из одной сложной волны в список отдельных частот, присутствующих в данный момент времени. Можно сказать, БПФ отвечает на вопрос: какие чистые тона нужно сложить, чтобы воссоздать этот звуковой фрагмент?

Соединив эти фрагменты друг за другом, мы получаем спектрограмму, описывающую звук в трёх измерениях: время движется по оси X, частота — по оси Y, а яркость каждой точки описывает амплитуду (громкость частоты на данный момент).

Что же на самом деле делает БПФ?

Любую волновую форму, какой бы зазубренной она ни была, можно описать в виде суммы гладких синусоид с разными частотами, амплитудами и фазами. БПФ — это эффективный алгоритм распаковки набора аудиосэмплов в такой список. Если передать ему 1024 сэмпла сырого аудио (примерно 23 миллисекунды в CD-качестве), то он вернёт спектр, сообщающий нам, какая величина энергии присутствует на каждой частоте. Вот базовая формула дискретного преобразования Фурье:

Для каждого блока частот k мы умножаем каждый сэмпл x[n] на синусоиду этой частоты и складываем их. Если сигнал содержит эту частоту, то сумма будет большой, если нет, она обнуляется.

Здесь важно, что это «быстрое» преобразование. При наивном разложении требовались бы миллионы операций на каждый блок. БПФ пользуется математической симметрией, чтобы выполнять этот процесс примерно за n log n операций (где n — количество сэмплов в блоке). Это можно делать достаточно быстро для того, чтобы выполнять процесс в телефоне сотни раз в секунду. Устройство перемещает это окно по аудио, выполняет БПФ для каждого фрагмента и соединяет получающиеся спектры один за другим. Результатом становится спектрограмма.

Показанное выше видео наглядно, но немного упрощено. В нём приведены только простые синтетические тона. Каждая нота — это чистая частота, волновая форма которой представляют собой идеальную синусоиду. К счастью, музыка обычно сложнее. Вспомните последнюю услышанную композицию, подумайте, сколько слоёв звука в ней было, каждый из которых отдельно и совместно состоит из множества частот.

Телефон сэмплирует входящий звук десятки тысяч раз в секунду (обычно с частотой 44100 Гц, которая также используется в CD). Каждый крошечный фрагмент этих сэмплов подвергается БПФ, а получающийся в результате формат уже может начинать анализировать система.

Чем меньше, тем больше

Даже на компьютере сохранение всех данных этой спектрограммы и поиск по ним происходили бы невероятно медленно, поэтому алгоритм поступает неожиданным образом: избавляется почти от всей информации.

В показанной ниже анимации при повышении порога слабые сигналы исчезают, а самые громкие пики сохранятся, оставляя только разбросанный набор точек. Эти точки представляют собой самые акустически значимые ориентиры записи.

Именно благодаря этому система становится устойчивой к шуму. Фоновый шум добавляет в спектрограмму низкоуровневую энергию, которая редко создаёт один самый громкий пик в какой-то из областей. Ориентиры — это частоты настолько доминирующие, что прорываются сквозь шум.

С другой стороны, из-за такого решения с «отпечатками пальцев» (фингерпринтами) Shazam плохо распознаёт песни, которые просто поёт пользователь. Скорее всего, при этом сгенерируется хэш, отличающийся от хэша оригинала, даже если он очень хорошо поёт! Новые системы на основе машинного обучения способны обрабатывать живое пение, сопоставляя мелодию, а не конкретные частоты.

Соединяем точки

Отдельная точка в этом «созвездии» сама по себе не особо полезна. Частота 1200 Гц в какой-то момент времени может встречаться в тысячах композиций. Но вот пара точек, допустим, 1200 Гц и 2400 Гц, разделённые ровно 0,3 секунды — это гораздо конкретнее.

Алгоритм назначает каждый пик по очереди якорем. Для каждого якоря он определяет целевую зону справа (окно времени и частоты) и соединяет якорь с каждым пиком внутри этой зоны. Каждая пара генерирует компактный хэш из этих трёх чисел: двух частот и разницы времени между ними.

Хэш — это короткая строка символов, используемая в качестве сокращённого кода: одни и те же три образца входных данных всегда генерируют один и тот же хэш, и даже небольшие изменения в одном из них генерирует совершенно иной. У Shazam и подобных ему систем есть способы учёта небольших вариаций, но поскольку хэши создаются на основе точных частот и таймингов, они, по сути, работают как отпечатки пальцев конкретной записи, а не песни. Из-за этого с ними сложнее сопоставлять каверы и ремиксы.

Для одной трёхминутной песни могут быть сгенерированы тысячи таких хэшей-отпечатков, которые хранятся в базе данных. Итак, телефон создал набор хэшей по своему пятисекундному клипу, а в базе данных есть миллионы хэшей почти всех популярных песен. Как же она находит совпадение?

Поиск идеального совпадения

Наивный подход: сначала песни

Мы интуитивно рассуждаем о музыке с точки зрения композиций. Если использовать такую ментальную модель, то нам бы пришлось искать каждую песню одну за другой, проверяя, пересекаются ли её хэши с хэшами из клипа пользователя. Эта работа выполняется за время O(N); в computer science это означает, что она будет всё медленнее с появлением в мире новых композиций.

Инвертированный индекс: сначала хэши

Компьютеры могут решать эту задачу наоборот. Вместо того, чтобы задавать вопрос: «Какая песня соответствует этой последовательности звуков?», телефон спрашивает: «Вот звуки, в каких песнях они есть?», и делает так для каждого хэша клипа. Принцип такой же, как у алфавитного указателя в конце книги: вместо того, чтобы перечитывать каждую страницу для нахождения слова мы переходим к слову и видим все страницы, на которых оно есть.

По сути, в этом случае для операции поиска требуется O(1), то есть время будет приблизительно одинаковым вне зависимости от того, сто у вас песен или сто миллионов. Точнее, телефон переходит прямо к адресу каждого хэша, а не сканирует композиции, а количество возможных хэшей достаточно велико, чтобы каждый адрес содержал всего несколько записей даже в случае миллионов песен.

Однако нахождения общих хэшей недостаточно. Популярный паттерн ударных может создать один и тот же хэш в сотнях песен. Последняя проверка заключается в сопоставлении таймингов. Если в клипе пользователя расстояние между хэшами 17403C и 19A998 равно 1,2 секунды, то в соответствующей композиции они тоже должны быть разделены 1,2 секунды. Если временные различия между всеми совпадающими хэшами согласуются и совпадений достаточно, то система будет уверена в том, что нашла нужную песню.

Система основана на операциях, с которыми компьютеры справляются очень хорошо: на сравнении чисел и поиске адресов. Весь процесс поиска среди миллионов композиций занимает доли секунды.

Более современные решения

В большинстве сервисов идентификации песен наподобие Shazam аудиоклип передаётся на сервер, где хранится огромная база данных отпечатков пальцев. Сервер ищет соответствие и возвращает результат. Такая система работает, потому что база данных огромна и динамична, а поиск по ней требует серьёзных вычислительных мощностей.

Существуют и более новые решения. Распознавание Apple и фича Google Pixel «Now Playing» способны работать локально на самом телефоне. В них используются базы данных меньшего размера и оптимизированные модели, пожертвовавшие исчерпывающими данными ради скорости; они обладают более сложными моделями машинного обучения с повышенной устойчивостью к шуму и вариативности в аудио.

Как и в любой системе, здесь приходится идти на компромиссы. Система поиска в устройстве быстрее и работает без подключения к Интернету, но имеет гораздо меньшую по размерам базу данных и ей приходится скачивать новые данные в случае изменения местоположения. Хитовые песни в Японии будут отличаться от хитов в США, и наоборот.

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

Думаю, мне нравится этот алгоритм тем, что это умное решение, в то же время остающееся детерминированным и прозрачным. Подобные решения занимают в моём сердце особое место, ведь сегодня слишком многие технологии используют чёрные ящики моделей машинного обучения, которые, несмотря на свою мощь, не обладают тем же изяществом и понятностью.

Данные для этой статьи я брал из научной статьи Эйвери Ванга An Industrial-Strength Audio Search Algorithm. Если вы хотите глубже изучить обработку сигнала и архитектуру системы, лежащей в основе Shazam, то рекомендую прочитать эту статью.