A code word is at least one bit

A wavelet tree of plain bit vectors, shaped by a Huffman code over its symbols, costs the weighted path length of that code: each symbol contributes one bit per level of its own code word.

That is how the document array reaches its entropy without any compressed representation. It is also where it stops, and the stopping point is exact rather than approximate.

A Huffman code word is at least one bit. No symbol, however probable, can be given a shorter one, because a prefix code over two or more symbols has to distinguish them at the root. So the mean code length is at least one, and a plain-vector wavelet tree over n symbols cannot cost less than n bits — however low the sequence’s entropy goes.

Where the floor becomes visible #

On three of the four collections measured here the floor is nowhere near. Equal-length documents give an entropy of 5.00 and a tree of 5.00 bits a symbol; one-over-rank gives 4.15 and 4.17; a two-mode collection gives 4.31 and 4.34. In each case the tree is within seven tenths of a per cent of the entropy, which is Huffman doing what Huffman does.

On the fourth — one document holding four fifths of the text — the entropy is 1.688 and the tree costs 1.976. That is a gap of 0.288 bits a symbol, or 17.1% over the entropy, on a structure whose whole claim is that it meets it.

Seventeen per cent is not a rounding and it is not a defect. It is the code doing the best a prefix code can do on a distribution whose most probable symbol has probability 0.80.

It is worth seeing where the 0.288 comes from, because the arithmetic is short and it makes the floor concrete. The collection has one document contributing 6,595 of 8,207 characters and thirty-one others contributing about fifty-two each. Huffman gives the dominant document a one-bit code and the thirty-one others codes of length five or six. The mean length is 0.804 × 1 + 0.196 × 5.9 = 1.98, which is the measured figure.

The entropy is 0.804 × log₂(1/0.804) + Σ over the small documents, which comes to 1.688. The gap is entirely in the dominant symbol: the entropy says it should cost log₂(1/0.804) = 0.315 bits and the code charges 1. Four fifths of the sequence is being overcharged by 0.685 bits each, which is 0.55 bits a symbol averaged over everything — offset by the small documents being charged slightly less than their entropy, leaving 0.288.

So the floor is not distributed across the sequence. It is one symbol, the common one, paying a whole bit for something worth a third of one.

The bound that says how much #

Huffman’s redundancy has a bound and it is worth using rather than remembering, because it turns “the code is not optimal here” into a checkable statement.

Gallager’s result: for a Huffman code over a distribution whose most probable symbol has probability p, the mean code length L satisfies L < H + p + 0.086.

On the dominated collection p is 0.804, so the bound is H + 0.890 = 2.578 bits. The measured 1.976 is comfortably inside it. On the one-over-rank collection p is 0.246 and the bound is 4.48 against a measured 4.17. On the equal collection p is 0.031 and the bound is 5.12 against a measured 5.00.

So the check the strand runs is not “is the tree within three per cent of the entropy” — that check fails on the collection that matters and would have to be loosened until it tested nothing. It is “is the tree inside Gallager’s bound”, which holds on all four and which fails if the code shape is wrong.

That distinction matters because a loosened tolerance is a check that stops rejecting. The first version of this measurement asked for the tree to be within 3% of n·H₀ and failed on the dominated collection at 17.1%; the temptation is to widen the tolerance to 20% and move on, at which point the check would accept a tree built from a code that is genuinely bad.

The bound also says when the floor will bite, which is the useful direction. L ≥ H and L ≥ 1, so the tree is at the floor rather than at the entropy precisely when H < 1 — and by the bound it is within p + 0.086 of the entropy otherwise. Since H < 1 requires a symbol of probability above about 0.6, the rule is:

A document array whose most frequent document holds more than about three fifths of the collection will be at the floor, and one that does not will be at its entropy. That is a threshold on a number computable from file sizes, and it is the whole of the decision about whether a compressed vector is worth its directory.

The optimal code that is beaten is where this collection first met the gap between a code’s optimality and its performance, on a different sequence and for a different reason. The two results are complementary: there, a code that is optimal among prefix codes loses to one that is not a prefix code; here, a code that is optimal among prefix codes loses to a representation that does not code symbols separately at all.

What gets underneath #

