A saving quoted without its collection

The obvious check on a compressed document array is that it is smaller than the plain one. It is a bad check and the way it fails is instructive.

A plain document array costs n⌈log₂ d⌉ bits — a ceiling, because a symbol has to fit in a whole number of bits. A wavelet tree costs n·H₀ plus directories, and H₀ is not rounded.

So on a collection of thirty-three equal-length documents the plain array costs six bits a symbol and the entropy is 5.044. The check reports a saving of 15.9%, and the collection has no redundancy at all: its document array is a uniform sequence over thirty-three symbols and no coding of any kind can compress it.

What the check is really about #

The claim being tested is that a frequency-shaped wavelet tree exploits the unevenness of a collection’s document lengths. A saving that appears on a perfectly even collection is not that.

So the check has to be two-ended. It must confirm that an uneven collection compresses and that an even one does not, and the second half is what a naive size comparison cannot supply.

The rejection test built for this feeds it both. The equal-length collection must report a ratio above 0.9 — essentially no saving — and the dominated collection must report one below 0.6. Measured: 1.000 and 0.395, a spread of 2.53.

A check that only asked for the second would pass on the rounding. A check that only asked for the first would be satisfied by a structure that compresses nothing.

There is a sharper way to say what has gone wrong in the naive check, and it makes the repair obvious. The check compares a compressed size against an implementation — the plain array with its rounding — rather than against the information the array holds. Any comparison against an implementation measures the implementation’s inefficiencies as well as the compression’s gains, and here the implementation’s inefficiency is a whole bit a symbol whenever d is just above a power of two.

The same trap is available anywhere a plain representation rounds. A packed text over a twenty-one symbol alphabet spends five bits a character where the entropy is 4.2, so a compressed text reported against the packed one is credited with 0.8 bits a character of rounding before it does anything. An index larger than what it indexes is where this collection first started reporting sizes against a stated base for exactly this reason.

Why the document count was chosen to be a power of two #

Every measurement in this strand uses d = 32, 64 or 128, and that is not an aesthetic preference.

At a power of two the ceiling is exact: ⌈log₂ 32⌉ = 5 = log₂ 32. So the plain array’s cost and the entropy’s ceiling are the same number, and a saving reported against the plain array is a saving against the entropy’s ceiling. The rounding contributes nothing and cannot be mistaken for a result.

At d = 33 the ceiling contributes 0.956 bits a symbol of pure rounding — 19% of the plain array — and any measurement taken there has that baked in.

That is a small methodological choice with a large effect, and it is the kind of thing that would not appear in a paper’s method section. It belongs in this collection’s because the alternative is a plate whose headline number is a ceiling function.

There is a second reason a power of two is the right choice and it has nothing to do with rounding. At d = 32 a balanced code is exactly five bits for every document, so the balanced tree and the plain array cost identically and the comparison between tree shapes — the smaller tree hands it back unsorted — is a comparison of shapes rather than of shapes plus a rounding. Two measurements in this strand depend on that and neither would be clean at d = 33.

The cost of the choice is that no collection in this strand has a realistic document count. Real archives have 47 documents, or 1,203, or 8,891. Every number reported here is at a count chosen for the instrument, and a reader applying them to a real collection should add the rounding back: up to a full bit a symbol on the plain array, and nothing on the entropy.

The general form #

This is an instance of a rule this collection has arrived at from three directions now, and the third is the one that named it.

A sixth of what, exactly found a saving reported as “about a sixth of the second index” that is 14.0% at one sampling rate and 30.5% at another, and made the general argument: a quoted share carries what it is a share of. Sixteen per cent of a structure at one setting is fourteen at another and thirty at a third, and a number without its denominator is a number about nothing.

Here the denominator is not a setting but a collection property, and the failure mode is different in a way worth marking. A share quoted without its sampling rate is a share of an unstated thing. A share quoted without its collection is a share of a thing that may have no redundancy in it at all — so the number is not merely underspecified, it may be measuring a rounding.

The null case’s behaviour under scaling is itself a check. If the equal-length collection’s ratio drifted from 1.000 as d grew, something in the measurement would depend on the document count in a way the argument says it should not. It stays at 1.000 at thirty-two, sixty-four and a hundred and twenty-eight, which is what “by construction” should look like when it is true.

The three numbers a compression figure needs #

Reporting a document array’s compression honestly takes three numbers rather than one.

The entropy of the length distribution, which is what the array can be compressed to. Computable from a list of file sizes.

The ceiling, log₂ d, unrounded. The difference between it and the entropy is the saving that exists.

The plain array’s cost, ⌈log₂ d⌉, which is what is actually paid today and which includes the rounding.

A saving quoted against the third and not the second is a saving that includes the rounding. On the collections in this strand, at a power-of-two document count, the two are the same and the distinction does not arise — which is exactly why the choice of d mattered.

What a null result is worth #

The equal-length collection reporting exactly 1.000 is the most useful number in this strand, and it is worth saying why a result of “nothing happened” earns a place.

It bounds the claim. A reader who knows the array compresses to 40% on one collection and 100% on another knows the range, and knows that the property being exploited is the length distribution rather than anything about the text. A reader given only the 40% would reasonably conclude that document arrays compress, full stop.

It identifies the mechanism. If the saving came from anything other than the length distribution — from the text, from the suffix order, from the document count — the equal-length collection would still show some of it. It shows exactly none, which is a strong statement about where the redundancy is.

And it makes the check possible. A two-ended check needs an end where the answer is no, and a collection that is guaranteed to have no redundancy is that end. Without it the check is one-sided and cannot reject.

