Formal modeling of structural repetition using tree compression

Repetition is central to musical structure as it gives rise both to piece-wise and stylistic coherence. Identifying repetitions in music is computationally not trivial, especially when they are varied or deeply hidden within treelike structures. Rather than focusing on repetitions of musical events, we propose to pursue repeated structural relations between events. More specifically, given a context-free grammar that describes a tonal structure, we aim to computationally identify such relational repetitions within the derivation tree of the grammar. To this end, we first introduce the Template, a grammar-generic structure for generating trees that contain structural repetitions. We then approach the discovery of structural repetitions as a search for optimally compressible Templates that describe a corpus of pieces in the form of production-rule-labeled trees. To make it tractable, we develop a heuristic, inspired by tree compression algorithms, to approximate the optimally compressible Templates of the corpus. After implementing the algorithm in Haskell1, we apply it to a corpus of jazz harmony trees, where we assess its performance based on the compressibility of the resulting Templates and the music-theoretical relevance of the identified repetitions.