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 while in the indexed text some occurrences of a given word are substituted 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 indices, and ensures that only indices 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 :
Article dans une revue
International Journal of Foundations of Computer Science, World Scientific Publishing, 2009, 20 (6), pp.1025-1045. 〈10.1142/S0129054109007029〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00471599
Contributeur : Pierre Peterlongo <>
Soumis le : jeudi 8 avril 2010 - 15:59:11
Dernière modification le : jeudi 11 janvier 2018 - 06:20:10
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 21:16:59

Fichier

SAupdate_ijfcs_2008.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Matthias Gallé, Pierre Peterlongo, François Coste. In-place update of suffix array while recoding words. International Journal of Foundations of Computer Science, World Scientific Publishing, 2009, 20 (6), pp.1025-1045. 〈10.1142/S0129054109007029〉. 〈inria-00471599〉

Partager

Métriques

Consultations de la notice

282

Téléchargements de fichiers

178