Multilevel Melodic Matching

C. Walshaw


This paper describes a multilevel algorithm for matching tunes when performing inexact searches in symbolic mu-sical data. The basis of the algorithm is straightforward: initially each tune in the search database is normalised and quantised and then recursively coarsened, typically by removing weaker off-beats, until the tune is reduced to a skeleton representation with just one note per bar. The same process is applied to the search query and melodic matching between query and data can then take place at every level. The algorithm implemented here uses the longest common substring algorithm at each level, but in principle a variety of similarity measures could be used. The multilevel framework allows inexact matches to occur by identifying similarities at course levels and is also exploited with the use of early termination heuristics at coarser levels, both to reduce computational complexity and to enhance the matching qualitatively. Experimenta-tion demonstrates the effectiveness of the approach for inexact melodic searches within a corpus of tunes.

Wed Nov 4 20:15:29 GMT 2015