A General Theoretical Framework for Transformed Geometric Pattern Matching in Music

Introduction

In this paper, we present a framework of concepts, terminology and notation for geometric pattern matching, centred around the idea of a transformation class. After defining some preliminary ideas, notation and terminology in Section 2, we provide a formal definition of the concept of a transformation class in Section 3. We then provide detailed definitions of a number of specific transformation classes that are particularly relevant to pattern matching and pattern discovery in music, as this has been the primary application domain within which the framework has been developed. In Section 4, we provide formal definitions of the notions of match, occurrence, maximal match and maximal occurrence and prove some results relating to these concepts. In Section 5, we define and explore in detail the notion of an occurrence set and the more general idea of a heterogeneous occurrence set. Finally, in Section 6, we explore in detail the concept of transformational equivalence, including a consideration of transformation groups, along with the group-theoretic and transformational equivalence properties of selected transformation classes.

Although the framework described in this paper has been developed primarily with music in mind, it is actually quite general and could, in principle, be applied in any domain where data takes the form of multi-dimensional point sets and meaningful relationships between sets of data points can be modelled by geometric transformations. The framework presented here generalizes and develops further that proposed by Meredith [7, 8, 9]. The transformation classes discussed in this paper were applied in [10] to the analysis of the relationships between occurrences of the so-called “HAYDN” theme in Maurice Ravel’s Menuet sur le nom d’Haydn.

Preliminary definitions of concepts, terminology and notation

In this section we define some basic concepts, terminology and notation that will be used throughout the remainder of this paper.

Sets and ordered sets

A set, $S = \{s_1, s_2, \ldots s_n\}$, is a collection of distinct objects. If $S$ is a set, then the cardinality of $S$, denoted by $|S|$, is the number of elements that it contains. Thus, if $S = \{s_1, s_2, \ldots s_n\}$, then $|S| = n$. If $\Psi= \{S_1, S_2, \ldots S_m\}$, where each $S_i$ is a set, then we define the following shorthand notations: $\bigcup_{S \in\Psi} S = S_1 \cup S_2 \cup\ldots\cup S_m$ and $\bigcap_{S \in\Psi} S = S_1 \cap S_2 \cap\ldots\cap S_m$. Note that we will use braces, $\{\cdot\}$, to denote sets and name them with capital italic letters. We will reserve the operators, $\subset$ and $\supset$, to mean proper subset and superset, respectively. That is, $A \subset B \Rightarrow A \ne B$ and $A \supset B \Rightarrow A \ne B$. If we want to express that a set, $A$, is either a proper subset of $B$ or is equal to $B$, then we write $A \subseteq B$.

An ordered set, $\mathbf{A} = \langle a_1, a_2, \ldots a_k\rangle$, is a collection of (not necessarily distinct) objects where the order in which the objects appear in the collection matters. Examples of ordered sets include sequences, vectors, lists, arrays and tuples. Thus, the ordered sets, $\mathbf{A} = \langle1,2,3\rangle$ and $\mathbf{B} = \langle2,1,3\rangle$, are distinct, whereas the sets, $X = \{1,2,3\}$ and $Y = \{2,1,3\}$, are equal. Note that we use angle brackets, $\langle\cdot\rangle$, to denote ordered sets and name them with bold letters. When an ordered set represents a vector or a tuple, we typically name it with a lower-case letter, whereas when it represents a sequence, array or list, we typically name it with a capital letter. We denote the set of distinct elements in an ordered set, $\mathbf{A}$, by $\operatorname{Set}(\mathbf{A})$ and define it as follows: $\operatorname{Set}(\mathbf{A}) = \bigcup_{a \in\mathbf{A}}\{a\}$.

Given an ordered set, $\mathbf{A} = \langle a_1, a_2, \ldots a_k\rangle$, then $\mathbf{A}[i]$ denotes the $(i+1)$th element in $\mathbf{A}$ (i.e., we use zero-based indexing). For example, if $\mathbf{B} = \langle2,1,3\rangle$, then $\mathbf{B}[0] = 2$, $\mathbf{B}[1] = 1$ and $\mathbf{B}[2] = 3$. We define the length or size of $\mathbf{A}$, denoted by $\operatorname{Len}(\mathbf{A})$, to be the number of elements in $\mathbf{A}$—for example, if $\mathbf{A} = \langle a_1, a_2, \ldots a_k\rangle$, then $\operatorname{Len}(\mathbf{A}) = k$ and $\mathbf{A}[\operatorname{Len}(\mathbf{A}) - 1]$ is the last element in $\mathbf{A}$. We define the cardinality of $\mathbf{A}$, denoted by $|\mathbf{A}|$, to be the number of distinct elements in $\mathbf{A}$. Thus $|\mathbf{A}| = \left|\bigcup_{i=0}^{\operatorname{Len}(\mathbf{A})-1}\{\mathbf{A}[i]\}\right|$. An ordered set, $\mathbf{A}$ can be represented as a set of ordered pairs, $\bigcup_{i=0}^{\operatorname{Len}(\mathbf{A})-1}\{\langle i,\mathbf{A}[i]\rangle\}$.

