Move-to-front transform
Move-to-front replaces each symbol with its position in an ordered list, then moves that symbol to the front.
Ranks: With zero-based positions and no eviction, a repeated symbol's rank equals the number of distinct symbols since its previous occurrence, not the number of intervening accesses. Initial occurrences depend on the starting alphabet order. [1] [2]
State: With alphabet abc, cabbaa becomes 2,1,2,0,1,0. Decoding its last three ranks from a fresh abc list gives abb instead of baa. A restart therefore needs the matching list state or an agreed reset boundary. [4]
Stored size: The transform emits one rank per input symbol. For a full 256-byte alphabet, storing every rank in one byte leaves the payload byte count unchanged. Smaller ranks help only with a subsequent coding scheme; alphabet descriptions, framing and indexes still cost space. [2] [4]
Block sorting: BWT groups symbols by context before move-to-front. The bzip2 1.0.8 implementation maps the used alphabet, run-codes zero ranks with RUNA/RUNB, shifts nonzero ranks by one and appends an end-of-block symbol before Huffman coding. Raw MTF ranks are not that file format. [2] [3]
Relations
- related
- Burrows-Wheeler transform, Bzip2, Reuse distance, Prediction by partial matching, Tsetlin library
Limitations
- The 1986 paper's experimental prototypes estimated coding costs without actually compressing and restoring files; those results are not round-trip validation. [1]
Citations
- Bentley, Sleator, Tarjan and Wei: A Locally Adaptive Data Compression Scheme, CACM 29(4), 320-330 (1986), sections 2-4 and 6
- Burrows and Wheeler: A Block-sorting Lossless Data Compression Algorithm, SRC Report 124 (1994), sections 3 and 5
- bzip2 1.0.8 official release: compress.c, makeMaps_e, generateMTFValues and sendMTFValues
- Hesela: move-to-front state, rank and payload-width examples, executable model and tests
Sources & caveats
- The historical word-list scheme and the fixed-alphabet byte transform use different initialization and rank conventions. The example models only the latter, with zero-based ranks.
- Primary papers and bzip2 1.0.8 implementation read; no historical speed comparison, bzip2 codec reimplementation or field-performance measurement is claimed.