Using general-purpose compression algorithms for music analysis

Abstract

General-purpose compression algorithms encode files as dictionaries of substrings with the positions of these strings’ occurrences. We hypothesized that such algorithms could be used for pattern discovery in music. We compared LZ77, LZ78, Burrows–Wheeler and COSIATEC on classifying folk song melodies. A novel method was used, combining multiple viewpoints, the k-nearest-neighbour algorithm and a novel distance metric, corpus compression distance. Using single viewpoints, COSIATEC outperformed the general-purpose compressors, with a classification success rate of 85% on this task. However, by combining 8 of the 10 best-performing viewpoints, including seven that used LZ77, the classification success rate rose to over 94%. In a second experiment, we compared LZ77 with COSIATEC on the task of discovering subject and countersubject entries in fugues by J.S. Bach. When voice information was absent in the input data, COSIATEC outperformed LZ77 with a mean score of 0.123, compared with 0.053 for LZ77. However, when the music was processed a voice at a time, the score for LZ77 more than doubled to 0.124. We also discovered a significant correlation between compression factor and score for all the algorithms, supporting the hypothesis that the best analyses are those represented by the shortest descriptions.

Keywords:

• representation
• music analysis
• pattern discovery
• Lempel–Ziv
• folk music
• data compression
• music information retrieval

Acknowledgements

The work reported in this paper was carried out as part of the EU FP7 project, ‘Learning to Create’ (Lrn2Cre8).

Notes

1 See, for example, chapter 25 of book 2 of Aristotle’s Posterior Analytics.

2 See, for example, the results reported at http://tukaani.org/lzma/benchmarks.html.

3 Of course, in practice, our alphabet would be a finite subset of , but this would still be very large and therefore significantly increase the size of the dictionary.

4 In practice, when , the algorithm returns (x, c). This improves compression a little because it uses one character, whereas ‘’ uses two.

Additional information

Funding

The project Lrn2Cre8 acknowledges the financial support of the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under FET grant number 610859.