Сьогодні дані практично з будь-якої області зберігаються і поширюються в електронному вигляді - не стали винятком і музичні твори, безліч файлів опису яких у вигляді аудіо, відео і текстових записів розміщують в Мережі. Закономірно виникає завдання пошуку в масивах музичних даних - наприклад, для відшукання повної нотного запису твору по залишився в пам'яті і записаному в нотній формі фрагменту полюбилася мелодії, або ж для виявлення фактів запозичень в нотних записах музичних творів, або для контролю за дотриманням авторських прав.
Багато нотні редактори можуть зберігати записи в додаток до свого внутрішнього формату і в форматі MusicXML, який підтримується більш ніж в 150 програмних продуктах (MuseScore, Finale, Guitar Pro і ін.). Однак в більшості сучасних електронних нотних бібліотек можливості пошуку вельми скромні - пошук ведеться, як правило, по текстовому опису: назвою музичного твору, прізвища автора (наприклад, www.wikifonia.org, www.notomania.ru). Але сьогодні не менше актуально шукати музичні файли, аналізуючи їх вміст, задавши в якості запиту тільки нотну послідовність. Також в якості запиту може бути запропонована нотний запис, побудована автоматично по звуковому фрагменту, а результатом пошуку буде оригінальна нотний запис музичного твору.
Для аудіофайлів реалізовані методи пошуку по звуковому фрагменту - акустичному відбитку (як, наприклад, в системах echoprint.me, Shazam, Tunatic і ін.), Проте всі ці методи мають обмеження на мінімальну тривалість вхідного фрагмента, по якому ведеться пошук, - як правило , для коректного порівняння зі зразком, що зберігається в базі акустичних відбитків, потрібно аудіозапис тривалістю не менше 10 секунд, але іноді виникає потреба виконати пошук, задавши в якості запиту коротший фрагмент, адекватно задається в нотної записи. Пошук на основі аналізу вмісту музичних файлів реалізований, наприклад, в системі Musipedia, на її вхід подається фрагмент нотного запису, мелодійний контур або ритм, а на виході отримуємо набір midi-файлів, в яких міститься заданий або схожий на нього музичний фрагмент. Ця система здійснює порівняння внутрішнього уявлення музичних фрагментів, що дозволяє, зокрема, знаходити мелодію, записану в іншій тональності, вихідне представлення якої відрізняється від запиту.
Всі ці методи чутливі до неминучих помилок завдання вихідних даних, що виникають під час запису мелодії на слух. Крім того, вони не підлаштовуються під помилки ручного введення або автоматичної генерації за наявною аудіозаписи.
хвильовий метод
Запис нот як файл MusicXML - це структурований документ у форматі, що представляє собою підмножина XML, в якому зафіксовано такі ключові слова розмітки вмісту, однак традиційні методи пошуку (векторна модель, пошук в файлах XML) в чистому вигляді тут неприйнятні. При пошуку в масиві музичних записів повинна враховуватися специфіка предметної області, наприклад, одна і та ж мелодія, записана в різних тональностях, - це зовсім різні файли. При пошуку потрібно оцінити схожість запиту з бібліотечним файлом і прийняти рішення про допустимість вважати їх поданням одного твору. Схожа ситуація виникає в математиці при проведенні докази методом математичної індукції. При виконанні кроку індукції є припущення, яке вважається дійсним, і потрібно довести істинність висновку індукції, яке схоже на гіпотезу. Одним з методів, за допомогою якого можна автоматизувати такий доказ, є метод хвильових правил, що пропонує спочатку виділити загальні частини (основу) гіпотези і укладення і відзначити відмінності (цей процес називається анотуванням виразів). Потім в доказі застосовуються тільки такі перетворення, які зменшують відмінності відповідно до деякої мірою. При успішному результаті докази все відмінності будуть усунені, висновок індукції зведеться до гіпотези і істинність буде доведена. Для використання методу хвильових правил при пошуку музичних творів необхідно визначити правила анотування запиту і бібліотечного файлу, а також правила, за допомогою яких виробляються перетворення, і задати міру.
Будь-музичний фрагмент (і запити, і збережені в бібліотеці записи) пропонується представляти у вигляді нотних відстаней і пауз. Нотні відстані зберігаються у вигляді пар (відносна висота, відносна тривалість), паузи характеризуються лише відносною тривалістю. Відносна висота ноти - це число, яке дорівнює зсуву (в півтонах) щодо попередньої ноти фрагмента. Таке уявлення, по-перше, дозволяє зробити однаковими уявлення однієї мелодії в різних тональностях і, по-друге, забезпечує те, що помилка при введенні однієї з нот проявиться лише в двох відносних висотах, але не вплине на інші ноти фрагмента.
Розглянемо обчислення відносних висот на прикладі фрагмента «Польки» С. В. Рахманінова (див. Малюнок). Відносні висоти всіх нот, починаючи з другої, підписані під відповідними нотами: позитивні числа з'являються при русі мелодії вгору, негативні - в разі, якщо висота наступної ноти нижче попередньої.
Відносна тривалість ноти - це відношення тривалості ноти до тривалості попередньої ноти або паузи. Перша нота фрагмента бере участь в обчисленні відносної тривалості наступної ноти, а для неї самої відносна тривалість трохи обчислюється. Якщо ноти однієї висоти пов'язані лігою, то у внутрішньому поданні вони вважаються однією нотою, їх тривалості складаються і відносна тривалість обчислюється як загальна для такої групи нот. Відносні тривалості пауз обчислюються за такими ж правилами. Зазначене подання дозволяє отримати однакову формальний запис для однакових мелодій, спрощуючи їх порівняння. Однак одного лише зміни уявлення ще недостатньо для вирішення завдання пошуку - наявність незбіжних внутрішніх уявлень не обов'язково означає, що розглядаються музичні записи не належать до одного твору. По-перше, розбіжність може бути викликано різними довжинами запиту і файлу з нотної бібліотеки. По-друге, в деяких нотах запиту можуть з'явитися помилки, зроблені користувачем. Тому потрібно шукати також фрагменти, в повному обсязі збігаються із запитом.
Порівняння музичних фрагментів
Порівняння запиту і записи з бібліотеки, вже переведених у внутрішнє представлення, відбувається в три етапи. Спочатку виконуються пошук найбільшою загальною підпослідовності нот і спеціальна розмітка (анотація) фрагментів. Потім здійснюються перетворення за допомогою хвильових правил. На останньому етапі обчислюється оцінка схожості фрагментів.
Ідея і термінологія методу хвильових правил з'явилися зі спостережень за природою Шотландії. Уявіть, що ви стоїте на березі озера, оточеного горами, і милуєтеся їх відображенням у воді. Несподівано в воду падає камінь і відображення порушується хвилями, але з плином часу хвилі розходяться і відображення картини відновлюється. Відображення в спокійному озері і відображення, порушене хвилями, схожі, і для перетворення другого до першого потрібно усунути хвилі. Ця ідея і використовується в методі хвильових правил. Вхідними даними методу є два музичних фрагмента у внутрішньому поданні. У них відзначаються загальні частини (основа) і відмінності (хвильовий фронт). Основою для музичних фрагментів є найбільша спільна підпослідовність нот, не обов'язково стоять поспіль. До розмічені таким чином фрагментами застосовуються хвильові правила. Хвильові правила є правила переписування. Якщо в хвильовому фронті зустрілася восьма нота, після якої стоїть пауза, то замість них у фрагменті можна написати одну четвертну ноту (більшої тривалості).
Оцінка схожості фрагментів виконується після завершення застосування хвильових правил. Схожість фрагментів обернено пропорційна довжині хвильового фронту, який залишився після застосування правил, а також залежить від кількості застосованих правил, оскільки правила застосовувалися для усунення відмінностей, тобто вихідні фрагменти були однаковими.
Індексування бібліотеки файлів MusicXML
Одне із завдань, яку потрібно вирішити при створенні пошукової системи, - індексування вмісту бібліотеки. Проблема полягає в тому, що не можна автоматично розбити твір на фрагменти і побудувати повноцінний словник. Якщо для текстових колекцій можна визначити поняття «слово» як текст між пробільними символами, то аналогом його в музичній області була б «музична фраза» або «мелодія», проте її межі складно визначити формально. Мелодія може бути у одного з інструментів, вона не завжди починається з першого такту і не завжди її межами є тактові риси. Якщо при роботі з текстовим файлом розбити його на окремі слова не складає труднощів, то автоматичне розбиття музичного твору на осмислені фрагменти - нетривіальне завдання. Для розбиття музичного твору використовується метод «ковзного вікна». Здається розмір (сумарна тривалості) вікна і розмір кроку.
Частина мелодії, що виражає закінчену музичну думку, в елементарній теорії музики називається періодом. Найпростіший тип періоду складається з восьми тактів. Період ділиться на дві частини по чотири такту, що називаються пропозиціями. Пропозиції, в свою чергу, можна розбити на двотактні фрази. Дотримуючись такого принципу поділу мелодії, твір проходиться ділити тричі - вікнами розміром в 8, 4 і 2 такту.
Отримані фрагменти переводяться у внутрішнє представлення і заносяться в словник. У словнику вони зберігаються у вигляді інвертованого файлу, тобто для кожного фрагмента вказується список творів, в яких він зустрічається, і число входжень в кожне з них. В силу особливостей порівняння музичних фрагментів, при занесенні в базу і підрахунку входжень фрагмента в твір розглядається не точний збіг нового фрагмента і наявного в базі, а такий збіг, при якому величина, отримана при обчисленні схожості, що не менше порогового значення.
***
Для ефективної роботи нотної пошукової системи було вибрано внутрішнє уявлення для зберігання нотних записів, що дозволяє проводити їх порівняння, складені правила перетворення, що застосовуються при оцінці ступеня збігу нотних фрагментів, і запропонований спосіб індексування бібліотеки нотних файлів. Найближчим часом планується розширити пошук на бібліотеки музичних творів, що зберігаються в Мережі, що потребують поліпшити швидкодію пошуку.
Юлія Корухова ( [email protected] ) - доцент кафедри алгоритмічних мов ВМК МГУ, Марина Митрова ( [email protected] ) - молодший науковий співробітник ІПМ ім. Келдиша РАН. Робота виконана за підтримки РФФД грант 12-01-31109-мол_а.
