What does the Mongeau-Sankoff algorithm compute?

Henry Boisgibault (1) , Mathieu Giraud (2, 3) , Florent Jacquemard (4)

1 SUPELEC-Campus Gif
2 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
3 Algomus
4 Inria de Paris

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.

Mots clés: Fragmentation; Edit distance; Music similarity; Alignment; Consolidation; Dynamic programming

Domaines: Algorithme et structure de données [cs.DS]; Théorie et langage formel [cs.FL]; Traitement du texte et du document; Son [cs.SD]; Musique, musicologie et arts de la scène

Henry Boisgibault, Mathieu Giraud, Florent Jacquemard. What does the Mongeau-Sankoff algorithm compute?. 2019. ⟨hal-02340896⟩