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

La programmation par contraintes est un type de programmation declarative, un paradigme naturellement adapte au traitement de problemes musicaux. En effet, la composition musicale s’apparente a un processus declaratif pendant lequel le compositeur travaille pour creer de la musique qui respecte les regles generales de l’art et les criteres plus specifiques du style adopte tout en y incorporant ses propres contraintes. Le parallele entre cet exercice et la resolution d’un probleme de satisfaction de contraintes se fait donc instinctivement. La principale difficulte se trouve au niveau de la modelisation du probleme. Une piece musicale est composee de plusieurs dimensions entre lesquelles existent beaucoup d’interactions. Il est pratiquement impossible pour un systeme informatique de representer precisement toutes ces dependances. Les systemes de contraintes concus pour traiter de problemes musicaux se concentrent alors sur des dimensions en particulier. Parmi ces problemes, on retrouve la generation de melodie qui concerne donc les hauteurs et les durees des notes d’une ligne melodique accompagnee par une suite d’accords. La modelisation d’un tel probleme se concentre sur une sequence de notes et ne presente donc aucun element de polyphonie ou d’instrumentation par exemple, ce qui simplifie la situation. L’objectif de ce projet est de concevoir un systeme de generation automatique de melodie selon une suite d’accords donnee qui utilise les informations d’un corpus pour guider la composition. Deux des principaux defis de ce type de probleme sont l’organisation des variables et le controle de la structure globale de la melodie generee. Pour relever le premier, nous avons emis l’hypothese qu’un systeme structure hierarchiquement offrait le plus de flexibilite et permettrait donc d’exprimer les contraintes plus facilement. En ce qui concerne la structure du resultat, nous avons mis au point un algorithme de detection de patrons repetitifs base sur des arbres des suffixes qui permet au systeme de repliquer les elements de la structure d’une melodie 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.