Artículos de revistas
Grammar compressed sequences with rank/select support
Fecha
2017Registro en:
Journal of Discrete Algorithms 43(2017)54–71
10.1016/j.jda.2016.10.001
Autor
Ordonez, Alberto
Navarro, Gonzalo
Brisaboa, Nieves R.
Institución
Resumen
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. (C) 2016 Elsevier B.V. All rights reserved.