Contents

1 What is entropy coding?

Entropy Coding (EC) [4] encompasses a whole series of coding techniques that exploit the statistical redundancy in data with the ultimate goal of finding a more compact representation, but without lossing information. EC is related to the definition of entropy in the context of the Information Theory [6]. In this area, the entropy quantifies the average amount of information represented by a data set, so that the higher the entropy, the better the efficiency of such representation (data).

2 Why EC?

All data (text, audio, image, video, etc.) compression techniques rely on EC to achieve an effective reduction of bits. For example, JPEG uses a combination of Huffman Coding (see below) and Run-Length Encoding to represent the quantized DCT coefficients.

3 A classification of entropy encoders

In general, data are sequences of symbols. There are basically two types of entropy encoders depending on how the symbols are processed:

1. Symbol encoders: Those that process the sequence symbol by symbol. Examples of this type of algorithms are Huffman Coding [5] and Arithmetic Coding [2]. These encoders are also called “probabilistic encoders” because the number of bits of code assigned to a symbol \(s\) depends on the probability of the symbol \(p(s)\).
2. String encoders: Those that process the sequence by blocks of symbols (strings). Examples are Run-Length Encoding (RLE) [9] and all the dictionary-based text compressors, such as LZW [7].

Those of the first type generally achieve more compact representations, but are computationally more expensive. The algorithms of the second class are usually faster, but slightly worse in compression ratio.

4 Huffman Coding (HC)

A Huffman code [5, 1] is a prefix code that, for each code-word, allows to “navigate” through the so called Huffman tree from the trunk to one of its leaves, without uncertainty. The Huffman tree satisfies that \begin {equation} l(c(s)) = \lceil I(s)\rceil , \label {eq:huffman_performance} \end {equation} where \(l(c(s))\) is the length of the (Huffman) code-word assigned to the symbol \(s\) and \(I(s)\) is the amount of information represented by \(s\), measured bits of information [6].

Notice that the minimum number of bits that can be used for representing a symbol (using Huffman) is 1, which can be a problem when the length of the alphabet is small.¹ Another drawback of Huffman Coding is that the Huffman tree must be updated each time the probabilistic model is updated, action very frequent when using adaptive models.

Resources

1. Compression algorithms in Python.
2. Huffman Coding Implementation in Python with Examples.
3. Huffman Coding.
4. Prediction by Partial Matching.
5. Lossless JPEG.
6. Context-Adaptive Variable-Length Coding.

5 Arithmetic Coding (AC)

In an arithmetic codec [2, 1], the number of bits of data that are used for representing symbols match exactly the number of bits of information provided by the symbols, i.e, \begin {equation} l(c(s)) = I(s). \end {equation}

This also means that, even if the size of the alphabet is small, the coding performance of an arithmetic code is optimal, although this optimality is only fully satisfied if the number of symbols to encode is infinite. Notice also that, if the alphabet is large, the encoding performance difference between a Huffman code (or any other prefix code) and an arithmetic code, vanishes.

Resources

1. Arithmetic Coding (notebook).
2. Reference Arithmetic Coding/Reference Arithmetic Coding.
3. Compression Algorithms in Python.
4. Prediction by Partial Matching.
5. Lossless JPEG.
6. Context-Adaptive Binary Arithmetic Coding.

6 zlib

zlib is based on DEFLATE, which in turn is based on LZ77 [7, 1] and Huffman coding. Therefore, zlib exploits the repetition of symbols and also, the the 0-order statistical redundancy². One of the main advantages of zlib is that is quite fast compared to symbol encoders such as HC and AC.

Nowadays, zlib is a keystone in data manipulation because it is the basic library used in such important applications as Zip and Gzip.

Resources

1. zlib — Compression compatible with gzip.
2. Lossless JPEG.

7 Portable Network Graphics (PNG)

PNG [8] (pronounced “ping”) is a dictionary-based (string encoding) lossless image compression format used for representing digital images and videos [3] in III... format [?]. The entropy encoder of PNG is based on HC and LZSS, and a pixel predictor that removes the spatial redundancy.

We must bear in mind that as such an image compressor, we can only interact with PNG at the image level, that is, it only accepts images (in shades of gray or in color, with the possibility of an alpha channel), and only returns images.

8 To-Do

Please, select one of the following tasks to develop:

1. Modify VCF to allow the use of Huffman coding as an entropy codec in the compression pipeline. A context-based probabilistic model should be used to minimize the probabilities of the symbols. See [10]. Complexity 3.
2. Modify VCF to allow the use of arithmetic coding as a entropy codec in the compression pipeline. Again, a context-based probabilistic model should be used, and in this case, to speed up the decoding of the symbols and to increase the compression ratio, it is convenient that they follow a Laplace statistical distribution that can be easily obtained using a spatial predictor. See [10]. Complexity 3.

9 References