SkywalkerY Sep 18 2009 at 00:40

Генерация музыки на основе заданного стиля

14 min

11K

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

Введение

Работать мы будем с файлами в формате MIDI. Да, хабраюзер, я рыдаю вместе с тобой, но именно в этом формате уже изначально прописаны какие в мелодии инструменты, ноты, длительности. А вот из MP3 их уже не получишь (тривиальным методом по крайней мере), а так бы хотелось...

Но не будем отчаиваться, в интернетах водится масса качественных MIDI-файлов. Могу порекомендовать сервис HamieNET.com. Он позволяет не только скачать MIDI-файл, но и слить сразу мелодию, конвертированную в MP3, а также слить XML-файл, полученный из MIDI, отображает треки, содержащиеся в файле, позволяет прослушать их по одному и т.д. Также есть онлайн-сервис конвертирования вашего MIDI в MP3. Правда, если не платить деньги, то можно конвертировать только одну мелодию в день.

Демонстрация работы

Это оригинальная мелодия Nightwish — Ever Dream:
ссылка зеркало
А это, то, что получилось в результате работы алгоритма:
ссылка зеркало
Это просто перезапуск проги, ничего не меняя, мелодия немного отличается:
ссылка зеркало

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

Описание алгоритма

Алгоритм основан на построении контекстно-зависимой грамматики по исходной мелодии, а затем генерировании на основе этой грамматики новой мелодии по заданной начальной последовательности.

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

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

Возьмем обычную строку: ABCDEFGIKFHLEFJ. И начнем строить для нее грамматику, начав, скажем, с символа F (вообще это нужно проделать для каждого символа).

Нам нужно написать правило, которое бы указывало нам, какую букву следует поставить, если мы вдруг встретили символ F. Записывается это так: F -> что-то. Как видим, мы не можем создать такое правило, так как лишь по одной букве не можем определить что же должно идти следом: после F может идти как G, так и H или J. Поэтому мы добавляем контекст к нашей букве F, контекст — это символы, окружающие F. Возьмем по одной букве перед F. Получим EF и KF. Контекстом для буквы F здесь служат буквы E и K. Мы с вами только что расширили контекст на один символ, поэтому данный метод построения грамматики называется методом динамически расширяющегося контекста.

Посмотрим можем ли мы сейчас создать правило. После KF идет H, и больше нет других вариантов. Мы получили первое конечное правило: KF -> H (читается как «KF продуцирует H). Теперь, если, например, на конце строки мы встретим KF и нужно будет продлить строку на один символ, мы смело напишем H.

Но у нас еще осталась проблема: после EF может идти как G, так и J. Поэтому мы должны расширить контекст еще на один символ: DEF и LEF. И наконец-то мы получили конечные правила:
KF -> H
DEF -> G
LEF -> J

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

Процесс генерации новой строки выглядит следующим образом: дана начальная последовательность, например ADEF. Начинаем брать буквы с конца. F — нет правила с такой левой частью, расширяем контекст — EF, опять нет, расширяем — DEF, есть такое правило, ставим G, получаем ADEFG. Начинаем все сначала: берем букву G и т.д. столько раз, сколько нам нужно.

Будет удобно представлять грамматику в виде дерева. Для буквы F дерево будет иметь следующий вид:

В узлах находятся левые части правил, рядом с узлами написаны правые части правил — возможные продукции. Числа слева от дерева указывают, на каком контекстном уровне находятся узлы.

Теперь перед нами встает следующая проблема: если мы будем генерировать новую последовательность строго по заданным правилам, то мы получим в точности исходную строку (мелодию), а мы хотим создать новую. Поэтому в ряде случаев мы должны не доходить до конечного правила, а взять промежуточное. Это означает, что иногда, встретив скажем такую последовательность: ADEF, мы не будем расширять контекст до конечного правила DEF -> G, а остановимся на F и рандомом или каким-то другим методом выберем любую продукцию (H, G, J) у узла F в дереве. Или остановимся на EF и выберем продукцию G или J. Т.е. мы случайно выбираем уровень контекста в дереве и продукцию на этом уровне.

