move-to-front · shipping · also MTF, Move-to-front coding

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

  1. Bentley, Sleator, Tarjan and Wei: A Locally Adaptive Data Compression Scheme, CACM 29(4), 320-330 (1986), sections 2-4 and 6 (accessed 2026-11-18)
  2. Burrows and Wheeler: A Block-sorting Lossless Data Compression Algorithm, SRC Report 124 (1994), sections 3 and 5 (accessed 2026-11-18)
  3. bzip2 1.0.8 official release: compress.c, makeMaps_e, generateMTFValues and sendMTFValues (accessed 2026-11-18)
  4. Hesela: move-to-front state, rank and payload-width examples, executable model and tests (accessed 2026-11-18)
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.

JSON: /data/terms/move-to-front.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Move-to-front transform. Hesela. 2026-11-21. https://hesela.dev/terms/move-to-front/