Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is$\boldsymbol {b}$, the least number of phrases of a general bidirectional parse of a text, where phrases can be copied from anywhere else in the text. Since computing$\boldsymbol {b}$is NP-complete, a popular gold standard is$\boldsymbol {z}$, the number of phrases in the Lempel-Ziv parse of the text, which is computed in linear time and yields the least number of phrases when those can be copied only from the left. Almost nothing has been known for decades about the approximation ratio of$\boldsymbol {z}$with respect to$\boldsymbol {b}$. In this paper we prove that$z=O(b\log (n/b))$, where$n$is the text length. We also show that the bound is tight as a function of$n$, by exhibiting a text family where$z = \Omega (b\log n)$. Our upper bound is obtained by building a run-length context-free grammar based on a locally consistent parsing of the text. Our lower bound is obtained by relating$\boldsymbol {b}$with$r$, the number of equal-letter runs in the Burrows-Wheeler transform of the text. We continue by observing that Lempel-Ziv is just one particular case ofgreedyparses–meaning that it obtains the smallest parse by scanning the text and maximizing the phrase length at each step–, and oforderedparses–meaning that phrases are larger than their sources under some order. As a new example of ordered greedy parses, we introducelexicographicalparses, where phrases can only be copied from lexicographically smaller text locations. We prove that the size$v$of the optimal lexicographical parse is also obtained greedily in$O(n)$time, that$v=O(b\log (n/b))$, and that there exists a text family where$v = \Omega (b\log n)$. Interestingly, we also show that$v = O(r)$because$r$also induces a lexicographical parse, whereas$z = \Omega (r\log n)$holds on some text families. We obtain some results on parsing complexity and size that hold on some general classes of greedy ordered parses. In our way, we also prove other relevant bounds between compressibility measures, especially with those related to smallest grammars of various types generating (only) the text.

We present the first solution to finding τ -majorities on tree paths. Given a tree of n nodes, each with a label from [ 1 . . σ ] , and a fixed threshold 0 < τ < 1 , such a query gives two nodes u and v and asks for all the labels that appear more than τ ⋅ | P u v | times in the path P u v from u to v , where | P u v | denotes the number of nodes in P u v . Note that the answer to any query is of size up to 1 / τ . On a w -bit RAM, we obtain a linear-space data structure with O ( ( 1 / τ ) lg ⁡ lg w ⁡ σ ) query time, which is worst-case optimal for polylogarithmic-sized alphabets. We also describe two succinct-space solutions with query time O ( ( 1 / τ ) lg ⁎ ⁡ n lg ⁡ lg w ⁡ σ ) . One uses 2 n H + 4 n + o ( n ) ( H + 1 ) bits, where H ≤ lg ⁡ σ is the entropy of the label distribution; the other uses n H + O ( n ) + o ( n H ) bits. By using just o ( n lg ⁡ σ ) extra bits, our succinct structures allow τ to be specified at query time. We obtain analogous results to find a τ -minority, that is, an element that appears between 1 and τ ⋅ | P u v | times in P u v .

Irreducible grammars are a class of context-free grammars with well-known representatives, such as Repair (with a few tweaks), Longest Match, Greedy, and Sequential. We show that a grammar-based compression method described by Kieffer and Yang (2000) is upper bounded by the high-order empirical entropy of the string when the underlying grammar is irreducible. Specifically, given a string S over an alphabet of size σ, we prove that if the underlying grammar is irreducible, then the length of the binary code output by this grammar-based compression method is bounded by |S|Hk(S) + o(|S|log σ) for any k ∈ 0(logσ|S|), where Hk(S) is the k-order empirical entropy of S. This is the first bound encompassing the whole class of irreducible grammars in terms of the high-order empirical entropy, with coefficient 1.

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size n and number of queries q fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.