Cairn
algorithms · compression · O(n·k) encode/decode naive (n = input length, k = alphabet size) · a transform, not a standalone compressor

↩ back to Compression

Move-to-Front Transform

Move-to-Front keeps one list containing every symbol in the alphabet, ordered by how recently each has been used. To encode the next input symbol: find its current position in that list, emit that position as the output code, then move the symbol to the front of the list — position 0. Decoding runs the identical rule in reverse: read a position, look up the symbol sitting there, emit it, then move that same symbol to the front — the same list, updated by the same rule, stays in lockstep on both ends with nothing else transmitted. The output has exactly as many codes as the input has symbols; unlike every other entry in this site's Compression category, Move-to-Front never shrinks a message by itself.

That's not a flaw — Move-to-Front isn't trying to be a complete compressor. A symbol used very recently gets emitted at a very small position (0 if it was literally the last symbol read), so wherever symbols recur close together in time, the output skews hard toward small numbers — and a small-number-heavy stream of codes is exactly what a follow-on Huffman stage, or a run of repeated small codes an RLE pass, can then crush far better than it could crush the original symbols directly — see Pitfalls below for exactly how much, measured, not estimated. This is the Compression category's sixth entry, and the first that's a pure transform rather than a standalone compressor — the same role the site's own Burrows-Wheeler Transform plays, filed under Exact Match instead since it answers a different question (reversible rearrangement, not compression) but named by that very page as the first stage of the real pipeline this page completes: Burrows-Wheeler Transform, then Move-to-Front, then Huffman coding — bzip2's actual format, not a hypothetical.

Try it

Type a message (lowercase letters only, up to 24 characters) and press Load, then Step or Run. The recency list starts as the message's own distinct characters in sorted order — a simplification for this demo; a real implementation fixes that starting order once, in advance, for every message (bzip2 uses all 256 byte values, always in the same order), so no per-message alphabet ever has to travel alongside the codes. Watch the highlighted chip in the list below: that's where the next input symbol was found, and that position is the code emitted — then it jumps to the front.

input (current symbol highlighted)

recency list — leftmost = most recently used (highlighted chip is where the current symbol was found)

codes emitted, in order

Press Load.

Why it works

Trace the default message, mississippi, against the initial list [i, m, p, s] — its four distinct letters, sorted, the order both encoder and decoder agree on before reading anything. m sits at index 1 — emit 1, move it to front: [m, i, p, s]. i is now at index 1 — emit 1, move to front: [i, m, p, s] (back to the start, by coincidence). s's first appearance finds it at index 3, the back of the list — emit 3, move to front: [s, i, m, p]. The very next character is another s, already sitting at index 0 — emit 0, nothing moves. Full output: 1, 1, 3, 0, 1, 1, 0, 1, 3, 0, 1 — eleven codes for eleven input characters, nine of them 0 or 1, because i and s keep recurring within a character or two of their last use. Only two codes hit the maximum, 3 — s and p's first appearances, which happen to start at the back of this particular sorted initial list; a symbol's first-ever code is whatever index it starts at, not necessarily the worst case.

That skew toward small numbers is the entire point, and it's invisible to frequency alone: mississippi's raw letter frequencies (i and s four times each, m once, p twice) already let Huffman beat the fixed-width baseline slightly, 21 bits against 22 — but Huffman-coding the Move-to-Front output instead, with no other change, drops that to 16 bits, a real 24% cut on top of what frequency alone already found. See Pitfalls for the full measured table, including the one well-known input where this same transform makes things measurably worse, not better.

Decoding reverses the direction of the lookup, not the logic: start from the same agreed initial list, read each code as a position, output whatever symbol sits there, then move that symbol to the front — the identical update rule, so the list never falls out of sync with the one the encoder built. No separate index or dictionary ever has to travel; the codes are the only thing transmitted, exactly like RLE and unlike Huffman's tree or Arithmetic Coding's frequency table.

Reference implementation

