5. ПОИСК В БАЗЕ ДАННЫХ

5.1 Алгоритм поиска

Поиск полученных отпечатков в базе данных отпечатков является нетривиальной задачей. Вместо поиска немногих точных отпечатков (что просто!), должны быть найдены наиболее похожие отпечатки. Проиллюстрируем это некоторыми числами на основе предложенной схемы отпечатков. Рассмотрим базу данных отпечатков умеренного размера, содержащую 10,000 песен со средней длиной в 5 минут. Это соответствует примерно 250 миллионам суб-отпечатков. Для выявления блока отпечатков, полученного от неизвестного куска звука, необходимо найти в базе данных наиболее похожий блок отпечатков. Другими словами, необходимо найти такую позицию в 250 миллионах суб-отпечатков, где число ошибочных битов минимально. Это, конечно, возможно простым прямым поиском. Однако это потребует 250 миллионов сравнений блоков отпечатков. При использовании современного ПК может быть достигнута скорость примерно в 200,000 сравнений блоков отпечатков в секунду. Поэтому общее время поиска для нашего примера будет порядка 20 минут! Это показывает, что для практического применения поиск с помощью грубой силы не является жизнеспособным решением.

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

В простой версии улучшенного алгоритма поиска позиции-кандидаты генерируются на основе предположения, что очень вероятно, что по крайней мере один суб-отпечаток имеет точное соответствие в оптимальной позиции в базе данных [3][5]. Если это предположение справедливо, должны быть проверены только те позиции, где один из 256 суб-отпечатков блока отпечатков запроса имеет точное соответствие. Чтобы убедиться в справедливости предположения, график на Рисунке 4 показывает количество ошибочных битов на суб-отпечаток для отпечатков, изображённых на Рисунке 2. Это показывает, что действительно существует суб-отпечаток, который не содержит никаких ошибок. На самом деле не содержат ошибок 17 из 256 суб-отпечатков. Если предположить, что это "оригинальный" отпечаток Рисунка 2a, действительно загруженный в базу данных, эта позиция будет среди выбранных позиций-кандидатов для "отпечатка MP3@128Kbps" Рисунка 2b.

Рисунок 4. Число ошибочных битов на суб-отпечаток для “версии MP3@128Kbps” фрагмента ‘O Fortuna’ Carl Orff.

Рисунок 5. Число ошибочных битов на суб-отпечаток (серая линия) и надёжность наиболее надёжного ошибочного бита (чёрная линия) для “версии MP3@32Kbps” ‘O Fortuna’ Carl Orff.

Позиции в базе данных, где находится определённый 32-х разрядный отпечаток, извлекаются с помощью архитектуры базы данных Рисунка 6. База данных отпечатков содержит таблицу поиска (lookup table, LUT) со всеми возможными 32-х разрядными суб-отпечатками в качестве записи. Каждая запись указывает на список с указателями на позиции в реальных списках отпечатков, в которых расположены соответствующие 32-х разрядные суб-отпечатки. В практических системах с ограниченным объёмом памяти (например, ПК с 32-х разрядным процессором Intel имеет предел памяти в 4 ГБ) таблица поиска, содержащая 232 записей, часто невозможна, или непрактична, или и то и другое. Кроме того, таблица поиска будет заполнена редко, потому что в памяти может находиться только ограниченное число песен. Таким образом, на практике вместо таблицы поиска используется хэш-таблица [19].

Рисунок 6. Строение базы данных отпечатков.

Давайте снова посчитаем среднее количество сравнений блоков отпечатков на идентификацию для базы данных из 10,000 песен. Поскольку база данных содержит около 250 миллионов суб-отпечатков, среднее число позиций в списке будет 0.058 (=250*106/232). Если предположить, что все возможные суб-отпечатки равновероятны, средним числом сравнений отпечатков на идентификацию является всего 15 (=0.058*256). Однако, на практике наблюдается, что из-за неравномерного распределения суб-отпечатков количество сравнений отпечатков увеличивается примерно в 20 раз. В среднем необходимо 300 сравнений, что даёт на современных ПК среднее время поиска 1.5 мс. Таким образом, таблица поиска может быть реализована, но это не влияет на время поиска. С дорогой таблицей поиска предложенный алгоритм поиска примерно в 800,000 раз быстрее, чем подход прямого поиска.

