Discovering patterns in musical sequences

Pattern discovery (or 'extraction') in sequences is a very general problem with diverse musical applications ranging from music generating systems to melodic content-based retrieval to music analysis. It naturally fits within the wider problematics of musical (and multimedia) content extraction. In this article, we focus on the automated discovery of patterns in corpuses o f melodic sequences. A melodic pattern is defined by a set of either identi cal or 'equipollent' (i.e., significantly similar) sequence segments. In pr evious work and articles, we addressed such critical issues in musical patt ern discovery as the representation of sequences and of their elements, and the definition of appropriate similarity metrics between (pairs of) sequen ce segments. We now present a novel pattern extraction algorithm named FlEx Pat ('FlExible Extraction of Patterns'), which builds upon the concepts and techniques we previously introduced. FlExPat articulates in two phases, pa ssage pair comparison and then categorization. Its theoretical worst-case c omplexity is quadratic in the corpus' total sequence length, but both runni ng time and required memory are far smaller in practice. FlExPat has been i mplemented in our Imprology software system. Experimental results, a few of which are detailed here, clearly show FlExPat's qualities and performances .