A \textit{really} simple approximation of smallest grammar
From MaRDI portal
Publication:906407
Abstract: In this paper we present a really simple linear-time algorithm constructing a context-free grammar of size O(g log (N/g)) for the input string, where N is the size of the input string and g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet Sigma of the input string can be identified with numbers from 1,ldots, N^c for some constant c. Algorithms with such an approximation guarantee and running time are known, however all of them were non-trivial and their analyses were involved. The here presented algorithm computes the LZ77 factorisation and transforms it in phases to a grammar. In each phase it maintains an LZ77-like factorisation of the word with at most l factors as well as additional O(l) letters, where l was the size of the original LZ77 factorisation. In one phase in a greedy way (by a left-to-right sweep and a help of the factorisation) we choose a set of pairs of consecutive letters to be replaced with new symbols, i.e. nonterminals of the constructed grammar. We choose at least 2/3 of the letters in the word and there are O(l) many different pairs among them. Hence there are O(log N) phases, each of them introduces O(l) nonterminals to a grammar. A more precise analysis yields a bound O(l log(N/l)). As l leq g, this yields the desired bound O(g log(N/g)).
Recommendations
Cites work
- A comparison of index-based Lempel-Ziv LZ77 factorization algorithms
- A fully linear-time approximation algorithm for grammar-based compression
- Algorithmics on SLP-compressed strings: a survey
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Approximation of grammar-based compression via recompression
- Approximation of smallest linear tree grammar
- Clustering by Compression
- Efficient algorithms for Lempel-Ziv encoding
- Fast and Practical Algorithms for Computing All the Runs in a String
- scientific article; zbMATH DE number 1045405 (Why is no real title available?)
- scientific article; zbMATH DE number 1149447 (Why is no real title available?)
- Lempel-Ziv Factorization Revisited
- Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
- Linear work suffix array construction
- Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
- The macro model for data compression (extended abstract)
- The Similarity Metric
- The Smallest Grammar Problem
Cited in
(22)- On the compressibility of finite languages and formal proofs
- Universal compressed text indexing
- The smallest grammar problem revisited
- Balancing straight-line programs for strings and trees
- Block trees
- Constructing small tree grammars and small circuits for formulas
- Document listing on repetitive collections with guaranteed performance
- Grammar-compressed indexes with logarithmic search time
- LZRR: LZ77 parsing with right reference
- Sensitivity of string compressors and repetitiveness measures
- Approximation of smallest linear tree grammar
- REDUCING SIMPLE GRAMMARS: EXPONENTIAL AGAINST HIGHLY-POLYNOMIAL TIME IN PRACTICE
- The Smallest Grammar Problem
- Approximation of grammar-based compression via recompression
- Conversion from RLBWT to LZ77
- A self-index on block trees
- A really simple approximation of smallest grammar
- Near-optimal search time in -optimal space, and vice versa
- Near-optimal search time in -optimal space
- Rpair: rescaling RePair with Rsync
- Construction of sparse suffix trees and LCE indexes in optimal time and space
- Counting on general run-length grammars
This page was built for publication: A \textit{really} simple approximation of smallest grammar
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906407)
