In-place Update of Suffix Array while Recoding Words - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2008

In-place Update of Suffix Array while Recoding Words

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.
Fichier principal
Vignette du fichier
PSC2008_article06.pdf (342.24 Ko) Télécharger le fichier
psc08p06_presentation.pdf (1.41 Mo) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Format : Other

Dates and versions

inria-00327582 , version 1 (08-10-2008)

Identifiers

  • HAL Id : inria-00327582 , version 1

Cite

Matthias Gallé, Pierre Peterlongo, François Coste. In-place Update of Suffix Array while Recoding Words. Prague Stringology Conference 2008, Sep 2008, Prague, Czech Republic. pp.54--67. ⟨inria-00327582⟩
112 View
201 Download

Share

Gmail Facebook X LinkedIn More