Grammar-Based Compression in a Streaming Model

DOI10.1007/978-3-642-13089-2_23MaRDI QIDQ3564868zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Paweł Gawrychowski

Publication date 26 May 2010

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

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

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)

Abstract: We show that, given a string $s$ of length $n$, with constant memory and logarithmic passes over a constant number of streams we can build a context-free grammar that generates $s$ and only $s$ and whose size is within an $Ohmin(glogg,sqrtnlogg)$-factor of the minimum $g$. This stands in contrast to our previous result that, with polylogarithmic memory and polylogarithmic passes over a single stream, we cannot build such a grammar whose size is within any polynomial of $g$.

Recommendations

• Approximation of Grammar-Based Compression via Recompression
• Approximation of grammar-based compression via recompression
• scientific article; zbMATH DE number 2119662
• A space-optimal grammar compression
• A fully linear-time approximation algorithm for grammar-based compression
• A fully linear-time approximation algorithm for grammar-based compression
• Grammar-Based Tree Compression
• String Processing and Information Retrieval
• An online algorithm for lightweight grammar-based compression
• Self-indexed grammar-based compression

Cited in

(3)

• Constructing small tree grammars and small circuits for formulas
• Approximation of Grammar-Based Compression via Recompression
• Tight bounds for compressing substring samples

This page was built for publication: Grammar-Based Compression in a Streaming Model

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