Распознавание мелодии с помощью нечеткого поиска
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
°пись должна состоять лишь из событий темпа и размера. В файле формата 2 каждая MTrk-запись должна начинаться с событий темпа и размера.
Замечание: Если в миди-файле нет событий темпа и размера, то по умолчанию подразумевается значение размера 4/4 и значение темпа 120 BPM.
Таким образом, мы можем побайтно считать MIDI-файл, из его заголовка узнать всю необходимую информацию для анализа (темп, такт, число тиков, приходящихся на один такт), считать музыку в массив байтов и мы непосредственно перейдем к проблеме определения подобности мелодий. Данная задача относится к задачам нечеткого поиска.
Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие Возможно вы имели в виду… в тех же поисковых системах. Нечеткий поиск в большинстве своем используется для поиска строк в тексте, подстроки в строке и т.д., но он подходит и для нашей задачи:
Для простоты рассматривается сравнение двух мелодий, а не сравнение мелодии с набором мелодий (то есть словарь из одного слова), то при сравнении без учета разбиения на такты одна мелодия (наименьшая по количеству нот) будет словом. Размер слова будет равен длине мелодии, а значением будет являться комбинация нот в мелодии.
При сравнении с учетом разбиения на такты размер слова будет равен такту, а значением слова будет являться кусочек мелодии из MIDI-файла. Словарем выступит мелодия, на сходство с которой и определяется предоставленный образец.
Для простоты изложения и понимания будем рассматривать нечеткий поиск применительно к строкам.
Алгоритмы нечеткого поиска характеризуются метрикой - функцией расстояния между двумя словами, позволяющей оценить степень их сходства в данном контексте. Строгое математическое определение метрики включает в себя необходимость соответствия условию неравенства треугольника (X - множество слов, p - метрика):
Между тем, в большинстве случаев под метрикой подразумевается более общее понятие, не требующее выполнения такого условия, это понятие можно также назвать расстоянием.
В числе наиболее известных метрик - расстояния Хемминга, Левенштейна и Дамерау-Левенштейна.
Расстояние Хэмминга - число позиций, в которых соответствующие символы двух слов одинаковой длины различны. В более общем случае расстояние Хэмминга применяется для строк одинаковой длины любых q-ичных алфавитов и служит метрикой различия (функцией, определяющей расстояние в метрическом пространстве) объектов одинаковой размерности.
Первоначально метрика была сформулирована Ричардом Хэммингом во время его работы в Bell Labs для определения меры различия между кодовыми комбинациями (двоичными векторами) в векторном пространстве кодовых последовательностей, в этом случае расстоянием Хэмминга d (x, y) между двумя двоичными последовательностями (векторами) x и y длины n называется число позиций, в которых они различны - в такой формулировке расстояние Хэмминга вошло в словарь алгоритмов и структур данных национального института стандартов и технологий США (англ. NIST Dictionary of Algorithms and Data Structures). При этом расстояние Хемминга является метрикой только на множестве слов одинаковой длины, что сильно ограничивает область его применения.
Впрочем, на практике расстояние Хемминга оказывается практически бесполезным, уступая более естественным с точки зрения человека метрикам. Одной из таких метрик является расстояние Левенштейна (также редакционное расстояние или дистанция редактирования). Расстояние Левенштейна - это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Впервые задачу упомянул в 1965 году советский математик Владимир Иосифович Левенштейн при изучении последовательностей 0 - 1. Впоследствии более общую задачу для произвольного алфавита связали с его именем. Большой вклад в изучение вопроса внёс Гасфилд.
Далее считается, что элементы строк нумеруются с первого, как принято в математике, а не с нулевого, как принято в языка программирования.
Шаг по i символизирует удаление из первой строки, по j вставку в первую строку, а шаг по обоим индексам символизирует замену символа или отсутствие изменений.
Весь процесс можно представить следующей матрицей:
Рис. 5. Матрица количества преобразований одного слова в другое
Как видно из матрицы, из слова арестант получится слово дагестан всего за три операции вставки, удаления, замещения.
Используя данные метрики можно определить расстояние между частью мелодии предлагаемого образца и частью мелодии из оригинала и на основе значения расстояния можно делать вывод о степени похожести мелодий.
3. Средства реализации
Для реализации решения поставленной задачи выбрана. Net платформа, среда разработки Microsoft Visual Studio 2010 и язык C#.
Основные особенности.NET:
Общеязыковая система типов
Проверка типов параметров
Отсутствие возможности прямого управления памятью
Сборка мусора
Компонентная технология
Преимущества:
Отсутствие традиционных проблем с утечкой памяти
Продвинутая система безопасности
Многообразие язы