Discovering distorted repeating patterns in polyphonic music through longest increasing subsequences
Antti Laaksonen, Kjell Lemström · Journal of Mathematics and Music · 2021
We study the problem of identifying repetitions under transposition and time-warp invariances in polyphonic symbolic music. Using a novel onset-time-pair representation, we reduce the repeating pattern discovery problem to instances of the classical problem of finding the longest increasing subsequences. The resulting algorithm works in O(n2logn) time where n is the number of notes in a musical work. We also study windowed variants of the problem where onset-time differences between notes are restricted, and show that they can also be solved in O(n2logn) time using the algorithm.