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

Сохранение слепка песни

Давайте разберем на простом примере, как работает эта часть алгоритма. 

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

Шаг 1: я записываю 10-секундную часть песни с телефона, играющую, например, по телевизору.

Шаг 2: я вычисляю спектрограмму этой песни.

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

И так нужно перебрать каждую песню, пока не получится последнее наложение. Но что делать, если идеального совпадения нет? В таком случае можно задать порог совпадения, к примеру, 90%: то есть если я нашел совпадение с 90%-ой точностью между отрывком и целой песней, то, скорее всего, это и есть правильная песня, потому что 10% от общего сходства вполне может быть обусловлено внешним шумом.

Такой алгоритм, конечно, работает хорошо, но он требует проводить очень много вычислений: ведь нужно сопоставлять этот 10-секундный отрывок каждой песне в коллекции. В среднем музыка содержит 3 пиковых частоты за каждую 0.1 секунду, поэтому отфильтрованная спектрограмма 10-секундного отрывка имеет 300 частотно-временных точки. В худшем случае вам понадобится 300*300*30*S операций, где S — количество секунд музыки в вашей коллекции. Если у вас всего 30000 песен (7*10⁶ секунд), то это будут квадриллионы операций. А ведь у Shazam коллекция как минимум в 40 миллионов треков, что делает такие вычисления даже на очень мощных серверах отнюдь не моментальными.

Итак, как же Shazam делает это эффективнее?

Целевые зоны

Вместо того, чтобы сравнивать каждую частотно-временную точку на спектрограмме одну за другой, идея состоит в том, чтобы искать несколько точек одновременно — в Shazam эта группа точек называется целевой зоной. Для упрощения я установил размер целевой зоны в 5 точек.

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

• Если две частотно-временные точки имеют одинаковое время, то точка с самой низкой частотой идет первой.
• Впереди идут точки с самым маленьким временем. 

Используя эти правила, можно пронумеровать точки на наших спектрограммах (говоря проще — сначала идет нумерация по столбцам, потом по строкам):

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

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

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

Генерация адресов точек

Теперь у нас есть несколько целевых зон — и что дальше? Мы создаем для каждой точки адрес, основанный на этих целевых зонах. Но, чтобы создать адреса, нам нужно опираться на какую-то точку для каждой целевой зоны. Для примера — пусть это будет 3-я точка перед каждой целевой зоной (адрес целевой точки может быть любым, главное — одинаковым для всех зон и вне для каждой из зоны, дабы не получить одни нули).

Вот так выглядят две целевые зоны с их опорными точками:
Формула получения адреса каждой точки выглядит так:

[«Частота опорной точки», «Частота целевой точки», «Разница во времени между опорной точкой и целевой точкой»]

Например, для фиолетовой зоны эта формула работает так:

• Адрес точки 6 — это «Частота опорной точки 3», «Частота точки 6», «Разница во времени между 3 и 6» — [10; 30; 1].
• Адрес точки 7 — [10; 20; 2].

Обе эти точки появились и в коричневой целевой зоне, их адреса в ней [10; 30; 2] для 6-ой точки и [10; 20; 3] для 7-ой точки.

Я говорил об адресах, не так ли? Значит, эти адреса связаны с чем-то еще, и в случае полных песен (то есть только на стороне сервера) эти адреса связаны со следующей парой — [«Абсолютное время опорной точки в песне», «ID песни»]. В нашем простом примере мы имеем следующий результат:

[10; 30; 1] -> [2; 1]

[10; 30; 2] -> [2; 1]

[10; 30; 2] -> [1; 1]

[10; 30; 3] -> [1; 1]

Если мы применим эту логику для всех точек всех целевых зон всех спектрограмм песен, мы получим очень большую таблицу с двумя столбцами

• Адреса точек;
• Пары («Время опорной точки», «ID песни»).

И вот эта таблица как раз и является базой слепков песен в Shazam. Если песня содержит 30 пиковых частот в секунду, а размер целевой зоны равен 5, то размер этой таблицы составляет всего 5*30*S (S — все также количество секунд музыки в коллекции). Раньше это было 300*300*30*S — как видите, мы упростили алгоритм на 4 порядка — очень и очень существенно.

Как вы помните, мы использовали БПФ с 1024 сэмплами, что дает нам только 512 возможных значений частоты — их можно закодировать 9 битами (2⁹=512). Предполагая, что разница во времени между опорной точкой и точкой целевой зоны составляет миллисекунды, оно никогда не будет больше 16 секунд, потому что это будет означать песню с 16 секундами тишины (или очень низкого звука). Таким образом, эта дельта (разница) во времени может быть закодирована 14 битами (2¹⁴=16384). В итоге адрес может быть закодирован всего 32 битами:

• 9 бит для «частоты опорной точки»
• 9 бит для «частоты точки в целевой зоне»
• 14 бит для «дельты между опорной и целевой точками»

Используя ту же логику, получаем, что пару («Время опорной точки», «ID песни») можно закодировать 64 битами (по 32 бита для каждой части — это дает нам по 4 миллиарда единиц данных — согласитесь, песен на Земле все же меньше, да и по времени это дает нам сотни часов — песни звучат куда меньше).

Таким образом, таблица слепков песен может быть реализована как простой массив из списка 64-битных целых чисел, где:

• Индексом массива является 32-разрядный целочисленный адрес;
• Cписок из 64-битных целых чисел — это все пары для этого адреса.

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

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