Round-trip tested with a 20,000-trial fuzz test (random strings, alphabet size 1-8, length 1-30 — the same harness convention RLE's own page uses), each trial building its own initial list from that trial's distinct characters, sorted — zero mismatches.

function mtfEncode(input, initialList) {
  const list = initialList.slice();
  const codes = [];
  for (const ch of input) {
    const idx = list.indexOf(ch);
    codes.push(idx);
    list.splice(idx, 1);
    list.unshift(ch);
  }
  return codes;
}

function mtfDecode(codes, initialList) {
  const list = initialList.slice();
  let out = '';
  for (const idx of codes) {
    const ch = list[idx];
    out += ch;
    list.splice(idx, 1);
    list.unshift(ch);
  }
  return out;
}

initialList has to be agreed before either function runs — this reference passes in the message's own sorted distinct characters for both the fuzz test and the demo above, but a real byte-oriented implementation fixes it once, sitewide, independent of any specific message (see Pitfalls below).

Pitfalls

Measured, not estimated — the site's own Huffman construction, run once on each input directly and once on that input's Move-to-Front output, both compared against the same ⌈log₂(alphabet size)⌉-bit fixed-width baseline the rest of this category uses:

inputfixed-widthHuffman, no MTFHuffman, after MTF
mississippi222116
abracadabra332324
aabbaabbccddccdd323225
abcdefghijabcdefghij806849
thecatsatonthecatmat805844

aabbaabbccddccdd is the cleanest demonstration of what Move-to-Front actually adds: all four letters occur exactly four times, so Huffman alone can't beat the fixed-width baseline at all (32 bits either way — a perfectly flat frequency table has nothing for a frequency-driven code to exploit). But every occurrence sits right next to a recent repeat of the same pair, a shape Huffman can't see because it only ever looks at how often a symbol occurs, never where. Move-to-Front turns that positional structure into frequency structure — the code stream it emits is heavily skewed toward 0 and 1 — and Huffman-coding that stream instead drops the real cost to 25 bits, a 22% cut Huffman alone could never have found on this input no matter how it was built.

abcdefghijabcdefghij looks like the opposite case at a glance — ten symbols, each occurring exactly twice, cycling through the whole alphabet before any symbol repeats. The code stream it produces is 0,1,2,3,4,5,6,7,8,9,9,9,9,9,9,9,9,9,9,9 — nine of the twenty codes are already the maximum possible index, which looks like a sign Move-to-Front found nothing. It still helps, and by the widest margin measured on this page: that long run of maximum-index codes is itself an extremely skewed distribution (one value, 9, covers more than half the stream), and Huffman-coding it costs 49 bits against 68 for Huffman on the raw letters — a 28% cut from an input whose per-symbol codes look like the worst case by eye. A big index doesn't mean the transform failed; a predictable index, even a maximal one, is exactly as compressible as a small one once something downstream is actually counting frequencies.

abracadabra — the same eleven-character example Huffman, RLE, and LZW's own pages all already use as their shared default — is the one input measured here where Move-to-Front makes things worse, not better: Huffman alone already reaches 23 bits, and Huffman-coding the Move-to-Front output instead costs 24, one bit more. Its repeats are real (a five times, b and r twice each) but never close together — by the time any letter recurs, one or more other distinct letters have already been promoted ahead of it, so the position it's found at isn't reliably any smaller than Huffman's own frequency-rank would have placed it at directly. The transform costs a constant amount of implementation complexity on every input; it only gets paid back when repeats actually cluster in time, not just in overall count.

The starting list has to be agreed, not derived from the message being sent. This page's own demo and fuzz test build the initial list from each message's own distinct characters, sorted — convenient for a self-contained demo, but a format that actually did this would have to transmit that per-message alphabet alongside the codes, the same side-information cost Huffman's own tree pays. Real byte-oriented implementations (bzip2 included) sidestep it entirely by fixing the initial list once, for every message, independent of content — all 256 byte values in a standard order — so nothing about the alphabet ever has to travel. The cost moves from a per-message table to a slightly larger worst-case first-appearance index (255 instead of 3 or 9 in the examples above), never to a transmitted side channel.

The naive list — an array, searched and spliced every symbol — costs O(k) per symbol, k the alphabet size, not O(1): indexOf scans linearly and splice/unshift shift every element in front of the move. For a 256-byte alphabet that's a small, fixed per-symbol constant in practice (256 comparisons, worst case, regardless of message length) rather than a real asymptotic problem — see Complexity below for exactly what a linked-list-based version trades away instead.

Complexity

Time: O(n·k) naive, worst case — one indexOf scan plus one splice shift per symbol, each up to O(k) where k is the alphabet size, over n input symbols. In practice k is a small fixed constant (256 for a byte-oriented implementation) regardless of how long the message is, so this behaves like O(n) with a flat per-symbol cost rather than growing with the input the way LZW's unbounded dictionary can. A doubly linked list with a symbol→node hash map makes the move itself O(1) — relink three pointers, no shifting — but emitting the position still means walking from the front to count how many nodes sit ahead of the target, so the straightforward linked-list version doesn't actually beat the array on time, only on the constant cost of the move step itself; a real O(log k)-per-symbol version needs an order-statistics structure (a balanced tree or skip list keyed by position) that neither this page nor bzip2's own reference implementation bothers with, since k staying at 256 makes the naive approach fast enough in practice. Space: O(k) for the list itself, independent of n — the smallest working-state footprint of anything in this category except RLE's single current run.

See Choosing a Compression Approach for where this entry fits relative to the site's other six — short version: it's not a seventh competing answer to "which compressor do I pick," it's the transform that makes the Burrows-Wheeler-Transform-to-Huffman pipeline actually work, named by BWT's own page but built here for the first time.