Pattern Processing in Melodic Sequences: Challenges, Caveats & Prospects

Emilios Cambouropoulos,* Tim Crawford,# Costas S. Iliopoulos⊗

*Austrian Research Institute for Artificial Intelligence, Vienna.
#
Department of Music, King’s College London.
*,⊗Department of Computer Science, King’s College London.
emilios@ai.univie.ac.at, tim.crawford@kcl.ac.uk, csi@dcs.kcl.ac.uk

Abstract
In this paper a number of issues relating to the application of string processing techniques on musical sequences
are discussed. A brief survey of some musical string processing algorithms is given and some issues of melodic
representation, abstraction, segmentation and categorisation are presented. This paper is not intended towards
providing solutions to string processing problems but rather towards highlighting possible stumbling-block areas
and raising awareness of primarily music-related particularities that can cause problems in matching applications.

1. Introduction changes etc.), can exact matching account for such a

phenomenon? Especially in relation to pattern
There exists a large number of string matching induction,1 are exact repetitions and similarity ratings
algorithms which are usually applied on text strings or between musical patterns sufficient for extracting
biological strings (e.g. DNA or protein strings) - a ‘significant’ patterns from a musical string? Should
plethora of string algorithms is surveyed in ( Apostolico categorisation techniques be considered a necessary or
and Galil, 1985) and (Chrochemore and Rytter, 1994). an optional part of pattern induction methods? Is the
It is often hypothesised that a musical surface may be pre-segmentation of a string necessary or even useful?
seen as a string of musical entities such as notes, chords In the next sections most of these questions will be
etc. on which pattern recognition or induction addressed and some possible solutions will be
techniques can be applied. Overviews of the application presented. First, problems in relation to the
of pattern processing algorithms on musical strings can representation of musical strings will be discussed, then,
be found in ( McGettrick, 1997; Crawford et al, 1998; some pros and cons of using exact or approximate
Rolland et al, 1999); a very brief overview of a number matching techniques will be presented and, finally, the
of such music pattern processing methods is presented relevance of categorisation techniques and segmentation
in this paper in Table 1 - see Appendix. in pattern induction problems will be addressed.
When attempts are made to apply string matching
algorithms to musical strings various questions arise 2. Musical String Representation
that have to do with the particular nature of musical
elements. For instance, should a melody be represented There is a wide range of possible representations of
at the lowest level as a single string of note tuples (pitch musical strings that researchers can use as input to
and duration) or the different parameters should be pattern processing algorithms. Often one representation
treated as separate strings? Should the melodic surface is chosen as a first test case (e.g. absolute pitch) and
be considered as a string of absolute pitches, pitch then the assumption is made that the same string-
classes, pitches in relation to a tonal centre or pitch matching mechanism can be applied to other
intervals? Should rhythmic strings consist of durations representations (e.g. contour or pitch intervals). This
or duration ratios? How about more abstract assumption is often valid; however there are some
representations such as step-leap and contour pitch caveats that the researcher should be aware of - some of
strings or shorter-longer-equal rhythm strings? How can these are discussed below.
structural prominence of some of the musical entities
(e.g. more prominent notes in terms of duration length, 2.1 Pitch Representation
harmonic content, metrical stress etc.) be taken into Pitch is most often represented - in the western tradition
account? - either by the traditional pitch naming system (e.g. F#4-
Apart from issues relating to the selection of an G#4-A4) or as absolute pitch (e.g. in MIDI: 66, 68, 69).
appropriate representation of the musical surface, other
issues arise as well. For instance, although approximate 1 In this text, the term pattern induction refers to techniques
matching seems to be the obvious solution for capturing that enable the extraction of useful patterns from a string
musical variation (e.g. filling and thinning of thematic whereas pattern recognition refers to techniques that find all
material, rhythmic changes, pitch changes, tonal the instances of a predefined pattern in a given string.
Most computer-aided musical applications adopt the
absolute pitch representation. It has been argued in
(Cambouropoulos, 1996) that the absolute pitch
encoding is insufficient for applications in tonal music pci: 2 -2 4 0 -5 1 -1 3 0 -5 0 2 0 1 4 -2 -2 -1
as it disregards the hierarchic importance of diatonic nci: 1 -1 2 0 -3 1 -1 2 0 -3 0 1 0 1 2 -1 -1 -1
scale tones over the 12-tone discrete pitch space (e.g.
Figure 1 Beginning of theme of the Amajor sonata by
enharmonic tones that have different tonal qualities are
Mozart (pci: pitch-class intervals, nci: name-class
made equivalent).
intervals)
As far as pattern matching is concerned, applications
There exists a somewhat ‘peculiar’ relationship between
that use the MIDI representation sometimes resort to
pitch strings and pitch interval strings. As Rowe (1995)
what will be referred to as δ-approximate matching in
notes, if one note is altered within a string of notes then
order to compensate for the information lost by the use
two corresponding intervals change. The converse also
of absolute pitch. In δ-approximate matching , equal-
needs attention: if one pitch interval in a string of pitch
length patterns consisting of integers match if each
intervals is altered then all the succeding notes are
corresponding integer differs by not more than δ - e.g. a
altered (transposed). So a change in a string of pitches
C-major (60, 64, 65, 67) and a C-minor (60, 63, 65, 67)
and in a string of pitch intervals is not exactly the same
sequence can be matched if a tolerance δ=1 is allowed
thing. Take, for instance, the ‘deletion’ (or ‘insertion’)
in the matching process (efficient algorithms for δ-
transformation commonly employed in approximate
approximate problems are currently studied by the
pattern processing techniques: the deletion of a pitch or
Algorithm Design Group at the Department of
the deletion of a pitch interval may have quite different
Computer Science, King’s College London).
effects on the transformed musical sequence (e.g. if the
The main problem however with applying a pattern second pitch of the first bar of the melody in figure 1 is
processing algorithm on an absolute pitch string is that deleted a not very different pitch pattern C#-C#-E-E
transpositions are not accounted for (e.g. the repeating occurs; if the second pitch interval is deleted a rather
pitch motive in bars 1 & 2 in figure 1). And there is more ‘radical’ change in the resulting pitch pattern C#-
plenty of evidence, both theoretical and experimental, D-F#-F# occurs).
that transposition is paramount in the understanding of
In terms of pattern induction techniques, the following
musical patterns. One partial solution that has
problem arises as well: successive contiguous non-
sometimes been devised is to transpose different
overlapping patterns in a string of pitch intervals result
musical works (e.g. folk melodies) to the same key - this
in overlapping patterns (by a single pitch) in the
approach, however, does not account for transpositions
corresponding string of pitches. For instance, if a
of a pattern within the same piece and of course the
pattern induction algorithm that attempts to find an
whole idea of a musical work being in one key is
‘economic’ non-ovelapping description of the string is
problematic. The obvious solution to this problem is the
applied to the nci string of figure 1 - e.g. minimal length
use of relative pitch, mainly through the derivation of
description methods such as (Annunziata et al, 1995) or
pitch intervals from the absolute pitch surface.
grammar-induction-based compression methods such as
(Nevill-Manning and Witten, 1997) - then the
2.2 Pitch Interval Representation and
underlined pattern illustrated in figure 1 appears; at the
Abstractions pitch level these two patterns overlap by one note! If a
Pitch intervals are adequate for representing relations whole melody could be described in terms of contiguous
between absolute pitches. Most commonly computer non-overlapping pitch interval patterns then, at the note
systems make use of intervals that consist of a number level, theses consecutive patterns would all be
of semitones. Cambouropoulos (1996) argues that this is overlapping by one note resulting in a rather implausible
insufficient for tonal music and proposes the General description.
Pitch Interval Representation (GPIR) that can encode
Pitch interval encodings readily lend themselves for
intervals according to the relevant set of scales in a
constructing a number of more abstract representations
given musical idiom. For instance, in figure 1 pitch-
of musical strings such as contour strings. Intervals can
class intervals are inappropriate for revealing the
be categorised in a number of classes according to their
repetition of the first two bars whereas name-class
sizes (e.g. repeat: nci=0, step: nci=1, leap: nci>1 and a
intervals (nci) - i.e. diatonic intervals in scale steps - are
string can be constructed from the alphabet {-l, -s, r, +s,
more adequate (see below for problems in this
example). +l} or according to the signs of intervals in which case
contour can be represented as a string from the alphabet
{-, +, =}. This way exact matching techniques can be
applied for revealing ‘approximate’ matches.
In the example of figure 2, if the patterns are type of matching can be very effective, but one should
represented by absolute pitch no interesting matches also consider encoding rhythm strings as strings of
occur; if encoded as pitch intervals in semitones then duration relations such as duration ratios or
the first 5 intervals are matched; if encoded as step-leap shorter/longer/equal strings. Duration ratios encapsulate
strings then the whole patterns are matched (of course the observation that listeners usually remember a
contours match as well but step-leap matching is more rhythmic pattern as a relative sequence of durations that
accurate).2 is independent of an absolute tempo. Duration ratios can
reveal augmentations or diminutions of a rhythmic
pattern (figure 3).

dur. 12 2 2 8 6 1 1 4
ratios 1/6 1 4 1/6 1 4

pci: 2 2 4 5 2 -5 1 -2 Figure 3. The above two rhythmic patterns match at the

level of duration ratios.
It should be noted, however, that the problems that arise
between pitch and pitch-interval representations (high-
lighted in the previous section) apply also for the
relationship between durations and duration ratios.

3. Matching of Structured Musical Patterns

2 2 4 5 2 -7 3 -4 The musical entities that constitute a musical pattern are
not usually of equal salience, i.e. some notes (or chords
etc.) are more prominent than others in terms of metrical
position, duration length, register, harmony, tonal
hierarchies and so on. In this section, ways in which
pattern processing techniques may account for
structured strings will be examined.

2 2 4 5 2 -9 5 -6 Exact pattern matching is aimed at finding instances of

given patterns (or inducing identical patterns). However,
pattern matching may be used for revealing or
establishing similarity between different patterns as
well. What kind of pattern matching methodology,
though, is most adequate when attempting to establish
similarities between complex entities such as melodic
passages?

2 2 4 5 2 -11 7 -8 Simplifying for the sake of argument we will suppose

that there are two main approaches:
Figure 2 The first 4 occurrences of a motive from a) approximate pattern-matching applied on the
Messiaen’s Vingt Regards sur l’Enfant J ésus (III- unstructured musical surface and,
L’échange). b) exact pattern-matching applied on the musical
surface and on a number of reduced versions of it that
2.3 Rhythm Representation consist of structurally more prominent components.
In terms of the rhythmic component of musical strings, The first approach is based on the assumption that
string processing algorithms are most commonly applied musical segments construed as being parallel (similar)
to strings of durations (or inter-onset intervals). This will have some of their component elements identical
(for example, two instances of a melodic motive will
have a 'significant' amount of common notes or intervals
2 This pitch pattern repeats 12 times in this piece, each time but not necessarily all) - some approximate pattern-
transposed upwards by one semitone and at the same time the matching algorithms based on this approach are
second-to-last and last pitches are transposed downwards by described in (Bloch and Dannenberg, 1985; Cope, 1990,
one semitone - ‘evolution’ algorithms such as (Crawford et al., 1991; Rowe and Li, 1995; Stammen and Pennycook,
1999) may be used to capture such gradually evolving 1993; Rolland, 1998 - see Appendix). The second
transformations.
approach is based on the assumption that parallel segments b, c, d to segment a? Let us suppose, for
musical segments are necessarily identical in at least one convenience, that each melodic segment is represented
parametric profile of the surface or reduction of it (for as a sequence of pitch and onset time note tuples (figure
example, two instances of a melodic motive will share 4, bottom).
an identical parametric profile at the surface level or
Approximate pattern matching would show that each of
some higher level of abstraction, e.g. pattern of
the segments b,c,d is 71% identical to segment a as 5
metrically strong or tonally important notes/intervals
out of 7 note tuples match. Depending on the threshold
and so on) - computational techniques based on this
that has been set, the three melodic segments are equally
approach are described in (Cambouropoulos, 1998a;
similar - or dissimilar - to segment a. It is quite clear
Hiraga, 1997).
however to a musician that segment b is - for most tonal
What are the pros and cons of each of the above pattern- contexts - much more similar to segment a than any of
matching methodologies? Perhaps an example will help the other segments because segments a & b match in
clarify the relative merits of each approach. Consider exactly the 'right' way, i.e. more prominent notes match
the tonal melodic segments of figure 4. How similar are and less important ornamentations are ignored.

b c d

segment a: [g,0],[c,4],[b,8],[c,9],[a,10],[b,11],[g,12]
segment b: [g,0],[a,2],[b,3],[c,4],[b,8], [a,10], [g,12]
segment c: [g,0],[a,4],[b,8],[c,9],[a,10],[b,11],[c,12]
segment d: [g,0],[c,4],[b,8],[c,9],[a,10],[c,11],[d,12]

Figure 4. How similar are melodic segments b, c, d to segment a?

Such explicit knowledge may be used constructively for

In order for the second pattern matching methodology
further analytic - or compositional - tasks.
to be applied, a significant amount of pre-processing is
required - for instance, the melodic segments are not
simply examined at the surface level but various more 4. Segmentation and Categorisation in
abstract levels of representation that reflect structural Relation to Pattern Induction
properties of the melodic segments have to be
constructed (e.g. longer notes, metrically stronger notes, 4.1 Segmentation
tonally important notes etc.). It should be noted, Pre-segmentation of a musical work can increase
however, that it is possible to take account of structural significantly the efficiency of pattern induction
prominence in approximate matching techniques by techniques (see table 1 for researchers that favour this
introducing weights to the matches of pattern elements - approach). However, committing oneself to a particular
e.g. similarity contributions for each transformation segmentation means that patterns crossing over
especially in relation to duration length and pitch boundaries are excluded a priori. This can be a serious
distance as proposed and implemented by Mongeau and drawback especially if one takes into account that often
Sankoff (1990) and Rolland (1998). significant musical patterns contribute to the
Both methodologies can handle musical similarity and segmentation process itself, i.e. although there may be
parallelism. One advantage, however, of the second no strong indication for a point of segmentation, due,
pattern-matching methodology is that the reasons for for instance, to a relatively long note or a relatively
which two musical segments are judged to be large melodic interval, a recurring musical pattern may
parallel/similar are explicitly stated, i.e. the properties indeed suggest a strong boundary at that point (see, for
common to both are discovered and explicitly encoded. instance, boundary between first two bars of Frère
Jacques).
Alternativelly, an analytical methodology that relies extension and the intension of the emerging categories
solely on pattern recurrence is bound to find patterns are explicitly defined.
that are cognitively and analytically implausible (e.g. a
frequently repeating pattern may end on a very short 5. Conclusions
note, or contain a long rest in the middle, and so on). It
is suggested that pattern induction techniques should not In this paper, a number of issues relating to the
rely heavily on a pre-segmented musical surface, but application of pattern processing techniques on melodic
they should take into account methods that are geared strings have been addressed. Special emphasis was
towards finding perceptually-pertinent local boundaries given to the various options and difficulties a researcher
faces when trying to select an adequate representation of
as such boundaries can facilitate the selection process of
the melodic surface for pattern processing. Issues
‘significant’ musical patterns. An integrated approach
relating to the application of exact or approximate
that takes into account both low-level discontinuities in
techniques on structured sequences were briefly
the musical surface and higher-level emerging patterns
discussed and also the relevance of pre-segmentation
has been proposed by Cambouropoulos (1998b)
and categorisation processes for pattern processing was
4.2 Similarity and Categorisation addressed.

A further serious consideration regarding pattern References

induction is finding suitable criteria (e.g. weights for
parameters such as pitch, rhythm and so on) for Apostolico, A. and Galil, Z. (eds) (1985) Combinatorial
comparing musical sequences and setting an appropriate Algorithms on Words. Springer-Verlag, NATO ASI Series.
Bakhmutova, I.V., Gusev, V.D. and Titkova, T.N. (1997) The
threshold for defining similarity between them. Most
Search for Adaptations in Song Melodies. Computer Music
commonly such criteria and thresholds are selected in an Journal, 12(1):58-67.
ad hoc manner by the user/programmer. Cambouropoulos, E. (1998a) Towards a General
Computational Theory of Musical Structure. Ph.D. Thesis,
Regarding parametric weights for contribution functions
University of Edinburgh.
in musical sequence comparison tasks Rolland et al. Cambouropoulos, E. (1998b) Musical Parallelism and Melodic
(1998) apply a supervised technique whereby the Segmentation. In Proceedings of the XII Colloquio di
analytic results given by a human analyst are used to Informatica Musicale, Gorizia, Italy.
optimise the system’s performance by finding the most Cambouropoulos, E. (1996) A General Pitch Interval
appropriate weights for pitch and rhythm parameters. Representation: Theory and Applications. Journal of New
Music Research, 25 (3): 231-251.
Defining an appropriate threshold for determining Cambouropoulos, E. and Smaill, A. (1997) Similarity and
which musical excerpts are similar - along with deciding Categorisation Inextricably Bound Together: The
which parameters contribute most in similarity Unscramble Machine Learning Algorithm. In Proceedings
judgements - is a very difficult issue. It has been of the Interdisciplinary Workshop on Similarity and
proposed by Cambouropoulos and Smaill (1997) that Categorisation, University of Edinburgh.
similarity is always dependent on context and that it is Chou, T.C., Chen, A.L.P. and Liu, C.C. (1996) Music
Database: Indexing Technique and Implementation. In
essentially meaningless unless it is seen in association
Proceedings of IEEE Intl. Workshop on Multimedia Data
with processes of categorisation (often the term Base Management System.
similarity is used to mean distance - the difference Crawford, T., Iliopoulos, C.S. , Winder, R. and Yu, H. (1999)
between the two is that the former requires a threshold). Approximate Musical Evolution. In Proceedings of
It is suggested that the notions of categorisation, AISB’99, Edinburgh.
similarity and the representation of entities/properties Crawford, T., Iliopoulos, C.S. and Raman, R. (1998) String
are strongly inter-related. It is not simply the case that Matching Techniques for Musical Similarity and Melodic
one starts with an accurate description of entities and Recognition. Computing in Musicology, 11:71-100.
properties, then finds pairwise similarities between them Cope, D. (1990) Pattern-Matching as an Engine for the
Computer Simulation of Musical Style. In Proceedings of
and, finally, groups the most similar ones together into
the International Computer Music Conference, Glasgow.
categories. It seems more plausible that as humans Crochemore, M. (1981) An Optimal Algorithm for Computing
organise their knowledge of the world, they alter their the Repetitions in a Word. Information Processing Letters,
representations of entities concurrently with emerging 12(5):244-250.
categorisations and similarity judgements. Crochemore, M. and Rytter, W. (1994) Text Algorithms.
Oxford University Press, Oxford.
Following this discussion on similarity and cate- Coyle, E.J. and Shmulevich (1998) A System for Machine
gorisation the Unscramble algorithm ( Cambouropoulos Recognition of Musical Patterns. In Proceedings of IEEE
and Smaill, 1997) has been devised which, given a set ICASSP’98.
of objects and an initial set of properties, generates a Hiraga, Y. (1997) Structural Recognition of Music by Pattern
range of plausible classifications for a given context. Matching. In Proceedings of the International Computer
During this dynamically evolving process, the initial set Music Conference, Thessaloniki, Greece.
Hsu, J-L., Liu, C-C and Chen, A.L.P. (1998) Efficient
of properties is adjusted so that a satisfactory
Repeating Pattern Finding in Music Databases. In
description is generated. There is no need to determine Proceedings of the Conference in Information and
in advance an initial number of classes or a specific Knowledge Management (CIKM’98), Bethesda, Maryland.
similarity threshold or the relative prominence of McGettrick, P. (1997) MIDIMatch: Musical Pattern Matching
properties. At every stage of the process both the in Real Time. Msc Dissertation, York University, U.K.
Mongeau, M. and Sankoff, D. (1990) Comparison of Musical of the 4th International Conference on Music Perception
Sequences. Computer and the Humanities, 24:161-175. and Cognition (ICMPC’96), Montreal.
Nevill-Manning, C.G. and Witten, I.H. (1997) Compression Rowe, R. (1995) Artificial Intelligence and Musical
and Explanation using Hierarchical Grammars. The Interaction. In Proceedings of the International Congress in
Computer Journal, 40(2/3):103-116. Music and AI, University of Edinburgh, Edinburgh.
Rolland, P.Y., Ganascia, J.G. (1999) Musical Pattern Rowe, R. and Li, T.C. (1995) Pattern Processing in Music. In
Extraction and Similarity Assessment. In Readings in Music Proceedings of the Fifth Biennial Symposium for Arts and
and Artificial Intelligence. E. Miranda. (ed.). Harwood Technology. Connecticut College, New London,
Academic Publishers (forthcoming). Connecticut.
Rolland, P-Y. (1998) FlExPat: A Novel Algorithm for Musical Smith, L.A., McNab, R.J. and Witten, I.H. (1998) Sequence-
Pattern Discovery. In Proceedings of the XII Colloquium in based Melodic Comparison: A Dynamic-Programming
Musical Informatics, Gorizia, Italy. Approach. Computing in Musicology, 11:101-117.
Rolland, P-Y. and Ganascia, J-G. (1996) Automated Motive- Stammen, D.R. and Pennycook, B. (1993) Real-time
Oriented Analysis of Musical Corpuses: a Jazz Case Study. Recognition of Melodic Fragments Using the Dynamic
In Proceedings of the International Computer Music Timewarp Algorithm. In Proceedings of the International
Conference, Hong-Kong. Computer Music Conference (ICMC’93).
Rolland, P-Y. and Ganascia, J-G. (1996) Automated Extraction
of Prominent Motives in Jazz Solo Corpuses. In Proceedings

Appendix
pitch rhythm other pre- type of type of string
representation representation structural segmentation pattern matching matching
factors required processing algorithm
Mongeau & pitch/degree durations weights based comparison approximate dynamic
Sankoff, 1990 difference from on degree of programming
tonal centre consonance
Stammen & intervals in duration no yes recognition approximate dynamic
Pennycook semitones ratios programming
1993
Smith,McNab intervals in durations no no recognition exact & dynamic
Witten, 1997 semitones & approximate programming
contour
Rowe, 1995 intervals in durations no yes recognition & approximate dynamic
Rowe & Li semitones induction programming
1995
Rolland absolute pitch durations & contribution no induction approximate dynamic
1996a,b 1998 & intervals ratios weights (e.g. programming
long dur.)
Bakhmutova, scale-step metric no induction approximate dynamic
Gusev, intervals position programming
Titkova 1997
Cope 1990, intervals in durations elimination of no m-length near-exact brute-force
1991 semitones very short pattern algorithm
notes induction
McGettrick abs. pitch, duration accented no recognition exact Boyer-Moore
1997 intervals in ratios notes algorithm
semitones
Coyle & intervals in duration key-finding comparison exact (+ error equal length
Shmulevich semitones ratios algorithm absolute and comparison
1998 (+error) (+error) perceptual)
Hsu, Liu & absolute pitch durations elementary no induction exact dynamic
Chen, 1998 chords and programming
metre (only exact)
Hiraga 1997 interv: sem, durations: reduction of yes induction exact not described
scale-steps, exact, log- surface (tentative) (emphasis in
step-leap, ratio, shorter- immediate
contour longer-equal repetition)
Cambouro- interv: sem, durations: reduction of no induction exact Chrochemore
poulos 1998 scale-steps, exact, ratio, surface (1981)
step-leap, shorter-
contour longer-equal

Table 1 Left column indicates a number of musical pattern processing methods. Top row indicates some useful aspects
of these methods (at least as far as this paper is concerned).