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

Abstract. 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 individual characters of s. This type of structures was investigated by the recent paper of Bille et al. [3]. Let n be the size of a context-free grammar that derives a unique string s of length L. (Note that L might be exponential in n.) Bille et al. showed a data structure that uses space O(n) and allows to query for the i-th character of s using running time O(logL). Their data structure works on a word RAM with a word size of logL bits. Here we prove that for such data structures, if the space is poly(n), then the query time must be at least (logL)1−ε / logS where S is the space used, for any constant ε> 0. As a function of n, our lower bound is Ω(n1/2−ε). Our proof holds in the cell-probe model with a word size of logL bits, so in particular it holds in the word RAM model. We show that no lower bound significantly better than n1/2−ε can be achieved in the cell-probe model, since there is a data structure in the cell-probe model that uses O(n) space and achieves O( n logn) query time. The “bad ” setting of parameters occurs roughly when L = 2 n. We also prove a lower bound for the case of not-as-compressible strings, where, say, L = n1+ε. For this case, we prove that if the space is n · polylog(n), then the query time must be at least Ω(logn / log log n). The proof works by reduction to communication complexity, namely to the LSD (Lopsided Set Dis-jointness) problem, recently employed by Pǎtraşcu and others. We prove lower bounds also for the case of LZ-compression and Burrows-Wheeler (BWT) compression. All of our lower bounds hold even when the strings are over an alphabet of size 2 and hold even for randomized data structures with 2-sided error.