Evolution of humancompetitive lossless compressio

Authors: Ahmed Kattan Riccardo Poli

Publish Date: 2011/03/03

Volume: 12, Issue: 4, Pages: 335-364

PDF Link

Abstract

We propose GPzip2 a new approach to lossless data compression based on Genetic Programming GP GP is used to optimally combine wellknown lossless compression algorithms to maximise data compression GPzip2 evolves programs with multiple components One component analyses statistical features extracted by sequentially scanning the data to be compressed and divides the data into blocks These blocks are projected onto a twodimensional Euclidean space via two further evolved program components Kmeans clustering is then applied to group similar data blocks Each cluster is labelled with the optimal compression algorithm for its member blocks After evolution evolved programs can be used to compress unseen data The compression algorithms available to GPzip2 are Arithmetic coding LempelZivWelch Unbounded Prediction by Partial Matching Run Length Encoding and Bzip2 Experimentation shows that the results produced by GPzip2 are humancompetitive being typically superior to wellestablished humandesigned compression algorithms in terms of the compression ratios achieved in heterogeneous archive filesThe authors would like to thank the editorinchief and the anonymous reviewers for their thoughtful constructive and supportive comments These have helped us enormously in improving this paper including uncovering and correcting an important mistake

Keywords: