The MTF (Move To Front) transform

Juan Francisco Rodríguez Herrera
Vicente González Ruiz

September 12, 2016

Contents

1 The MTF transform
2 Forward transform
3 Inverse transform

1 The MTF transform

PIC

2 Forward transform

  1. Create a list L with the symbols of the source alphabet where L[s] ← s;0 ≤ s ≤ r.

  2. While the input is not exhausted:
    1. s ← next input symbol.
    2. c ← position of s in L (L[c] = s).
    3. Output ← c.
    4. Move s to the front of L.

3 Inverse transform

  1. The step 1 of the forward transform.
  2. While the input is not exausted:
    1. c ← next input code.
    2. s ← L[c].
    3. Output s.
    4. The step 2.c of the forward transform.

Example

L Input Output



⋯abc⋯ b b
b⋯ ac⋯ a b
ab⋯c⋯ a 0
ab⋯ c⋯ a 0
ab⋯c⋯ a 0
ab⋯ c⋯ a 0
ab⋯c⋯ a 0
ab⋯ c⋯ b 1
ba⋯c⋯ b 0
ba⋯c⋯ a 1
ab⋯c⋯ b 1
ba⋯c⋯ a 1
ab⋯c⋯ a 0
ab⋯c⋯ c c
cab⋯⋯ a 1
acb⋯⋯ a 0

Let’s go the the lab!

  1. make mtf.
  2.                                  Codec | lena boats pepers zelda Average  
    ---------------------------------------+--------------------------------  
                                         : |    :     :      :     :       :  
                      mtf | arith-n-c -o 0 | ....  ....   ....  ....    ....  
                      rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
                rle | mtf | arith-n-c -o 0 | ....  ....   ....  ....    ....  
                mtf | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
          bwt | mtf | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
    rle | bwt | mtf | rle | arith-n-c -o 0 | ....  ....   ....  ....    ....  
          bwt | mtf | rle | arith-n-c -o 1 | ....  ....   ....  ....    ....

  3. Be lossless, my friend!