Contents

1 Preamble

• The MTF uses a model where the next encoded symbol (that can be happened only one time) can get an index-code that is lower than the index-code of a symbol that previously 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 there is a counter for every node in the list.
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$.

2.1 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.

3.1 Example

TO-DO

4 $N$-order encoder

1. Let $\mathcal{𝒞}\left[i\right]$ the context of a input symbol $s$ and $L_{\mathcal{𝒞}\left[i\right]}$ the list previous simbols for that context. If $i>0$ then the lists are empty, else, the list is fully populated and the count of every node is $0$.
2. Let $k$ 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\setminus L_{\mathcal{𝒞}\left[i\right]}$. So, 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$.

4.1 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]}=\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)$.
   5. Update the count of $L_{\mathcal{𝒞}\left[i\right]}$.
   6. While $i<k$:
      1. $i\leftarrow i+1$.
      2. Insert the symbol $s$ in $L_{\mathcal{𝒞}\left[i\right]}$.

5.1 Example

TO-DO