Увеличение производительности алгоритмов поиска дубликатов аудиозаписей | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Информатика

Опубликовано в Молодой учёный №49 (183) декабрь 2017 г.

Дата публикации: 09.12.2017

Статья просмотрена: 58 раз

Библиографическое описание:

Маленко С. А. Увеличение производительности алгоритмов поиска дубликатов аудиозаписей // Молодой ученый. — 2017. — №49. — С. 22-26. — URL https://moluch.ru/archive/183/47026/ (дата обращения: 19.04.2019).



Алгоритм обработки аудиозаписи для определения дубликата.

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

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

Для вычисления акустического отпечатка нужно начать с декодирования аудиосигнала, который упакован в аудиофайл. Как правило аудиофайл (например, в формате MP3) представляет собой цепочку фреймов (блоков), в которых содержатся закодированные данные об аудио. Для декодирования файла можно использовать, например, библиотеку с открытым исходным кодом FFmpeg. В результате декодирования получается массив значений, описывающих изменение амплитуды сигнала по времени.

Далее необходимо определить спектрограмму полученного декодированного сигнала. Проще всего использовать алгоритм быстрого преобразования Фурье (FFT), исходный код алгоритма можно легко найти в сети Интернет, а некоторые его реализации включены в пакеты наподобие Matlab.

Рис. 1. Пример спектрограммы аудиосигнала

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

Многолетняя практика показала, что частота наиболее хорошо характеризует аудиозапись, поэтому именно частоту возьмем за основу вычисления отпечатка. Для этого разобьем всю временную область на несколько частей длиной dt, то есть всего получаем частей. В каждом таком промежутке будем вычислять n пиков амплитуды, каждый пик будем характеризовать временем и частотой. Далее отсортируем пики по времени и добавим в один список длины n. Таким образом, получим списков, которые объединим в один массив длины . Этот массив и будет нашим отпечатком аудиозаписи.

image

Рис. 2. Выделение пиков на спектрограмме

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

Улучшение устойчивости алгоритма.

Для нахождения отпечатков аудиозаписи был проведен анализ основных частот сигнала в определенный момент времени. В большинстве случаев точного совпадения частот наблюдаться не будет, но они будут близки друг к другу. То есть необходимо разработать алгоритм поиска найденных пиков с некоторым допуском, или, иначе, искать K ближайших соседей (K-means) к данной частоте с некоторой максимальной разницей.

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

(аксиома тождества)

(аксиома симметрии)

(аксиома треугольника)

Для хранения значений и поиска воспользуемся такой структурой данных как VP-дерево (vantage-point tree). Из первоначального множества берется одна из точек («опорная точка») и выбирается «радиус» R для этой точки. Остальные точки делятся на два подмножества — с расстоянием меньше R до опорной точки, и расстоянием больше R. В каждом из получившихся подмножеств выбирается следующая опорная точка и новый радиус, и т. д., пока количество элементов в каждом из оставшихся подмножеств не станет меньше определенного порогового значения. Опорные точки и «радиусы» сфер разбиения выбираются так, чтобы дерево получилось максимально сбалансированным [1].

Рис. 3. Графическое изображение VP дерева

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

Кластеризация ишардирование базы ввиде VP дерева.

Постараемся оценить размер базы данных. Разобьем все аудиозаписи на отрывки равной длины и возьмем из каждого n измерений. Для конкретики возьмем длину промежутка в 1 секунду, а количество измерений 30. Для средней аудиозаписи длины 4 минуты получим 7200 значений частот. Для базы в миллион аудиозаписей это число достигает 7 200 000 000 измерений, что соответствует 230 гигабайтам при размере одного значения 32 бита. Для ускорения поиска желательно хранить базу данных в оперативной памяти сервера, но при таких объемах это становится проблематично, кроме того, для поиска будут задействоваться все ресурсы машины. Поэтому необходимо разработать механизмы кластеризации и шардирования данных. Шардирование — разделение (партиционирование) базы данных на отдельные части (шарды) так, чтобы каждую из них можно было вынести на отдельный сервер для увеличения производительности системы.