There is a fourth number some readers will want and it is worth explaining why it is not on the list: the measured size of the built structure. It is the honest total — payload plus directories plus code table — and it is what a system pays. It is not on the list because it answers a different question. The three above say how much redundancy exists and whether a representation reached it; the fourth says what the whole object costs, including machinery that has nothing to do with compression.

Mixing them produces the claim this strand had to correct twice: a wavelet tree over an equal-length collection’s document array is twenty per cent larger than the plain array, and reporting that as “the compression is negative” would be true of the object and false of the compression. The directories are not a failure of the coding.

The two failures a single number hides #

Two different things can make a reported saving wrong and they need separating.

Overstating, which is the rounding above: a saving that is a ceiling function reported as compression.

Understating, which is the floor: on a collection whose array has an entropy of 1.69, a plain-vector tree costs 1.98 because a Huffman code word is at least one bit. A code word is at least one bit is where that is measured, and a check requiring the tree to reach the entropy fails there — correctly, and for a reason that has nothing to do with the collection being incompressible.

So a saving figure can be too high because of a ceiling and too low because of a floor, and the two are in different places. The first is in the comparison; the second is in the structure.

The repair for the first is to compare against the unrounded ceiling. The repair for the second is to use a bound the structure actually satisfies — Gallager’s L < H + p + 0.086 — rather than loosening a tolerance until the failure stops.

The tolerance that would have been fitted #

That second repair is worth a paragraph on its own, because the wrong version of it was written first.

The check asked whether the tree’s payload was within three per cent of n·H₀. On three collections it passed. On the dominated one it failed at 17.1%, which is a correct measurement of a real gap.

Widening the tolerance to twenty per cent makes the failure go away and makes the check useless: a tree twenty per cent over the entropy is a tree whose code could be badly built, and the check would accept it.

A tolerance chosen so that the data passes has been fitted to the data, and a fitted tolerance cannot reject anything. This collection has hit that shape before from the other side — a sixth of what, exactly records a rejection test that required two ends of a dial to differ by a factor of three when they differ by 2.19, where the check was wrong and the measurement was the finding.

Both times the repair was to state a claim the structure genuinely satisfies. Neither time was it to widen a number until the red went away.

The rejection tests this strand ships #

Three checks came out of the strand and they are worth listing together, because each one exists to catch a different way of being wrong about a size.

The saving needs its collection. Feed the check an equal-length collection and a dominated one and require them to differ by a factor of two — 1.000 against 0.395. A structure that compressed both, or neither, fails.

The tree meets Gallager’s bound rather than the entropy. Feed it four collections and require the payload to sit between n·H₀ and n(H₀ + p + 0.086). A tree under the entropy is impossible and indicates a measurement error; one over the bound indicates a badly built code.

The apparatus still holds no range structure. Ask the descent index for a chain listing and require it to fail. An object that kept the arrays and promised not to read them would have the same size as one that uses them, which is the failure what the chain cost named and which this strand has now had to guard against three times.

The third is the odd one out and it is the one this collection reaches for most often. Two of the three checks are about arithmetic and one is about an object being what it says it is, and the second kind is the one a size measurement cannot catch on its own — a structure that reports a small size while holding a large array reports a small size.

What a reader should ask #

Three questions, and any compression figure for a document array that does not answer them is not usable.

What is the collection’s length distribution? Uniform means no saving exists. The more skewed, the more there is.

Is the document count a power of two? If not, part of any reported saving is a ceiling function, and the part is up to log₂((d+1)/d) of a bit — which at small d is most of it.

Was the saving measured against the plain array or against the entropy? Against the array includes the rounding; against the entropy does not.

None of those needs the index to exist, which is the useful property. All three are answerable from a directory listing and a document count, before anything has been built, and they determine whether the compression is worth its directories.

Where the collections came from #

One more thing has to be said about the four collections, because a rejection test is only as good as the objects it is fed and these were constructed.

Each is thirty-two documents totalling about eight thousand characters, differing only in how the characters are apportioned: equal, one over rank, an eight-to-one two-mode split, and one document holding four fifths. The texts are drawn from the same source, so the character frequencies and the alphabet are common to all four.

That construction is deliberate and it is what makes the comparison clean: the only thing varying is the length distribution, which is the thing the claim is about. A set of four real collections would vary in a dozen ways at once and could not separate the mechanism.

The cost is that none of the four is a real collection, and the numbers are therefore about a mechanism rather than about a corpus. A corpus that was not generated is where this collection’s discomfort with that trade is recorded, and the resolution it settled on applies here: use constructed objects to isolate a mechanism and real ones to find out whether the mechanism matters.

Which real collections have skewed enough length distributions for this to be worth anything is a question this strand does not answer. A directory of source files is roughly log-normal, which by the arithmetic above gives an entropy deficit of about a bit — so around 17% off the array, on a structure that is now the whole apparatus.

What this does not license #

The check above is about a size, and there is a second reason to put the document array in a wavelet tree that the check has nothing to say about.

The tree answers the listing query. The tree answers the question is that argument, and it is what removed the range minimum — 186,000 bits on the collection measured, against an array that got 21,000 bits larger.

So on a collection where the size check reports no saving at all, the representation is still worth taking, and the accounting that says so is not the one this essay is about. A structure can be justified by a capability it buys rather than by bits it saves, and a check that only tests the bits will call it a regression.

That is the last thing a compression figure needs and it is the one hardest to put in a number: what else the representation does.

The same point cuts against a check as well as for one. Two tree shapes over the same array differ by sixteen per cent in size and by whether the answer comes back sorted, and a check comparing sizes will pick the smaller one every time. It is the right pick for a full answer and the wrong one for a truncated answer, and nothing about the size says which case the caller is in.

So the honest state of this apparatus’s checking is that the arithmetic is guarded and the capabilities are not. A structure could shed a property a caller depends on and every size check in the strand would report an improvement.