𝄞 TSM Diff

Description

TSM Diff calculates a list of differences and a similarity distance value between two digital music scores, based on an abstract representation called the Tree Score Model (TSM) — labelled trees with sharing, formally labelled Directed Acyclic Graphs (DAGs).

Starting from two scores in an XML encoding (MusicXML or MEI), it converts them into two TSM DAGs (left and right respectively) and performs a recursive comparison. During the comparison, two separate computations are carried out in parallel:

• Construction of a diff-list. Each difference is associated with a type (see the diff codes below) and references to nodes in the left and right TSM DAGs, making it possible to locate the temporal positions of the elements involved in both scores.
• Calculation of a numerical similarity value, obtained by combining two distances described below.

An export of the TSM DAGs of both scores with differences highlighted is in preparation.

Description of TSM

TSM is an intermediate representation of music scores inspired by rhythm trees [1], where a score is encoded as a labelled DAG. Every node has an ordered sequence of incoming and outgoing edges.

We assume a unique node with zero incoming edges, called the root. Nodes with zero outgoing edges are called leaves and represent basic score elements (notes, rests, etc.). Non-leaf nodes are called inner.

Every node and every edge is associated with a time interval, expressed as a fraction of a bar, closed on the left and open on the right — it may be an empty interval [t, t). The root node is associated with a fixed interval covering the whole score. The interval of every other node is the union of the intervals of its incoming edges. The intervals of incoming edges form a partition.

The label of every inner node is an operator dividing one time interval into sub-intervals. The available inner-node labels are:

• Bar — binary division of I₀ into 1 bar (or less for a pickup bar) and the rest.
• dBar — marker for the end of the last bar.
• Fork — duplication of I₀ into n concurrent voices.
• Chord — same semantics as Fork with additional syntactic restrictions.
• Tuplet — division of I₀ into n > 1 sub-intervals of equal length.
• Deco — binary division: an interval of length 0 for an ornament, and a copy of I₀ for the decorated note or chord.
• Orn — I₀ is empty, as are all its descendants (labelled Note).

Leaf-node labels:

• Note
• Rest
• Tie — continuation of a note or rest via a tie.
• ChordCont — continuation of a chord by another chord, all tied to the previous.

A pseudo-leaf is a leaf node labelled by one of the above, or by Chord.

Normal form

Input TSM DAGs are assumed to be in the following normal form:

• The root is labelled Bar.
• The two descendants of a Bar node are labelled Fork and Bar or doubleBar (end of score).
• Every descendant of a Fork node describes one voice; it contains no Fork, Bar, or dBar.
• The two descendants of a Deco node are labelled Orn (ornament) and Note or Chord.
• All descendants of an Orn node are labelled Note.
• All descendants of a Chord node are labelled Note or Tie.

The yield of a sub-DAG is the sequence of its pseudo-leaves.

Annotations

The TSM DAG also carries annotations:

• Attached to a Bar node: clef, key signature, time signature.
• Attached to one pseudo-leaf: dynamics, articulations, fermata, etc.
• Spanning annotations attached to two pseudo-leaves.
• Floating annotations attached to a Bar node with one or two onset references.

During comparison, annotations are also taken into account in the diff-list. They contribute to the surface distance, but not to the time distance, since they do not change the time interval represented by a TSM node.

Differences

Every entry in the diff-list (called a diff) consists of:

• one or several nodes in the left TSM DAG;
• one or several nodes in the right TSM DAG.

At least one of the two sets of nodes must be a singleton. An empty left (resp. right) set corresponds to the case of an insertion (resp. deletion). A set with more than one node, with a singleton node on the other side, occurs in the case of shared nodes in the DAG, for resynchronizing. The general principle is that a difference always covers the same time interval in both scores.

The relevant information in a diff reported to the user is the labels of these nodes and the corresponding time intervals.

Moreover, a name of edit operation (also called diff code) can optionally be added to help interpret the musical meaning of the diff. In the following demos, the diff codes are chosen among:

• insert
• delete
• replace
• multi
• fragment
• consolidate

The names of the two latter codes are borrowed from Mongeau & Sankoff [15], and correspond to the replacement of a single note by several notes preserving the total duration. The replacement can be horizontal (e.g. replacement of a quarter note by two eighth notes, or vice versa) or vertical (replacement of a note by a chord, or vice versa).

The first three categories of codes are the primitive operations of classical edit distances. We consider moreover some specific subclasses of replace:

• pitch: replacement of a note with a note of different pitch,
• name: replacement of a note with a note of same MIDI pitch but different name,
• tie: replacement of a note with a tie (tied note of same pitch and name),
• split: the opposite operation,
• rhythm: replacement of a Tuplet node with another Tuplet of different arity.

Finally, multi corresponds to the case of more than one node on one side and a singleton node on the other.

The above choice of codes is arbitrary; their selection occurs only in a post-processing step (it depends on the algorithms used for comparison). This list of codes could easily be adapted as required for different case studies.

Distances

Two normalised distance values are computed:

• Time distance (rhythmic distance) — sum of durations of time intervals where scores differ, divided by total duration. Normalised by 2 / (D₁ + D₂), where D₁, D₂ are the total durations (in bars) of the left and right scores.
• Surface distance — for each difference, a comparison of the corresponding yields (lists of leaves), computed as a symbol error rate or Levenshtein edit-distance. Normalised by 1 / (N₁ + N₂), where N₁, N₂ are the total numbers of symbols in the left and right scores.

The similarity measure is 1 minus the harmonic mean of the two distances above.

Computation of the Diff-List and Distances

The diff-list and distances are constructed in five steps.

1. Normalisation

Each score is parsed using the music21 toolkit and converted into a TSM. Both TSMs are then transformed into the normal form described above via term-rewriting rules, guaranteeing a unique representative per score and enabling a fair comparison (not possible by diffing XML encodings directly).

2. Bar-level alignment by LCS

A Longest Common Subsequence (LCS) algorithm aligns equal bars between the two scores. Equality tests are accelerated using hash codes. Bar equality is considered modulo voice permutation to avoid problems from inconsistent voice numbering; for this purpose, voice hashes are combined by sum. The complement of the alignment is a sequence of diff-blocks, each being a pair of sub-sequences of successive bars between alignment points.

3. Diff-block resolution

A Levenshtein edit-distance is computed between the two sequences of bars in each diff-block, using the following bar-level operations:

• Bar insertion (in the right score)
• Bar deletion (from the left score)
• Bar replacement → resolved in step 4.

4. Comparison of bars and voice sets

A bar contains a sequence of homophonic voices under a Fork label. Given two bars to compare, a matching between voices is computed by first pairing equal voices (via hash codes), then finding an optimal sequence of voice insertions, voice deletions, or voice replacements (resolved in step 5).

5. Comparison of two voices

The content of two matched voices is compared by recursive descent through their DAG representations. Starting from a pair of nodes:

• If labels and number of incoming edges coincide → recurse into each pair of descendant nodes of the same rank.
• Otherwise → a difference is added to the diff-list with a code determined by the pair of labels.