A Pattern Extraction Algorithm for Abstract Melodic Representations that Allow Partial Overlapping of Intervallic Categories

Abstract : This paper proposes an efficient pattern extraction algorithm that can be applied on melodic sequences that are represented as strings of abstract intervallic symbols; the melodic representation introduces special "don't care" symbols for intervals that may belong to two partially overlapping intervallic categories. As a special case the well established "step-leap " representation is examined. In the step-leap representation, each melodic diatonic interval is classified as a step (±s), a leap (±l) or a unison (u). Binary don't care symbols are introduced to represent categories e.g. ∗ = s, ∗ = l and # = -s, # = -l. For such a sequence, we are interested in finding maximal repeating pairs and repetitions with a hole (two matching subsequences separated with an intervening non-matching symbol). We propose an O(n+d(n-d)+z)-time algorithm for computing all such repetitions in a given sequence x = x[1..n] with d binary don't care symbols, where z is the output size.