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

Поиск по базе слепков песен

Теперь у нас есть отличная структура данных на стороне сервера, но как нам ее использовать? 

Для выполнения поиска в записанном звуковом файле на устройстве выполняется все тот же алгоритм получения слепка, чтобы создать структуру адрес-значение, но она немного отличается от той, которая на стороне сервера — по понятным причинам тут нет ID песни:

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

Затем эти данные отправляются на сервер, в Shazam. Если у нас как и раньше 300 точек на 10-секундной спектрограмме и размер целевой зоны составляет 5 точек, то в Shazam будет отправлено 1500 адресов.

Каждый адрес из записи используется для поиска в базе данных слепков для связанных пар [«Абсолютное время опорной точки в песне»; «ID песни»]. С точки зрения временной сложности, предполагая, что база данных отпечатков пальцев находится в памяти, стоимость поиска зависит от количества адресов, отправленных Shazam (1500 в нашем случае). Этот поиск возвращает большое количество пар, скажем, M штук.

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

Фильтрация результатов

Следующая задача — отфильтровать результаты поиска пар (у нас их M штук), сохранив только те пары в треках, которые имеют максимальное количество целевых зон, общих с записью отрывка песни на устройстве.

Например, предположим, что наш поиск вернул такой результат:

• 100 пар из песни 1, которая имеет 0 целевых зон, схожих с записью
• 10 пар из песни 2, которая имеет 0 целевых зон, схожих с записью
• 50 пар из песни 5, которая имеет 0 целевых зон, схожих с записью
• 70 пар из песни 8, которая имеет 0 целевых зон, схожих с записью
• 83 пары из песни 10, которая имеет 30 целевых зон, схожих с записью
• 210 пар из песни 17, которая имеет 100 целевых зон, схожих с записью
• 4400 пар из песни 13, которая имеет 280 целевых зон, схожих с записью
• 3500 пар из песни 25, которая имеет 400 целевых зон, схожих с записью

Наша 10-секундная запись имеет, приблизительно, 300 целевых зон. Поэтому в лучшем случае:

• песня 1 и запись будет иметь коэффициент соответствия 0%
• песня 2 и запись будет иметь коэффициент соответствия 0%
• песня 5 и запись будет иметь коэффициент соответствия 0%
• песня 8 и запись будет иметь коэффициент соответствия 0%
• песня 10 и запись будет иметь коэффициент соответствия 10%
• песня 17 и запись будет иметь коэффициент соответствия 33%
• песня 13 и запись будет иметь коэффициент соответствия 91,7%
• песня 25 и запись будет иметь коэффициент соответствия 100%

Мы оставим только пары из песен 13 и 25. Хотя песни 1, 2, 5 и 8 имеют множество пар, совпадающих с записью, ни одна из них не образует по крайней мере одну целевую зону (5 точек), общую с записью. Треки 10 и 17 имеют несколько общих с записью целевых зон, однако их процент достаточно низок, поэтому мы их тоже не берем. Этот шаг может отфильтровать множество ложных результатов, потому что база слепков песен в Shazam имеет много пар для одного и того же адреса, и вы можете легко найти пары с одинаковыми адресами, которые не принадлежат к одной и той же целевой зоне. Если вы не понимаете, почему так, прочтите конец предыдущей части статьи: адрес [10; 30; 2] используется двумя частотно-временными точками, которые не принадлежат к одной и той же целевой зоне. Если в записи также есть [10; 30; 2], то, по крайней мере, одна из этих двух пар будет отфильтрована на этом этапе.

Сложность этого этапа не превышает O(M) — то есть с увеличением параметра M временная сложность алгоритма растет не быстрее, чем некоторая константа, умноженная на M. Иными словами — сложность достаточно низкая. Реализуется этот этап с помощью хэш-таблицы, то есть таблицы, в которой хранятся пары (ключ, значение), и с ними могут выполняться три операции: добавление/удаление пары и поиск нужной пары. В нашем случае ключ — пара (ID трека, Абсолютное время опорной точки в треке) и количество раз, когда эта пара появляется в результате:

• Мы перебираем все наши пары M и подсчитываем (в хеш-таблице) количество раз, когда эта пара присутствует в записи.
• Мы удаляем все пары (т. е. ключи хэш-таблицы), которые появляются менее 4 раз (другими словами, мы удаляем все точки, которые не образуют целевую зону)*.
• Мы подсчитываем количество раз, когда ID песни является частью ключа в хеш-таблице (т. е. мы подсчитываем количество полных целевых зон в песне. Поскольку наши пары M есть в базе данных слепков, то их целевые зоны также находятся в записи).
  
• Мы сохраняем только тот результат, где номер целевой зоны не выше 300*K (300 — это количество целевых зон в записи, и мы уменьшаем это число с помощью коэффициента из-за шума).
• Остальные результаты мы помещаем в новую хеш-таблицу, индексом которой является ID песни (этот хэш-файл будет полезен для следующего шага).
  

* Идея заключается в том, чтобы искать целевую зону, созданную опорной точкой в ​​песне. Эта опорная точка может быть определена идентификатором принадлежащей ей песни и абсолютным временем ее появления. Я сделал приближение, потому что в песне вы можете одновременно иметь несколько опорных точек. Поскольку мы имеем дело с фильтрованной спектрограммой, у вас не будет много опорных точек одновременно. Но ключ [ID песни, Абсолютное время опорной точки в песне] соберет все целевые зоны, созданные этими опорными точками.

Согласованность времени

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

