Grammar-based compression and its use in symbolic music analysis. Issue 1 (2nd January 2023)

• Record Type: Journal Article
• Authors: Mondol, Tiasa; Brown, Daniel G.
• Is Part Of: Journal of mathematics and music. Volume 17:Issue 1(2023)
• Page Start: 133
• Page End: 150
• Publication Date: 2023-01-02
• Subjects: Kolmogorov complexity -- conditional Kolmogorov complexity -- best-fitting model selection -- context-free grammar -- music information retrieval; 68Q30 -- 03D32 -- 68Q42; applied computing -- Theory of Computation -- Information systems Information retrieval; Music theory -- Periodicals; Music -- Mathematical models -- Periodicals; Music -- Mathematics -- Periodicals; 781.2
• DOI: 10.1080/17459737.2021.2002956
• Languages: English
• ISSNs: 1745-9737

Abstract

Abstract : 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.