Document - Dynamic compressed strings with random access

2013

Conference article Open Access

Dynamic compressed strings with random access

Grossi R., Raman R., Rao S., Venturini R.

H.3 INFORMATION STORAGE AND RETRIEVAL Indexing

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].

Source: ICALP 2013 - Automata, Languages, and Programming. 40th International Colloquium, pp. 504–515, Riga, Latvia, 8-12 July 2013

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:277759,
	title = {Dynamic compressed strings with random access},
	author = {Grossi R. and Raman R. and Rao S. and Venturini R.},
	doi = {10.1007/978-3-642-39206-1_43},
	booktitle = {ICALP 2013 - Automata, Languages, and Programming. 40th International Colloquium, pp. 504–515, Riga, Latvia, 8-12 July 2013},
	year = {2013}
}