Contents

1 Funtionality

• Compute the probabilities of the symbols (see Figure ??).
• Both, the encoder and the decoder must be syncronized.

2 Static models

• The simplest models because the probabilities of the symbols remain constant.
• The variable-length codec can be precomputed.
• If the last premise is true, the entropy codec is efficient an fast. For this reason, static models are very common in codecs such as JPEG, MPEG (audio and video), etc.

Let’s go the the lab!

1. Download http://www.ace.ual.es/~vruiz/doctorado/text-compression.tar.gz and make huff_s0.
2. Encode each image of The Test Image Corpus using the codec. Continue filling the table:
       Codec | lena boats pepers zelda  
   ----------+------------------------  
         RLE | ....  ....   ....  ....  
     BWT+RLE | ....  ....   ....  ....  
        LZSS | ....  ....   ....  ....  
         LZW | ....  ....   ....  ....  
     huff_s0 | ....  ....   ....  ....

3. Check that the huff_s0 codec is lossless.

3 Adaptive models

• The probabilities of the symbols are computed in run-time.
• In general, the compression ratios that an adaptive model get are better than the static model’s ones because the probabilities of the symbols are localy computed.

4 Encoding

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

5 Decoding

1. Identical to the step 1 of the encoder.
2. 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!

1. Download http://www.ace.ual.es/~vruiz/doctorado/progs.tar.gz and make huff_a0 and make arith_a0.
2. Encode each image of The Test Image Corpus using the codec. Continue filling the table:
       Codec | lena boats pepers zelda Average  
   ----------+--------------------------------  
           : |    :     :      :     :       :  
     huff_s0 | ....  ....   ....  ....    ....  
     huff_a0 | ....  ....   ....  ....    ....  
    arith_a0 | ....  ....   ....  ....    ....

3. Remember to check that both codecs are lossless.

6 Initially empty models

• Used in adaptive 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.

7 Encoder

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

8 Decoder

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

Let’s go the the lab!

1. make arith-n-c and make arith-n-d.
2.          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

3. 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 $\mathcal{𝒞}\left[i\right]$ the last $i$ encoded symbols and $p\left(s|\mathcal{𝒞}\left[i\right]\right)$ the probability that the symbol $s$ follows the context $\mathcal{𝒞}\left[i\right]$.
• Let $k$ the maximal order of the prediction (i.e. the largest number of symbols of $\mathcal{𝒞}\left[\right]$ that are going to be used as the actual context). Notice that $\mathcal{𝒞}\left[0\right]=\varnothing$ and the model has no memory.
• We suppose that arithmetic coding is used and therefore, when we input or output $c\left(s\right)$, we are transmitting $I\left(s\right)$ bits of code.
• Let $r$ the size of the source alphabet.

10 Encoder

1. Create an empty model for every context $0\le i\le k$.
2. Create an non-empty model for $k=-1$.
3. While the input is not exhausted:
   1. $s\leftarrow$ Input${}_{{log}_2\left(r\right)}$.
   2. $i\leftarrow k$ (except for the first symbol, where $i\leftarrow 0$).
   3. While $p\left(s|\mathcal{𝒞}\left[i\right]\right)=0$ (it is the first time that $s$ follows $\mathcal{𝒞}\left[i\right]$):
      1. Output $\leftarrow c\left(\text{ESC}|\mathcal{𝒞}\left[i\right]\right)$.
      2. Update $p\left(\text{ESC}|\mathcal{𝒞}\left[i\right]\right)$.
      3. Update $p\left(s|\mathcal{𝒞}\left[i\right]\right)$ (insert $s$ into the $\mathcal{𝒞}\left[i\right]$ context).
      4. $i\leftarrow i-1$.
   4. Output $\leftarrow c\left(s|\mathcal{𝒞}\left[i\right]\right)$. The symbols that were in contexts with order $>i$ must be excluded of the actual ($\mathcal{𝒞}\left[i\right]$) context because $s$ is not none of them.
   5. If $i\ge 0$, update $p\left(s|\mathcal{𝒞}\left[i\right]\right)$.

Example

• Let $r=256$ the size of the source alphabet.
• The probabilistic model $M\left[\mathcal{𝒞}\left[-1\right]\right]$ (for the special context $\mathcal{𝒞}\left[-1\right]$) is non adaptative, non empty and has an special symbol EOF (End Of File) that is going to be used when the compression has finished: $$M\left[\mathcal{𝒞}\left[-1\right]\right]=\left\{0,11,1\cdots \mathtt{a},1\mathtt{b},1\cdots 255,1\text{EOF},1\right\}.$$

  In a pair $a,b$, $a$ is the symbol and $b$ is its probability (counts).

• $M\left[\mathcal{𝒞}\left[0\right]\right]$ is adaptative and empty: $$M\left[\mathcal{𝒞}\left[0\right]\right]=\left\{\text{ESC},1\right\}.$$

• 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\left[\mathcal{𝒞}\left[1\right]\right]=\left\{\text{ESC},1\right\},0\le \mathcal{𝒞}\left[1\right]\le r.$$

• Encoding of the first symbol (a) (see Figure 1):
  1. $s\leftarrow$ a.
  2. $i\leftarrow 0$ (we don’t know the previous symbol).
  3. $p\left(\mathtt{a}|\mathcal{𝒞}\left[0\right]\right)=0$ (the context only has the ESC).
  4. Output $\leftarrow c\left(\text{ESC}|\mathcal{𝒞}\left[0\right]\right)$ (althought $l\left(c\left(\text{ESC}|\mathcal{𝒞}\left[0\right]\right)\right)=0$).
  5. Update $p\left(\text{ESC}|\mathcal{𝒞}\left[0\right]\right)$ (now, the count of ESC is 2).
  6. Insert a into $M\left[\mathcal{𝒞}\left[0\right]\right]=\left\{\mathsf{ESC},2\mathtt{a},1\right\}$.
  7. $i\leftarrow -1$.
  8. $p\left(\mathtt{a}|\mathcal{𝒞}\left[-1\right]\right)\ne 0$.
  9. Output $\leftarrow c\left(\mathtt{\text{a}}|\mathcal{𝒞}\left[-1\right]\right)$ where $p\left(\mathtt{\text{a}}|\mathcal{𝒞}\left[-1\right]\right)=1∕\left(256+1\right)$.

• Encoding of the second symbol (b):
  1. $s\leftarrow$ b.
  2. $i\leftarrow 1$.
  3. $p\left(\mathtt{b}|\mathcal{𝒞}\left[1\right]\right)=0$ because $\mathcal{𝒞}\left[1\right]=\mathtt{\text{a}}$ and $M\left[\mathtt{\text{a}}\right]=\left\{\text{ESC},1\right\}$.
  4. Output $\leftarrow c\left(\text{ESC}|\mathtt{\text{a}}\right)$ (althought $l\left(c\left(\text{ESC}|\mathtt{\text{a}}\right)\right)=0$).
  5. Update $p\left(\text{ESC}|\mathtt{\text{a}}\right)$ (now, the count of ESC is 2).
  6. Insert b into $M\left[\mathtt{\text{a}}\right]=\left\{\text{ESC},2\mathtt{\text{b}},1\right\}$.
  7. $i\leftarrow 0$.
  8. $p\left(\mathtt{b}|\mathcal{𝒞}\left[0\right]\right)=0$ because $M\left[\mathcal{𝒞}\left[0\right]\right]=\left\{\mathsf{ESC},2\mathtt{\text{a}},1\right\}$.
  9. Output $\leftarrow c\left(\text{ESC}|\mathcal{𝒞}\left[0\right]\right)$ where $p\left(\text{ESC}|\mathcal{𝒞}\left[0\right]\right)=2∕3$.
  10. Update $p\left(\text{ESC}|\mathcal{𝒞}\left[0\right]\right)$ (now, the count of ESC is 3).
  11. Insert b into $M\left[\mathcal{𝒞}\left[0\right]\right]=\left\{\text{ESC},3\mathtt{\text{a}},1\mathtt{\text{b}},1\right\}$.
  12. $i\leftarrow -1$.
  13. $p\left(\mathtt{b}|\mathcal{𝒞}\left[-1\right]\right)\ne 0$.
  14. Output $\leftarrow c\left(\mathtt{\text{b}}|\mathcal{𝒞}\left[-1\right]\right)$ where $p\left(\mathtt{b}|\mathcal{𝒞}\left[-1\right]\right)=1∕r$. The symbol a has been excluded in the calculus of the probability of b because $\mathtt{\text{a}}\in M\left[\mathcal{𝒞}\left[0\right]\right]=\left\{\text{ESC},3\mathtt{\text{a}},1\mathtt{\text{b}},1\right\}$.

11 Decoder

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

Let’s go the the lab!

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

2. Check the reversibility.

References