We define that, if $\mathbf{A}$ is an ordered set, and $i$ and $j$ are integers such that $0 \leq i \leq j \leq\operatorname{Len}(\mathbf{A})$, then $\mathbf{A}[i,j] = \mathbf{A}[i,j-1],\ldots,\mathbf{A}[j-1]$. Note that $\operatorname{Len}(\mathbf{A}[i,j]) = j-i$. For example, if $\mathbf{B} = \langle5,6,7\rangle$, then $\mathbf{B}[0,2] = \langle5,6\rangle$, $\mathbf{B}[1,3] = \langle6,7\rangle$ and $\mathbf{B}[0,3] = \mathbf{B}$.

If $\mathbf{A} = \langle a_1,a_2,\ldots a_k\rangle$ and $\mathbf{B} = \langle b_1,b_2,\ldots b_\ell\rangle$ then the concatenation of $\mathbf{B}$ onto $\mathbf{A}$ is the ordered set, $\mathbf{A} \oplus\mathbf{B} = \langle a_1,a_2,\ldots a_k,b_1,b_2,\ldots b_\ell\rangle$. It follows that, for any ordered set, $\mathbf{A} = \mathbf{A}[0,k] \oplus\mathbf{A}[k,\operatorname{Len}(\mathbf{A})]$ (note that $\mathbf{A}[i,j]$ is only defined for $i,j \in\mathbb{Z}$ and $0 \leq i \leq j \leq \operatorname{Len}(\mathbf{A})).

If we want to express that a sequence is the result of concatenating some sequence of other sequences together, then we can use the $\bigoplus$ operator. For example, $\bigoplus_{i=1}^{5}\langle0\rangle=$ $\langle0\rangle\oplus\langle0\rangle\oplus\langle0\rangle\oplus\langle0\rangle\oplus\langle0\rangle= \langle0,0,0,0,0\rangle$ and $\bigoplus_{i=1}^{5}\langle i\rangle= \langle1,2,3,4,5\rangle$. Note that the argument expression of $\bigoplus_{i=j}^{k}$ must be an ordered set. If $\Phi= \langle A_1,A_2,\ldots A_n\rangle$, where each $A_i$ is an ordered set, then we define the following shorthand notation: $\bigoplus_{i=1}^{n} A_i = \bigoplus_{A\in\Phi} A = A_1 \oplus A_2 \oplus\ldots\oplus A_n$.

If $S$ is a set of numbers, then we define that $\min(S)$ and $\max(S)$ return the minimum and maximum values in $S$, respectively.

If A and B are two ordered sets, then we define that A < B if and only if A is lexicographically less than B. That is, A < B if and only if

1. there exists an integer, $0 \leq i < \min(\{\operatorname{Len}(\mathbf{A}),\operatorname{Len}(\mathbf{B})\})$ such that $\mathbf{A}[i] < \mathbf{B}[i]$ and $\mathbf{A}[j] = \mathbf{B}[j]$ for all $0 \leq j < i$; or

2. $\operatorname{Len}(\mathbf{A}) < \operatorname{Len}(\mathbf{B})$ and $\mathbf{A} = \mathbf{B}[0,\operatorname{Len}(\mathbf{A})]$.

Pseudocode

Algorithms are described in this paper using a form of pseudocode that we have used in several previous publications [e.g., 3–6, 11]. This pseudocode closely resembles that used by Cormen et al. [1] in terms of the assumptions that it makes about, for example, the machine model and data structures. In this pseudocode, data-structures are typically represented as sets and ordered sets. It is generally assumed that ordered sets will be implemented as arrays or some other array-like data structures that support constant-time random access. Sets are assumed to be implemented by data structures that allow for dictionary operations (add, delete and test for membership) to be carried out in $O(\log n)$ time in the worst case (e.g., by using a binary tree) or $O(1)$ time on average (e.g., by using a hash table), where $n$ is the number of elements in the set. If a specific data structure implementation is intended, then this will be explicitly stated.

