Author: Arkadi Kagan arkadi_kagan@hotmail.com Document: Entropy Compression Methods.

The goal of this work is to provide programmer with ability to build effective compression algorithm without doing complex research on subject of Entropy Coding Methods. The scope of this document is Universal Entropy Coding Methods for general purposes and is not including specialized preprocessing methods like XML parsing etc. The Lossy Compressions are out of scope too.

Here is the Content of this document:

• Arithmetic Coding.
• Huffman Coding.
• Lempel-Ziv Compression Methods.
• Auxilary preprocessing methods.
  • BWT - Burrows-Wheeler Transform.
  • MTF - Move To Front.
  • RLE - Run Length Encoding.
    • RLE0 - Zero Run Length Encoding.
  • Universal Integer Coding.
    • Elias Universal Coding of integers.
    • Fibonacci Universal Coding of integers.
  • PPM - Prediction by Partial Matching.

Things to do:

I did an attempt to gather the main Entropy Compression Algorithms of practical interest. However, the more I know, far seems the goal. Since English is not my native language, grammatic error corrections are wellcome.

Known problems:

1. Algorithms for large alphabets are toughed too briefly.
2. Fibonacci Coding must be checked. The basic idea is clear, but I am not sure if my Decoding will restore the Encoded source integer right.
3. Reliable classification of RLE-like compressions is missing.
4. The limitation of Maximal Code Length with "The Warm-up Algorithm" is not described.
5. Not all algorithms in this document I tried personally. Therefore misses are possible.