In-place update of suffix array while recoding words - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Foundations of Computer Science Année : 2009

In-place update of suffix array while recoding words

Résumé

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.
Fichier principal
Vignette du fichier
SAupdate_ijfcs_2008.pdf (365.31 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00471599 , version 1 (08-04-2010)

Identifiants

Citer

Matthias Gallé, Pierre Peterlongo, François Coste. In-place update of suffix array while recoding words. International Journal of Foundations of Computer Science, 2009, 20 (6), pp.1025-1045. ⟨10.1142/S0129054109007029⟩. ⟨inria-00471599⟩
153 Consultations
264 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More