Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

What does the Mongeau-Sankoff algorithm compute?

Henry Boisgibault 1 Mathieu Giraud 2, 3 Florent Jacquemard 4
3 Algomus
MIS - Modélisation, Information et Systèmes - UR UPJV 4290, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : 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.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Florent Jacquemard <>
Submitted on : Thursday, October 31, 2019 - 9:58:42 AM
Last modification on : Monday, April 19, 2021 - 8:56:28 AM
Long-term archiving on: : Saturday, February 1, 2020 - 3:07:02 PM


Files produced by the author(s)


  • HAL Id : hal-02340896, version 1


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



Record views


Files downloads