|
Title |
Grammar Compressed Sequences with Rank/Select Support |
|
Authors |
Gonzalo Navarro, Alberto Ordóñez Pereira |
|
Publication date |
2014 |
|
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. In several recent applications, the need to represent highly repetitive sequences arises, where statistical compression is ineffective. We introduce grammar-based representations for repetitive sequences, which use up to 10% of the space needed by representations based on statistical compression, and support direct access and rank/select operations within tens of microseconds. |
|
Pages |
31-44 |
|
Conference name |
International Symposium on String Processing and Information
Retrieval |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
Reference URL |
|