As an example, Figure 1 shows pseudocode for the well-known insertion-sort algorithm. As can be seen in this example, an algorithm is expressed as a function which begins with a header line (unnumbered) in which the name of the function is printed flush-left in CapitalizedSmallCaps. The name of the function is followed on the same line by a list of parameters enclosed in parentheses (in this example, simply A). The numbered lines following the header line form the body of the function and describe the steps carried out by the algorithm on its parameters.

As exemplified in Figure 1, each line starts with a number and then the line itself is printed, indented by at least one tab stop. The looping constructs, for and while, and the conditional constructs, if and else, have the same meaning as they do in languages like C, C++, Java and C#. Block structure is indicated solely by indentation, which reduces clutter and dispenses with the need for reserved keywords such as do, begin, end and then. It also removes the need for punctuation such as semicolons to mark the ends of statements. Note that comments are written in grey italics and start with a grey, right-pointing arrowhead (e.g., ▸ A comment.). Anything to the right of such an arrowhead on a line does not form part of the algorithm. Lines that only contain comments are not numbered.

In this pseudocode, the assignment operator is $\leftarrow$ and the equality operator is $=$. Variables and parameters in a function should generally be considered local to the function, unless otherwise stated, and variables are not declared or typed before they

InsertionSort(A)
▶ A is an ordered set of elements in an arbitrary order.
1 for j ← 1 to Len(A) − 1
2   k ← A[j]
▶ Following inserts A[j] into the sorted sequence A[0, j]
3   i ← j − 1
4 while i ≥ 0 ∧ A[i] > k
5   A[i + 1] ← A[i]
6   i ← i − 1
7   A[i + 1] ← k

are used. Typically, as in languages like Java and C#, we assume that, when provided as the argument of a function, a primitive type value (e.g., a basic integer or floating-point value) is passed by value, while more complex structures and objects (e.g., sets and ordered sets) are passed by reference. If this distinction is significant in any specific case, then it will be noted in the text. As an example, the parameter A in Figure 1 is assumed to be passed by reference. This means that there is no need for the algorithm to return a new ordered set of values, as the elements in the ordered set passed to the algorithm in the parameter A will be in sorted order after the algorithm has completed. Other features of the pseudocode will be introduced at the points in the paper where they are first required.

As a concrete example of how such pseudocode might be implemented, Figure 2 shows a straightforward Java implementation of the insertion sort algorithm shown in Figure 1.

Datasets and patterns

In this paper, we suppose that we are provided with a set of points, $D \subset\mathbb{R}^{k}$, that we call a dataset. If $D \subset\mathbb{R}^{k}$, then the dimensionality of $D$ is $k$, so we can call it a $k$-dimensional dataset. We denote the cardinality or size of $D$ by $|D|$. Typically, in the context of an application in computational music analysis or music information retrieval, a dataset represents a piece of music, part of a piece of music, or a collection of pieces of music, with each point representing a tone, in the sense defined in footnote 2 on page 7 of [10]—that is, either an untied note in a score or a sequence of tied notes. Most commonly in the literature, the datasets considered are two-dimensional, with pitch represented on the $y$-axis and time represented on the $x$-axis. The eight types of two-dimensional representation introduced in [10]—that is, CPO, CPM, MPO, MPM, CO, CM, MO, and MM—are examples of this type of dataset. Figure 8 to Figure 15 in [10] are therefore examples of datasets.

We use the term pattern to refer to any finite point set, $P \subset\mathbb{R}^{k}$, usually (but not always) under consideration in the context of some specified dataset. For example, if we are interested in knowing if a point set, $A$, occurs within a dataset, then we might refer

package com.chromamorph.patternsbook;

import java.util.ArrayList;

public class InsertionSort {
    public static void sort(int[] A) {
        for (int j = 1; j < A.length; j++) {
            int k = A[j];
            int i = j - 1;
            while (i >= 0 && A[i] > k) {
                A[i+1] = A[i];
                i = i - 1;
            }
            A[i + 1] = k;
        }
    }

    public static void main(String[] args) {
        int[] A = new int[args.length];
        for(int i = 0; i < args.length; i++)
            A[i] = Integer.parseInt(args[i]);

        sort(A);
        ArrayList<Integer> AList = new ArrayList<Integer>();
        for(int a : A) AList.add(a);
        System.out.println(AList);
    }
}

to $A$ as a “query pattern” or just a “pattern”, even if it does not actually occur within the dataset.

Transformations