ExCom Library Compression Methods

• Statistical methods
  • Shannon-Fano coding
  • Static Huffman coding
  • Adaptive Huffman coding – FGK
  • Adaptive Huffman coding – Vitter
• Dictionary methods
  • LZ77
  • LZ78
  • LZSS
  • LZW
• Context methods
  • ACB
  • DCA
  • PPM
• Other methods

Statistical methods

Shannon-Fano Coding

• Authors: Claude Elwood Shannon, Robert Fano
• Implementation by: Jakub Řezníček, 2010
• Part of: Cabarc, WinZip
• References:
  • C. E. Shannon and W. Weaver, The Mathematical Theory of Communication. Urbana and Chicago: University of Illinois Press, 1949.

Static Huffman Coding

• Author: David Albert Huffman
• Implementation by: Jakub Řezníček, 2010; Michal Valach, 2011 (in order to overcome the speed issues)
• References:
  • D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the Institute of Radio Engineers, vol. 40, pp. 1098-1101, Sept. 1952.

Adaptive Huffman Coding – FGK

• Authors: Newton Faller, Robert Gray Gallager, and Donald Ervin Knuth
• Implementation: Jakub Řezníček, 2010; Michal Valach, 2011 (in order to overcome the speed issues)
• Part of: ARJ, JAR, WinACE, WinRAR, WinZip
• References:
  • N. Faller, An adaptive system for data compression, in In Record of the 7th .Asilomar Conference on Circuits, Systems, and Computers, pp. 593-597, 1973.
  • R. Gallager, Variations on a theme by Huffman, Information Theory, IEEE Transactions on, vol. 24, pp. 668-674, Nov. 1978.
  • D. E. Knuth, Dynamic Huffman coding, J. Algorithms, vol. 6, no. 2, pp. 163-180, 1985.

Adaptive Huffman Coding – Vitter

• Authors: Newton Faller, Robert Gray Gallager, and Donald Ervin Knuth
• Implementation: to be implemented
• Part of: ARJ, JAR, WinACE, WinRAR, WinZip
• References:
  • J. S. Vitter, Design and analysis of dynamic Huffman codes, J. ACM, vol. 34, no. 4, pp. 825-845, 1987.

Dictionary methods

LZ77

• Authors: Abraham Lempel, Jacob Ziv
• Implementation by: Jakub Řezníček, 2010
• Part of: 7-Zip, GZip, LZ, PKZIP, WinACE, WinRAR
• References:
  • J. Ziv and A. Lempel, A universal algorithm for sequential data compression, IEEE Transactions on Information Theory, vol. 23, pp. 337-343, 1977.

LZ78

• Authors: Abraham Lempel, Jacob Ziv
• Implementation by: Jakub Řezníček, 2010
• References:
  • J. Ziv and A. Lempel, Compression of individual sequences via variable-rate coding, IEEE Transactions on Information Theory, vol. 24, no. 5, pp. 530-536, 1978.

LZSS

• Authors: James Storer, Thomas Szymanski
• Implementation by: Jakub Řezníček, 2010
• Part of: ARJ, JAR
• References:
  • J. A. Storer and T. G. Szymanski, Data compression via textual substitution, J. ACM, vol. 29, no. 4, pp. 928-951, 1982.

LZW

• Authors: Abraham Lempel, Jacob Ziv, and Terry Welch
• Implementation by: Jakub Řezníček, 2010
• Part of: WinZip
• References:
  • T. A. Welch, A Technique for High-Performance Data Compression, Computer, vol. 17, no. 6, pp. 8-19, 1984.
  • J. Nieminen, An efficient LZW implementation. http://warp.povusers.org/EfficientLZW/, April 2011.

LZMW

LZAP

LZY

Context methods

ACB (Associative Coder of Buyanovsky)

• Author: George Buyanovsky
• Implementation by: Filip Šimek, 2009; Michal Valach, 2011
• Part of: ACB
• References:
  • G. Buyanovsky, Associative Coding, Monitor, pp. 10-22, 1994.

DCA (Data Compression Using Antidictionaries)

• Authors: Maxime Crochemore, Filippo Mignosi, Antonio Restivo, and Sergio Salemi
• Implementation by: Martin Fiala, 2007; Filip Šimek, 2009 (integration into ExCom)
• References:
  • M. Crochemore, F. Mignosi, A. Restivo, and S. Salemi, Data Compression Using Antidictionaries, in Proceedings of the IEEE, Lossless Data Compression, pp. 1756-1768, 2000.
  • Fiala, M., Holub, J.: DCA using Suffix Arrays. In J. A. Storer, M. W. Marcellin (eds.): Proceedings of Data Compression Conference 2008, IEEE Computer Society Press, p. 516, 2008.

PPM (Prediction by Partial Matching)

• Authors: John Cleary, Ian Witten
• Implementation by: Dmitry Shkarin, 2009; Igor Pavlov, 2009; Filip Šimek, 2009 (integration into ExCom)
• Part of: 7-Zip, FreeARC, WinRAR, WinZip
• References:
  • J. Cleary and I. Witten, Data Compression Using Adaptive Coding and Partial String Matching, IEEE Transactions on Communications, vol. 32, pp. 396-402, Apr. 1984.
  • A. Moffat, Implementing the PPM data compression scheme, IEEE Trans. Comms., vol. 38, pp. 1917-1921, Nov. 1990.

Other methods

BurrowsWheeler Transformation

Move To Front

Variable length integer coding