Henry Boisgibault
email: h.boisgibault@gmail.com

Mathieu Giraud
email: mathieu@algomus.fr

Florent Jacquemard
email: florent.jacquemard@inria.fr

What does the Mongeau-Sankoff algorithm compute ?

Keywords: Music similarity, edit distance, alignment, dynamic programming, consolidation, fragmentation

How similar are two melodies? Proposed in 1990, the Mongeau-Sankoff algorithm computes the best alignment between two melodies with insertion, deletion, substitution, fragmentation, and consolidation operations. This popular algorithm is sometimes misunderstood. Indeed, computing the best edit distance, which is the best chain of operations, is a more elaborated problem. Our objective is to clarify the usage of the Mongeau-Sankoff algorithm. In particular, we observe that an alignment is a restricted case of edition. This is especially the case when some edit operations overlap, e.g. when one further changes one or several notes resulting of a fragmentation or a consolidation. We propose recommendations for people wanting to use or extend this algorithm, and discuss the design of combined or extended operations, with specific costs.

Introduction

Assessing music similarity is a fundamental task in Music Information Retrieval (MIR) studies. [START_REF] Mongeau | Comparison of Musical Sequences[END_REF] proposed to extend sequence comparison algorithms computing an edit distance (the minimal cost for transforming one given string into one other, using a definite set of weighted primitive operations) in order to compare melodies. At that time, Marcel Mongeau was a bachelor student in computer science, and also played and produced experimental music with friends. David Sankoff was already an expert in string comparison, notably for applications in bioinformatics, and worked in the Centre de recherches mathématiques (CRM) at Université de Montréal. David Sankoff taught a lecture on sequence comparison and bioinformatics and proposed this topic to Marcel Mongeau 1 . Both authors are now successful scholars, but neither of them continued research in MIR -Marcel Mongeau works on optimization and operations research, and David Sankoff on bioinformatics. The algorithm of [START_REF] Mongeau | Comparison of Musical Sequences[END_REF] became very popular, and this paper is one of the most cited in the MIR field, being referenced by more than 300 academic works (Figure 1). Today, there is a lot of research in music similarity that spans other music concepts than melodies, using possibly harmony or structure [START_REF] Berit | Finding repeated patterns in music: State of knowledge, challenges, perspectives[END_REF][START_REF] Janssen | A comparison of symbolic similarity measures for finding occurrences of melodic segments[END_REF]. Even when one restricts to melodies, some methods do not rely anymore on string comparison, like geometric matching [START_REF] Ukkonen | Geometric algorithms for transposition invariant content based music retrieval[END_REF], or, more recently, fuzzy approaches, wavelets or deep learning [START_REF] Cheng | Comparing RNN parameters for melodic similarity[END_REF][START_REF] Velarde | An approach to melodic segmentation and classification based on filtering with the Haar-wavelet[END_REF]. However, the classical Mongeau-Sankoff algorithm is still used and extended in many studies, even if most of the people do not use the exact cost functions proposed by the authors.

One of the core ideas of the authors is to use, together with the standard primitive operations of the Levenshtein distance (namely single-character insertion, deletion and substitution) the new operations of consolidation (a few characters being compressed into a single one) and fragmentation (a single character being expanded into a few), for a better match with musical content. Consolidation and fragmentation operations are similar to the compression and expansion operations of Dynamic Time-Warping algorithms used in music but also for e.g. speech recognition, where they allow to compare two speech recordings with different variations in speed [START_REF] Kruskal | The Symmetric Time-Warping Problem: from Continuous to Discrete[END_REF].

