Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations

Résumé

We study edit distances between strings, based of 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. We propose weighted automaton constructions to compute in polynomial time an edit distance taking into account both consolidations and deletions, or both fragmentations and insertions. We finally show that the optimal weight of sequences made of consolidations chained with fragmenta-tions, in that order, is computable in polynomial time, and not computable if we reverse the order of fragmentations and consolidations.
Fichier principal
Vignette du fichier
ms-automata.pdf (345.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01857267 , version 1 (14-08-2018)
hal-01857267 , version 2 (17-08-2018)
hal-01857267 , version 3 (31-10-2018)
hal-01857267 , version 4 (16-10-2019)

Identifiants

  • HAL Id : hal-01857267 , version 2

Citer

Mathieu Giraud, Florent Jacquemard. Weighted Automata Computation of Edit Distances with Consolidations and Fragmentations. 2018. ⟨hal-01857267v2⟩
548 Consultations
765 Téléchargements

Partager

Gmail Facebook X LinkedIn More