Move-to-Front Transform
The Move-to-Front (MTF) transform maintains a symbol table, outputs each symbol's current index in the table, and then moves that symbol to the front, so frequent symbols acquire small indices.
Purpose
After BWT, it turns the clustered identical characters into many small integers, creating a favorable distribution for run-length or entropy coding.
Mechanism
Initialize the symbol table in some order; for each symbol, output its current index in the table and then move it to the front — repeated symbols yield 0. Decoding runs the same table operations in reverse.
Use cases
- Second stage of bzip2 compression
- Post-processing after BWT
- Locality exploitation