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

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


    Введение


    Работать мы будем с файлами в формате 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"?><br><!DOCTYPE MIDIFile PUBLIC<br> "-//Recordare//DTD MusicXML 0.9 MIDI//EN"<br> "http://www.musicxml.org/dtds/midixml.dtd"><br><MIDIFile><br><Format>0</Format><br><TrackCount>1</TrackCount><br><TicksPerBeat>384</TicksPerBeat><br><TimestampType>Absolute</TimestampType><br><Track Number="0"><br> <Event><br>  <Absolute>0</Absolute><br>  <ControlChange Channel="2" Control="91" Value="46"/><br> </Event><br> <Event><br>  <Absolute>0</Absolute><br>  <ProgramChange Channel="2" Number="49"/><br> </Event><br> <Event><br>  <Absolute>0</Absolute><br>  <ControlChange Channel="2" Control="0" Value="0"/><br> </Event><br>...<br> <Event><br>  <Absolute>24908</Absolute><br>  <NoteOff Channel="11" Note="41" Velocity="127"/><br> </Event><br> <Event><br>  <Absolute>24912</Absolute><br>  <NoteOn Channel="11" Note="41" Velocity="127"/><br> </Event><br> <Event><br>  <Absolute>24956</Absolute><br>  <NoteOff Channel="11" Note="41" Velocity="127"/><br> </Event><br> <Event><br>  <Absolute>24960</Absolute><br>  <NoteOn Channel="11" Note="41" Velocity="127"/><br> </Event><br>...<br></Track><br></MIDIFile><br><br>* This source code was highlighted with Source Code Highlighter.


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

    шКодим


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


    Заодно напишем класс для сравнения „аккордов“:
      public class ChordComparer : IEqualityComparer<Chord><br>  {<br>    public bool Equals(Chord x, Chord y)<br>    {<br>      if (x.Delay != y.Delay)<br>        return false;<br>      if (x.Events.Count != y.Events.Count)<br>        return false;<br>      foreach (var ev in x.Events)<br>        if (!y.Events.Contains(ev))<br>          return false;<br>      foreach (var ev in y.Events)<br>        if (!x.Events.Contains(ev))<br>          return false;<br>      return true;<br>    }<br><br>    public int GetHashCode(Chord obj)<br>    {<br>      int hash = obj.Delay.GetHashCode();<br>      obj.Events.ForEach(ev => hash += ev.GetHashCode());<br>      return hash;<br>    }<br>  }<br><br>* This source code was highlighted with Source Code Highlighter.


    И класс для сравнения последовательностей „аккордов“:
      public class ListComparer : IEqualityComparer<List<Chord>><br>  {<br>    private ChordComparer cc = new ChordComparer();<br><br>    public bool Equals(List<Chord> x, List<Chord> y)<br>    {<br>      if (x.Count != y.Count)<br>        return false;<br>      for (int i = 0; i < x.Count; i++)<br>        if (!cc.Equals(x[i], y[i]))<br>          return false;<br>      return true;<br>    }<br><br>    public int GetHashCode(List<Chord> obj)<br>    {<br>      int hash = 0;<br>      obj.ForEach(ch => ch.Events.ForEach(ev => hash += ev.GetHashCode()));<br>      obj.ForEach(ch => hash += ch.Delay.GetHashCode());<br>      return hash;<br>    }<br>  }<br><br>* This source code was highlighted with Source Code Highlighter.


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


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

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

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

    Подробнее
    Реклама
    Комментарии 61
    • –10
      Пример в студию!
      • 0
        а в посте пример вам чем не угодил?)
        • 0
          не проигрываются через листер камандера в отличии от оригинала
          • 0
            Я тоже смог послушать только оригинал =(
            • 0
              под виндой прекрасно слушается виндоус медиаплеером, квиктаймом, км плеером, под другими не знаю
          • –18
            я слепой прости, поцан
        • +8
          «об очень простом способе» :)
          • +1
            Нереально понравилось… Спасибо.
            • +5
              Просто здорово! Вот из-за таких статей я люблю хабр!
              • НЛО прилетело и опубликовало эту надпись здесь
                • +12
                  о боже, из-за моего поста вы спятили, простите, я больше так не буду…
                • НЛО прилетело и опубликовало эту надпись здесь
                  • +3
                    Хабракири?
                    • +2
                      Хочет выйти на первое место в рейтинге отхабренных.
                  • 0
                    Теперь всё это в веб-оболочку надо. Чтоб юзали взрослые и дети.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +2
                        Я после первого же вашего поста заподозрил ВЕЩЕСТВА.
                      • +2
                        Насколько я понимаю весь алгоритм вертится вокруг цепей Маркова. В свое время с помощью них писал генератор текстов. Там ещё был такой момент — для англоязычных текстов для удобоваримого результата словарь надо было строить по 2 предыдущим словам, для русскоязычного — по трем.
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • +7
                            О боже, на хабре завелись боты-идиоты…
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • +2
                              Когда-то давно пытался написать что-то подобное, правда все было гораздо проще — выбираем тонику, а от нее в минорной гамме начинаем строить рандомную мелодию. Правила просты — 3 вида ритма 1\2, 1\4 и 1\8. Переходы +- 2, 3, 5 полутонов + повторять и пытаться заполнить до 2 или 4-х тактов, проиграть пару раз.

                              На выходе получался абсолютный и немного управляемый рандом (если уж пошли в плюс — так, пару раз прибавить в тоне к примеру до такта или половины, а после обратно. В итоге после получаса такой вот генерациии можно было найти пару прикольно и довольно приятно звучащих моментов. Но с музыкальной точки зрения считаю что они не несли в себе ничего — что-то подобное у меня получалось когда я сам сидел и под метроном пытался импровизировать в ля-миноре по часу или полтора, находя «правильные» и красивые фразы.

                              А вообще считаю что врядли можно заменить полноценного композитора, уж слишком безграничная эта область. Если и получиться что-то подобное, то на выходе будем получать обыкновенный «корм», который и так есть в 90% в любом стиле. Пытаться найти новое звучание — тоже не вариант, оно каждый день находится сотней школьников, которые считают что за год игры на инструменте они всему научились и теперь могут творить.

                              Тут же главное правильно подать это все ;)
                              • 0
                                тоже с MIDI работал?
                                • 0
                                  не, гораздо проще, софтинка эта писалась еще на паскале, и писала в очень простой формат — высота и длительность, а после это все скарливалось какой-то сторонней звуковой библиотечке для того же паскаля.
                              • 0
                                Только что закончил писать пост о грамматиках (8
                                Совпадение.

                                Но, на самом деле, как-то полученные файлы не слишком-то отличаются от оригинала )8
                                • 0
                                  и где этот пост?
                                • 0
                                  Не качает по ссылкам. Сделайте зеркала.
                                  • 0
                                    Why MIDI? Есть же MOD (и не только он), который обеспечивает всё то же, и ещё больше, а качество музыки зависит только от качества сэмплов. Но вообще-то интересно, спасибо :)
                                    • +1
                                      наверное потому, что MIDI — это в первую очередь протокол (повсеместно поддерживаемый), а MOD — antique формат =)
                                      • 0
                                        Не согласен про антиквариат. Музыка в Unreal Tournament хранится в одной из разновидностей MOD. Да и открытый он и простой.
                                        • +1
                                          см. «ложные друзья переводчика» =)
                                          MIDI тоже открытый.

                                          и вообще, для манипуляций лучше — текстовый формат Vortex Tracker'а ^_^'
                                          • +1
                                            все предельно просто: midi это всемирный стандарт записи и передачи нот в цифре. его поддерживает подавляющее большинство устройств (будь то realtek за 1$ с програмным синтезом в вашей материнке или синтезатор за 5k$, эмулирующий поведение аналогового) и софта (начиная от винампа, заканчивая всеми цифровыми DAW), он универсален. смысла переходить на что либо другое или использовать для некоторых целей другой формат нет, и вряд ли появится.
                                            • 0
                                              За пять килобаксов бывают и настоящие аналоговые синты с миди-управлением.
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                        • +6
                                          Я со своим аватаром не могу не отметиться в этом посте. =)
                                          • 0
                                            А что за мультик на пикче?)
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            • 0
                                              Вот на вольфраме правильно результать назвали — композиция.
                                              Ибо то, что генерируется алгоритмом никак не может быть музыкой…
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                • 0
                                                  Композитор — ни разу не алгоритм.

                                                  Или вы к сочетанию композитор-композиция прицепились?
                                              • 0
                                                Сгенерировал партию на piano, и подумал, что наверняка у Aphex Twin'а есть что-то подобное)
                                                • 0
                                                  Примерно подобрал. В composition controls выставляем:
                                                  generator
                                                  rule type: 62
                                                  height: 25
                                                  instrumentation
                                                  Grand Piano — Chords 1
                                                  Grand Piano — Chords 2
                                                  Synth Bass — Bass 1
                                                  Synth Bass — Bass 2
                                                  Electric Piano 2 — Polyphonic

                                                  перкуссия Metronome или Hip-Hop
                                                  time controls
                                                  208 bpm
                                                  2 notes per beat

                                                  Еще можно надо поиграться с pitch mapping.
                                                  P.S.: пока игрался, чуть с ума не сошёл от этой какофонии)
                                              • +1
                                                Спасибо, интересно.

                                                У меня коллега на работе, в качестве кандидатской писал нечто подобное. Только у него строилась матрица вероятностей нот. У него нет аккаунта на Хабре, но он сейчас посмотрел Ваш код и проект и сказал, что плюсом у Вас является анализ в дереве предыдущих нот, тогда как у него — следующая нота строится лишь в зависимости от текущей, но, зато, у него учитывается вероятности ноты появления ноты в оригинальном произведении (не просто рандомом берётся). Если вдруг заинтересуетесь, могу скинуть его аську.
                                                • +1
                                                  Очень интересная и ГРАМОТНАЯ статья. Мне интересно, это так для себя или…
                                                • +1
                                                  не скачивает нифига. выложите в другое (нормальное, более распространненное место)
                                                  • +1
                                                    Интересная идея. Я экспериментировал так с текстами — из Властелина Колец отличные сказки получаются ;)

                                                    Только файлы с примерами не скачиваются — если можно, выложите куда-нибудь еще.
                                                    • +1
                                                      Спасибо огромное за то, что узнал про формат MusicXML. Уже давно ношу в голове несколько идей (правда о генерации гармонии, а не мелодии), но все мои попытки разобраться в формате MIDI не увенчались успехом (хотя сам формат хорош). А тут старый добрый XML. Супер!
                                                      • 0
                                                        Примеры не качаются.
                                                        • 0
                                                          добавил зеркала, буду рад если посоветуете, какими хранилищами пользуетесь вы, а то мне как-то не приходилось раньше.
                                                          • 0
                                                            Мне интересно, может ли эта техника использоваться для метаморфа малварей?..
                                                            • 0
                                                              а теперь то же самое с s3m/xm/it и игрописатели всего мира вам поставят памятник.
                                                            • –4
                                                              с одного говнохостинга на другой переложили… у вас подборка самых отстойных файлопомоек?
                                                              • +1
                                                                вместо того, чтобы умничать, лучше бы дали адреса НЕ говнохостингов, потому что выше я спросил, какие юзать, т.к. до этого не пользовался ими
                                                                • 0
                                                                  ge.tt — лучшее из того, что я видел. Просто, понятно, без рекламы.
                                                              • 0
                                                                есть ещё вот такой метод для генерации текста:
                                                                qmax.habrahabr.ru/blog/50630/

                                                                в своё время мы пробовали применить его для музыки,
                                                                но с фиксированной глубиной дерева (длинной левой части), и midi файлы ковырять не умели, поэтому «обучали» генерилку, вводя партитуры руками,
                                                                соотвественно, в правилах были только ноты мелодии, и их было весьма немного.
                                                                а в результате получалась, вообще говоря, лажа,
                                                                но очень похожая на твою :)

                                                                было бы интересно совместить эти два метода,
                                                                например, используя вероятностный в качестве «рандомом или каким-то другим методом»
                                                                • +1
                                                                  Просто красота :)

                                                                  Среди друзей-диджеев ходит прибаутка о том, как Tiesto пишет свои шедевры. Он просто открывает любой аудио редактор и нажимает File → Create new track и сохраняет в MP3, так вот о каком способе шла речь :)
                                                                  • 0
                                                                    это один из лучших постов хабра
                                                                    • 0
                                                                      Впечатлён, но как полученный xml конвертировать в midi? В mp3 понятно не получится, но из midi в mp3 понятно как.

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