The Mongeau-Sankoff algorithm is perceived as relevant to measure music similarity, and was evaluated against other algorithms [START_REF] Gomez | An analysis of the Mongeau-Sankoff algorithm for music information retrieval[END_REF][START_REF] Grachten | A Comparison of Different Approaches to Melodic Similarity[END_REF]. Indeed, fragmentations and consolidations are frequently used in variations (Figure 5 and 6, later in the article), but also in songs and vocal music, where several lyrics are used on a same melodic contour (Figure 2). Several authors used or extended these consolidation/fragmentation operations, and sometimes proposed other edit operations, for a wide range of MIR applications, such as query-by-humming [START_REF] Dannenberg | A Comparative Evaluation of Search Techniques for Query-by-Humming Using the MUSART Testbed[END_REF][START_REF] Dannenberg | Understanding search performance in Query-By-Humming systems[END_REF][START_REF] Hu | A Comparison of Melodic Database Retrieval Techniques Using Sung Queries[END_REF], musical dictations marking [START_REF] Tremblay | Automatic Marking of Musical Dictations By Applying the Edit Distance Algorithm On a Symbolic Music Representation[END_REF], ornementation [START_REF] Grachten | Evolutionary Optimization of Music Performance Annotation[END_REF], performers behavior annotation [START_REF] Arcos | Extracting Performers' Behaviors to Annotate Cases in a CBR System for Musical Tempo Transformations[END_REF], polyphonic alignment [START_REF] Hanna | Improvments of Aligmnement Algorithms for polyphonic music Retrieval[END_REF], rhythm alignment [START_REF] Levé | Rhythm extraction from polyphonic symbolic music[END_REF], or variation analysis and sampling [START_REF] Giraud | Fragmentations with pitch, rhythm and parallelism constraints for variation matching[END_REF][START_REF] Pachet | Sampling variations of sequences for structured music generation[END_REF].

The Mongeau-Sankoff algorithm is presented as a set of Dynamic Programming equations. The common idea is that it compares two melodies while finding the best combination of substitutions, deletions, insertions, consolidations, and fragmentations. Indeed, it computes the best alignment (called trace by Mongeau and Sankoff, see Figure 3) between two melodies with these operations, that is a correspondence between their respective positions describing applications of primitive operations: "It can be shown that the optimal trace linking two musical sequences is obtained through the use of pointers [in the] recurrence equation and the best alignment is found by following the pointers starting at [the last case of the recurrence table]" [START_REF] Mongeau | Comparison of Musical Sequences[END_REF] Figure 3. Trace linking two sequences, from [START_REF] Mongeau | Comparison of Musical Sequences[END_REF].

Aim and Contents

We aim here to lay out precisely what Dynamic Programming algorithms like the Mongeau-Sankoff algorithm does compute, stressing this difference between alignments and edit distances. Note that some relations between alignments and edit distances, not applied to music, were already studied by [START_REF] Ukkonen | Algorithms for Approximate String Matching[END_REF]. In particular, we observe that an edit distance with fragmentations and consolidations is, in general, not even computable, even if many practical cases are tractable. After some definitions in Sections 2 (operations), 3 (edit distances) and 4 (alignments), we show in Section 5 that it is sometimes different to compute the best alignment and the edit distance between two melodies, as some transformations by edit operations cannot be viewed as an alignment. In other words, an alignment is a restricted case of edition. This is especially the case when some edit operations overlap, operations cost s 1 Hamming distance sdi 1 Levenshtein distance sdiCF 1 some in sdicf family 1, adding w pitch or/and w dur for non-strict f/c Table 1. Some rulesets and costs used in this paper. The actual [START_REF] Mongeau | Comparison of Musical Sequences[END_REF]) algorithm used more elaborated costs. e.g. when one further changes one or several notes resulting of a fragmentation or a consolidation.

This case was partly taken into account by Mongeau and Sankoff, who encoded into the costs of fragmentation or consolidation other potential operations. Nevertheless, some musically relevant cases are not optimally handled by the original algorithm, such as the one depicted on Figure 4, that involves a fragmentation followed by a consolidation. Section 6 discusses the design of such combined or extended operations, with specific costs, and opens perspectives on future research.