Ну а теперь представим, что каждая буква — это не буква, а аккорд, а применительно к MIDI-файлу будет вернее сказать, что это совокупность событий (к которым относится включение/выключение ноты, смена канала и т.д.), и вот уже наш алгоритм готов для мелодии.

Еще немного о MIDI

Наткнувшись на онлайн-сервис, позволяющий конвертировать MIDI в XML, я понял, что так с ним будет работать намного удобнее. Также нам нужно проделать еще одну вещь. Есть несколько форматов MIDI файлов. Формат 0 содержит 1 трек, форматы 1 и 2 содержат несколько треков. Чаще всего попадаются MIDI с форматом 1, где под каждый инструмент отводится свой трек: на одном треке играют гитарки, на другом скрипка и т.д. Это добавит некоторые трудности при построении грамматики. Нужно будет следить, что происходит на другом треке. Поэтому мы просто конвертируем формат 1 в формат 0, чтобы все инструменты были в куче на одном треке, а после перегоним еще и в XML. Все эти инструменты доступны здесь.

В конечном итоге получим примерно такой файл:

<?xml version="1.0" encoding="ISO-8859-1"?> <!DOCTYPE MIDIFile PUBLIC "-//Recordare//DTD MusicXML 0.9 MIDI//EN" "http://www.musicxml.org/dtds/midixml.dtd"> <MIDIFile> <Format>0</Format> <TrackCount>1</TrackCount> <TicksPerBeat>384</TicksPerBeat> <TimestampType>Absolute</TimestampType> <Track Number="0"> <Event> <Absolute>0</Absolute> <ControlChange Channel="2" Control="91" Value="46"/> </Event> <Event> <Absolute>0</Absolute> <ProgramChange Channel="2" Number="49"/> </Event> <Event> <Absolute>0</Absolute> <ControlChange Channel="2" Control="0" Value="0"/> </Event> ... <Event> <Absolute>24908</Absolute> <NoteOff Channel="11" Note="41" Velocity="127"/> </Event> <Event> <Absolute>24912</Absolute> <NoteOn Channel="11" Note="41" Velocity="127"/> </Event> <Event> <Absolute>24956</Absolute> <NoteOff Channel="11" Note="41" Velocity="127"/> </Event> <Event> <Absolute>24960</Absolute> <NoteOn Channel="11" Note="41" Velocity="127"/> </Event> ... </Track> </MIDIFile> * This source code was highlighted with Source Code Highlighter.

Здесь мы можем увидеть темп мелодии 384. Вначале устанавливаются настройки каналов для каждого инструмента, но нас больше будут интересовать события NoteOn и NoteOff — включения и выключения ноты. Они содержат канал, на котором играет нота, сам номер ноты и ее скорость. Также мы видим абсолютное время для каждого события. Можно генерировать XML с абсолютным и относительным временем. Абсолютное время — время, прошедшее с самого начала трека, относительное — прошедшее с момента последнего события. Для нас удобнее брать абсолютное, т.к. по нему мы можем легко сгруппировать события, произошедшие в один и тот же момент времени. Эти группы я обзову „аккордами“.

шКодим

Опишем класс „аккорда“:

