Move to front coder/transform
First a little explanation about what a move to front coder is. Its a revesible transform which remaps symbols to an index into a table which initially contains (0,1,2,3,…) and every time a symbol is used its moved to the front of the table.
example: input: “to be or not to be” initial table: (abcdefghijklmnopqrstuvwxyz), for the first ‘t’ we output 19 as its the 19th entry in the table and move it to the front to build the new table (tabcdefghijklmnopqrsuvwxyz) the complete list of steps looks like:
abcdefghijklmnopqrstuvwxyz 19(t) tabcdefghijklmnopqrsuvwxyz 15(o) otabcdefghijklmnpqrsuvwxyz 27( ) otabcdefghijklmnpqrsuvwxyz 4(b) b otacdefghijklmnpqrsuvwxyz 7(e) eb otacdfghijklmnpqrsuvwxyz 2( ) ebotacdfghijklmnpqrsuvwxyz 3(o) o ebtacdfghijklmnpqrsuvwxyz 19(r) ro ebtacdfghijklmnpqsuvwxyz 2( ) roebtacdfghijklmnpqsuvwxyz 17(n) n roebtacdfghijklmpqsuvwxyz 3(o) on rebtacdfghijklmpqsuvwxyz 6(t) ton rebacdfghijklmpqsuvwxyz 3( ) tonrebacdfghijklmpqsuvwxyz 1(t) t onrebacdfghijklmpqsuvwxyz 2(o) ot nrebacdfghijklmpqsuvwxyz 2( ) ot nrebacdfghijklmpqsuvwxyz 6(b) bot nreacdfghijklmpqsuvwxyz 6(e)
As you can see the mtf transform will generally favor small numbers on “non random” data, on its own its not too usefull for compression but together with the BWT and a simple order 0 entropy coder its a pretty good general purpose compressor.
Now to the actual reason why i am writing this blog entry, can you use the symbol which the index represents as context for the entropy coder coding the index? You say no because thats like knowing the index together with the table.
Well if you think so, you are wrong, the trick is not to know the table :)
First to compress our data we run an mtf transform over it, we store the mtf table after the whole transform (this is not strictly needed but simplifies things). Next we encode the indexes from the end to the begin each time moving the zero entry of our table to the point pointed to by the index, each time we do know the symbol before the index and so can use it as context. This really is nothing else as the MTF coder in reverse.
An example, we start with the table (ebot nracdfghijklmpqsuvwxyz), the first symbol is ‘e’ the corresponding index is 6 (we know this from the forward MTF pass), so we store 6 with context ‘e’ and move e to the 6th place to find the table (bot nreacdfghijklmpqsuvwxyz), the next steps are all just the same than the MTF example above just in reverse.
Decompression is pretty much the same, read the table (again this isnt needed but its simpler as it avoids a 2nd pass over the data) then take the value from position 0 of the table and use it as context to decode the next index, after that use the index to move the entry from position 0 to its new position and repeat until you are out of input data.