an online algorithm for lightweight grammar-based compression一个在线轻量级基于语法的压缩算法.pdfVIP

Algorithms 2012, 5, 214-235; doi:10.3390/a5020214 OPEN ACCESS algorithms ISSN 1999-4893 /journal/algorithms Article An Online Algorithm for Lightweight Grammar-Based Compression Shirou Maruyama 1, Hiroshi Sakamoto 2 and Masayuki Takeda 1,* 1 Department of Informatics, Kyushu University, 744 Motooka Nishi-ku Fukuoka-shi, Fukuoka, Japan; E-Mail: shiro.maruyama@i.kyushu-u.ac.jp 2 Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, 680-4 Kawazu Iizuka-shi Fukuoka, Japan; E-Mail: hiroshi@ai.kyutech.ac.jp Author to whom correspondence should be addressed; E-Mail: takeda@inf.kyushu-u.ac.jp; Tel./Fax: +81-92-802-3788. Received: 30 January 2012; in revised form: 26 March 2012 / Accepted: 28 March 2012 / Published: 10 April 2012 Abstract: 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 - approximation ratio for the minimum grammar size, where 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. Keywords: lossless compression; grammar-based compression; online algorithm;