This paper is intended for people working in computer music wanting to understand, use, or extend a Mongeau-Sankoff-like algorithm for melodic similarity computation. We present in [START_REF] Giraud | Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations[END_REF]) a more theoretical content on the computability of such edit distances.

Operations, rulesets and costs

We consider a fixed finite set N of symbols representing notes and denoted by α, β... Each symbol α gathers two attributes of pitch and duration, respectively denoted by pitch(α) and dur(α). A monophonic sequence of notes, or, for short, a melody, is a sequence over N . The set of sequences over N is denoted N * and ε denotes the empty sequence.

Operations and rulesets

An edit operations is a pair (ℓ → r) with ℓ, r ∈ N * . A ruleset E is a set of edit operations of one of the following types, which are commonly applied to melodies:

(s) substitution: α → β, (i) insertion: ε → β, (d) deletion: α → ε, (f) fragmentation: α → α 1 . . . α k , with k ≥ 0, (c) consolidation: α 1 . . . α k → α, with k ≥ 0.
Note that (s) and (d) are particular cases of (f), with respectively k = 1 and k = 0, and (s) and (i) are particular cases of (c).

We also consider strict fragmentation (F) that splits one note into a set of notes of the same pitch and of the same total duration, that is, such that ∑ k i=1 dur(α i ) = dur(α) and pitch(a 1 ) = . . . = pitch(α k ) = pitch(α), and strict consolidation (C) that proceeds in the other direction, with the same restrictions. (Middle) With strict fragmentation and consolidations with a cost of 1, some optimal sequence of edit operations are not alignments: They are overlapping, here with a substitution in the middle of a fragmentation (left) and a consolidation after a fragmentation (right). Alignments can here be represented by using other melodies b and y.

Edit dist. D sdi (a, c) = 3 Best alig. D ′ sdi (a, c) = 3 Best alig. D ′ sdiCF (a, c) = 3 Edit dist. D sdi (x, z) = 3 Best alig. D ′ sdi (x, z) = 3 Best alig. D ′ sdiCF (x, z) = 3 Edit dist. D sdiCF (a, c) = 2 Edit dist. D sdiCF (x, z) = 2 Alig. D ′ sdicf (a, c) = 1 + w pitch Alig. D ′ sdicf (x, z) = 2 + w dur
(Bottom) When fragmentation and consolidation can include pitch or total duration change, some alignments can be closer or equal the edit distance, depending on the costs w pitch and w dur for these operations.

Chain of positioned operations

A positioned operation of a ruleset E is a pair π = ⟨ℓ → r, i⟩ made of an edit operation of E and a natural number, meaning that ℓ → r is applied at position i. For two melodies s, t of N * , we write s -→ π t if for some u, v ∈ N * , s = u ℓv, t = urv, and

i = |u|. For a chain of positioned operations ⃗ π = π 1 π 2 . . . π n , with π j = ⟨ℓ j → r j , i j ⟩ for all j = 1..n, we write s -→ ⃗ π t if s = s 0 --→ π1 s 1 . . . --→ πn s n = t for some s 0 , . . . , s n ∈ N * .
For example, we consider the three melodies of the left of

c 1 = b 1 , c 2 = b 2 , c 4 = b 4 , c 5 = b 5 ). It is written as positioned operations a -----→ ⟨frag,1⟩ b
and b ------→ ⟨subst,2⟩ c, and, as a chain, a ------------→ ⃗ π=⟨frag,1⟩⟨subst,2⟩ c.

Costs

In order to look to the best way to transform a melody into another one, one has to be able to measure the likelihood of a chain of operations. Each operation ℓ → r of a ruleset E is associated a strictly positive cost δ(ℓ → r). The cost of a chain of positioned operations is then the sum of the individual costs:

