The move-to-front (MTF) transform is a standard data compression technique that reduces the entropy of data streams. After a symbol has been processed, it is moved to the top of the history table, which ensures that frequently used symbols are encoded using fewer bits.

Uzelac and Milenkovic propose using the MTF transform to perform program tracing by enhancing the technique to two levels--the double move-to-front (DMTF) method. As the paper states, “consider the following repeating stream pattern {ABAC}.” {ABAC} may be encoded as a pattern of {1212} at the first-level MTF, and then encoded as a pattern of {1111} at the second-level MTF. This way, “the MTF transformation lowers the number of frequent symbols.” The authors further extend the method by using last-value predictors and adaptive zero-length counters.

The trace compressor with the best performance configuration achieves a compression ratio between 83:1 and 29389:1; “the average weighted compression ratio is 268:1.” The resulting code requires 0.001 to 0.39 bits per instruction, with an average of 0.12 bits per instruction. The estimated complexity of the best performing configuration is equivalent to 25,000 logic gates.

This well-written paper proposes an innovative technique. Unfortunately, the authors fail to compare the performance of the proposed technique to that of other program trace compressors. Also, since DMTF is an enhancement of the MTF transform in data compression, the paper should have evaluated the method in relation to other data compression techniques.