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

Emilios Cambouropoulos 1 Maxime Crochemore 2 Costas S. Iliopoulos 3 Manal Mohamed 3 Marie-France Sagot 4
1 Department of Music Studies
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 DCS - Department of Computer Science
4 Baobab
PEGASE - Département PEGASE [LBBE]
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.
Keywords : string don't care repetitions suffix tree lowest common ancestor
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-00619902
Contributor : Maxime Crochemore <>
Submitted on : Monday, March 25, 2013 - 8:23:46 AM
Last modification on : Thursday, November 21, 2019 - 1:14:17 PM
Long-term archiving on : Wednesday, June 26, 2013 - 2:30:11 AM

File

ismir2005.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619902, version 1

Collections

CNRS | LIGM | UNIV-MLV | LIGM_ALGO | ENPC | PARISTECH | UPEC-UPEM | INRIA | BIOENVIS | UNIV-LYON1 | UDL

Citation

Emilios Cambouropoulos, Maxime Crochemore, Costas S. Iliopoulos, Manal Mohamed, Marie-France Sagot. A Pattern Extraction Algorithm for Abstract Melodic Representations that Allow Partial Overlapping of Intervallic Categories. Proceedings of the 6th International Conference on Music Information Retrieval (ISMIR 2005), 2005, Londres, United Kingdom. pp.167-174. ⟨hal-00619902⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

495

Files downloads

229

Contact

CCSD