Наблюдательный читатель может спросить: "Но что, если ваши предположение, что один из суб-отпечатков не содержит ошибок, не выполняется"? Ответом является то, что данное предположение почти всегда выполняется для звуковых сигналов с "умеренными" искажениями звукового сигнала  (смотрите также Раздел 5.2). Однако, для сильно искажённых сигналов предположение действительно не всегда справедливо. Пример графика числа ошибочных битов на суб-отпечаток для блока отпечатков, который не содержит ни одного безошибочного суб-отпечатка, показан на Рисунке 5. Однако, есть суб-отпечатки, которые содержат только одну ошибку. Таким образом, вместо проверки только тех позиций в базе данных, где встречается один из 256 суб-отпечатков, мы также можем проверить все позиции, в которых встречаются суб-отпечатки, находящиеся на расстоянии Хэмминга, равном единице (то есть переключен один бит), для всех 256 суб-отпечатков. Это приведёт к числу сравнений отпечатков в 33 раза большему, которое всё ещё приемлемо. Однако, если мы хотим справиться с ситуациями, в которых, например, минимальное количество ошибочных битов на суб-отпечаток равно трём (это может произойти в приложении для мобильного телефона), число сравнений отпечатков будет увеличено в 5489 раз, что приведёт к неприемлемым затратам времени для поиска. Обратите внимание, что наблюдаемый фактор неоднородности 20 снижается с увеличением числа переключенных битов. Если, например, для переключения используются все 32 бита суб-отпечатков, мы в конце концов снова придём к прямому перебору, получив коэффициент умножения 1.

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

Суб-отпечатки получаются путём сравнения и оценки порога разности энергий (смотрите блок получения битов на Рисунке 1). Если разность энергий очень близка к порогу, достаточно вероятно, что бит был получен неправильно (ненадёжный бит). С другой стороны, если разность энергий гораздо больше порога, вероятность неправильности бита мала (надёжный бит). Получив информацию о надёжности для каждого бита суб-отпечатка, можно расширить данный отпечаток до списка вероятных суб-отпечатков. Если считать, что один из наиболее вероятных суб-отпечатков имеет точное соответствие в оптимальной позицией в базе данных, такой блок отпечатков может быть идентифицирован, как раньше. Битам назначается рейтинг надёжности от 1 до 32, где 1 обозначает самый ненадёжный, а 32 -  самый надёжный бит.

Это приводит к простому способу создания списка наиболее вероятных суб-отпечатков переключением только самых ненадёжных битов. Точнее, список состоит из всех суб-отпечатков, которые имеют N фиксированных самых надёжных бит, а все другие изменяются. Если достоверность информации является безупречной, можно ожидать, что в случае, когда суб-отпечаток имеет 3 ошибочных бита, биты с надёжностью 1, 2 и 3 являются ошибочными. Если это так, блоки отпечатков, где минимальное количество ошибочных битов на суб-отпечаток равно 3, могут быть идентифицированы созданием позиций-кандидатов с помощью только 8 (=23) суб-отпечатков на суб-отпечаток. По сравнению с коэффициентом 5489, полученном при использовании всех суб-отпечатков с расстоянием Хэмминга, равным 3 для генерации позиций-кандидатов, это - улучшение с коэффициентом около 686.

На практике достоверность информации не является безупречной (например, бывает так, что бит с низкой надёжностью получен правильно и наоборот), и, следовательно, улучшение менее впечатляющее, но всё же значительное. Например, это можно увидеть на Рисунке 5. Минимальное количество ошибочных битов на суб-отпечаток равно единице. Как уже упоминалось ранее, такой блок отпечатков может быть идентифицирован созданием в 33 раза большего числа позиций-кандидатов. Рисунок 5 также содержит график надёжности для самого надёжного бита, который получен ошибочно. Надёжность получена из версии MP3@32Kbps с помощью предложенного метода. Мы видим, что первый суб-отпечаток содержит 8 ошибок. Эти 8 бит не являются самыми ненадёжными битами, поскольку один из ошибочных битов имеет назначенную надёжность 27. Таким образом, информация о надёжности не всегда надёжна. Однако, если мы рассмотрим суб-отпечаток 130, который имеет только один ошибочный бит, то увидим, что назначенная надёжность ошибочного бита равна 3. Поэтому этот блок отпечатков указывал бы на правильное расположение в базе данных отпечатков при переключении только 3-х наиболее ненадёжных битов. Таким образом, эта песня была бы определена правильно.

