Algorithms & Data Structures
the bound is a claim, and it is checkable
Series

Bits — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. bits per symbolhuffman3.9371.01× the floorarithmetic (adaptive)3.8981.00× the floorLZSS (window 4096)2.1130.54× the floorLZ783.1470.81× the floorH₀ = 3.89216,384 symbols · alphabet 21 · floor shown is H0 = 3.892 bits/symbolmodel: order 0 · Words from a fixed vocabularybest here: 2.113 bits/symbol

    The bits a coder emits

    A stream of 16,384 symbols with a zeroth-order entropy of 3.891 bits per symbol was coded by a Huffman coder into 3.937 and by an arithmetic coder into 3.898, and neither went under 3.891 because neither can. That floor is a third kind of limit, the first that is a property of a model rather than of a question, and the same stream has a different one under every model of it.

    part 1 · floors
  2. 0.1250.30.50.70.80.90.99probability of the dominant symbolbits per symbol0.01.63.2one bit per symbolHuffmanArithmeticEntropy H₀model: order 0 · 16,384 symbols per point8.7× at p = 0.99

    The optimal code that is beaten

    Huffman's code is optimal, the proof is correct, and on a stream where one symbol arrives 99 times in a hundred it spends 1.030 bits per symbol against an arithmetic coder's 0.119. Both facts hold. The word "optimal" in the theorem has a precondition attached that almost nobody quotes with it, and everything interesting about coding lives on the other side of that precondition.

    part 2 · wrong
  3. H0H1H2H3H4model order — symbols of contextbits per symbol0.02.14.2Uniform over 8 symbolsOrder-1 Markov chainWords from a fixed vocabulary32,768 symbols · at H4 the deepest source has 709 contexts, 0 seen oncemodels: orders 0, 1, 2, 3, 42.06 bits found by one symbol of context

    The model is the compressor

    One stream of 32,768 symbols has an entropy of 3.886 bits per symbol, and 2.243, and 1.186, and 0.991, and 0.909. All five numbers are correct, all five are floors, and nothing about the data changed between them. The only thing that changed is how many preceding symbols the model was allowed to look at — which makes the entropy of a file a property of a decision rather than a property of a file.

    part 3 · text
  4. H₀ = 3.8916642561k4k16kwindow, in symbolsbits per symbol0.04.38.6LZSSmean symbols covered per match4.65.15.76.98.79.6model: a window of recent text, no probabilities2.13 bits/symbol at a window of 16,384

    The dictionary that builds itself

    LZSS contains no probability, no frequency table and no entropy calculation. Its entire model is a window of recent text and its only move is to say "the next nine symbols are the ones that appeared 1,200 positions ago". On a stream whose zeroth-order floor is 3.89 bits per symbol it spends 2.11, and widening its window past 4,096 makes it worse rather than better.

    part 4 · practice
  5. each row is one rotation · the table is sorted · the transform is the last columnfirstlast◇the-order-is-the-message-is-the-message◇the-order-message◇the-order-is-the-order-is-the-message◇the-the-message◇the-order-isage◇the-order-is-the-messder-is-the-message◇the-ore◇the-order-is-the-message-message◇the-order-is-the-order-is-the-message◇ther-is-the-message◇the-ordessage◇the-order-is-the-mge◇the-order-is-the-messahe-message◇the-order-is-t… 11 further rotationsmeasured on 8,192 symbols of the same source:H₀ of the text3.899 bitsH₀ of the last column3.899 bitsH₀ after move-to-front, before4.156 bitsH₀ after move-to-front, after1.802 bitsmodel: order 0, before and after a permutationmean run 1.01 → 3.38

    The transform that emits nothing

    The Burrows–Wheeler transform outputs exactly the characters it was given, in a different order. Its zeroth-order entropy is therefore identical to its input's, to fifteen decimal places, and by that measure it has done nothing at all. A Huffman coder handed the result spends 1.935 bits per symbol where the same coder on the same data spends 4.209, and the difference is entirely in the order.

    part 5 · text
  6. thousands of bits · the floor is 31.9kthe text as it is34.0k streamto undo itnothinga shuffle agreed in advance34.4k streamto undo itnothingthe characters sorted0.3k streamto undo it31.8kthe Burrows–Wheeler transform14.8k streamto undo itnothingmodel: order 0 after move-to-front · Words from a fixed vocabularydashed: coding the text as it stands

    What a reordering costs to undo

    Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.

    part 6 · floors
  7. 01234characters of context the sort reads, kbits a symbol after move-to-front012481632the full transform, 1.802ties kept in text orderties sorted by symbol: the stream alonethe text's own floormodel: order 0 after move-to-front · Words from a fixed vocabularyexactly the transform from k = 24

    The order inside a tie

    Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.

    part 7 · floors

All series