Grammar Compressed Sequences with Rank/Select Support
| Autor: | Ordóñez, Alberto, Navarro, Gonzalo, Brisaboa, Nieves R. |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Journal of Discrete Algorithms 43, pp. 54-71 (2017) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.jda.2016.10.001 |
| Popis: | 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. Comment: This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941 |
| Databáze: | arXiv |
| Externí odkaz: |
|