Вернемся к структуре VP дерева. Это бинарное дерево, каждый его узел имеет 2 потомка. Нарушим условие сбалансированности дерева. Выберем радиус таким образом, что левое поддерево всегда меньше правого. Кластеризовать шарды будем по принципу VP-дерева. Каждый шард хранит в себе левое поддерево, а правое поддерево — ссылка на следующий шард. “Листовой” сервер хранит и левое и правое поддерево в себе.

Рис. 4. Схема шардирования

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

Второй подход — в каждом шарде динамически вычислять отношение размеров левого и правого поддерева. Так, для первого отношение будет 1 к 3, для второго — 1 к 2 и так далее. Это позволит хранить на каждом сервере одинаковый объем данных, что даст возможность равномерного реплицирования.

Ускорение обработки аудиозаписи.

Рассмотрим процесс загрузки аудиозаписи с сети и последующего ее анализа:

Рис. 5. Схема последовательной загрузки и обработки

В такой схеме общее время работы с аудиозаписью складывается из времени загрузки и времени обработки. Однако вернемся к алгоритму вычисления отпечатка. Аудиозапись анализируется последовательно, выделяются некоторые кванты времени и далее обрабатываются. То есть для вычисления очередного кванта не нужно наличие всей аудиозаписи. Постараемся сделать процесс загрузки и обработки параллельным. При загрузке и декодировании очередного кванта сразу отправляем его на обработку. В то время как обрабатывается первый отрезок, следующий уже успевает загрузиться и отправляется на обработку сразу после окончания загрузки. Это позволяет сократить общее время вычисления отпечатка до времени загрузки и времени обработки одного кванта. Кроме того, в предположении, что сеть работает в n раз медленнее вычисления отпечатка, без дополнительных затрат можно обрабатывать параллельно n аудиозаписей.

Рис 6 Схема параллельной обработки при условии отношения времени обработки к времени загрузки 1 к 2

Заключение.

Изложенные методы позволяют увеличить устойчивость алгоритма поиска дубликатов аудиозаписей к различным искажениям. Кроме того, схема шардирования в виде VP дерева позволяет построить устойчивую к высоким нагрузкам систему вычисления акустических отпечатков. Все это было использовано при разработке системы антиплагиата в веб-приложении, на которое был получен грант в Фонде содействия развитию малых форм предприятий в научно-технической сфере.

Литература:

  1. VP-дерево // Википедия. URL: https://ru.wikipedia.org/wiki/VP-дерево.
  2. Архитектура и алгоритмы индексации аудиозаписей ВКонтакте // Хабрахабр. URL: https://habrahabr.ru/company/vkontakte/blog/330988/.
Основные термины (генерируются автоматически): аудиозапись, правое поддерево, время загрузки, момент времени, левое поддерево, очередной квант, данные, время обработки, баз данных, FFT.


Похожие статьи

Первичная обработка сигналов вейвлетами на примере...

Часто первичная обработка может занимать большее количество времени, чем анализ.

