Please use this identifier to cite or link to this item:
Title: Dynamic Compressed Strings with Random Access
Authors: Grossi, Roberto
Raman, Rajeev
Rao, Satti Srinivasa
Venturini, Rossano
First Published: Jul-2013
Presented at: 40th International Colloquium, ICALP 2013, Riga, Latvia
Start Date: 8-Jul-2013
End Date: 12-Jul-2013
Publisher: Springer Berlin Heidelberg
Citation: Grossi, R.; Raman, R. et al. ‘Dynamic Compressed Strings with Random Access’ in Fomin, F.V.; Freivalds, R. et al. (Eds.) Automata, Languages, and Programming - Proceedings of the 40th International Colloquium, ICALP 2013, Part 1 (2013 Springer-Verlag Berlin Heidelberg), pp. 504-515.
Abstract: 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 ith 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. [ICALP, 2012], and Nekrich and Navarro [SODA, 2013].
Series/Report no.: Lecture Notes in Computer Science;7965
DOI Link: 10.1007/978-3-642-39206-1_43
ISSN: 0302-9743
ISBN: 978-3-642-39205-4
eISSN: 1611-3349
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2013 Springer-Verlag Berlin Heidelberg. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website. The final publication is available at
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
icalp13.pdfPost-review (final submitted)370.2 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.