MTF transform and adaptive coding
The move-to-front transform is typically used in conjunction with the burrows-wheeler-transform (BWT), where it takes advantage of the local correlation of symbol frequencies.
Adaptive coding is generally used for data streams with changing probability distributions. If the data block contains small Islands of similar symbols, so that each island would be well compressible with a static entropy coder, but at large the data block is not very compressible with the static entropy coder, adaptive entropy coding can alleviate the problem. An example for context modeling for an adaptive arithmetic coder can be found here.
The similarity between MTF and Adaptive Coding
BZIP3 uses, in conjunction with the BWT, an order-0 adaptive arithmetic coder instead of an MTF transform. To me, this is an indication, that adaptive coding can yield similar benefits as an MTF transform, and vice versa. In a way, an MTF transform in conjunction with a static entropy coder could be seen as a 2-pass adaptive entropy coder.
Get Dat Sword’s stories in your inbox
Join Medium for free to get updates from this writer.
MTF will work instantly well, if the data contains a lot of runs of identical symbols. This property can be achieved with an adaptive arithmetic coder, if the context modeling is properly designed to handle this.
MTF as a adaptive ranking pre-coder
I wish to generalize the concept, therefore I introduce a new term: adaptive ranking pre-coder. A pre-coder does not perform the entropy coding itself, but only performs the context modeling for the entropy coder. A ranking pre-coder does this, by representing each symbol as a rank of frequencies, such that 0 is the symbol with the highest probability, 1 is the symbol with the second highest probability and so on. And the term adaptive is pretty much self-explanatory. The MTF transform is an adaptive ranking pre-coder.
Higher order adaptive coding
Adaptive arithmetic coding is often implemented as context-sensitive adaptive arithmetic coding. For example as an order-1 adaptive arithmetic coder. That means, that the probability model for a current symbol is selected based on the last symbol.
A similar technique can be used for the MTF transform. Lets call it an order-1 MTF transform, where the MTF list is selected based on the previous symbol. This combination could be considered to be an order-1 adaptive ranking pre-coder.
As a processing step after BWT, an order-1 adaptive coder or an order-1 MTF transform makes no sense, since the BWT already increases the local correlation between symbol frequencies. An order-1 algorithm makes sense, when no previous processing is done, or when LZ77 literals need to be compressed.
How well an order-1 MTF transform as an order-1 adaptive ranking pre-coder can reduce the entropy of compressible data is to be investigated. Potentially, other transforms similar to the MTF should be considered for this use-case.
