Data structure lower bounds on random access to grammar-compressed strings

DOI10.1007/978-3-642-38905-4_24zbMATH Open1381.68073arXiv1203.1080OpenAlexW1800468673MaRDI QIDQ4928577FDOQ4928577

Authors: Elad Verbin, Wei Yu 

Publication date: 14 June 2013

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

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. 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(log L). 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 (log L)^{1-epsilon}/log S where S is the space used, for any constant eps>0. As a function of n, our lower bound is Omega(n^{1/2-epsilon}). Our proof holds in the cell-probe model with a word size of log L bits, so in particular it holds in the word RAM model. We show that no lower bound significantly better than n^{1/2-epsilon} 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(sqrt{n log n}) query time. The "bad" setting of parameters occurs roughly when L=2^{sqrt{n}}. We also prove a lower bound for the case of not-as-compressible strings, where, say, L=n^{1+epsilon}. For this case, we prove that if the space is n polylog(n), then the query time must be at least Omega(log n/loglog n). The proof works by reduction to communication complexity, namely to the LSD problem, recently employed by Patrascu 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.

Full work available at URL: https://arxiv.org/abs/1203.1080

Recommendations

• Access, rank, and select in grammar-compressed strings
• Random access to grammar-compressed strings and trees
• Random access to grammar-compressed strings
• Finger Search in Grammar-Compressed Strings
• Finger search in grammar-compressed strings

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Cited In (15)

• Finger search in grammar-compressed strings
• Block trees
• Access, rank, and select in grammar-compressed strings
• Approximate pattern matching in LZ77-compressed texts
• Grammar compressed sequences with rank/select support
• Block graphs in practice
• Document listing on repetitive collections with guaranteed performance
• Random access to grammar-compressed strings
• Random access to grammar-compressed strings and trees
• Random access to high-order entropy compressed text
• Grammar-compressed indexes with logarithmic search time
• Optimal rank and select queries on dictionary-compressed text
• Title not available (Why is that?)
• Balancing run-length straight-line programs
• Random access in persistent strings and segment selection

This page was built for publication: Data structure lower bounds on random access to grammar-compressed strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928577)