The floor is a property of the shape, so getting under it needs a different mechanism — and the mechanism is the one this collection has already built for a different sequence.

Store each level’s bit vector in blocks, with each block represented by its class — the number of ones in it — and an offset saying which block with that class it is. A block that is all zeros has one possible offset, so its offset costs nothing. A level that is nearly all zeros is nearly all such blocks.

On the dominated collection the root level is exactly that: the dominant document’s code is one bit, so at the root four fifths of the bits are the same value. A plain vector charges one bit per bit and a compressed one charges the block entropy, which is H(0.8) = 0.72 rather than 1.

Measured: the plain tree costs 1.976 bits a symbol and the compressed-block tree costs 1.571, a factor of 1.26. That is below the one-bit floor and above the entropy, which is where a real structure should be.

The two mechanisms, on the same object #

That gives a clean statement of a division this collection has been circling for several strands.

The shape reaches the entropy down to a bit a symbol. A frequency-shaped tree of plain vectors costs the weighted path length, which Huffman minimises, and which is within p + 0.086 of the entropy. That is free — no extra structure, no extra operations, just a different set of code words.

The vector reaches below it. A block-classed representation charges the entropy of the block classes, which has no floor at one bit and which goes to zero on a constant vector. That costs a directory and a decoding step per rank.

Neither substitutes for the other. On a high-entropy sequence the shape does everything and the compressed vector adds a few per cent. On a sequence with a dominant symbol the shape hits the floor and the vector does the rest.

The document array is the first sequence in this collection where both matter on the same object at once, and the reason is that its distribution can be arbitrarily skewed — a property of the collection’s construction rather than of any text.

Raising the document count does not move the floor — one bit a symbol is one bit a symbol — but it does move three of the four entropies up, so the gap between them and the floor widens and the dominated collection stays where it is. That is the direction that matters for a real archive: adding more small documents to a collection with one large one leaves its array at the floor, because the large one still holds most of the characters and still gets a one-bit code.

So the floor is sticky in a way the entropy is not. A collection can grow its document count by a factor of four, watch its plain array get wider by two bits a symbol, and see its compressed array stay at almost exactly the same size, because the extra documents contribute few characters and long code words.

Why the transform is the other way round #

The comparison worth drawing is with the sequence this machinery was built for.

The Burrows–Wheeler transform of a text has, by construction, exactly the text’s character frequencies — it is a permutation. So a frequency-shaped wavelet tree over the transform costs n·H₀ of the text, which is what an uncompressed tree over the text itself would cost. The shape buys nothing. The transform that emits nothing is the measurement, taken to fifteen decimal places.

The bits a coder emits is where the difference between a code’s length and a source’s entropy first became a measurement here, and the model is the compressor is where the distinction between a code and the distribution it is built for became the subject rather than the setting. What the transform does is gather: it puts characters with the same right context together, which turns the text’s higher-order structure into runs in the last column. A run is invisible to a code shape and visible to a block-classed vector. So on the transform the vector does everything and the shape does nothing.

On the document array it is the reverse: the shape does almost everything and the vector adds a quarter on the one collection where the floor is reached.

Two sequences, one structure, opposite splits. That is why “a compressed wavelet tree” is not a single technique with a single benefit, and why a size quoted for one says nothing about the other.

One consequence of that reversal is worth stating because it corrects a habit. “Use compressed bit vectors” is offered as general advice for succinct structures, and on the two sequences measured here it is right about one and nearly pointless about the other. On the document array of an ordinary collection the compressed vector buys between four and six per cent, at the cost of several times the work per rank — a trade most systems would decline. On the transform it buys the difference between zeroth-order and higher-order entropy, which is most of what a compressed index is.

The advice that survives is narrower and checkable: use a compressed vector where the levels have long runs or a dominant value, and measure whether they do. Levels of a wavelet tree over a frequency-shaped code do not, except at the root of a skewed distribution — which is exactly the case above.

The floor in general #

Stated without the document array, the result is a small piece of coding theory that is easy to lose track of inside a data structure.

