Move-To-Front Coding
Move-To-Front (MTF) Coding
Another excellent transformation method is the Move-to-Front algorithm. The MTF scheme simply “moves to front” the last symbol seen such that its index in the table of codes becomes zero (0). It is immediately apparent that a run of bytes will be transformed to these zero bytes, like what RLT does.
MTF coding is an inherent part in the “locally adaptive data compression scheme” of Bentley, Sleator, Tarjan and Wei (1984); it was independently discovered by Peter Elias [1987]. Elias was already giving “homework problems” about MTF at Harvard in 1984, calling it recency rank encoding. He also described (along with recency rank encoding) another locally adaptive scheme called interval encoding which he taught at MIT in 1979 [Elias 1987].
Encoding. Take a close look at the MTF algorithm (Figure 1) and you will realize that what MTF really outputs is not a character or symbol but the character’s position in the symbol table. This is the most important characteristic of MTF since this property allows it to output the same sequence of position codes but the sequence could actually denote different strings of bytes at separate states of the compression process.
The pseudo-code for the MTF algorithm is as follows:
initialize the symbol table;
while ( not end-of-file ) {
K = get character;
output K’s position(P) in the symbol table;
move K to front of the symbol table.
}
Figure 1. The MTF Coding Algorithm
The simplest of these sequences is a “run” of bytes, as we have seen in RLT. The MTF encoding algorithm will output for these runs of distinct bytes the same run of zero bytes: the first run byte will immediately acquire a “position value” of zero and, eventually, this zero byte will be the one transmitted as the output code for the next run of the same byte.
Decoding. Remember that what MTF really outputs is a position in the table and not an actual symbol or character, and then it proceeds to transform the table. Thus, because the table is transformed only after the position is transmitted, the MTF decoding algorithm can also perfectly maintain the same table created by the encoding method, since they both start with the same symbol table. The pseudo-code description of the MTF decoding algorithm follows:
initialize the symbol table;
while ( not end-of-file ) {
P = get position;
output the symbol(K) in position P;
move K to front of the symbol table.
}
Figure 2. The MTF Decoding Algorithm
What the decoder accepts are table positions and not symbol codes, and thus would have to “translate” that table position into the correct output symbol found at that table position. Then, again, the table would have to be reconstructed to move-to-front the new symbol received. Hence, the same table is being used as a “look-up” table of the MTF encoding and decoding algorithms, allowing perfect reconstruction of the data source.
Higher-Order Processing
It might seem that the transmitted zero position of MTF coding is the only benefit that it provides to the second-stage algorithm. However, there is indeed an important characteristic of MTF. It turns out that it not only maps runs of distinct bytes to a run of a single byte, but also maps a sequence of distinct bytes (with the same pattern characteristics) into the same pattern of position codes. To illustrate, consider now the following data source:
Source String:
XYXYXYZZZZZZZMNMNMNCCCCCCC
When the MTF encoder sees this data input, it will eventually assign the initial codes 1 and 0 to characters ‘X’ and ‘Y’, respectively. What is interesting in this instance is that the MTF encoder will also assign the same code pair {1,0} to the first character pair “MN”!
Therefore, since the letter pairs ‘M’ and ‘N’ or ‘X’ and ‘Y’ just alternate in positions in the MTF process, the next occurrences of “XY” and “MN” will both assume the code pair {1,1}.
MTF allows more possibilities of pattern matches. A string-gathering algorithm like LZW will only assign a single string code for the code pair {1,1}, when in reality the code actually translates to two different strings (“XY” and “MN”) in each state of the compression process. Further, observe that the code pair {1,1}, when repeated as output, still creates a byte “run” of the form {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}.
The repeated patterns can be of any size: the next sequence of the strings, e.g., “XYZ’ and “MNO’ (with no letter appearing twice in the string) will be assigned by MTF with a code triplet of {2, 2, 2}. In this instance, the string “XYZXYZ” will give an output of {‘X’, ‘Y’, ‘Z’, 2, 2, 2}. In general, this can be extended to any order as long as the string does not contain a letter which appears twice in the string, like the strings “HELLO” and “ADVANCE” which contain the repeated letters ‘L’ and ‘A’, respectively.
There are many more interesting patterns appearing in an MTF output that you can observe. Obviously, this would greatly help the second-stage compression algorithm. An algorithm specifically-designed for processing the MTF output might even surpass current compression methods.
Hence, we can see that the Move-to-Front scheme is more powerful than the Run-Length Transform since it can transform not just “runs” of bytes but also other kinds of string patterns. If you want faster encoding time, RLT is faster and achieves the same single-byte “run-encoding” property of MTF. For highly-redundant files like image files, however, MTF is observed to be twice better than RLT in terms of compression ratio.
In empirical tests, the output of RLT and MTF significantly improves the compression performance of various algorithms like Huffman coding and the LZW algorithm. However, the RLT and MTF transforms are only effective when used in “highly-redundant” files and for files replete with runs of distinct bytes and “similar-context” strings. User-created text files do not always have these patterns, as well as executable files and any binary data that we customarily create.
Therefore, if that is the case (if we only have a few files that exhibit these patterns), we should deliberately “transform” all our files to explicitly assume these kinds of redundant patterns. What we need, then, is a kind of transform that will accept a seemingly-random file and produce as output a file of redundant bytes. The excellent transform described in the following section (BWT) exactly achieves this feat.
We implement MTF in a C program which is better than the simple RLT implementation. This program uses a linked list to implement the “move-to-front” operation [Elias 1987]. In practice, the list functions offer great improvements in speed than the array versions (which are also included here for your reference). Specifically, we use a “doubly-linked” list to easily delete a node in the middle of the list, allowing us to simply move it to front. This is obviously faster than the array version which has to actually shift the characters in the table. The speed improvement is certainly very helpful in encoding very large files.
Source code:
MTF.ZIP - contains a fast MTF implementation which uses a doubly-linked list data structure.