Génération automatique de mélodie par la programmation par contraintes

RÉSUMÉ: La programmation par contraintes est un type de programmation déclarative, un paradigme naturellement adapté au traitement de problèmes musicaux. En effet, la composition musicale s'apparente à un processus déclaratif pendant lequel le compositeur travaille pour créer de la musique qui respecte les règles générales de l'art et les critères plus spécifiques du style adopté tout en y incorporant ses propres contraintes. Le parallèle entre cet exercice et la résolution d'un problème de satisfaction de contraintes se fait donc instinctivement. La principale difficulté se trouve au niveau de la modélisation du problème. Une pièce musicale est composée de plusieurs dimensions entre lesquelles existent beaucoup d'interactions. Il est pratiquement impossible pour un système informatique de représenter précisément toutes ces dépendances. Les systèmes de contraintes conçus pour traiter de problèmes musicaux se concentrent alors sur des dimensions en particulier. Parmi ces problèmes, on retrouve la génération de mélodie qui concerne donc les hauteurs et les durées des notes d'une ligne mélodique accompagnée par une suite d'accords. La modélisation d'un tel problème se concentre sur une séquence de notes et ne présente donc aucun élément de polyphonie ou d'instrumentation par exemple, ce qui simplifie la situation. L'objectif de ce projet est de concevoir un système de génération automatique de mélodie selon une suite d'accords donnée qui utilise les informations d'un corpus pour guider la composition. Deux des principaux défis de ce type de problème sont l'organisation des variables et le contrôle de la structure globale de la mélodie générée. Pour relever le premier, nous avons émis l'hypothèse qu'un système structuré hiérarchiquement offrait le plus de flexibilité et permettrait donc d'exprimer les contraintes plus facilement. En ce qui concerne la structure du résultat, nous avons mis au point un algorithme de détection de patrons répétitifs basé sur des arbres des suffixes qui permet au système de répliquer les éléments de la structure d'une mélodie existante. ABSTRACT: Constraint programming belongs to the declarative programming paradigm which is naturally suited to tackle musical problems. Musical composition can be seen as a declarative process during which the composer works to create music respecting the general and specific rules of the chosen style and also adds his own touch. The connection between this process and resolving a constraint satisfaction problem is made instinctively. The main challenge of this field is modeling the problem because of all the different dimensions which interact together in a music piece. It is virtually impossible for a computer-based system to provide a view of the same quality a human composer would have. Thus, constraint systems designed to tackle musical problems usually focus on specific dimensions. One of these problems consists of generating a melody given a chord sequence, which only involves note durations and pitches, there is no concept of polyphony or instrumentation, for example. The goal of this project is to design and implement a system able to generate a melody given a chord sequence, using information from a corpus to guide composition. Two of the main challenges of this kind of problems are the variables arrangement and the control of the global structure of the melody. Regarding variables, we made the assumption that a hierarchical organization would improve the system's flexibility which would make it easier to express constraints. For the structure, we designed an algorithm which uses suffix trees to detect repeating patterns in existing melodies and made the system able to replicate them in the result. Our system is made of hierarchically organized blocs. The melody is made of bars which contain chords under which are located the notes. Each block has a variable number of notes which needs to be fixed first in order to instantiate the corresponding variables. This means that the system has to work in two phases. The first one assigns a rhythm pattern to every bar, which decides both the number of notes and their durations. The second phase fixes the pitch of every note of the melody