Концептуальный обзор и сквозная реализация Python
Делиться
Музыкальные композиторы известны тем, что повторно используют мотивы (то есть характерные последовательности нот или мелодические фрагменты) в своих произведениях. Например, такие известные голливудские композиторы, как Джон Уильямс («Супермен», «Звёздные войны», «Гарри Поттер») и Ханс Циммер («Начало», «Интерстеллар», «Тёмный рыцарь»), искусно перерабатывают мотивы, создавая мгновенно узнаваемые, фирменные саундтреки.
В этой статье мы покажем, как сделать нечто подобное, используя науку о данных. В частности, мы будем сочинять музыку, используя теоретико-графовую концепцию эйлеровых путей, чтобы собирать стохастически сгенерированные музыкальные мотивы в акустически приятные мелодии. После обзора теоретических концепций и канонического примера использования для закрепления нашего понимания основ мы рассмотрим полную реализацию алгоритмической процедуры сочинения музыки на Python.
Примечание: Все рисунки в следующих разделах созданы автором данной статьи.
Учебник по эйлеровым путям
Предположим, у нас есть граф, состоящий из узлов и рёбер. Степень узла в неориентированном графе определяется числом рёбер, соединённых с этим узлом. Входящая и исходящая степени узла в ориентированном графе определяются числом входящих и исходящих рёбер для этого узла соответственно. Эйлеров путь определяется как обход узлов и рёбер графа, который начинается в некотором узле и заканчивается в некотором узле, проходя через каждое ребро ровно один раз; если путь начинается и заканчивается в одном и том же узле, это называется эйлеровым циклом.
В неориентированном графе эйлеров путь существует тогда и только тогда, когда ни один или два узла имеют нечётную степень, и все узлы с ненулевой степенью являются частью одной компоненты связности графа. В то же время, в ориентированном графе эйлеров путь существует тогда и только тогда, когда не более чем один узел (начальный) имеет на одно исходящее ребро больше, чем входящее, не более чем один узел (конечный) имеет на одно входящее ребро больше, чем исходящее, все остальные узлы имеют одинаковое количество входящих и исходящих рёбер, и все узлы с ненулевой степенью захода или исхода являются частью одной компоненты связности. Ограничения, связанные с принадлежностью к одной компоненте связности, гарантируют достижимость всех рёбер графа.
На рисунках 1 и 2 ниже показаны графические изображения Семи мостов Кёнигсберга и Дома Николауса соответственно. Это две известные головоломки, требующие поиска эйлерова пути.
На рисунке 1 два острова (Кнайпхоф и Ломзе) соединены друг с другом и двумя материковыми частями (Альтштадт и Форштадт) города Кёнигсберга в Пруссии в общей сложности семью мостами. Вопрос в том, существует ли способ посетить все четыре части города, используя каждый мост ровно один раз; другими словами, мы хотим узнать, существует ли эйлеров путь для неориентированного графа, показанного на рисунке 1. В 1736 году известный математик Леонард Эйлер, в честь которого эйлеровы пути и циклы получили свое название, показал, что для этой конкретной задачи такой путь не может существовать. Мы можем понять, почему, используя определения, изложенные ранее: все четыре части (узлы) города Кёнигсберга имеют нечетное количество мостов (ребер), т. е. не бывает так, чтобы ноль или два узла имели нечетную степень.
На рисунке 2 требуется нарисовать Дом Николауса, начиная с любого из пяти углов (узлы, обозначенные цифрами 1–5) и проведя каждую линию (ребро) ровно один раз. Здесь мы видим, что два узла имеют степень четыре, два узла — степень три, а один узел — степень два, поэтому должен существовать эйлеров путь. Фактически, как показывает следующая анимация, для этой головоломки, по-видимому, возможно построить 44 различных эйлеровых пути:
Эйлеровы пути можно вывести программно с помощью алгоритма Хирхольцера, как объясняется в видео ниже:
Алгоритм Хирхольцера использует метод поиска с возвратом, который более подробно рассматривается в этой статье.
Эйлеровы пути для сборки фрагментов
Имея набор узлов, представляющих фрагменты информации, мы можем использовать концепцию эйлеровых путей для осмысленного объединения фрагментов.
Чтобы понять, как это работает, начнём с задачи, не требующей особых знаний в данной области: можно ли расположить эти числа в последовательности x1, x2, …, xn так, чтобы цифра десятков числа xi совпадала с цифрой единиц числа xi+1? Предположим, у нас есть следующий список: [22, 23, 25, 34, 42, 55, 56, 57, 67, 75, 78, 85]. При внимательном рассмотрении можно заметить, что, например, если xi = 22 (с цифрой единиц 2), то xi+1 может быть 23 или 25 (цифрой десятков 2), тогда как если xi = 78, то xi+1 может быть только 85. Если теперь преобразовать список целых чисел в ориентированный граф, где каждая цифра является узлом, а каждое двузначное целое число смоделировано как направленное ребро от своей цифры десятков к своей цифре единиц, то нахождение эйлерова пути в этом ориентированном графе даст нам одно из возможных решений нашей задачи, что и требуется. Реализация этого подхода на Python представлена ниже:
from collections import defaultdict def find_eulerian_path(numbers): # Инициализация графа graph = defaultdict(list) indeg = defaultdict(int) outdeg = defaultdict(int) for num in numbers: a, b = divmod(num, 10) # a = цифра десятков, b = цифра единиц graph[a].append(b) outdeg[a] += 1 indeg[b] += 1 # Поиск начального узла start = None start_nodes = end_nodes = 0 for v in set(indeg) | set(outdeg): outd = outdeg[v] ind = indeg[v] if outd — ind == 1: start_nodes += 1 start = v elif ind — outd == 1: end_nodes += 1 elif ind == outd: continue else: return None # Эйлеров путь невозможен if not start: start = numbers[0] // 10 # Произвольное начало if Эйлеров контур if not ( (start_nodes == 1 and end_nodes == 1) or (start_nodes == 0 and end_nodes == 0) ): return None # Эйлеров путь невозможен # Использовать алгоритм Хирхольцера path = [] stack = [start] local_graph = {u: list(vs) for u, vs in graph.items()} while stack: u = stack[-1] if local_graph.get(u): v = local_graph[u].pop() stack.append(v) else: path.append(stack.pop()) path.reverse() # Получаем путь в обратном порядке из-за возврата # Преобразуем путь в последовательность решений с исходными числами result = [] for i in range(len(path) — 1): result.append(path[i] * 10 + path[i+1]) return result if len(result) == len(numbers) else None given_integer_list = [22, 23, 25, 34, 42, 55, 56, 57, 67, 75, 78, 85] solution_sequence = find_eulerian_path(given_integer_list) print(solution_sequence)
Результат:
[23, 34, 42, 22, 25, 57, 78, 85, 56, 67, 75, 55]
Сборка фрагментов ДНК является каноническим примером использования описанной выше процедуры в области биоинформатики. По сути, в процессе секвенирования ДНК учёные получают несколько коротких фрагментов ДНК, которые необходимо сшить вместе для получения подходящих кандидатов на полную последовательность ДНК. Это потенциально можно сделать относительно эффективно, используя концепцию эйлерова пути (подробнее см. в этой статье). Каждый фрагмент ДНК, известный как k-мер, состоит из k букв, взятых из множества {A, C, G, T}, обозначающих нуклеотидные основания, из которых может состоять молекула ДНК; например, ACT и CTG будут 3-мерами. Теперь можно построить так называемый граф де Брейна с узлами, представляющими префиксы (k-1)-меров (например, AC для ACT и CT для CTG), и направленными рёбрами, обозначающими перекрытие между исходным и конечным узлами (например, будет ребро, идущее от AC к CT из-за перекрывающейся буквы C). Получение подходящего кандидата на полную последовательность ДНК сводится к поиску эйлерова пути в графе де Брейна. Видео ниже демонстрирует рабочий пример:
Алгоритм генерации мелодий
Если у нас есть набор фрагментов, представляющих музыкальные мотивы, мы можем использовать подход, описанный в предыдущем разделе, чтобы расположить мотивы в разумной последовательности, преобразуя их в граф де Брейна и определив эйлеров путь. Далее мы рассмотрим полную реализацию этого на Python. Код протестирован на macOS Sequoia 15.6.1.
Часть 1: Установка и настройка проекта
Для начала нам нужно установить FFmpeg и FluidSynth — два полезных инструмента для обработки аудиоданных. Вот как установить их с помощью Homebrew на Mac:
brew install ffmpeg brew install fluid-synth
Мы также будем использовать UV для управления проектами на Python. Инструкции по установке можно найти здесь.
Теперь мы создадим папку проекта с именем eulerian-melody-generator, файл main.py для хранения логики генерации мелодий и виртуальную среду на основе Python 3.12:
mkdir eulerian-melody-generator cd eulerian-melody-generator uv init —bare touch main.py uv venv —python 3.12 source .venv/bin/activate
Далее нам необходимо создать файл requirements.txt со следующими зависимостями и поместить файл в каталог eulerian-melody-generator:
matplotlib==3.10.5 midi2audio==0.1.1 midiutil==1.2.1 networkx==3.5
Пакеты midi2audio и midiutil необходимы для обработки звука, а matplotlib и networkx будут использоваться для визуализации графика де Брейна. Теперь мы можем установить эти пакеты в нашу виртуальную среду:
uv add -r requirements.txt
Выполните команду uv pip list, чтобы убедиться, что пакеты установлены.
Наконец, нам понадобится файл SoundFont для рендеринга аудиосигнала в ответ на MIDI-данные. В этой статье мы будем использовать файл TimGM6mb.sf2, который можно найти на сайте MuseScore или скачать прямо здесь. Мы разместим его рядом с файлом main.py в каталоге eulerian-melody-generator.
Часть 2: Логика генерации мелодии
Теперь реализуем логику генерации мелодии в main.py. Начнём с добавления соответствующих операторов импорта и определения некоторых полезных переменных поиска:
import os import random import subprocess from collections import defaultdict from midiutil import MIDIFile from midi2audio import FluidSynth import networkx as nx import matplotlib.pyplot as plt # Определите путь к SoundFont (предположим, что он совпадает с рабочим каталогом) BASE_DIR = os.path.dirname(os.path.abspath(__file__)) SOUNDFONT_PATH = os.path.abspath(os.path.join(BASE_DIR, «.», «TimGM6mb.sf2»)) # 12-нотная хроматическая ссылка NOTE_TO_OFFSET = { «C»: 0, «C#»:1, «D»:2, «D#»:3, «E»:4, «F»:5, «F#»:6, «G»:7, «G#»:8, «A»:9, «A#»:10, «B»:11 } # Популярный интервал, удобный для поп-музыки Модели (в полутонах от основного тона) MAJOR = [0, 2, 4, 5, 7, 9, 11] NAT_MINOR = [0, 2, 3, 5, 7, 8, 10] MAJOR_PENTA = [0, 2, 4, 7, 9] MINOR_PENTA = [0, 3, 5, 7, 10] MIXOLYDIAN = [0, 2, 4, 5, 7, 9, 10] DORIAN = [0, 2, 3, 5, 7, 9, 10]
Мы также определим несколько вспомогательных функций для создания словаря гамм во всех двенадцати тональностях:
def generate_scales_all_keys(scale_name, intervals): «»» Построить заданную гамму во всех 12 тональностях. «»» scales = {} chromatic = [*NOTE_TO_OFFSET] # Получить ключи словаря for i, root in enumerate(chromatic): notes = [chromatic[(i + step) % 12] for step in intervals] key_name = f»{root}-{scale_name}» scales[key_name] = notes return scales def generate_scale_dict(): «»» Построить главный словарь всех тональностей. «»» scale_dict = {} scale_dict.update(generate_scales_all_keys(«Major», MAJOR)) scale_dict.update(generate_scales_all_keys(«Natural-Minor», NAT_MINOR)) scale_dict.update(generate_scales_all_keys(«Major-Pentatonic», MAJOR_PENTA)) scale_dict.update(generate_scales_all_keys(«Минорная пентатоника», MINOR_PENTA)) scale_dict.update(generate_scales_all_keys(«Миксолидийский», MIXOLYDIAN)) scale_dict.update(generate_scales_all_keys(«Дорийский», ДОРИАНСКИЙ)) return scale_dict
Далее мы реализуем функции для генерации k-меров и соответствующего им графа де Брейна. Обратите внимание, что генерация k-меров ограничена тем, чтобы гарантировать наличие эйлерова пути в графе де Брейна. Мы также используем случайное начальное значение при генерации k-меров для обеспечения воспроизводимости:
def generate_eulerian_kmers(k, count, scale_notes, seed=42): «»» Генерирует k-меры по заданной шкале, которые образуют связный граф Де Брейна с гарантированным эйлеровым путем. «»» random.seed(seed) if count < 1: return [] # выбирает случайный начальный кортеж из (k-1) start_node = tuple(random.choice(scale_notes) for _ in range(k-1)) nodes = {start_node} edges = [] out_deg = defaultdict(int) in_deg = defaultdict(int) current = start_node for _ in range(count): # выбирает следующую ноту из шкалы next_note = random.choice(scale_notes) next_node = tuple(list(current[1:]) + [next_note]) # добавляет ребро из k-меров edges.append(current + (next_note,)) nodes.add(next_node) out_deg[current] += 1 in_deg[next_node] += 1 current = next_node # проход продолжается # Проверяем дисбаланс степеней и повторяем попытку для удовлетворения условия степени эйлерова пути start_candidates = [n for n in nodes if out_deg[n] - in_deg[n] > 0] end_candidates = [n for n in nodes if in_deg[n] — out_deg[n] > 0] if len(start_candidates) > 1 or len(end_candidates) > 1: # Для простоты: перегенерируем, пока условие не выполнится return generate_eulerian_kmers(k, count, scale_notes, seed+1) return edges def build_debruijn_graph(kmers): «»» Построение графа в стиле Де Брейна. «»» adj = defaultdict(list) in_deg = defaultdict(int) out_deg = defaultdict(int) для kmer в kmers: prefix = tuple(kmer[:-1]) suffix = tuple(kmer[1:]) adj[prefix].append(suffix) out_deg[prefix] += 1 in_deg[suffix] += 1 return adj, in_deg, out_deg
Мы реализуем функцию визуализации и сохранения графика де Брейна для дальнейшего использования:
def generate_and_save_graph(graph_dict, output_file=»debruijn_graph.png», seed=100, k=1): «»» Визуализируйте граф и сохраните его как PNG. «»» # Создайте ориентированный граф G = nx.DiGraph() # Добавьте ребра из словаря смежности for prefix, suffixes in graph_dict.items(): for suffix in suffixes: G.add_edge(prefix, suffix) # Разметка для узлов (большее k означает большее расстояние между узлами) pos = nx.spring_layout(G, seed=seed, k=k) # Нарисуйте узлы и ребра plt.figure(figsize=(10, 8)) nx.draw_networkx_nodes(G, pos, node_size=1600, node_color=»skyblue», edgecolors=»black») nx.draw_networkx_edges( G, pos, arrowstyle=»-|>», arrowsize=20, edge_color=»black», connectionstyle=»arc3,rad=0.1″, min_source_margin=20, min_target_margin=20 ) nx.draw_networkx_labels(G, pos, labels={node: » «.join(node) for node in G.nodes()}, font_size=10) # Метки ребер edge_labels = { (u,v): «» for u,v in G.edges() } nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color=»red», font_size=8) plt.axis(«off») plt.tight_layout() plt.savefig(output_file, format=»PNG», dpi=300) plt.close() print(f»Graph saved to {output_file}»)
Далее мы реализуем функции для построения эйлерова пути в графе де Брейна и преобразуем его в последовательность нот. В отличие от подхода к сборке фрагментов ДНК, который обсуждался ранее, мы не будем дедуплицировать перекрывающиеся части k-меров в процессе преобразования, чтобы мелодия получилась более эстетичной:
def find_eulerian_path(adj, in_deg, out_deg): «»» Найти эйлеров путь в графе де Брейна. «»» start = None for node in set(list(adj) + list(in_deg)): if out_deg[node] — in_deg[node] == 1: start = node break if start is None: start = next(n for n in adj if adj[n]) stack = [start] path = [] local_adj = {u: vs[:] for u, vs in adj.items()} while stack: v = stack[-1] if local_adj.get(v): u = local_adj[v].pop() stack.append(u) else: path.append(stack.pop()) return path[::-1] def flatten_path(path_nodes): «»» Свести список кортежей заметок в один список. «»» flattened = [] для kmer в path_nodes: flattened.extend(kmer) return flattened
Теперь мы напишем несколько функций для создания и экспорта мелодии в формате MP3. Ключевая функция — compose_and_export, которая добавляет вариации к рендерингу нот, составляющих эйлеров путь (например, разные длительности нот и октавы), чтобы итоговая мелодия не звучала слишком монотонно. Мы также подавляем/перенаправляем подробный вывод FFmpeg и FluidSynth:
def note_with_octave_to_midi(note, octave): «»» Вспомогательная функция для преобразования музыкальной высоты звука, например, «C#» в некоторой октаве, в её числовой номер MIDI-ноты. «»» return 12 * (octave + 1) + NOTE_TO_OFFSET[note] @contextlib.contextmanager def suppress_fd_output(): «»» Перенаправляет stdout и stderr на уровень файлового дескриптора ОС. Это позволяет перехватывать вывод из библиотек C, таких как FluidSynth. «»» with open(os.devnull, 'w') as devnull: # Дублировать исходные файловые дескрипторы old_stdout_fd = os.dup(1) old_stderr_fd = os.dup(2) try: # Перенаправление в /dev/null os.dup2(devnull.fileno(), 1) os.dup2(devnull.fileno(), 2) yield Finally: # Восстановить исходные файловые дескрипторы os.dup2(old_stdout_fd, 1) os.dup2(old_stderr_fd, 2) os.close(old_stdout_fd) os.close(old_stderr_fd) def compose_and_export(final_notes, bpm=120, midi_file=»output.mid», wav_file=»temp.wav», mp3_file=»output.mp3″, soundfont_path=SOUNDFONT_PATH): # Ритмические мотивы в классическом стиле rhythmic_patterns = [ [1.0, 1.0, 2.0], # четверть, четверть, половина [0.5, 0.5, 1.0, 2.0], # восьмая, восьмая, четверть, половина [1.5, 0.5, 1.0, 1.0], # четверть с точкой, восьмая, четверть, четверть [0.5, 0.5, 0.5, 0.5, 2.0] # серия восьмых, затем половина ] # Построение контура октавы: подъем, затем спуск base_octave = 4 peak_octave = 5 contour = [] half_len = len(final_notes) // 2 for i in range(len(final_notes)): if i < half_len: # Постепенное подъем contour.append(base_octave if i < half_len // 2 else peak_octave) else: # Спуск contour.append(peak_octave if i < (half_len + half_len // 2) else base_octave) # Назначение событий в соответствии с ритмическими рисунками и контуром events = [] note_index = 0 while note_index < len(final_notes): pattern = random.choice(rhythmic_patterns) for dur in pattern: if note_index >= len(final_notes): break octave = contour[note_index] events.append((final_notes[note_index], octave, dur)) note_index += 1 # Запись MIDI mf = MIDIFile(1) track = 0 mf.addTempo(track, 0, bpm) time = 0 for note, octv, dur in events: pitch = note_with_octave_to_midi(note, octv) mf.addNote(track, channel=0, pitch=pitch, time=time, duration=dur, volume=100) time += dur with open(midi_file, «wb») as out_f: mf.writeFile(out_f) # Рендеринг в WAV с помощью suppress_fd_output(): fs = FluidSynth(sound_font=soundfont_path) fs.midi_to_audio(midi_file, wav_file) # Конвертировать в MP3 subprocess.run( [ «ffmpeg», «-y», «-hide_banner», «-loglevel», «quiet», «-i», wav_file, mp3_file ], check=True ) print(f»Сгенерирован {mp3_file}»)
Наконец, мы покажем, как использовать генератор мелодий в разделе if name == «main» файла main.py. Несколько параметров — масштаб, темп, длина k-мера, количество k-меров, количество повторений (или циклов) эйлерова пути и начальное значение случайной величины — можно изменять для создания различных мелодий:
если __name__ == «__main__»: SCALE = «C-Major-Pentatonic» # Установите «key-scale», например «C-Mixolydian» BPM = 200 # Ударов в минуту (музыкальный темп) KMER_LENGTH = 4 # Длина каждого k-мера NUM_KMERS = 8 # Сколько k-меров нужно сгенерировать NUM_REPEATS = 8 # Как часто должна повторяться окончательная последовательность нот RANDOM_SEED = 2 # Начальное значение для воспроизведения результатов scale_dict = generate_scale_dict() chosen_scale = scale_dict[SCALE] print(«Выбранный лад:», chosen_scale) kmers = generate_eulerian_kmers(k=KMER_LENGTH, count=NUM_KMERS, scale_notes=chosen_scale, seed=RANDOM_SEED) adj, in_deg, out_deg = build_debruijn_graph(kmers) generate_and_save_graph(graph_dict=adj, output_file=»debruijn_graph.png», seed=20, k=2) path_nodes = find_eulerian_path(adj, in_deg, out_deg) print(«Эйлеров путь:», path_nodes) final_notes = flatten_path(path_nodes) * NUM_REPEATS # Несколько циклов эйлерова пути mp3_file = f»{SCALE}_v{RANDOM_SEED}.mp3″ # Создание имени файла с возможностью поиска compose_and_export(final_notes=final_notes, bpm=BPM, mp3_file=mp3_file)
Выполнение uv run main.py дает следующий вывод:
Выбранный масштаб: ['C', 'D', 'E', 'G', 'A'] График сохранен в debruijn_graph.png Эйлеров путь: [('C', 'C', 'C'), ('C', 'C', 'E'), ('C', 'E', 'D'), ('E', 'D', 'E'), ('D', 'E', 'E'), ('E', 'E', 'A'), ('E', 'A', 'D'), ('A', 'D', 'A'), ('D', 'A', 'C')] Сгенерировано C-Major-Pentatonic_v2.mp3
В качестве более простой альтернативы описанным выше действиям автор этой статьи создал библиотеку Python emg для достижения того же результата, предполагая, что FFmpeg и FluidSynth уже установлены (подробности см. здесь). Установите библиотеку с помощью pip install emg или uv add emg и используйте её, как показано ниже:
from emg.generator import EulerianMelodyGenerator # Путь к файлу SoundFont sf2_path = «TimGM6mb.sf2″ # Создание экземпляра генератора generator = EulerianMelodyGenerator( soundfont_path=sf2_path, scale=»C-Major-Pentatonic», bpm=200, kmer_length=4, num_kmers=8, num_repeats=8, random_seed=2 ) # Запуск полного конвейера generator.run_generation_pipeline( graph_png_path=»debruijn_graph.png», mp3_output_path=»C-Major-Pentatonic_v2.mp3″ )
(Необязательно) Часть 3: Конвертация MP3 в MP4
Мы можем использовать FFmpeg для преобразования файла MP3 в файл MP4 (используя экспортированный PNG-файл графика де Брейна в качестве обложки), который можно загрузить на такие платформы, как YouTube. Параметр -loop 1 повторяет изображение PNG на протяжении всего аудио, -tune stillimage оптимизирует кодирование для статических изображений, -shortest гарантирует, что видео остановится примерно в момент окончания аудио, а -pix_fmt yuv420p гарантирует совместимость выходного формата пикселей с большинством плееров:
ffmpeg -loop 1 -i debruijn_graph.png -i C-Major-Pentatonic_v2.mp3 -c:v libx264 -tune stillimage -c:a aac -b:a 192k -pix_fmt yuv420p -shortest C-Major-Pentatonic_v2.mp4
Вот конечный результат, загруженный на YouTube:
Обертка
В этой статье мы увидели, как такая абстрактная тема, как теория графов, может найти практическое применение в, казалось бы, не связанной с ней области алгоритмической музыкальной композиции. Интересно, что использование нами стохастически сгенерированных музыкальных фрагментов для построения эйлерова пути, а также случайные вариации длительности нот и октав перекликаются с практикой алеаторической музыкальной композиции (alea – латинское слово, означающее «игральные кости»), в которой некоторые аспекты композиции и её исполнения предоставлены случаю.
Помимо музыки, концепции, обсуждаемые в предыдущих разделах, находят практическое применение в науке о данных в ряде других областей, таких как биоинформатика (например, сборка фрагментов ДНК), археология (например, реконструкция древних артефактов по разрозненным фрагментам на раскопках) и логистика (например, оптимальное планирование доставки посылок). По мере развития технологий и всё большей цифровизации мира эйлеровы пути и связанные с ними концепции теории графов, вероятно, найдут всё больше инновационных применений в самых разных областях.
Источник: towardsdatascience.com