δ(⃗ π) = ∑ n i=1 δ(ℓ i → r i ).
Ideally, cost precisely model the likelihood of an operation. In bioinformatics, to compare proteins seen as sequences over the 20-letter alphabet of amino acids, the BLOSUM62 substitution matrix [START_REF] Henikoff | Amino acid substitution matrices from protein blocks[END_REF], learned on aligned data, reflects the logarithm of the probability of substitution of any two amino acids, and the cost of a chain estimates the probability of this chain of operations.

Designing actual cost functions play an important role in achieving musically relevant results and will be discussed in Section 6. To keep the argument simple, we will use here very simple costs: 1 for every (sdiCF) operation, and additional costs when one allows non-strict fragmentations and consolidations. Table 1 shows these rulesets and costs.

Edit distance: chains of operations

Edit distance quantifies the proximity of two sequences by asserting the minimum cost of operations transforming one into the other one. The idea here is that when operations are "atomic", one can combine them. Formally, the edit distance between s and t wrt a ruleset E is:

D E (s, t) = min { δ(⃗ π) s ⃗ π -→ t } .
This implies that, for two rulesets E and F with E ⊂ F , we have

D E (s, t) ≥ D F (s, t) (1)
Indeed, all chain of operations using E are chains of operations using F , and thus having a larger ruleset may lower the minimum cost.

For example, taking all substitution, deletion and insertion operations (E sdi ) with a cost of 1, for the melodies in Figure 4 (left), we have D sdi (a, c) = 3, with a chain of one (duration) substitution and insertions of two eights (we write D sdi instead of D Esdi to enlighten notations).

If we add the strict fragmentations and consolidations, also with cost 1, the edit distance is now D sdiCF (a, c) = 2 with the chain presented above with one fragmentation and one substitution. Here D sdiCF ≤ D sdi because E sdi ⊂ E sdiCF .

Note that as soon as a ruleset contains at least E di , that is all deletion and insertion operations, there is always at least one way to transform one melody s into another one t, by deleting all notes of s then inserting all notes of t. However, in the general case, with arbitrary rulesets, there can be no chain of operations of E transforming s into t, and in this case we set D E (s, t) = +∞.

Computability of the edit distance

The edit distance D E can be efficiently computed in some common cases (see Section 5). On may even observe however that, in general, the problem whether D E (s, t) < +∞, given some arbitrary ruleset E and sequences s and t, is equivalent to the problem of the existence of a chain ⃗ π of E such that s -→ ⃗ π t (a problem called reachability of t from s using E).

It is possible to encode the computations of a given Turing machine M in these settings. More precisely, every configuration of M can be encoded into a finite sequence of N * , and every computation step M can be simulated by a combination of operations of types (c), (f) (with at most 4 symbols), and (i), (d). Hence, there exists a finite ruleset E(M) such that, M, when starting in a configuration encoded into s ∈ N * , can terminate its computation into another configuration encoded into t ∈ N * , if and only if D E(M) (s, t) < +∞. As the former problem is known to be undecidable, there is no hope to be able to compute D E (s, t) in general. This reachability can also be encoded into another undecidable problem [START_REF] Giraud | Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations[END_REF].

Alignments: chains of non-overlapping operations

Alignments between sequences represent some chains of operations by layering down how some elements of the first sequence are transformed into elements of the second one. To conveniently represent the alignment on two lines, a key principle is that the operations are non-overlapping: Blocks of elements from the first sequences are transformed into blocks of elements of the second sequence.

Alignment

An alignment (that was called a trace by Mongeau and Sankoff) ⃗ π = π 1 π 2 . . . π n is a chain of consecutive non-overlapping positioned operations of E, that is, such that i j ≥ i j-1 + |r j-1 | for all j = 2..n, writing π j = ⟨ℓ j → r j , i j ⟩. We call D ′ E (s, t) the optimal cost of an alignment between s and t using E:

D ′ E (s, t) = min { δ(⃗ π) s ⃗ π -→ t, ⃗ π is a alignment }
For two rulesets E and F with E ⊂ F , all alignements using E are alignements using F , thus we have again, as in (1)