Последний этап работы алгоритма — упорядочивание по времени. Идея такова:

• Вычислить для каждой оставшейся песни ноты и их абсолютное время в песне.
• Сделать то же самое для записи.
• Если ноты в песне и записи являются согласованными во времени, мы должны найти соотношение такого типа: «абсолютное время ноты в песне = абсолютное время ноты в записи + дельта (некоторая разница)», где дельта — время начала части песни, которая соответствует записи.
• Для каждой песни нам нужно найти дельту, которая максимизирует количество нот, которые согласуются с этим соотношением времени.
• Затем мы выбираем песню с максимальным количеством согласованных с записью нот.

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

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

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

[«Частота опорной точки», «Частота целевой точки», «Разница во времени между опорной точкой и нужной точкой»] -> [«Абсолютное время опорной точки в записи»; «ID песни»]

Для всех остальных песен необходимо выполнить следующий процесс:

• Для каждого адреса в записи мы получаем связанное с ним значение в песне, и вычисляем дельту = «абсолютное время опорной точки в записи» - «абсолютное время опорной точки в песне», и помещаем дельту в «список дельта».
• Возможно, что адрес в записи связан с кратными значениями в песне (т. е. с несколькими точками в разных целевых зонах песни), в этом случае мы вычисляем дельту для каждого связанного значения и мы помещаем ее в «список дельт».
• Для каждого значения дельты в «списке дельт» мы подсчитываем, сколько раз она встречается (другими словами, мы рассчитываем для каждой дельты количество нот, соблюдающих правило «абсолютное время ноты в песне = абсолютное время ноты в записи + дельта»).
• Мы сохраняем наибольшее значение дельты (что дает нам максимальное количество нот, которые согласованы между записью и песней).

Из всех песен мы сохраняем песню с максимальным количеством согласованных по времени нот. Если эта согласованность выше «количества нот в записи»*K, то эта песня является правильной.

Дальше нам нужно просто искать метаданные песни («имя исполнителя», «название песни», «URL в iTunes», «URL в Amazon», ...), связанные с идентификатором песни, и возвращать эти данные пользователю.

Поговорим о сложности

Алгоритм выше действительно сложнее, чем простой перебор, который я описал ранее, так что давайте посмотрим, что мы выиграли по времени поиска. Расширенный поиск представляет собой поэтапный подход, который уменьшает сложность на каждом этапе.

Для понимания я вспомню все сделанные мною выборы и введу новые, чтобы упростить ситуацию:

• У нас есть 512 возможных частот;
• В среднем песня содержит 30 пиковых частот в секунду;
• Поэтому 10-секундная запись содержит 300 частотно-временных точек;
• S — количество секунд музыки со всех песен;
• Размер целевой зоны — 5 нот;
• (Новое) Я предполагаю, что разница во времени между целевой и ее опорной точкой лежит в промежутке от 0 до 10 мс;
• (Новое) Я предполагаю, что генерация адресов распределена равномерно, что означает, что для любого адреса [X, Y, T] имеется одинаковое количество пар, где X и Y — одна из 512 частот, а T — от 0 до 10 мс.

Первый шаг, поиск, требует только 5 * 300 = 1500 операций.

Величина числа пар M является итогом всех 1500 операций:

M = (5 * 300) * (S * 30 * 5 * 300) / (512 * 512 * 2)

На втором этапе фильтрация результатов может быть выполнена в M операций. В конце этого шага у нас есть N нот, находящихся в Z песнях. Без статистического анализа музыкальной коллекции невозможно получить значение N и Z, однако очевидно, что N действительно меньше, чем M и Z, даже для 40-миллионной базы данных песен, такой как Shazam.

Последний шаг — анализ временного согласования записи в Z песнях. Мы предположим, что каждая песня имеет примерно одинаковое количество нот: N / Z. В худшем случае (запись, которая получается из песни, которая содержит только одну ноту, воспроизводимую непрерывно), сложность одного анализа (5 * 300) * (N / Z).

Временная стоимость Z песен составляет 5 * 300 * N.

Так как N << M, реальная стоимость этого поиска равна M = (300 * 300 * 30 * S) * (5 * 5) / (512 * 512 * 2).

Если вы помните, стоимость простого перебора была 300 * 300 * 30 * S, то есть новый поиск в 20 000 раз быстрее!

Примечание. Реальная сложность зависит от распределения частот внутри песен в коллекции, но это простое исчисление дает нам хорошее представление о реальной сложности.

Улучшения и компромиссы

Документ от том, как работает Shazam, относится к 2003 году, что означает, что связанное с ним исследование еще более старое. В 2003 году 64-битные процессоры только-только были выпущены на потребительский рынок. Вместо того, чтобы использовать одну опорную точку для целевой зоны, как предлагается в документе (из-за ограниченного размера 32-разрядного целого числа), можно использовать 3 опорные точки (например, 3 точки как раз перед целевой зоной) и сохранить адрес точки в целевой зоне как 64-битовое число — это значительно улучшит время поиска. Действительно, поиск будет заключаться в том, чтобы найти 4 ноты в песне, отделенные на дельта_1, дельта_2 и дельта_3 секунд, что означает, что количество пар M будет серьезно меньше, чем то, которое мы только что вычислили.

Большим преимуществом этого поиска слепков песен является его высокая масштабируемость:

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

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

• Уменьшают влияние шума;
• Уменьшают время поиска;
• Увеличивают точность (уменьшают число ложных положительных результатов).

Но это уже за пределами доступной для обычного пользователя информации.

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