Grammar compressed sequences with rank/select support
Use este enlace para citar
http://hdl.handle.net/2183/18191
A non ser que se indique outra cousa, a licenza do ítem descríbese como Atribución-NoComercial-SinDerivadas 3.0 España
Coleccións
- GI-LBD - Artigos [54]
- OpenAIRE [368]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Grammar compressed sequences with rank/select supportData
2016-10-14Cita bibliográfica
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.
Resumo
[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.
Palabras chave
Grammar compression
Repetitive sequences
Text indexing
Repetitive sequences
Text indexing
Descrición
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
Versión do editor
Dereitos
Atribución-NoComercial-SinDerivadas 3.0 España
ISSN
1570-8667
1570-8675
1570-8675