Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings

Shiteng Chen, Elad Verbin, Wei Yu

In this paper we investigate the problem of building a static data structure that represents a string s using space close to its compressed size, and allows fast access to individu…