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

Context model — where it appears

A model predicting the next symbol from the k symbols before it, which gives a stream a lower entropy floor than its symbol frequencies alone. The order k is a parameter and the floor moves with it, so a compressibility claim is only a quantity once the order has been named.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

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.

text · Bits 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.

text · Bits 1,00010,00010³10⁴bits · runs12481632characters in the collection · copies aboven·H₃, bitsr, runs in thetransformEnglish-like · base 512 · divergence 0n·H₃ x15.8 · r x1.00

The entropy that cannot see a copy

Two copies of a text have exactly the same symbol statistics as one, so every entropy on this site doubles when the second copy arrives and the second copy carries no information at all. The number of runs in the Burrows-Wheeler transform is 224 at two copies and 224 at thirty-two.

text · Repeat is·holds·no·the·the·of·of·rather·count·class·that·is·algorithm·o1111111211111151141131111111211122213111111212phrase lengths below each block · a shaded block is a literalEnglish-like · 64 charactersz = 46 · 17 literals

The phrases a text copies from itself

Four thousand characters of English-like text hold 604 phrases in the greedy parse and 1,219 runs in the transform. Thirty-two copies of one text hold 156 phrases and 233 runs. Two measures of repetition, neither of them an entropy, and they do not agree about which text is the more repetitive.

text · Parse 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.

floors · Bits

Named alongside it

The objects these essays reach for when they reach for this one.

EntropyBurrows-wheeler transformConditional entropyRun-lengthAlphabetCompressibilityHonest limitInvertibilityMeasurementModel orderMove to frontPermutation

All concepts