3. Если F < F + F , то F включается в число выбранных узлов (при этом всё поддерево под этим узлом

Обработка и загрузка данных для тендеров по лекарственным препаратам.

Основы разработки баз данных реального времени

Ключевые слова: база данных, реальное время, СУБД. СУБД реального времени является наследует основные свойства системы реального времени. Такие СУБД должны обеспечивать хранение, обработку и вывод данных в режиме реального времени.

Программная реализация анализатора аудиофайлов

В настоящее время анализ различных аудиозаписей в общем и речи в частности является крайне необходимым и актуальным.

Программная реализация алгоритма Левенштейна для устранения опечаток в записях баз данных.

Реализация алгоритма поиска ближайших объектов с помощью...

Ключевое значение при реализации такой возможности имеют используемые структуры данных и алгоритмы их обработки.

В зависимости от их соотношения мы запускаем поиск либо в правое поддерево, либо в левое поддерево, либо в оба.

Алгоритмы преобразования Фурье и их применение при анализе...

– БПФ по основанию 2 с прореживанием по времени, БПФ по основанию 2 с

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

Алексей Лукин. Введение в цифровую обработку сигналов (математические основы).

Анализ поисковых алгоритмов при решении задач идентификации...

Проблемы идентификации объектов в базах данных. Эффективность управления современным бизнесом основана на возможности получения

В отличие от обычных сбалансированных деревьев, в trie-дереве все строки, имеющие общее начало, располагаются в одном поддереве.

Решение проблем параллельной обработки транзакций и выход...

Термин параллелизм означает возможность одновременной обработки в СУБД многих транзакций с доступом к одним и тем же данным, причем в одно и то же время.

Исследование процесса цифровой обработки сигнала при работе...

Рис. 1 Схема БПФ по основанию 2 с прореживанием по времени. Основой алгоритма, как видно по рис. 1, является «ДПФ N=2», именуемое операцией

Например, в пакете прикладных программ MATLAB имеется готовая функция FFT. Её мы и будем использовать в данной работе.

Технологии обработки больших данных | Статья в журнале...

Необходимость обработки больших данных привело к развитию новых технологий.

Такое хранение данных еще называют noSQL базы данных. Для запросов к таким данным

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

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Первичная обработка сигналов вейвлетами на примере...

Часто первичная обработка может занимать большее количество времени, чем анализ.

3. Если F < F + F , то F включается в число выбранных узлов (при этом всё поддерево под этим узлом

Обработка и загрузка данных для тендеров по лекарственным препаратам.

Основы разработки баз данных реального времени

Ключевые слова: база данных, реальное время, СУБД. СУБД реального времени является наследует основные свойства системы реального времени. Такие СУБД должны обеспечивать хранение, обработку и вывод данных в режиме реального времени.

Программная реализация анализатора аудиофайлов

В настоящее время анализ различных аудиозаписей в общем и речи в частности является крайне необходимым и актуальным.

Программная реализация алгоритма Левенштейна для устранения опечаток в записях баз данных.

Реализация алгоритма поиска ближайших объектов с помощью...

Ключевое значение при реализации такой возможности имеют используемые структуры данных и алгоритмы их обработки.

В зависимости от их соотношения мы запускаем поиск либо в правое поддерево, либо в левое поддерево, либо в оба.

Алгоритмы преобразования Фурье и их применение при анализе...

– БПФ по основанию 2 с прореживанием по времени, БПФ по основанию 2 с

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

Алексей Лукин. Введение в цифровую обработку сигналов (математические основы).

Анализ поисковых алгоритмов при решении задач идентификации...

Проблемы идентификации объектов в базах данных. Эффективность управления современным бизнесом основана на возможности получения

В отличие от обычных сбалансированных деревьев, в trie-дереве все строки, имеющие общее начало, располагаются в одном поддереве.

Решение проблем параллельной обработки транзакций и выход...

Термин параллелизм означает возможность одновременной обработки в СУБД многих транзакций с доступом к одним и тем же данным, причем в одно и то же время.

Исследование процесса цифровой обработки сигнала при работе...

Рис. 1 Схема БПФ по основанию 2 с прореживанием по времени. Основой алгоритма, как видно по рис. 1, является «ДПФ N=2», именуемое операцией

Например, в пакете прикладных программ MATLAB имеется готовая функция FFT. Её мы и будем использовать в данной работе.

Технологии обработки больших данных | Статья в журнале...

Необходимость обработки больших данных привело к развитию новых технологий.

Такое хранение данных еще называют noSQL базы данных. Для запросов к таким данным

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

Задать вопрос