Skip to Main content Skip to Navigation
Journal articles

All Maximal Pairs in Step-Leap Representation of Melodic Sequences

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 “binary 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 used to represent the possible overlapping between the various abstract categories e.g. ∗=s, ∗=l and #=-s, #=-l. We propose an O(n+d(n-d)+z)-time algorithm for computing all maximal-pairs in a given sequence x=x[1..n], where x contains d occurrences of binary don’t cares and z is the number of reported maximal-pairs.
Document type :
Journal articles
Complete list of metadatas
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, September 6, 2011 - 5:14:13 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM



Emilios Cambouropoulos, Maxime Crochemore, Costas S. Iliopoulos, Manal Mohamed, Marie-France Sagot. All Maximal Pairs in Step-Leap Representation of Melodic Sequences. Information Sciences, Elsevier, 2007, 177 (9), pp.1954-1962. ⟨10.1016/j.ins.2006.11.012⟩. ⟨hal-00619690⟩



Record views