public class Chord { //задержка после предыдущего "аккорда" public int Delay { get; set; } //события public List<string> Events { get; set; } public Chord() { Events = new List<string>(); } } * This source code was highlighted with Source Code Highlighter.

Заодно напишем класс для сравнения „аккордов“:

public class ChordComparer : IEqualityComparer<Chord> { public bool Equals(Chord x, Chord y) { if (x.Delay != y.Delay) return false; if (x.Events.Count != y.Events.Count) return false; foreach (var ev in x.Events) if (!y.Events.Contains(ev)) return false; foreach (var ev in y.Events) if (!x.Events.Contains(ev)) return false; return true; } public int GetHashCode(Chord obj) { int hash = obj.Delay.GetHashCode(); obj.Events.ForEach(ev => hash += ev.GetHashCode()); return hash; } } * This source code was highlighted with Source Code Highlighter.

И класс для сравнения последовательностей „аккордов“:

public class ListComparer : IEqualityComparer<List<Chord>> { private ChordComparer cc = new ChordComparer(); public bool Equals(List<Chord> x, List<Chord> y) { if (x.Count != y.Count) return false; for (int i = 0; i < x.Count; i++) if (!cc.Equals(x[i], y[i])) return false; return true; } public int GetHashCode(List<Chord> obj) { int hash = 0; obj.ForEach(ch => ch.Events.ForEach(ev => hash += ev.GetHashCode())); obj.ForEach(ch => hash += ch.Delay.GetHashCode()); return hash; } } * This source code was highlighted with Source Code Highlighter.

Класс узла дерева:

//целиком не вставляется, так что приведен частично public class Node { //значение узла - левая часть правила public List<Chord> Value { get; set; } //лист пар ключ-значение, ключ - возможная продукция, значение - следующий узел, который может быть null public List<KeyValuePair<Chord, Node>> Nodes { get; set; } //получить продукцию для переданной последовательности public Chord GetProduction(List<Chord> seq) { //если всего один подузел и у него нет потомков, возвращаем единственно возможную продукцию if (Nodes.Count == 1 && Nodes[0].Value == null) { return Nodes.First().Key; } else { //путь от корня дерева до конечного правила List<Node> path = new List<Node>(); ListComparer lc = new ListComparer(); path.Add(this); //если последовательность состоит лишь из одного "аккорда", мы не можем расширить контекст, //поэтому возвращаем рандомную продукцию корня if (seq.Count == 1) { if (Nodes.Count != 0) { return Nodes[Helper.rand.Next(Nodes.Count)].Key; } //если вдруг оказалось, что продукций нет, то возвращаем "аккорд", находящийся поблизости от //текущего else { int t = Helper.rand.Next(-10, 11); int index = 0, i; for (i = 0; i < Helper.listchords.Count; i++) if ((index = Helper.listchords[i].IndexOf(seq.Last())) != -1) break; return Helper.listchords[i][Math.Max(0, Math.Min(index + t, Helper.listchords[i].Count - 2))]; } } else { //расширяем контекст List<Chord> extseq = seq.GetRange(seq.Count - 2, 2); //ищем в подузлах правило для расширенного контекста List<Node> nodes = Nodes .Where(node => node.Value != null && lc.Equals(node.Value.Value, extseq)) .Select(node => node.Value) .Distinct() .ToList(); //не нашли, тогда возвращаем рандомную продукцию корня или ближайший "аккорд" if (nodes.Count == 0) { if (Nodes.Count != 0) { return Nodes[Helper.rand.Next(Nodes.Count)].Key; } else { int t = Helper.rand.Next(-10, 11); int index=0, i; for (i = 0; i < Helper.listchords.Count; i++) if ((index = Helper.listchords[i].IndexOf(seq.Last())) != -1) break; return Helper.listchords[i][Math.Max(0, Math.Min(index + t, Helper.listchords[i].Count - 2))]; } } //нашли else { //правило для контекста Node rule = nodes.First(); //ищем более точное правило, увеличивая контекст rule.GetProduction(seq, ref path, 3); //с вероятностью 60% возвращаем продукцию конечного правила if (Helper.rand.NextDouble() <= 0.6) { return path.Last().Nodes[0].Key; } //с оставшейся вероятностью возвращаем рандомную продукцию рандомного узла ветви дерева, //которая идет от корня до конечного правила else { Node p = path[Helper.rand.Next(path.Count)]; return p.Nodes[Helper.rand.Next(p.Nodes.Count)].Key; } } } } } //продолжаем искать конечное правило для переданной последовательности, c - уровень контекста private void GetProduction(List<Chord> seq, ref List<Node> path, int c) { //добавляем себя в ветвь path.Add(this); //далее происходит примерно то же самое, что в функции выше } } * This source code was highlighted with Source Code Highlighter.

Целиком проект можно слить здесь (зеркало).

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

Пост написан после прочтения данной статьи.

Tags:

Hubs:

Algorithms