Contents

1 A MTF transform that uses a probabilistic model

• The MTF uses a model where a symbol that has happened only one time can get a index-code that is lower than the index-code of a symbol that has been found thousands of times :-(
• We can solve this problem if the positions of the symbols are determined by their probability. In other words, the list $L$ will be sorted by the ocurrence of the symbols.

2 0-order encoder

1. The step 1 of the MTF transform, although now every node of the list stores also a count of the symbol.
2. While the input is not exhausted:
   1. $s\leftarrow$ next input symbol.
   2. $c\leftarrow$ position of $s$ in $L$ (the prediction error).
   3. Output $\leftarrow c$.
   4. Update the count of $L\left[c\right]$ (the count of $s$) and keep sorted $L$.

Example

3 0-order decoder

1. The step 1 of the encoder.
2. While the input is not exhausted:
   1. $c\leftarrow$ next input code.
   2. $s\leftarrow L\left[c\right]$.
   3. Output $s$.
   4. Step 2.d of the encoder.

Let’s go the the lab!

1. make tpt (Notice that tpt should be invoked using the sintaxis tpt e <order> < input_file > output_file).
2.                              Codec | lena boats pepers zelda Average  
   -----------------------------------+--------------------------------  
                                    : |    :     :      :     :       :  
               tpt 0 | arith-n-c -o 0 | ....  ....   ....  ....    ....  
         tpt 0 | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
         bwt | tpt 0 | arith-n-c -o 0 | ....  ....   ....  ....    ....  
   bwt | tpt 0 | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....

3. Are they lossless?

4 N-order encoder

1. Let $\mathcal{𝒞}\left[i\right]$ the context of $s$ and $L_{\mathcal{𝒞}\left[i\right]}$ the list for that context. If $i>0$ then the lists are empty, else, the list is full and the count of every node is $0$.
2. Let $N$ the order of the prediction.
3. Let $H=\varnothing$ a list of tested symbols. All symbols in $H$ must be different.
4. While the input is not exhausted:
   1. $s\leftarrow$ the next input symbol.
   2. $i\leftarrow k$ (except for the first symbol, where $i\leftarrow 0$).
   3. While $s\notin L_{\mathcal{𝒞}\left[i\right]}$:
      1. $H\leftarrow \text{reduce}\left(H\cup L_{\mathcal{𝒞}\left[i\right]}\right)$. (reduce$\left(\right)$ deletes the repeated nodes).
      2. Update the count of $s$ in $L_{\mathcal{𝒞}\left[i\right]}$ and keep sorted it.
      3. $i\leftarrow i-1$.
   4. Let $c$ the position of $s$ en $L_{\mathcal{𝒞}\left[i\right]}$.
   5. $c\leftarrow c+$ symbols of $H-L_{\mathcal{𝒞}\left[i\right]}$. In this way, the decoder will know the length of the context where $s$ happens and does not count the same symbol twice.
   6. Output $\leftarrow c$.
   7. Update the count of $s$ in $L_{\mathcal{𝒞}\left[i\right]}$ and keep sorted it.
   8. $H\leftarrow \varnothing$.

Example ($k=1$)

5 N-order decoder

1. Steps 1, 2 and 3 of the encoder.
2. While the input is not exhausted:
   1. $c\leftarrow$ the next input code.
   2. $i\leftarrow k$ (except for the first symbol, where $i\leftarrow 0$).
   3. While $L_{\mathcal{𝒞}\left[i\right]}\left[c\right]=\varnothing$:
      1. $H\leftarrow \text{reduce}\left(H\cup L_{\mathcal{𝒞}\left[i\right]}\right)$.
      2. $i\leftarrow i-1$.
   4. $s\leftarrow \text{reduce}\left(H\cup L_{\mathcal{𝒞}\left[i\right]}\right)\left[c\right]$.
   5. Update the count of $L_{\mathcal{𝒞}\left[i\right]}\left[c\right]$.
   6. While $i<k$:
      1. $i\leftarrow i+1$.
      2. Insert the symbol $s$ in $L_{\mathcal{𝒞}\left[i\right]}$.

Let’s go the the lab!

1.                              Codec | lena boats pepers zelda Average  
   -----------------------------------+--------------------------------  
                                    : |    :     :      :     :       :  
               tpt 1 | arith-n-c -o 0 | ....  ....   ....  ....    ....  
               tpt 2 | arith-n-c -o 0 | ....  ....   ....  ....    ....  
         bwt | tmp 1 | arith-n-c -o 0 | ....  ....   ....  ....    ....