Grammar-based compression and its use in symbolic music analysis

We apply Context-free Grammars (CFG) to measure the structural information content of a symbolic music string. CFGs are appropriate to this domain because they highlight hierarchical patterns, and their dictionary of rules can be used for compression. We adapt this approach to estimate the conditional Kolmogorov complexity of a string with a concise CFG of another string. Thus, a related string may be compressed with the production rules for the first string. We then define an information distance between two symbolic music strings, and show that this measure can separate genres, composers and musical styles. Next, we adapt our approach to a model-selection problem, expressing the model as a CFG with restricted size, generated from a set of representative strings. We show that a well-generated CFG for a composer identifies characteristic patterns that can significantly compress other pieces from the same composer, while not being useful on pieces from different composers. We identify further opportunities of this approach, including using CFGs for generating new music in the style of a composer.