In-place Update of Suffix Array while Recoding Words

Matthias Gallé 1 Pierre Peterlongo 1 François Coste 1, *
* Auteur correspondant
1 SYMBIOSE - Biological systems and models, bioinformatics and sequences
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Motivated by grammatical inference and data compression applications, we propose an algorithm to update a suffix array after the substitution, in the indexed text, of some occurrences of a given word by a new character. Compared to other published index update methods, the problem addressed here may require the modification of a large number of distinct positions over the original text. The proposed algorithm uses the specific internal order of suffix arrays in order to update simultaneously groups of entries, and ensures that only entries to be modified are visited. Experiments confirm a significant execution time speed-up compared to the construction of suffix array from scratch at each step of the application.
Type de document :
Communication dans un congrès
Jan Holub and Jan }}}rek. Prague Stringology Conference 2008, Sep 2008, Prague, Czech Republic. pp.54--67, 2008
Liste complète des métadonnées

https://hal.inria.fr/inria-00327582
Contributeur : François Coste <>
Soumis le : mercredi 8 octobre 2008 - 18:01:08
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : vendredi 4 juin 2010 - 12:22:35

Fichiers

Identifiants

  • HAL Id : inria-00327582, version 1

Citation

Matthias Gallé, Pierre Peterlongo, François Coste. In-place Update of Suffix Array while Recoding Words. Jan Holub and Jan }}}rek. Prague Stringology Conference 2008, Sep 2008, Prague, Czech Republic. pp.54--67, 2008. 〈inria-00327582〉

Partager

Métriques

Consultations de la notice

414

Téléchargements de fichiers

117