Grammar compressed sequences with rank/select support
Use this link to citehttp://hdl.handle.net/2183/18191
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 España
MetadataShow full item record
TitleGrammar compressed sequences with rank/select support
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] 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.
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–44The final publication is available at Springer via http://dx.doi.org/10.1016/j.jda.2016.10.001
Atribución-NoComercial-SinDerivadas 3.0 España