D ′ E (s, t) ≥ D ′ F (s, t) (2)
Figure 4 (top, left) depicts an example of alignment π 1 π 2 π 3 between the melodies a and c, where π 1 is a substitution (preserving pitch but reducing duration) applied at position 1, and π 2 , π 3 are two insertions applied respectively at positions 2 and 3. This alignment is optimal for E sdi and a, c, hence we have D ′ sdi (a, c) = 3. It also holds that D sdi (a, c) = 3: the best alignment is here the edit distance.

Computing best alignments with Dynamic Programming

Let S(i, j) be the cost of the best alignment D ′ E (α 1 . . . α i , β 1 . . . β j ). As the alignments are not overlapping, Bellman's principle of optimality can be applied. When the ruleset is finite, this cost can be computed by Dynamic Programming, as shown in 1985 by Ukkonen (Algorithm 13 of [START_REF] Ukkonen | Algorithms for Approximate String Matching[END_REF]):

S(i, j) = min { S(i -k, j -ℓ) + δ(α i-k+1 . . . α i → β j-ℓ+1 . . . β j ) (3)
If the ruleset is E sdicf , this is the well-known [START_REF] Mongeau | Comparison of Musical Sequences[END_REF] algorithm:

S(i, j) = min                S(i -1, j -1) if α i = β j (match) S(i -1, j -1) + δ(α i → β j ) (substitution) S(i -1, j) + δ(α i → ε) (deletion) S(i, j -1) + δ(ε → β j ) (insertion) S(i -k, j -1) + δ(α i-k+1 . . . α i → α j ) (consolidation) S(i -1, j -k) + δ(α i → β b-k+1 . . . β j ) (fragmentation)
To compute the best local alignment D ′ E (α i ′ . . . α i , β j ′ . . . β j ), one may use the same equations adding a 0 in each minimum. In both cases, computing S(i, j) is done in time O(i • j • |E|).

Do best alignments correspond to the edit distance ?

As every alignment is a sequence of positioned operations, we always have

D ′ E (s, t) ≥ D E (s, t) (4)
This inequality can be strict in some cases, as a sequence of positioned operations may not be an alignment.

With insertions, deletions and substitutions, best alignments correspond to the edit distance

In the case E = E sdi , we have D sdi = D ′ sdi . Indeed, there is always an optimal sequence of non-overlapping operations yielding to the (minimal) edit distance.

More formally, when the costs respect the triangle inequality, for every chain of positioned operations ⃗ π such that s ⃗ π -→ t, there exists an alignment ⃗ τ such that s ⃗ τ -→ t, with δ(⃗ τ ) ≤ δ(⃗ π). Thus D sdi can be computed using the above Dynamic Programming equation (3). This is true for the Levenshtein distance (E sdi , all costs 1), but also for any other costs, leading to the [START_REF] Needleman | A general method applicable to the search for similarities in the amino acid sequence of two proteins[END_REF] and [START_REF] Smith | Identification of common molecular subsequences[END_REF] algorithms used in bioinformatics sequence comparison. The popular conception such that "the best alignment is the edit distance" is thus true on these common cases.

In general, best alignments do not always correspond to edit distance

As we have seen that the edit distance D E is not computable in general [START_REF] Giraud | Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations[END_REF], whereas the best alignment D ′ E is always computable in polynomial time. Hence it comes with no surprise that the two concepts deviate at some point. Indeed, for some rulesets more elaborated than D sdi , it might hold that D ′ E (s, t) > D E (s, t), in the case where the optimal sequence of positioned operations involves overlapping positioned operations [START_REF] Ukkonen | Algorithms for Approximate String Matching[END_REF].

In Figure 4 (both left and right), adding strict fragmentations and consolidations to the set of operations does not change the optimal alignment, with

D ′ sdi (a, c) = D ′ sdiCF (a, c) = 3 and D ′ sdi (x, z) = D ′ sdiCF (x, z) = 3 (top)
, whereas the edit distances with the same operations are 2 (middle). The reason is that in both cases, the last operation of the optimal chain of edit operations overlaps with the result of a previous fragmentation: on the left, the optimal chain is a - -----------→ ⃗ π=⟨frag,1⟩⟨subst,2⟩ c and the second position 2 < 1 + 3 (1 is the position of fragmentation a 2 ---→ frag b 2 b 3 b 4 and 3 is its length); on the right, the optimal chain is a ------------→ ⃗ π=⟨frag ′ ,0⟩⟨cons,2⟩ c and similarly, 2 < 0+3.

Therefore in both cases, the restriction that i j ≥ i j-1 + |r j-1 | in the definition of alignement is not satisfied. [START_REF] Mongeau | Comparison of Musical Sequences[END_REF], annotations are ours. While they are both in binary meter, Variation 3 is with binary subdivisions and variation 7 with ternary subdivisions, making note-by-note alignment difficult. Here none of the fragmentations (f) do preserve the total duration, whereas all of the substitutions (s) change durations. This alignment involves 5 fragmentations, 6 substitutions, 1 deletion and 1 insertion, for a cost of about 14 + 12w dur .

Impact on computed similarities

We take the same example that was used in 1990, on variations on Ah vous dirai-je maman, by Mario [START_REF] Duschenes | Variations on Twinkle, Twinkle[END_REF] in his recorder method, which was very popular in Québec and more generally in Canada. Even if these variations may have been inspired by Mozart's own variations K265/300e, they are not the ones of Mozart nor an arrangement, but an original work by Mario Duchesnes. Comparing Variations 3 and 7 confirms that a proper computation of edit distances, with fragmentations and consolidations, yields here a more musically relevant similarity than the alignments output by the Mongeau-Sankoff algorithm (Figures 5 and6). As usual, note that the actual edit distance and optimal costs depend on the chosen costs. This example is particularly challenging as both variations do not have the same subdivision of time. An extreme way of chaining operations, consolidating every beat then refragmenting them (Figure 6, bottom), yields here a very low edit distance. This also confirms the "central role of the theme", as already noted by Mongeau and Sankoff: Somehow a very relevant way to compare variations is to align each of them to the theme.

Discussion and Perspectives: Combined and Extended Operations

The previous sections showed that, while proper edit distances with fragmentations and consolidation yield interesting melodic similarities, they are not as easy to compute as best alignments. One could use other algorithms -such as geometric algorithms or algorithms learning similarity from annotated data -to assess the music similarity between melodies. But edit distances are a good way to model how musical patterns may evolve. Dynamic Programming methods are relatively efficient and simple to model. As some of these cases may be musically relevant, especially in paradigmatic music analysis, can we compute alignments that reflect or approximate the edit distance?

Exact Computation of Edit Distance

Edit distance can be seen as the length or the weight of the shortest path in a edition graph where vertices are melodies and edges the edit operations. Assuming that this graph is finite, the Dijkstra's algorithm finds the shortest path in O(e + v log v), where e is the number of edges and v the number of vertices [START_REF] Dijkstra | A Note on Two Problems in Connexion with Graphs[END_REF]. However, this graph is almost always infinite, for example as soon as there are insertions or fragmentations.

We have seen that for E sdi , the edit distance coincides with the notion of best alignment that can be computed efficiently with (3). Besides this well-known case, further research should explore which edit distances considering some fragmentations and consolidations can be efficiently computed, in particular for rulesets containing only consolidations and deletions, or only fragmentations and insertions [START_REF] Giraud | Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations[END_REF].

Over-Approximation of Edit Distance

Mongeau and Sankoff were themselves aware that the similarity they compute was not a distance, and proposed in their original article the use of elaborated costs within the fragmentation and consolidations. Researching on the best costs to model music similarity is still an open problem, but we restate here the link between these costs and sequence of edit operations.

To cope with the fact that edit distance can not always be exactly computed, a simple idea is to have combined or extended operations that will finally be sequenced in a non-overlapping way to allow a proper use of a generalized Algorithm (3). One can indeed create new edit operations that combines two or more successive positioned edit operations, possibly overlapping, in E. For example, the new operation (α → αβα) combines the fragmentation (α → ααα) with a substitution (α → β) in second position. 2 The cost of this new operation is the sum of the two former operations. This new "fragmentation-then-substitution" operation is one (non-strict) (f) operation, that allows, at once, to align melodies a with c in Figure 4 (bottom left). If one strictly combines the costs, the cost of this operation is here 1 + w pitch = 2, allowing here to have a alignment cost D ′ sdicf (a, c) equal to the edit distance. Similarly, a combined operation transforming x into z (right of Figure 4) would be on the form (αβ → γδ).

We call E 2 the set obtained by completing E with all edit operations combining two operations in E. We can observe on the one hand that D E 2 (s, t) = D E (s, t) for all melodies s, t: Applying a combined operation in a chain is just a shortcut to the application of two operations of E, with the same cost. But on the other hand, it holds by Equation ( 2

) that D ′ E 2 (s, t) ≤ D ′ E (s, t):
Such shortcuts allow, in some cases, to turn an overlapping operation chain into an alignment, without overlaps. In other terms,

D ′ E 2 is a better approximation of D E than D ′ E . The combination can be continued into sets E 3 , E 4 ... until a closure E * = ∪ i≥1 E i . By construction, D E (s, t) = D ′ E * (s, t).
In general, E * will be infinite -and even with the ruleset E = E sdi , E * is infinite. We may however consider any finite subset E

• ⊂ E * with E ⊂ E • to compute with Equation (3) an approximation of D E better than D ′ E .
Indeed, by application of Equation ( 2), we have:

D E (s, t) = D ′ E * (s, t) ≤ D ′ E • (s, t) ≤ D ′ E (s, t).
However, even when E = E sdicf , the set E 2 is difficult to construct, and there are still chains of operations on E that will not be alignments on E 2 , as for example two consolidations overlapping both ends of a pattern created by a fragmentation (in that case this combination will be in E 3 ).

Note that E is implicitly represented in Dynamic Programming methods. For exemple, the substitution on the form α → β has a quadratic number of instances, substituting each note to another one, but they are handled by a single line in the Algorithm (3). The possible dependence on α and β is hidden in the cost δ(α, β).

On the contrary, explicitly representing E 2 or any other E • ⊂ E * may lead to combinatorial explosion, beginning with operations such as (αβ → γδ) seen above. In the general case, this explosion can not be prevented as it reflects the exponential number of paths into an edition graph. Further research should be done on the computability of such combined operations in some restricted cases.

Using and designing costs on extended operations

One can nevertheless advise the proper use of consolidations and fragmentations. The original costs of the Mongeau-Sankoff algorithm involve pitches (and intervals) and durations: S(i, j) = min    . . . S(i -k, j -1) + δ(α i-k+1 . . . α i → β j ) S(i -1, j -k) + δ(α i → β j-k+1 . . . β j )

Researches should continue on designing cost functions δ encoding some operations of E or E * as insertion, substitutions, or even other operations. Indeed, defining operations, costs, and thresholds is an opportunity to think on music similarity [START_REF] Berit | Finding repeated patterns in music: State of knowledge, challenges, perspectives[END_REF][START_REF] Cambouropoulos | How similar is similar?[END_REF][START_REF] Janssen | A comparison of symbolic similarity measures for finding occurrences of melodic segments[END_REF]. Costs are thus not only implementation details but fundamental to any such a method.

When comparing most Western common practice music, the impact of the operations on tonality and meter can be assessed through costs. For example, substitutions, consolidation, and fragmentation changing durations break the metric structure and may have higher costs. Substitutions of pitches may also be weighted differently, for example favoring neighbor notes or notes within the same consonant chord. Such "close" substitutions are commonly used in variations (see again Figure 6), or, more generally, in elaborations of a pattern.

As suggested by [START_REF] Giraud | Fragmentations with pitch, rhythm and parallelism constraints for variation matching[END_REF], one could even use extended operations such as a transformation operation, editing as once several notes into several others, that is taking exactly the [START_REF] Ukkonen | Algorithms for Approximate String Matching[END_REF] algorithm (3). This opens both musicological and computational questions on how to pertinently and efficiently evaluate δ(α i-k+1 . . . α i → β j-ℓ+1 . . . β j ). The evaluation of δ could be delegated to other techniques, either computing exact edit distances (for example on an edition graph), or using other ways to model small transformations. Once δ is defined, the algorithm (3) would again compute the best chain of non-overlapping extended editions.

Figure 1 .

 1 Figure 1. Citations of the Mongeau-Sankoff algorithm throughout the years, data from semanticscholar.

Figure 2 .

 2 Figure 2. Patterns in the verse of Imagine, by John Lennon and Yoko Ono, can be seen as fragmentations of a melody G/B/A. The same melody is found in the piano theme, not shown here.

Figure 4 .

 4 Figure 4. Two independent examples (left and right columns) where best alignments do not correspond to the edit distance for some edit operations and costs. Rulesets and costs are defined on Table 1. (Top) With insertion/deletion/substitutions, best alignements between melodies a and c (left) and between melodies x and z (right) are the edit distances.(Middle) With strict fragmentation and consolidations with a cost of 1, some optimal sequence of edit operations are not alignments: They are overlapping, here with a substitution in the middle of a fragmentation (left) and a consolidation after a fragmentation (right). Alignments can here be represented by using other melodies b and y. (Bottom) When fragmentation and consolidation can include pitch or total duration change, some alignments can be closer or equal the edit distance, depending on the costs w pitch and w dur for these operations.

  Figure 4: a = a 1 a 2 a 3 , b = b 1 b 2 b 3 b 4 b 5 , and c = c 1 c 2 c 3 c 4 c 5 . Going from a to b is done by the fragmentation of the dotted quarter A into three eights, a 2 ---→ frag b 2 b 3 b 4 (and a 1 = b 1 , a 3 = b 5 ), and going from b to c is done by the (pitch) substitution of one eight b 3 ----→ subst c 3 (and

Figure 5 .

 5 Figure 5. Alignments between variations 3 and 7 by M. Duchesnes on Ah vous dirai-je maman. Figure from the original article[START_REF] Mongeau | Comparison of Musical Sequences[END_REF], annotations are ours. While they are both in binary meter, Variation 3 is with binary subdivisions and variation 7 with ternary subdivisions, making note-by-note alignment difficult. Here none of the fragmentations (f) do preserve the total duration, whereas all of the substitutions (s) change durations. This alignment involves 5 fragmentations, 6 substitutions, 1 deletion and 1 insertion, for a cost of about 14 + 12w dur .

Figure 6 .

 6 Figure 6. Alignments between variations 3 and 7 by M. Duchesnes on Ah vous dirai-je maman, compare to Figure 5. Chains with overlapping operations. All considered consolidations and fragmentations preserve the total duration, as Variation 7 is written with triplets. (Top) This chain of operation involves 2 strict consolidation, 3 strict fragmentations, and 3 other fragmentations. Other places are use 6 s/d/i operations similar to the original aligment of the Figure 5. The total cost is 14 + 3w pitch . (Bottom) Here the chain contains only consolidation and fragmentation operations (11 operations, including 5 strict ones). The total cost is 11 + 6w pitch .

In fact, it is a combination of positioned operations: ⟨α → ααα, i⟩ and ⟨α → β, i + 1⟩ gives ⟨α → αβα, i⟩.