An Online Algorithm for Lightweight Grammar-Based Compression

Algorithms

Shirou Maruyama¹  Hiroshi Sakamoto¹ 

[1] ¹Department of Informatics, Kyushu University, 744 Motooka Nishi-ku Fukuoka-shi, Fukuoka, Japan ²Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology,680-4 Kawazu Iizuka-shi Fukuoka, Japan

关键词: lossless compression;    grammar-based compression;    online algorithm;    approximation algorithm;   

DOI  :  10.3390/a5020214

来源: mdpi

【 摘 要 】

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² 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.

【 授权许可】

CC BY   
This is an open access article distributed under the Creative Commons Attribution License (CC BY) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.