Music retrieval algorithms for the lead sheet problem

Methods from string and pattern matching have recently been applied to many problems in music retrieval. We consider the so-called \emph{lead sheet problem}, where symbolic representations of the harmony, melody, and, usually, bass line are presented separately. This is a common situation in some forms of popular music but is also significant for ``classical"" music in many cases. A number of different but related musical situations are analysed and efficient algorithms are presented for music retrieval in each one.