@article{RYTTER2003211,
    Abstract = {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(nlog|Σ|) time and O(logn)-ratio approximation of minimal grammar-based compression of a given string of length n over an alphabet Σ and O(klogn) time transformation of LZ77 encoding of size k into a grammar-based encoding of size O(klogn). A preliminary version of this paper has been presented in Rytter (Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 2373, Springer, Berlin, June 2000, pp. 20--31), independently of Charikar et al. (STOC, 2002), where grammar-based approximation has been attacked with different construction and a more complicated type of grammars ({$\alpha$}-balanced grammars for {$\alpha$}⩽1−122). The AVL-grammar is a very natural and simple tool for grammar based compression, it is a straightforward extension of the classical AVL-tree.},
    Author = {Rytter, Wojciech},
    File = {Application of Lempel–Ziv factorization to the approximation of grammar-based compression - 1-s2.0-S0304397502007776-main.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {LZ-compression, Minimal grammar, -tree, -grammar},
    Number = {1},
    Pages = {211-222},
    Title = {Application of Lempel--Ziv factorization to the approximation of grammar-based compression},
    URL = {https://www.sciencedirect.com/science/article/pii/S0304397502007776},
    Volume = {302},
    Year = {2003},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397502007776},
    bdsk-url-2 = {https://doi.org/10.1016/S0304-3975(02)00777-6},
    date-added = {2023-08-09 13:59:49 +0200},
    date-modified = {2023-08-09 13:59:49 +0200},
    doi = {10.1016/S0304-3975(02)00777-6}
}

@article{RYTTER2003211, Abstract = {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(nlog|Σ|) time and O(logn)-ratio approximation of minimal grammar-based compression of a given string of length n over an alphabet Σ and O(klogn) time transformation of LZ77 encoding of size k into a grammar-based encoding of size O(klogn). A preliminary version of this paper has been presented in Rytter (Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 2373, Springer, Berlin, June 2000, pp. 20--31), independently of Charikar et al. (STOC, 2002), where grammar-based approximation has been attacked with different construction and a more complicated type of grammars ({$\alpha$}-balanced grammars for {$\alpha$}⩽1−122). The AVL-grammar is a very natural and simple tool for grammar based compression, it is a straightforward extension of the classical AVL-tree.}, Author = {Rytter, Wojciech}, File = {Application of Lempel–Ziv factorization to the approximation of grammar-based compression - 1-s2.0-S0304397502007776-main.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {LZ-compression, Minimal grammar, -tree, -grammar}, Number = {1}, Pages = {211-222}, Title = {Application of Lempel--Ziv factorization to the approximation of grammar-based compression}, URL = {https://www.sciencedirect.com/science/article/pii/S0304397502007776}, Volume = {302}, Year = {2003}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397502007776}, bdsk-url-2 = {https://doi.org/10.1016/S0304-3975(02)00777-6}, date-added = {2023-08-09 13:59:49 +0200}, date-modified = {2023-08-09 13:59:49 +0200}, doi = {10.1016/S0304-3975(02)00777-6} }