PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Grossi R., Raman R., Rao S., Venturini R. Dynamic compressed strings with random access. In: ICALP 2013 - Automata, Languages, and Programming. 40th International Colloquium (Riga, Latvia, 8-12 July 2013). Proceedings, vol. Part I pp. 504 - 515. Fedor V. Fomin, Rūsiņ Freivalds, Marta Kwiatkowska, David Peleg. (Lecture Notes in Computer Science, vol. 7965). Springer, 2013.
 
 
Abstract
(English)
We consider the problem of storing a string $S$ in dynamic compressed form, while permitting operations directly on the compressed representation of $S$: access a substring of $S$; replace, insert or delete a symbol in $S$; count how many occurrences of a given symbol appear in any given prefix of $S$ (called rank operation) and locate the position of the $i$th occurrence of a symbol inside $S$ (called select operation). We discuss the time complexity of several combinations of these operations along with the entropy space bounds of the corresponding compressed indexes. In this way, we extend or improve the bounds of previous work by Ferragina and Venturini [TCS,~2007], Jansson et al.mbox{} [ICALP,~2012], Nekrich and Navarro [SODA,~2013].
URL: http://link.springer.com/chapter/10.1007/978-3-642-39206-1_43
DOI: 10.1007/978-3-642-39206-1_43
Subject Indexing
H.3 INFORMATION STORAGE AND RETRIEVAL


Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional