research-article

Evolutionary lossless compression with GP-ZIP*

Authors:

Riccardo PoliAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1211 - 1218

https://doi.org/10.1145/1389095.1389333

Published: 12 July 2008 Publication History

Abstract

In recent research we proposed GP-zip, a system which uses evolution to find optimal ways to combine standard compression algorithms for the purpose of maximally losslessly compressing files and archives. The system divides files into blocks of predefined length. It then uses a linear, fixed-length representation where each primitive indicates what compression algorithm to use for a specific data block. GP-zip worked well with heterogonous data sets, providing significant improvements in compression ratio compared to some of the best standard compression algorithms. In this paper we propose a substantial improvement, called GP-zip*, which uses a new representation and intelligent crossover and mutation operators such that blocks of different sizes can be evolved. Like GP-zip, GP-zip* finds what the best compression technique to use for each block is. The compression algorithms available in the primitive set of GP-zip* are: Arithmetic coding (AC), Lempel-Ziv-Welch (LZW), Unbounded Prediction by Partial Matching (PPMD), Run Length Encoding (RLE), and Boolean Minimization. In addition, two transformation techniques are available: the Burrows-Wheeler Transformation (BWT) and Move to Front (MTF). Results show that GP-zip* provides improvements in compression ratio ranging from a fraction to several tens of percent over its predecessor.

References

[1]

I. M. Pu, Fundamental Data Compression, HB, ISBN-13: 978-0-7506-6310-62006. Chapter 1.]]

Digital Library

[2]

Ahmad Kattan and Riccardo Poli, Evolutionary Lossless Compression with GP-ZIP, Proceedings of the IEEE World Congress on Computational Intelligence, IEEE 2008.]]

Digital Library

[3]

William H. Hsu and Emy E. Zwarico, Automatic Synthesis of Compression Techniques for Heterogeneous Files SOFTPREX: Software-Practice and Experience, Vol. 25, 1995.]]

Digital Library

[4]

John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.]]

Digital Library

[5]

Peter Nordin and Wolfgang Banzhaf. Programmatic compression of images and sound. In John R. Koza, David E. Goldberg, David B. Fogel, and Rick L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 345--350, Stanford University, CA, USA, 28-31 July 1996. MIT Press.]]

Digital Library

[6]

Evelyne Lutton, Jacques Levy-Vehel, Guillaume Cretin, Philippe Glevarec, and Cidric Roll. Mixed IFS: Resolution of the inverse problem using genetic programming. Complex Systems, 9:375--398, 1995.]]

[7]

Evelyne Lutton, Jacques Levy-Vehel, Guillaume Cretin, Philippe Glevarec, and Cidric Roll. Mixed IFS: Resolution of the inverse problem using genetic programming. Research Report No 2631, Inria, 1995.]]

[8]

Anargyros Sarafopoulos. Automatic generation of affine IFS and strongly typed genetic programming. In Riccardo Poli, Peter Nordin, William B. Langdon, and Terence C. Fogarty, editors, Genetic Programming, Proceedings of EuroGP'99, volume 1598 of LNCS, pages 149--160, Goteborg, Sweden, 26-27 May 1999. Springer-Verlag.]]

Digital Library

[9]

Andreas Klappenecker and Frank U. May. Evolving better wavelet compression schemes. In Andrew F. Laine, Michael A. Unser, and Mladen V. Wickerhauser, editors, Wavelet Applications in Signal and Image Processing III, volume 2569, San Diego, CA, USA, 9-14 July 1995. SPIE.]]

[10]

Alex Fukunaga and Andre Stechert. Evolving nonlinear predictive models for lossless image compression with genetic programming. In John R. Koza, Wolfgang Banzhaf, Kumar Chellapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Garzon, David E. Goldberg, Hitoshi Iba, and Rick Riolo, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 95--102, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.]]

[11]

Johan Parent and Ann Nowe. Evolving compression preprocessors with genetic programming. In W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska, editors, GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pages 861--867, New York, 9-13 July 2002. Morgan Kaufmann Publishers.]]

[12]

Bell, R.A.a.T.C. A corpus for the evaluation of lossless compression algorithms. in IEEE Data Compression Conference (DCC'97). March 25 1997. Los Alamitos, California.: IEEE Computer Society.]]

Digital Library

[13]

Thomas Krantz, Oscar Lindberg, Gunnar Thorburn, and Peter Nordin. Programmatic compression of natural video. In Erick Cantú-Paz, editor, Late Breaking Papers at the Genetic and Evolutionary Computation Conference (GECCO-2002), pages 301--307, New York, NY, July 2002. AAAI.]]

[14]

Jingsong He, Xufa Wang, Min Zhang, Jiying Wang, and Qiansheng Fang. New research on scalability of lossless image compression by GP engine. In Jason Lohn, David Gwaltney, Gregory Hornby, Ricardo Zebulum, Didier Keymeulen, and Adrian Stoica, editors, Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware, pages 160--164, Washington, DC, USA, 29 June-1 July 2005. IEEE Press.]]

Digital Library

[15]

I. Witten and R. Neal and J. Cleary, Arithmetic coding for data compression, Communications of the ACM, Vol. 30, pp. 520--541, 1987.]]

Digital Library

[16]

J. Ziv and A. Lempel, Compression of Individual Sequences via Variable--Rate Coding, IEEE Transactions on Information Theory, September 1978.]]

[17]

J. G. Cleary and W. J. Teahan and Ian H. Witten, Unbounded Length Contexts for PPM, Data Compression Conference, pp. 52--61, 1995.]]

Digital Library

[18]

S. W. Golomb, Run-length encodings, IEEE Trans. Inform. Theory, Vol. IT-12, pp. 399--401, 1966.]]

[19]

A. Kattan, Universal Lossless Data Compression with built in Encryption. Master Thesis, University of Essex 2006.]]

[20]

M. Burrows and D. J. Wheeler, A block-sorting lossless data compression algorithm, SRC, Number 124, 1994.]]

[21]

Z. Arnavut, Move-to-Front and Inversion Coding, DCC: Data Compression Conference, IEEE Computer Society TCC, 2000.]]

Digital Library

[22]

ACT Archive Compression Test {cited 2 December 2007} Available from: http://compression.ca/act/act-win.html]]

Cited By

AŞŞIK MORAL M(2022)Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesiGazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi10.17341/gazimmfd.88274538:2(771-780)Online publication date: 7-Oct-2022
https://doi.org/10.17341/gazimmfd.882745
Viveros-Jiménez FLeón-Borges JCruz-Cortés N(2012)A simple adaptive algorithm for numerical optimizationProceedings of the 11th Mexican international conference on Advances in Computational Intelligence - Volume Part II10.1007/978-3-642-37798-3_11(115-126)Online publication date: 27-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-37798-3_11
Ullah FYahya K(2012)A New Data Compression Technique Using an Evolutionary Programming ApproachEmerging Trends and Applications in Information Communication Technologies10.1007/978-3-642-28962-0_49(524-531)Online publication date: 2012
https://doi.org/10.1007/978-3-642-28962-0_49
Show More Cited By

Recommendations

RETRACTED ARTICLE: Improved image compression using effective lossless compression technique
Abstract
The data or image transmission plays a very important role in current days. In general image can be transmitted in terms of data. The basic image can be converted or encoded into bits or chunks. This data can be transmitted in efficient form. ...
Lossless Data Compression: Data compression, Algorithm, Lossy compression, Bit rate, ZIP (file format), Unix, Gzip, Portable Network Graphics, Graphics Interchange Format, Tagged Image File Format
BWT-based Data Preprocessing for LZW
CMSP '11: Proceedings of the 2011 International Conference on Multimedia and Signal Processing - Volume 01

In this paper we propose a BWT-based LZW algorithm for reducing the compressed size and the compression time. BWT and MTF can expose potential redundancies in a given input and then significantly improve the compression ratio ofLZW. In order to avoid ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
445
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

AŞŞIK MORAL M(2022)Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesiGazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi10.17341/gazimmfd.88274538:2(771-780)Online publication date: 7-Oct-2022
https://doi.org/10.17341/gazimmfd.882745
Viveros-Jiménez FLeón-Borges JCruz-Cortés N(2012)A simple adaptive algorithm for numerical optimizationProceedings of the 11th Mexican international conference on Advances in Computational Intelligence - Volume Part II10.1007/978-3-642-37798-3_11(115-126)Online publication date: 27-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-37798-3_11
Ullah FYahya K(2012)A New Data Compression Technique Using an Evolutionary Programming ApproachEmerging Trends and Applications in Information Communication Technologies10.1007/978-3-642-28962-0_49(524-531)Online publication date: 2012
https://doi.org/10.1007/978-3-642-28962-0_49
Kattan APoli R(2011)Evolution of human-competitive lossless compression algorithms with GP-zip2Genetic Programming and Evolvable Machines10.1007/s10710-011-9133-612:4(335-364)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1007/s10710-011-9133-6
Kattan A(2010)Universal intelligent data compression systems: A review2010 2nd Computer Science and Electronic Engineering Conference (CEEC)10.1109/CEEC.2010.5606482Online publication date: Sep-2010
https://doi.org/10.1109/CEEC.2010.5606482
Kattan APoli R(2010)Evolutionary synthesis of lossless compression algorithms with GP-zip3IEEE Congress on Evolutionary Computation10.1109/CEC.2010.5585956(1-8)Online publication date: Jul-2010
https://doi.org/10.1109/CEC.2010.5585956
Kattan APoli R(2010)Genetic-Programming Based Prediction of Data Compression SavingArtifical Evolution10.1007/978-3-642-14156-0_16(182-193)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14156-0_16
Kattan APoli R(2009)Genetic-programming based prediction of data compression savingProceedings of the 9th international conference on Artificial evolution10.5555/1883723.1883746(182-193)Online publication date: 26-Oct-2009
https://dl.acm.org/doi/10.5555/1883723.1883746

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten