Probabilistic models

Vicente González Ruiz

January 7, 2020

1 Funtionality
2 Static models
3 Adaptive models
4 Encoding
5 Decoding
6 Initially empty models
7 Encoder
8 Decoder
9 Models with memory
10 Encoder
11 Decoder
References

1 Funtionality

Compute the probabilities of the symbols (see Symbol Encoding).
Both, the encoder and the decoder must be syncronized.

2 Static models

Static models are the simplest ones because they suppose that the probabilities of the symbols remain constant through the compression/decompression.
In this case, variable-length code-words can be precomputed.
Static models are very common in codecs such as JPEG and MPEG (audio and video).

Let’s go the the lab!

Clone https://github.com/vicente-gonzalez-ruiz/basic-compression-tools and run make huff_s0.
Encode the images of the table below that can be found at The Test Image Corpus using the codec.
    Codec | lena boats pepers zelda
----------+------------------------
      RLE | ....  ....   ....  ....
  BWT+RLE | ....  ....   ....  ....
     LZSS | ....  ....   ....  ....
      LZW | ....  ....   ....  ....
  huff_s0 | ....  ....   ....  ....

Continue ﬁlling the table ...
Check that the huff_s0 codec is lossless.

3 Adaptive models

The probabilities of the symbols are computed while they arrive to the compressor.
In general, the compression ratios that adaptive models reach are better than static model’s ones, because the probabilities of the symbols are localy computed (think of the sequence ‘aaaaaaaaaaaaaabbbbbbbbbbbbbbb‘).

4 Encoding

Asign the same probability to all the symbols of the source alphabet.
While the input if not exhausted:
1. Encode the next symbol.
2. Update (increase) its probability.

5 Decoding

Identical to the step 1 of the encoder.
While the input is not exhausted:
1. Decode the next symbol.
2. Identical to the step 2.b of the encoder.

Let’s go the the lab!

Continue ﬁlling the table:
    Codec | lena boats pepers zelda Average
----------+--------------------------------
        : |    :     :      :     :       :
  huff_s0 | ....  ....   ....  ....    ....
  huff_a0 | ....  ....   ....  ....    ....
arith_a0 | ....  ....   ....  ....    ....
Remember to check that both codecs are lossless.

6 Initially empty models

The smaller the number of symbols used by the model, the higher the probabilities, and therefore, the better the compression ratios.
An initially empty model only stores the $ESC$ (cape) symbol (a symbol that it is used by the encoder only when a new symbol is found and therefore, it must be part of the encoder’s and decoder’s models).
We assume that arithmetic coding is used and therefore, when we input or output $c (s)$ , we are transmitting $I (s)$ bits of code.

7 Encoder

Set the probability of the $ESC$ symbol to $1.0$ (and the probability of the rest of the symbols to $0.0$ ).
While the input is not exhausted:
1. $s \leftarrow$ next symbol.
2. If s has been found before, then:
  1. Output $c (s)$ (encode).
3. Else:
  1. Output $c (ESC)$ .
  2. Output a raw symbol $s$ .
4. Update $p (s)$ .

8 Decoder

Identical to the step 1 of the encoder.
While the input is not exhausted:
1. $c (s) \leftarrow$ next code-word.
2. Decode $s$ .
3. If s = ESC, then:
  1. Input a raw symbol $s$ .
4. Update $p (s)$ .
5. Output $s$ .

Let’s go the the lab!

make arith-n-c and make arith-n-d.
         Codec | lena boats pepers zelda Average
---------------+--------------------------------
             : |    :     :      :     :       :
arith-n-c -o 0 | ....  ....   ....  ....    .... #1
BWT | ahuff_0 | ....  ....   ....  ....    ....
      bzip2 -9 | ....  ....   ....  ....    .... #2
       gzip -9 | ....  ....   ....  ....    .... #3

#1 -> Similar to arith_a0 but using an initially
      empty model.

#2 -> Similar to BWT | ahuff_0

#3 -> Similar to LZ77 + ahuff_0
Check the reversibility.

9 Models with memory

In most cases, the probability of a symbol depends on its neighborhood (context).
The higher the memory of the model (the context), the higher the accuracy of the predictions (probabilities), and therefore, the lower the length of the code-words [1].
Let $𝒞 [i]$ the last $i$ encoded symbols and $p (s | 𝒞 [i])$ the probability that the symbol $s$ follows the context $𝒞 [i]$ .
Let $k$ the maximal order of the prediction (i.e. the largest number of symbols of $𝒞 []$ that are going to be used as the actual context). Notice that $𝒞 [0] = \emptyset$ and the model has no memory.
We suppose that arithmetic coding is used and therefore, when we input or output $c (s)$ , we are transmitting $I (s)$ bits of code.
Let $r$ the size of the source alphabet.

10 Encoder

Create an empty model for every possible context of length $0 \leq i \leq k$ .
Create an non-empty model for $k = - 1$ .
While the input is not exhausted:
1. $s \leftarrow$ Input ${log}_{2} (r)$ bits. # Input a symbol.
2. $i \leftarrow k$ (except for the ﬁrst symbol, where $i \leftarrow 0$ ).
3. i ← k (except for the ﬁrst symbol, where i ← 0):
  1. Output $\leftarrow c (ESC | 𝒞 [i])$ .
  2. Update $p (ESC | 𝒞 [i])$ .
  3. Update $p (s | 𝒞 [i])$ (insert $s$ into the $𝒞 [i]$ context).
  4. $i \leftarrow i - 1$ .
