TY - JOUR
T1 - Exact and approximate rhythm matching algorithms
AU - CHAN, Joseph W T
AU - Iliopoulos, Costas S.
AU - Michalakopoulos, Spiros
AU - Rahman, M. Sohel
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012/8
Y1 - 2012/8
N2 - An interesting problem in music information retrieval is to classify songs according to rhythms. A rhythm is represented by a sequence of "Quick" (Q) and "Slow" (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. Christodoulakis et al. presented an efficient algorithm that can be used to classify musical sequences according to rhythms. In this article, the above algorithm is implemented, along with a naive brute force algorithm to solve the same problem. The theoretical time complexity bounds are analyzed with the actual running times achieved by the experiments, and the results of the two algorithms are compared. Furthermore, new efficient algorithms are presented that take temporal errors into account. This, the approximate pattern matching version, could not be handled by the algorithms previously presented. The running times of two algorithmic variants are analyzed and compared and examples of their implementation are shown.
AB - An interesting problem in music information retrieval is to classify songs according to rhythms. A rhythm is represented by a sequence of "Quick" (Q) and "Slow" (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. Christodoulakis et al. presented an efficient algorithm that can be used to classify musical sequences according to rhythms. In this article, the above algorithm is implemented, along with a naive brute force algorithm to solve the same problem. The theoretical time complexity bounds are analyzed with the actual running times achieved by the experiments, and the results of the two algorithms are compared. Furthermore, new efficient algorithms are presented that take temporal errors into account. This, the approximate pattern matching version, could not be handled by the algorithms previously presented. The running times of two algorithmic variants are analyzed and compared and examples of their implementation are shown.
KW - Music information retrieval
KW - Pattern matching
KW - Quick-slow
KW - Rhythm
UR - http://www.scopus.com/inward/record.url?scp=84865819354&partnerID=8YFLogxK
U2 - 10.1007/s00799-012-0085-0
DO - 10.1007/s00799-012-0085-0
M3 - Journal article
AN - SCOPUS:84865819354
SN - 1432-5012
VL - 12
SP - 149
EP - 158
JO - International Journal on Digital Libraries
JF - International Journal on Digital Libraries
IS - 2-3
ER -