Grammar Compressed Sequences with Rank/Select Support
Gonzalo Navarro and Alberto Ordóñez
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.