HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Thursday, October 31, 2019 - 9:58:42 AM
Last modification on : Thursday, March 24, 2022 - 3:42:51 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