𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Application of Lempel–Ziv factorization to the approximation of grammar-based compression

✍ Scribed by Wojciech Rytter

Book ID
104325708
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
235 KB
Volume
302
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

Analytical approximation to the solution
Analytical approximation to the solutions of Richards' equation with applications to infiltration, ponding, and time compression approximation
✍ J.-Y. Parlange; W.L. Hogarth; D.A. Barry; M.B. Parlange; R. Haverkamp; P.J. Ross 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 163 KB

A recent approach to solve Richards' equation is further improved. This approach brings understanding into the physical processes of in®ltration and ponding. In particular we apply it to analyze the standard hydrologic tool of Time Compression Approximation (TCA). We also suggest that the new approa