We introduce the first grammar-compressed representation of a sequence that supports searches in time that depends only logarithmically on the size of the grammar. Given a text @math that is represented by a (context-free) grammar of @math (terminal and nonterminal) symbols and size @math (measured as the sum of the lengths of the right hands of the rules), a basic grammar-based representation of @math takes @math bits of space. Our representation requires @math bits of space, for any @math . It can find the positions of the @math occurrences of a pattern of length @math in @math in @math time, and extract any substring of length @math of @math in time @math , where @math is the height of the grammar tree.
Finding the smallest grammar @math that represents a given text @math is NP-complete @cite_26 @cite_8 . Moreover, the smallest grammar is never smaller than an LZ77 parse @cite_14 of @math . A simple method to achieve an @math -approximation to the smallest grammar size is to parse @math using LZ77 and then to convert it into a grammar @cite_26 . A more sophisticated approximation achieves ratio @math , where @math is the size of @math .
@cite_14 @cite_26 @cite_8
2107745473 1973608346 2113004376
A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source. We introduce new type of context-free grammars, AVL-grammars, and show their applicability to grammar-based compression. Using this type of grammars we present O(n log |Σ|) time and O(log n)-ratio approximation of minimal grammar-based compression of a given string of length n over an alphabet Σ and O(k log n) time transformation of LZ77 encoding of size k into a grammar-based encoding of size O(k log n). A preliminary version of this paper has been presented in Rytter (Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 2373, Springer, Berlin, June 2000, pp. 20-31), independently of (STOC, 2002), where grammar-based approximation has been attacked with different construction and a more complicated type of grammars (α-balanced grammars for α ≤ 1 - ½ √2). The AVL-grammar is a very natural and simple tool for grammar based compression, it is a straightforward extension of the classical AVL-tree. This paper addresses the smallest grammar problem: What is the smallest context-free grammar that generates exactly one given string spl sigma ? This is a natural question about a fundamental object connected to many fields such as data compression, Kolmogorov complexity, pattern identification, and addition chains. Due to the problem's inherent complexity, our objective is to find an approximation algorithm which finds a small grammar for the input string. We focus attention on the approximation ratio of the algorithm (and implicitly, the worst case behavior) to establish provable performance guarantees and to address shortcomings in the classical measure of redundancy in the literature. Our first results are concern the hardness of approximating the smallest grammar problem. Most notably, we show that every efficient algorithm for the smallest grammar problem has approximation ratio at least 8569 8568 unless P=NP. We then bound approximation ratios for several of the best known grammar-based compression algorithms, including LZ78, B ISECTION, SEQUENTIAL, LONGEST MATCH, GREEDY, and RE-PAIR. Among these, the best upper bound we show is O(n sup 1 2 ). We finish by presenting two novel algorithms with exponentially better ratios of O(log sup 3 n) and O(log(n m sup * )), where m sup * is the size of the smallest grammar for that input. The latter algorithm highlights a connection between grammar-based compression and LZ77.