Contents

1 How it works?

• We can compress a sequence of symbols if each one is translated by a code-word and, in average, the lengths of the code-words are smaller than the length of the symbols.
• The encoder and the decoder have a probabilistic model $M$ which provides to a variable-length encoder ($C$)/decoder($C^{-1}$) the probability $p\left(s\right)$ of each symbol $s$.
• The most probable symbols are represented by the shorter code-words and viceversa.

2 Bits, data and information

• data != information (data is the representation of the information).
• Lossless data compression uses a shorter representation for information.
• By definition, a bit of data stores a bit of information, if and only if, it represents the occurrence of an equiprobable event (an event that can be true or false with the same probability). In this ideal situation, the representation is fully efficient (no futher compression would be possible).
• By definition, a symbol $s$ with probability $p\left(s\right)$ stores

  $$I\left(s\right)=-{log}_{2}p\left(s\right)$$

  (Eq:symbol_information)

  bits of information.

• So, ideally, the length of a code-word in bits (of data) should match with the number bits of information.

3 Entropy

• The entropy $H\left(S\right)$ measures the amount of information per symbol that a source of information $S$ produces, in average. By definition

  $$H\left(S\right)=\frac{1}{N}\sum _{s=1}^{N}p\left(s\right)\times I\left(s\right)$$

  (1)

  bits-of-information/symbol, where $N$ is the size of the source alphabet (number of different symbols).

4 Compression basics

4.1 Encoding of a symbol

1. While the decoder does not know the symbol:
   1. Assert something about the symbol that allows to the decoder to minimize the uncertainty of finding that symbol. This guess should have true or false with the same probability.
   2. Output a bit of code that says if the last guess is true or false.

4.2 Decoding of a symbol

1. While the symbol is not known without uncertainty:
   1. Make the same guess that the encoder.
   2. Input a bit of code that represents the result of the last guess.

4.2.1 Tip

• This codec is 100% efficient if the guesses are equiprobable.

4.3 Example

• Let’s suppose that we use the Spanish alphabet. Humans know that symbols does not form words in any order, so we can formulate the following VLC (Variable Length Codec):

  In Spanish there are 28 letters. Therefore, to encode, for example, the word preciosa, the first symbol p can be represented by its index inside of the Spahish alphabet with a code-word of 5 bits. In this try, the encoding is not a very efficient, but this we are in first letter … For the second one r we can see (using a Spanish dictionary) that after a p, the following symbols are possible: (1) a, (2) e, (3) i, (4) l, (5) n, (6) o, (7) r, (8) s and (9) u. Therefore, we don’t need 5 bits now, 4 are enough.

• Notice that the compression ratio has been 40/25:1 (preciosa has 8 letters).

5 Probabilistic models

6 Shannon-Fano coding

7 Huffman coding

8 Arithmetic coding

9 Move-to-front transform

10 Context-base text predictive transform

11 Unary coding

12 Golomb-Rice coding

13 gzip

References