Ordóñez, AlbertoNavarro, GonzaloBrisaboa, Nieves R.2017-02-272016-10-14Alberto 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.1570-86671570-8675http://hdl.handle.net/2183/18191An 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[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.engAtribución-NoComercial-SinDerivadas 3.0 Españahttp://creativecommons.org/licenses/by-nc-nd/3.0/es/Grammar compressionRepetitive sequencesText indexingjournal articleopen access10.1016/j.jda.2016.10.001