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 tree-like 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 Haskell, 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.