4. Output $\leftarrow c (s | 𝒞 [i])$ . The symbols that were found in the models for contexts with order $> i$ must be excluded of the actual ( $𝒞 [i]$ ) context-model because, for sure, $s$ is not any of them.
5. If $i \geq 0$ , update $p (s | 𝒞 [i])$ .

Example

Let $r = 256$ the size of the source alphabet.
The probabilistic model $M [𝒞 [- 1]]$ (for the special context $𝒞 [- 1]$ ) is static, non empty and has an special symbol $EOF$ (End Of File) that is going to be used when the compression has ﬁnished: $M [𝒞 [- 1]] = {0, 1 1, 1 \dots a, 1 b, 1 \dots 255, 1 EOF, 1} = A .$
In a pair $(a, b)$ , $a$ is the symbol and $b$ is its probability (represented by a counter of ocurrences of $s$ in the processed input until that moment).
$M [𝒞 [0]]$ is adaptative and empty: $M [𝒞 [0]] = {ESC, 1} .$
In this example (for the sake of the simplicity), the maximal order of the prediction k = 1 (we only remember the previous symbol). Therefore, there are r = 256 probabilistic models: M[𝒞[1]] = {ESC,1},0 ≤𝒞[1] ≤ r.
1. $s \leftarrow a$ .
2. $i \leftarrow 0$ (we don’t know the previous symbol).
3. $p (a | 𝒞 [0]) = 0$ (the context $M [C [0]]$ has only the $ESC$ symbol, $M [C [0]] = {ESC, 1}$ ).
4. Output $\leftarrow c (ESC | 𝒞 [0])$ (in fact, zero bits because $l (c (ESC | 𝒞 [0])) = 0$ ).
5. Update $p (ESC | 𝒞 [0])$ (now, $M [C [0]] = {ESC, 2}$ ).
6. [3.C.c] Insert symbol $a$ into $M [𝒞 [0]] = {ESC, 2 a, 1}$ .
9. $p (a | 𝒞 [- 1]) \neq 0$ .
10. Output $\leftarrow c (a | 𝒞 [- 1])$ where $p (a | 𝒞 [- 1]) = 1 ∕ (256 + 1)$ .
Encoding of the second symbol (b):
1. $s \leftarrow b$ .
2. $i \leftarrow 1$ .
3. $p (b | 𝒞 [1]) = 0$ because $𝒞 [1] = a$ and $M [a] = {ESC, 1}$ .
4. Output $\leftarrow c (ESC | a)$ with $l (c (ESC | a)) = 0$ .
5. Update $p (ESC)$ in $M [a]$ (now, $M [a] = {ESC, 2}$ ).
6. Insert $b$ into $M [a] = {ESC, 2 b, 1}$ .
7. $i \leftarrow 0$ .
8. $p (b | 𝒞 [0]) = 0$ $M [𝒞 [0]] = {ESC, 2 a, 1}$ .
9. $p (b | 𝒞 [0]) = 0$ because $M [𝒞 [0]] = {ESC, 2 a, 1}$ .
10. Output $\leftarrow c (ESC | 𝒞 [0])$ , where $p (ESC | 𝒞 [0]) = 2 ∕ 3$ .
11. Update $p (ESC | 𝒞 [0])$ (now, the count of $ESC$ is $3$ ).
12. Insert $b$ into $M [𝒞 [0]] = {ESC, 3 a, 1 b, 1}$ .
13. $i \leftarrow - 1$ .
14. $p (b | 𝒞 [- 1]) \neq 0$ .
15. Output $\leftarrow c (b | 𝒞 [- 1])$ where $p (b | 𝒞 [- 1]) = 1 ∕ r$ . The symbol $a$ has been excluded of the calculus of the probability of $b$ for context $C [- 1]$ because $a \in M [𝒞 [0]] = {ESC, 3 a, 1 b, 1}$ .

Figure 1: An example of context-based statistical encoding.

11 Decoder

Equal to the step 1 of the encoder.
While the input is not exhausted:
1. $i \leftarrow k$ (except for the ﬁrst symbol, where $i \leftarrow 0$ ).
2. $s \leftarrow$ next decoded symbol.
3. While s = ESC:
  1. Update $p (ESC | 𝒞 [i])$ .
  2. $i \leftarrow i - 1$ .
  3. $s \leftarrow$ next decoded symbol.
4. Update $p (s | 𝒞 [i])$ .
5. While i < k:
  1. $i \leftarrow i + 1$ .
  2. Update $p (s | 𝒞 [i])$ (insert $s$ into the $𝒞 [i]$ context).

Let’s go the the lab!

         Codec | lena boats pepers zelda Average
---------------+--------------------------------
             : |    :     :      :     :       :
arith-n-c -o 1 | ....  ....   ....  ....    ....
arith-n-c -o 2 | ....  ....   ....  ....    ....
arith-n-c -o 3 | ....  ....   ....  ....    ....
Check the reversibility.

References

[1] John Cleary and Ian Witten. Data compression using adaptive coding and partial string matching. IEEE transactions on Communications, 32(4):396–402, 1984.

Probabilistic models

Contents

1 Funtionality

2 Static models

Let’s go the the lab!

3 Adaptive models

4 Encoding

5 Decoding

Let’s go the the lab!

6 Initially empty models

7 Encoder

8 Decoder

Let’s go the the lab!

9 Models with memory

10 Encoder

Example

11 Decoder

Let’s go the the lab!

References