%0 Journal Article
%T An Online Algorithm for Lightweight Grammar-Based Compression
%A Shirou Maruyama
%A Hiroshi Sakamoto
%A Masayuki Takeda
%J Algorithms
%D 2012
%I MDPI AG
%R 10.3390/a5020214
%X Grammar-based compression is a well-studied technique to construct a context-free grammar (CFG) deriving a given text uniquely. In this work, we propose an online algorithm for grammar-based compression. Our algorithm guarantees O(log 2 n)- approximation ratio for the minimum grammar size, where n is an input size, and it runs in input linear time and output linear space. In addition, we propose a practical encoding, which transforms a restricted CFG into a more compact representation. Experimental results by comparison with standard compressors demonstrate that our algorithm is especially effective for highly repetitive text.
%K lossless compression
%K grammar-based compression
%K online algorithm
%K approximation algorithm
%U http://www.mdpi.com/1999-4893/5/2/214