Эта часть статьи будет предпоследней — мы поговорим о том, как создается база данных слепков песен на серверах Shazam. Ну и в заключительной статье поговорим о том, как происходит сравнение слепка, полученного на устройстве, с этой базой данных. Как обычно — я рекомендую прочесть все предыдущие части для лучшего понимания материала.
Давайте разберем на простом примере, как работает эта часть алгоритма.
Предварительный шаг: я сначала компилирую базу данных фильтрованных спектрограмм всех песен на моем компьютере (то есть для каждой песни получаю картинку из последней статьи).
Шаг 1: я записываю 10-секундную часть песни с телефона, играющую, например, по телевизору.
Шаг 2: я вычисляю спектрограмму этой песни.
Шаг 3: я сравниваю эту «маленькую» спектрограмму с «полной» спектрограммой каждой песни на моем ПК. Как я могу сравнить 10-секундную спектрограмму отрывка со спектрограммой 180-секундной песни? Давайте обратимся к картинкам:
«Визуально говоря», мне нужно наложить спектрограмму отрывка на полную песню так, чтобы они совпали:
Как видно, хотя некоторые самые громкие частоты совпали на первых двух наложениях, идеально подходит только последнее, так как тут совпадают все пиковые частоты и на отрывке песни, и на спектрограмме полной песни.
И так нужно перебрать каждую песню, пока не получится последнее наложение. Но что делать, если идеального совпадения нет? В таком случае можно задать порог совпадения, к примеру, 90%: то есть если я нашел совпадение с 90%-ой точностью между отрывком и целой песней, то, скорее всего, это и есть правильная песня, потому что 10% от общего сходства вполне может быть обусловлено внешним шумом.
Такой алгоритм, конечно, работает хорошо, но он требует проводить очень много вычислений: ведь нужно сопоставлять этот 10-секундный отрывок каждой песне в коллекции. В среднем музыка содержит 3 пиковых частоты за каждую 0.1 секунду, поэтому отфильтрованная спектрограмма 10-секундного отрывка имеет 300 частотно-временных точки. В худшем случае вам понадобится 300*300*30*S операций, где S — количество секунд музыки в вашей коллекции. Если у вас всего 30000 песен (7*106 секунд), то это будут квадриллионы операций. А ведь у Shazam коллекция как минимум в 40 миллионов треков, что делает такие вычисления даже на очень мощных серверах отнюдь не моментальными.
Итак, как же Shazam делает это эффективнее?
Целевые зоны
Вместо того, чтобы сравнивать каждую частотно-временную точку на спектрограмме одну за другой, идея состоит в том, чтобы искать несколько точек одновременно — в Shazam эта группа точек называется целевой зоной. Для упрощения я установил размер целевой зоны в 5 точек.
Чтобы быть уверенным в том, что и отрывок, и полная песня, будут генерировать одни и те же целевые зоны, нам понадобятся соотношения между частотно-временными точками в фильтрованной спектрограмме. Вот они:
- Если две частотно-временные точки имеют одинаковое время, то точка с самой низкой частотой идет первой.
- Впереди идут точки с самым маленьким временем.
Теперь, когда спектрограммы внутренне упорядочены, мы можем создавать целевые зоны на разных спектрограммах по следующему правилу:
Чтобы генерировать целевые зоны на спектрограмме, нам нужно для каждой временной точки создать группу, состоящую из нее и 4-ех следующих точек.
В итоге мы получим столько целевых зон, сколько и точек, причем это верно и для песен, и для записи:
На этой упрощенной спектрограмме можно увидеть целевые зоны, созданные по этому алгоритму. Поскольку размер каждой зоны равен пяти, большинство точек принадлежат пяти целевым зонам (кроме точек в начале и в конце).
Генерация адресов точек
Теперь у нас есть несколько целевых зон — и что дальше? Мы создаем для каждой точки адрес, основанный на этих целевых зонах. Но, чтобы создать адреса, нам нужно опираться на какую-то точку для каждой целевой зоны. Для примера — пусть это будет 3-я точка перед каждой целевой зоной (адрес целевой точки может быть любым, главное — одинаковым для всех зон и вне для каждой из зоны, дабы не получить одни нули).
Вот так выглядят две целевые зоны с их опорными точками:
Формула получения адреса каждой точки выглядит так:
[«Частота опорной точки», «Частота целевой точки», «Разница во времени между опорной точкой и целевой точкой»]
Например, для фиолетовой зоны эта формула работает так:
- Адрес точки 6 — это «Частота опорной точки 3», «Частота точки 6», «Разница во времени между 3 и 6» — [10; 30; 1].
- Адрес точки 7 — [10; 20; 2].
Я говорил об адресах, не так ли? Значит, эти адреса связаны с чем-то еще, и в случае полных песен (то есть только на стороне сервера) эти адреса связаны со следующей парой — [«Абсолютное время опорной точки в песне», «ID песни»]. В нашем простом примере мы имеем следующий результат:
[10; 30; 1] -> [2; 1]
[10; 30; 2] -> [2; 1]
[10; 30; 2] -> [1; 1][10; 30; 3] -> [1; 1]
Если мы применим эту логику для всех точек всех целевых зон всех спектрограмм песен, мы получим очень большую таблицу с двумя столбцами
- Адреса точек;
- Пары («Время опорной точки», «ID песни»).
Как вы помните, мы использовали БПФ с 1024 сэмплами, что дает нам только 512 возможных значений частоты — их можно закодировать 9 битами (29=512). Предполагая, что разница во времени между опорной точкой и точкой целевой зоны составляет миллисекунды, оно никогда не будет больше 16 секунд, потому что это будет означать песню с 16 секундами тишины (или очень низкого звука). Таким образом, эта дельта (разница) во времени может быть закодирована 14 битами (214=16384). В итоге адрес может быть закодирован всего 32 битами:
- 9 бит для «частоты опорной точки»
- 9 бит для «частоты точки в целевой зоне»
- 14 бит для «дельты между опорной и целевой точками»
Таким образом, таблица слепков песен может быть реализована как простой массив из списка 64-битных целых чисел, где:
- Индексом массива является 32-разрядный целочисленный адрес;
- Cписок из 64-битных целых чисел — это все пары для этого адреса.
На этом на сегодня все, в следующей части мы, как я уже говорил, поговорим о том, как происходит сравнение слепка, полученного на устройстве, с базой данных, описанной выше — пожалуй, самая интересная часть из всего цикла статей по Shazam.