Entropy — where it appears
Named by 24 essays across 9 fields — each of them below, with the objects they name alongside it.
One pass, k slots, and two randomness budgets
Reservoir sampling takes a uniform sample of k items from a stream of unknown length in one pass and k slots. The textbook version and a second version draw from exactly the same distribution, and at 65,536 items one of them spends 1,356,399 random bits and the other spends 9,380.
The index that is smaller than the text
The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.
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.
The floor when the values repeat
log₂(n!) counts orderings of distinguishable things. Two hundred and fifty-six values drawn from eight distinct ones have 1,684 bits of permutation entropy and 739 bits of distinguishability, so the real floor is less than half the one every table quotes — and merge sort, which sits exactly on the quoted floor, is 2.3 times above the one that applies.
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.
The adversary who knows the seed
Every randomised figure on this site is drawn from a stated seed, so that the numbers in the captions are the numbers on the reader's screen. That is also the exact condition under which none of the guarantees those figures demonstrate applies. A published seed is a published function.
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.
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.
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.
Rank is the only thing it does
Constant time and o(n) extra space — a phrase true of a rank directory costing 163% overhead and reading three words, and equally true of one costing 3% and reading eighteen. Both numbers are decided by two integers somebody typed into a header, and the phrase names neither.
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.
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.
A block, a class and an offset
Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.
A corpus that was not generated
Every collection in five strands has been copies of a generated text with a fraction of its characters replaced — three numbers, one dial. Here is one that was not — twelve essays, eight source modules, ten revisions of one file — measured beside the model of it.
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.
A million characters of the same thing
Every measurement this collection has published about real text was taken on twenty-four thousand characters, because the phrase count was quadratic. It is linear now, so here is the same corpus at forty times the size — and what forty times does to its own numbers.
The half of a fall that is the logarithm
Phrases per character on a real collection of essays fall by a factor of 2.34 as it grows. A shuffle of the same characters falls by 1.70. Nearly three quarters of the movement is arithmetic, and no definition of the measure says so.
A bit for every bit
A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.
What repetition is worth once the logarithm is gone
On prose, nearly three quarters of the fall in phrases per character with size is arithmetic that any text pays. On a collection built of copies it is a fifth, and what is left is a factor of three that is genuinely the arrangement.
The array is the length distribution
The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.
The tree the operation insists on
The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small.
A code word is at least one bit
A wavelet tree of plain vectors reaches the entropy by its shape, and a Huffman code word cannot be shorter than one bit. On a collection whose document array has an entropy of 1.69 the tree costs 1.98, and the gap is a floor rather than an inefficiency.
The index that does not notice
Three compressed indexes over the same characters. One is flat at six and a half bits a character however many copies the collection holds; the other two fall by factors of five and six. At one copy the two that fall are the largest of the three.
A saving quoted without its collection
A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.
Named alongside it
The objects these essays reach for when they reach for this one.
Index sizeWavelet treeMeasurementRepetitionAlphabetBurrows-wheeler transformContext modelControlDocument collectionPermutationPhrase countSelf-index