Aligning music notes using String matching algorithms or Dynamic Programming

Question

Hi

I need to compare 2 sets of musical pieces (i.e. a playing-taken in MIDI format-note details extracted and saved in a database table, against sheet music-taken into XML format). When evaluating playing against sheet music (i.e.note details-pitch, duration, rhythm), note alignment needs to be done - to identify missed/extra/incorrect/swapped notes that from the reference (sheet music) notes.

I have like 1800-2500 notes in one piece approx (can even be more-with polyphonic, right now I'm doing for monophonic). So will I have to have all these into an array? Will it be memory overloading or stack overflow?

There are string matching algorithms like KMP, Boyce-Moore. But note alignment can also be done through Dynamic Programming. How can I use Dynamic Programming to approach this? What are the available algorithms? Is it about approximate string matching?

Which approach is much productive? String matching algos like Boyce-Moore, or dynamic programming? How can I assess which is more effective?

Greatly appreciate any insight or suggestions Thanks in advance

Answer 1

Interesting question - I think this paper covers a lot of what you're interested in. They address the issue of errors and music alignment and discuss their results using DP as a solver. They introduce an algorithm called "fast approximate matching" which they claim is better than the DP approach.

It looks like the key authors to use in a search are Mongeau & Sankoff. It would appear that their original paper set off a lot of work in this area.

Neat stuff. Hope this helps.