Мы закончим этот подраздел вновь ссылаясь на Рисунок 6 и давая пример того, как работает предложенный алгоритм поиска. Последний извлечённый суб-отпечаток из блока отпечатков на Рисунке 6 это 0x00000001. Первый блок отпечатков сравнивается с теми позициями в базе данных, где находится суб-отпечаток 0x00000001. Для суб-отпечатка 0x00000001 LUT указывает только на одну позицию, относящуюся к позиции p в песне 1. Вычислим теперь BER между 256-ю полученными суб-отпечатками (блоком отпечатков) и значениями суб-отпечатков песни 1 от позиции p-255 до позиции p. Если BER ниже порога в 0.35, высока вероятность того, что полученный блок отпечатков происходит от песни 1. Однако, если это не так, либо в базе данных нет песни, либо этот суб-отпечаток содержит ошибку. Допустим напоследок и что бит 0 является наименее надёжным битом. Следующим наиболее вероятным кандидатом является суб-отпечаток 0x00000000. По-прежнему ссылаясь на Рисунок 6, суб-отпечаток 0x00000000 имеет две возможные позиции-кандидаты: одна в песне 1, а другая в песне 2. Если блок отпечатков имеет BER ниже порога по отношению к связанному блоку отпечатков в песне 1 или 2, то совпадение будет объявлено соответственно для песни 1 или 2. Если ни одна из двух позиций-кандидатов не даёт BER ниже порога, то либо можно использовать другие возможные суб-отпечатки  для генерации большего числа позиций-кандидатов, либо переключиться на один из 254 оставшихся суб-отпечатков для повтора процесса. Если для создания позиций-кандидатов были использованы все 256 суб-отпечатков и их наиболее вероятные суб-отпечатки, и не было найдено соответствия ниже порога, алгоритм решает, что не может опознать песню.

5.2 Экспериментальные результаты

Таблица 2 показывает, как много из сгенерированных позиций-кандидатов указывают на соответствующий блок отпечатков в базе данных для того же набора искажённых сигналов, использованного в экспериментах по надёжности. Мы будем называть это число как число совпадений в базе данных. Число совпадений должно быть равно единице или больше, чтобы идентифицировать блок отпечатков и может быть максимально равно 256 в случае, когда все суб-отпечатки создают верную позицию-кандидат. Первое число в каждой ячейке является числом совпадений в случае, когда для создания позиций-кандидатов использовались только сами суб-отпечатки (то есть программная информация декодирования не используется). Заметим, что большинство блоков отпечатков могут быть идентифицированы, так как произошло одно или более совпадений. Однако, несколько блоков отпечатков, главным образом происходящие из более серьёзно искажённого звука, например, в GSM с C/I равным 4 дБ, не генерируют никаких совпадений. Такую настройку алгоритма поиска можно использовать в таких приложениях, как мониторинг вещания и автоматизированную маркировку MP3, где ожидается лишь незначительное искажение звука.

Второе число в каждой ячейке соответствует числу совпадений с настройкой, которая используется для идентификации сильно искажённого звука, как, например, в приложении для мобильного телефона. По сравнению с предыдущей настройкой для генерации кандидатов дополнительно используются 1024 наиболее вероятных суб-отпечатков для каждого суб-отпечатка. Другими словами, для генерации большего числа позиций-кандидатов переключались 10 наименее надёжных бит каждого суб-отпечатка. В результате число совпадений выше, и могут быть идентифицированы даже "блоки отпечатков GSM C/I = 4 дБ". Большинство блоков отпечатков с линейными изменениями скорости по-прежнему не имеют ни одного совпадения. BER этих блоков уже выше, чем порог, и по этой причине они не могут быть определены, даже если есть совпадения. Кроме того, надо иметь в виду, что при соответствующем предыскажении, как это предложено в Разделе 4.4, такие блоки отпечатков с большим изменением линейной скорости могут быть определены достаточно легко.

Таблица 2. Совпадения в базе данных для разных видов искажения сигнала. Первая цифра показывает совпадения для использования только 256 суб-отпечатков для получения позиций-кандидатов. Второе число указывает показывает совпадения, когда также используются 1024 наиболее вероятных кандидатов для каждого суб-отпечатка.