Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations

Mathieu Giraud 1, 2, * Florent Jacquemard 3, *
* Auteur correspondant
2 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 : We study edit distances between strings, based on operations of character substitutions, insertions, deletions and additionally consolidations and fragmentations. The two latter operations transform a sequence of characters into one character and vice-versa. They correspond to the compression and expansion in Dynamic Time-Warping algorithms for speech recognition and are also used for the formal analysis of written music. Such edit distances are not computable in general for arbitrary rulesets. We propose weighted automaton constructions to compute an edit distance taking into account both consolidations and deletions, or both fragmentations and insertions. Assuming that the operation ruleset has a constant size, these constructions are polynomial into the lengths of the involved strings. We finally show that the optimal weight of sequences made of consolidations chained with fragmentations, in that order, is computable for arbitrary rulesets, and not computable if we reverse the order of fragmentations and consolidations.
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01857267
Contributeur : Florent Jacquemard Connectez-vous pour contacter le contributeur
Soumis le : mercredi 16 octobre 2019 - 12:13:09
Dernière modification le : jeudi 24 mars 2022 - 03:42:49
Archivage à long terme le : : vendredi 17 janvier 2020 - 15:55:18

Fichier

ms-automata.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Mathieu Giraud, Florent Jacquemard. Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations. Information and Computation, Elsevier, 2022, 282, pp.104652. ⟨10.1016/j.ic.2020.104652⟩. ⟨hal-01857267v4⟩

Partager

Métriques

Consultations de la notice

455

Téléchargements de fichiers

648