A \textit{really} simple approximation of smallest grammar

DOI10.1016/j.tcs.2015.12.032zbMath1333.68156arXiv1403.4445OpenAlexW1532033082MaRDI QIDQ906407

Artur Jeż

Publication date: 21 January 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

compressiongrammar-based compressionSLPLZ77construction of the smallest grammar

Mathematics Subject Classification ID

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

Related Items

Document listing on repetitive collections with guaranteed performance, Approximation of smallest linear tree grammar, Constructing small tree grammars and small circuits for formulas, Grammar-compressed indexes with logarithmic search time, LZRR: LZ77 parsing with right reference, Near-optimal search time in \(\delta \)-optimal space, and vice versa, Near-optimal search time in \(\delta \)-optimal space, Sensitivity of string compressors and repetitiveness measures, On the compressibility of finite languages and formal proofs, Block trees, Universal compressed text indexing, A Self-index on Block Trees, Tree compression using string grammars, Unnamed Item, Balancing straight-line programs for strings and trees

Uses Software

• LZ77

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation of grammar-based compression via recompression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• A fully linear-time approximation algorithm for grammar-based compression
• Faster Fully Compressed Pattern Matching by Recompression
• Algorithmics on SLP-compressed strings: A survey
• A comparison of index-based lempel-Ziv LZ77 factorization algorithms
• Lempel-Ziv Factorization Revisited
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• Linear work suffix array construction
• Fast and Practical Algorithms for Computing All the Runs in a String
• The Smallest Grammar Problem
• Clustering by Compression
• The Similarity Metric
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Efficient algorithms for Lempel-Ziv encoding
• The macro model for data compression (Extended Abstract)