2

Как работает Shazam: алгоритм получения базы данных слепков песен



Эта часть статьи будет предпоследней — мы поговорим о том, как создается база данных слепков песен на серверах 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].
Обе эти точки появились и в коричневой целевой зоне, их адреса в ней [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 битами (29=512). Предполагая, что разница во времени между опорной точкой и точкой целевой зоны составляет миллисекунды, оно никогда не будет больше 16 секунд, потому что это будет означать песню с 16 секундами тишины (или очень низкого звука). Таким образом, эта дельта (разница) во времени может быть закодирована 14 битами (214=16384). В итоге адрес может быть закодирован всего 32 битами:
  • 9 бит для «частоты опорной точки»
  • 9 бит для «частоты точки в целевой зоне»
  • 14 бит для «дельты между опорной и целевой точками»
Используя ту же логику, получаем, что пару («Время опорной точки», «ID песни») можно закодировать 64 битами (по 32 бита для каждой части — это дает нам по 4 миллиарда единиц данных — согласитесь, песен на Земле все же меньше, да и по времени это дает нам сотни часов — песни звучат куда меньше).

Таким образом, таблица слепков песен может быть реализована как простой массив из списка 64-битных целых чисел, где:
  • Индексом массива является 32-разрядный целочисленный адрес;
  • Cписок из 64-битных целых чисел — это все пары для этого адреса.
Иными словами, мы инвертировали (перевернули) таблицу слепков, что дало нам временную сложность всего лишь O(1) (если вкратце — очень эффективный и быстрый поиск).

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

Рекомендации

Рекомендации

Будь в курсе последних новостей из мира гаджетов и технологий

Мы в соцсетях

Комментарии

Cowboy
+285
Егор, я так понимаю, у Вас случайно так получилось, что тут шумиха вокруг Шазам, и Вы с этим циклом статей. )
пришлось перечитать, чтобы понять её. вроде все понял, но как ID получатся, я не понял, это 1,2; 1;2 — это такие ID?
14 декабря 2017 в 02:37
#
+1764
Пользователь удален Cowboy
Смотрите, у нас есть две абсолютные величины — это время опорной точки в треке и ID трека. В моем примере время опорных точек это 1 и 2, а трек у меня в примере только один, поэтому и ID трека только 1. В итоге абсолютные значения это [1; 1] и [2; 1]. Если треков будет тысячи, то, к примеру, для 10ой опорной точки в 543ем треке формула будет выглядеть как [10; 543]. Просто в чем суть — мы хотим перейти от переменных величин, где у нас есть, к примеру, разница во времени между опорной и целевой точкой, к абсолютным, то есть неизменным — к времени опорных точек и идентификаторам песен: они зависят только от нашего трека и от алгоритма выбора опорных точек.
14 декабря 2017 в 10:49
#
Cowboy
+285
теперь понятно, спасибо! ждём четвертую часть)
14 декабря 2017 в 21:49
#

Читайте также