We present almost linear time (O(n·log |Σ|) time) 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 · logn). Computing exact size of the minimal grammar-based compression is known to be NP-complete. The basic novel tool is the AVL-grammar.
Keywords LZ-compression - minimal grammar - AVL-tree - AVL-grammar