Grammar Compressed Sequences with Rank/Select Support

11/20/2019
by   Alberto Ordóñez, et al.
0

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 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset