Approximation of grammar-based compression via recompression

DOI10.1016/J.TCS.2015.05.027MaRDI QIDQ500975zbMATH OpenOpenAlexFDO

Authors Artur Jeż

Publication date 8 October 2015

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

Full work available at URL https://doi.org/10.1016/j.tcs.2015.05.027

zbMATH Keywords

grammar-based compressionsmallest grammar

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Recommendations

• Approximation of Grammar-Based Compression via Recompression
• String Processing and Information Retrieval
• A fully linear-time approximation algorithm for grammar-based compression
• A \textit{really} simple approximation of smallest grammar
• A really simple approximation of smallest grammar

Cites work

• scientific article; zbMATH DE number 6678923 (Why is no real title available?)
• scientific article; zbMATH DE number 1149447 (Why is no real title available?)
• 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
• Efficient algorithms for Lempel-Ziv encoding
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• On the Evaluation of Powers
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• Probability and Computing
• Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
• The Smallest Grammar Problem
• The complexity of compressed membership problems for finite automata
• The macro model for data compression (extended abstract)

Cited in

(33)

• A space-optimal grammar compression
• Automata, Languages and Programming
• Compressibility of Finite Languages by Grammars
• A fully linear-time approximation algorithm for grammar-based compression
• A \textit{really} simple approximation of smallest grammar
• Approximation of smallest linear tree grammar
• scientific article; zbMATH DE number 2087040 (Why is no real title available?)
• scientific article; zbMATH DE number 2119662 (Why is no real title available?)
• Computing all-vs-all MEMs in grammar-compressed text
• Universal compressed text indexing
• Lyndon factorization of grammar compressed texts revisited
• A fully linear-time approximation algorithm for grammar-based compression
• Comparison of LZ77-type parsings
• Grammar-Based Compression in a Streaming Model
• String Processing and Information Retrieval
• Approximation of smallest linear tree grammar
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings
• Rpair: rescaling RePair with Rsync
• Document listing on repetitive collections with guaranteed performance
• Reducing Simple Grammars: Exponential Against Highly-Polynomial Time in Practice
• Balancing run-length straight-line programs
• Constructing small tree grammars and small circuits for formulas
• Edit distance with block operations
• Balancing straight-line programs for strings and trees
• Quasi-distinct Parsing and Optimal Compression Methods
• An online algorithm for lightweight grammar-based compression
• A self-index on block trees
• Grammar-compressed indexes with logarithmic search time
• A really simple approximation of smallest grammar
• On the compressibility of finite languages and formal proofs
• Approximation of Grammar-Based Compression via Recompression
• A separation between RLSLPs and LZ77

This page was built for publication: Approximation of grammar-based compression via recompression

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