Any structure charging one unit per symbol per level of a prefix code has a floor of one unit per symbol. Wavelet trees are the obvious instance; so is any hierarchical partition of an alphabet where each level costs a bit. The floor is not about wavelet trees; it is about prefix codes, and it is the same floor that stops a Huffman coder compressing a source whose entropy is below one bit per symbol.

The standard remedy in coding is arithmetic coding, which does not emit whole bits per symbol and therefore has no such floor. Rank is the only thing it does is where that structure was priced in this collection. The structural analogue is the block-classed vector, which does not emit whole bits per position. Both work for the same reason: they stop insisting that each symbol be paid for separately.

That is a satisfying correspondence and it has a limit worth marking. An arithmetic coder gives up random access; a block-classed vector does not, which is why it is the one used here. The cost is a directory and a decode, and the decode is what makes a rank on a compressed vector several times the cost of a rank on a plain one.

What this changes about the apparatus #

The listing apparatus is now the document array and a descent over it, so the array’s size is the apparatus’s size, and the floor decides how small it can get.

On the three ordinary collections the answer is: as small as the length distribution allows, which is 83% to 100% of the plain array. On the dominated collection: 40% with the shape alone and 31% with compressed blocks.

Those are the numbers a reader should carry rather than a single figure. An apparatus that is “the compressed document array” costs somewhere between the plain array and a third of it, and where in that range is decided by the length distribution and then by whether the floor is reached.

The check that had to be written twice #

There is a methodological note here that belongs in the essay because the first version of this measurement was wrong in a specific way.

The check asked whether the tree’s payload was within a small tolerance of n·H₀. On three collections it passed and on the fourth it failed at 17.1%, and the failure was correct — the tree genuinely does cost 17.1% more than the entropy there.

Two repairs were available. Widen the tolerance until the fourth collection passes, which requires 20% and which then accepts any tree whose code is within 20% of optimal — a check that would pass on a badly built code and therefore checks nothing. Or replace the claim with one that is true, which is Gallager’s bound.

The second repair is more work and it is the one that leaves a check behind. A tolerance chosen to make the data pass is a tolerance that has been fitted to the data, and a fitted tolerance cannot reject.

This collection has hit that shape before from the other direction: a rejection test that measured the wrong end required two ends of a dial to differ by a factor of three when they differ by 2.19, and the check was wrong rather than the measurement. Here the check was wrong about which bound applies. Both times the fix was to state a claim the structure actually satisfies rather than to loosen one it does not.

Two floors, and only one of them is this one #

There is a second floor in the neighbourhood and conflating the two would be easy, so it is worth separating them.

This essay’s floor is one bit per symbol, and it comes from a prefix code needing to distinguish at least two symbols at its root. It binds when the sequence’s entropy is below one bit.

The other floor is on the whole structure and it is the directory. A wavelet tree of any shape needs rank directories on its levels, and those are a function of the levels’ total length rather than of their contents. On the collections here they are 19% to 23% of the payload, and on the compressed-block version they are a larger share still, because the payload has shrunk and the directory has not. So a structure whose payload goes to zero does not go to zero; it goes to its directory.

Those two are independent and both are real. The dominated collection’s tree at 1.571 bits a symbol with compressed blocks has a directory of about 0.35 bits a symbol on top, so its total is 1.92 — back above the plain tree’s payload, though below the plain tree’s total. That is the kind of accounting where a number quoted without saying whether the directory is in it can be off by a fifth, which is an index has a size applied one level down.

The general lesson is that a bound stated on a payload is not a bound on a structure. Every “n·H₀ + o(n)” in this field has an o(n) that is 20% at the sizes anybody runs, and a floor argument that ignores it is arguing about the smaller half.

What the floor means for a collection #

The practical consequence is one sentence and it is the kind of thing a system’s sizing calculation should include.

If the collection’s length distribution has an entropy below about one bit — one document holding more than about two thirds of the characters — the document array will not reach its entropy with a plain-vector tree, and a compressed representation is worth its directory. Above that, the shape is enough and the compressed vector adds a few per cent for a several-fold cost per rank.

The array is the length distribution is where that threshold’s input comes from, and the last array in the apparatus is where it stopped being one part of three and became the whole. That threshold is computable from file sizes, like everything else in this strand, and it decides a choice between two representations rather than a choice about whether to build anything.