Grammar compressed sequences with rank/select support
Use this link to cite
http://hdl.handle.net/2183/18191
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 España
Collections
- GI-LBD - Artigos [51]
- OpenAIRE [358]
Metadata
Show full item recordTitle
Grammar compressed sequences with rank/select supportDate
2016-10-14Citation
Alberto Ordóñez, Gonzalo Navarro, Nieves R. Brisaboa, Grammar compressed sequences with rank/select support, Journal of Discrete Algorithms, Available online 14 October 2016, ISSN 1570-8667, http://dx.doi.org/10.1016/j.jda.2016.10.001.
Abstract
[Abstract] Sequence representations supporting not only direct access to their symbols, but also rank/select operations, are a fundamental building block in many compressed data structures. Several recent applications need to represent highly repetitive sequences, and classical statistical compression proves ineffective. We introduce, instead, grammar-based representations for repetitive sequences, which use up to 6% of the space needed by statistically compressed representations, and support direct access and rank/select operations within tens of microseconds. We demonstrate the impact of our structures in text indexing applications.
Keywords
Grammar compression
Repetitive sequences
Text indexing
Repetitive sequences
Text indexing
Description
An early partial version of this paper appeared in Proc. SPIRE 2014: G. Navarro, A. Ordóñez Grammar compressed sequences with rank/select support, Proc. 21st International Symposium on String Processing and Information Retrieval, LNCS, SPIRE, vol. 8799 (2014), pp. 31–44 The final publication is available at Springer via http://dx.doi.org/10.1016/j.jda.2016.10.001
Rights
Atribución-NoComercial-SinDerivadas 3.0 España
ISSN
1570-8667
1570-8675
1570-8675