.png)
Сегодня данные практически из любой области хранятся и распространяются в электронном виде — не стали исключением и музыкальные произведения, множество файлов описания которых в виде аудио, видео и текстовых записей размещают в Сети. Закономерно возникает задача поиска в массивах музыкальных данных — например, для отыскания полной нотной записи произведения по оставшемуся в памяти и записанному в нотной форме фрагменту полюбившейся мелодии, или же для выявления фактов заимствований в нотных записях музыкальных произведений, или для контроля за соблюдением авторских прав.
Многие нотные редакторы могут сохранять записи в дополнение к своему внутреннему формату и в формате MusicXML, который поддерживается более чем в 150 программных продуктах (MuseScore, Finale, Guitar Pro и др.). Однако в большинстве современных электронных нотных библиотек возможности поиска весьма скромны — поиск ведется, как правило, по текстовому описанию: названию музыкального произведения, фамилии автора (например, www.wikifonia.org, www.notomania.ru). Но сегодня не менее актуально искать музыкальные файлы, анализируя их содержимое, задав в качестве запроса только нотную последовательность. Также в качестве запроса может быть предложена нотная запись, построенная автоматически по звуковому фрагменту, а результатом поиска будет оригинальная нотная запись музыкального произведения.
Для аудиофайлов реализованы методы поиска по звуковому фрагменту — акустическому отпечатку (как, например, в системах echoprint.me, Shazam, Tunatic и др.), однако все эти методы имеют ограничение на минимальную длительность входного фрагмента, по которому ведется поиск, — как правило, для корректного сравнения с образцом, хранящимся в базе акустических отпечатков, требуется аудиозапись продолжительностью не менее 10 секунд, но иногда возникает потребность выполнить поиск, задав в качестве запроса более короткий фрагмент, адекватно задаваемый в нотной записи. Поиск на основе анализа содержимого музыкальных файлов реализован, например, в системе Musipedia, на ее вход подается фрагмент нотной записи, мелодический контур или ритм, а на выходе получаем набор midi-файлов, в которых содержится заданный или похожий на него музыкальный фрагмент. Эта система осуществляет сравнение внутреннего представления музыкальных фрагментов, что позволяет, в частности, находить мелодию, записанную в другой тональности, исходное представление которой отличается от запроса.
Все эти методы чувствительны к неизбежным ошибкам задания исходных данных, возникающим при записи мелодии на слух. Кроме того, они не подстраиваются под ошибки ручного ввода или автоматической генерации по имеющейся аудиозаписи.
Волновой метод
Запись нот в виде файла MusicXML — это структурированный документ в формате, представляющем собой подмножество XML, в котором зафиксирован набор тегов разметки содержимого, однако традиционные методы поиска (векторная модель, поиск в файлах XML) в чистом виде здесь неприменимы. При поиске в массиве музыкальных записей должна учитываться специфика предметной области, например, одна и та же мелодия, записанная в разных тональностях, — это совсем разные файлы. При поиске требуется оценить сходство запроса с библиотечным файлом и принять решение о допустимости считать их представлением одного произведения. Сходная ситуация возникает в математике при проведении доказательства методом математической индукции. При выполнении шага индукции имеется предположение, которое считается истинным, и требуется доказать истинность заключения индукции, которое похоже на гипотезу. Одним из методов, с помощью которого можно автоматизировать такое доказательство, является метод волновых правил, предлагающий сначала выделить общие части (основу) гипотезы и заключения и отметить различия (этот процесс называется аннотированием выражений). Затем в доказательстве применяются только такие преобразования, которые уменьшают различия в соответствии с некоторой мерой. При успешном исходе доказательства все различия будут устранены, заключение индукции сведется к гипотезе и истинность будет доказана. Для использования метода волновых правил при поиске музыкальных произведений необходимо определить правила аннотирования запроса и библиотечного файла, а также правила, с помощью которых производятся преобразования, и задать меру.
Любой музыкальный фрагмент (и запросы, и хранимые в библиотеке записи) предлагается представлять в виде нотных расстояний и пауз. Нотные расстояния хранятся в виде пар (относительная высота, относительная длительность), паузы характеризуются только относительной длительностью. Относительная высота ноты — это число, равное смещению (в полутонах) относительно предыдущей ноты фрагмента. Такое представление, во-первых, позволяет сделать одинаковыми представления одной мелодии в разных тональностях и, во-вторых, обеспечивает то, что ошибка при вводе одной из нот проявится только в двух относительных высотах, но не повлияет на остальные ноты фрагмента.
Рассмотрим вычисление относительных высот на примере фрагмента «Польки» С. В. Рахманинова (см. рисунок ). Относительные высоты всех нот, начиная со второй, подписаны под соответствующими нотами: положительные числа появляются при движении мелодии вверх, отрицательные — в случае, если высота следующей ноты ниже предыдущей.
.png "Относительные высоты нот") |
| Относительные высоты нот |
Относительная длительность ноты — это отношение длительности ноты к длительности предыдущей ноты или паузы. Первая нота фрагмента участвует в вычислении относительной длительности следующей ноты, а для нее самой относительная длительность не вычисляется. Если ноты одной высоты связаны лигой, то во внутреннем представлении они считаются одной нотой, их длительности складываются и относительная длительность вычисляется как общая для такой группы нот. Относительные длительности пауз вычисляются по таким же правилам. Данное представление позволяет получить одинаковую формальную запись для одинаковых мелодий, упрощая их сравнение. Однако одного лишь изменения представления еще недостаточно для решения задачи поиска — наличие несовпадающих внутренних представлений не обязательно означает, что рассматриваемые музыкальные записи не относятся к одному произведению. Во-первых, несовпадение может быть вызвано разными длинами запроса и файла из нотной библиотеки. Во-вторых, в некоторых нотах запроса могут появиться ошибки, сделанные пользователем. Поэтому требуется искать также фрагменты, не полностью совпадающие с запросом.
Сравнение музыкальных фрагментов
Сравнение запроса и записи из библиотеки, уже переведенных во внутреннее представление, происходит в три этапа. Сначала выполняются поиск наибольшей общей подпоследовательности нот и специальная разметка (аннотация) фрагментов. Затем осуществляются преобразования с помощью волновых правил. На последнем этапе вычисляется оценка похожести фрагментов.
Идея и терминология метода волновых правил появились из наблюдений за природой Шотландии. Представьте, что вы стоите на берегу озера, окруженного горами, и любуетесь их отражением в воде. Неожиданно в воду падает камень и отражение нарушается волнами, но с течением времени волны расходятся и отражение картины восстанавливается. Отражение в спокойном озере и отражение, нарушенное волнами, похожи, и для преобразования второго к первому нужно устранить волны. Эта идея и используется в методе волновых правил. Входными данными метода являются два музыкальных фрагмента во внутреннем представлении. В них отмечаются общие части (основа) и различия (волновой фронт). Основой для музыкальных фрагментов является наибольшая общая подпоследовательность нот, не обязательно стоящих подряд. К размеченным таким образом фрагментам применяются волновые правила. Волновые правила представляют собой правила переписывания. Если в волновом фронте встретилась восьмая нота, после которой стоит пауза, то вместо них во фрагменте можно написать одну четвертную ноту (большей длительности).
Оценка похожести фрагментов выполняется после завершения применения волновых правил. Похожесть фрагментов обратно пропорциональна длине волнового фронта, который остался после применения правил, а также зависит от количества примененных правил, поскольку правила применялись для устранения различий, то есть исходные фрагменты не были одинаковыми.
Индексирование библиотеки файлов MusicXML
Одна из задач, которую требуется решить при создании поисковой системы, — индексирование содержимого библиотеки. Проблема заключается в том, что нельзя автоматически разбить произведение на фрагменты и построить полноценный словарь. Если для текстовых коллекций можно определить понятие «слово» как текст между пробельными символами, то аналогом его в музыкальной области была бы «музыкальная фраза» или «мелодия», однако ее границы сложно определить формально. Мелодия может быть у одного из инструментов, она не всегда начинается с первого такта и не всегда ее границами являются тактовые черты. Если при работе с текстовым файлом разбить его на отдельные слова не составляет труда, то автоматическое разбиение музыкального произведения на осмысленные фрагменты — нетривиальная задача. Для разбиения музыкального произведения используется метод «скользящего окна». Задается размер (суммарная длительность нот) окна и размер шага.
Часть мелодии, выражающая законченную музыкальную мысль, в элементарной теории музыки называется периодом. Простейший тип периода состоит из восьми тактов. Период делится на две части по четыре такта, называющиеся предложениями. Предложения, в свою очередь, можно разбить на двухтактные фразы. Следуя такому принципу разделения мелодии, произведение проходится делить трижды — окнами размером в 8, 4 и 2 такта.
Полученные фрагменты переводятся во внутреннее представление и заносятся в словарь. В словаре они хранятся в виде инвертированного файла, то есть для каждого фрагмента указывается список произведений, в которых он встречается, и число вхождений в каждое из них. В силу особенностей сравнения музыкальных фрагментов, при занесении в базу и подсчете вхождений фрагмента в произведение рассматривается не точное совпадение нового фрагмента и имеющегося в базе, а такое совпадение, при котором величина, полученная при вычислении похожести, не меньше порогового значения.
***
Для эффективной работы нотной поисковой системы было выбрано внутреннее представление для хранения нотных записей, позволяющее проводить их сравнение, составлены правила преобразования, применяющиеся при оценке степени совпадения нотных фрагментов, и предложен способ индексирования библиотеки нотных файлов. В ближайшее время планируется расширить поиск на библиотеки музыкальных произведений, хранящиеся в Сети, что потребует улучшить быстродействие поиска.
Юлия Корухова (yulia@cs.msu.su) — доцент кафедры алгоритмических языков ВМК МГУ, Марина Мытрова (mytrova@keldysh.ru) — младший научный сотрудник ИПМ им. Келдыша РАН. Работа выполнена при поддержке РФФИ грант 12-01-31109-мол_а.
