All maximal-pairs in step-leap representation of melodic sequence
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[l..n], where x contains d occurrences of binary don't cares and z is the number of reported maximal-pairs. (c) 2006 Elsevier Inc. All rights reserved.
maximal-pair string don't care suffix tree lowest common ancestor combinatorial algorithm music retrieval repetitions