The array is the length distribution

The document array is one symbol per row of the suffix array, saying which document that row’s suffix belongs to. It is n⌈log₂ d⌉ bits stored plainly, and on a collection of any size that is a substantial array — the same width as the text over a σ-symbol alphabet whenever d and σ are comparable.

The question of how far it compresses has a complete answer, and the answer is not a measurement of the array. It is a measurement of the collection.

Each document appears in the array exactly as many times as it contributed characters to the collection. So the array’s symbol distribution is the collection’s length distribution — not approximately, not in expectation, but by construction and to the character. Whatever a zeroth-order coder can save on the array is whatever the length distribution’s entropy is below log₂ d, and that quantity is computable from a list of file sizes before anything is built.

The null case, measured #

On a collection of thirty-two equal-length documents the entropy of the document array is 5.000 bits a symbol. The ceiling, log₂ 32, is 5.000.

A Huffman-shaped wavelet tree over that array costs 40,960 bits. The plain array costs 40,960 bits. The compression is exactly nothing, to the bit, and there is no coder that would do better — the sequence has no zeroth-order redundancy of any kind.

That is worth measuring rather than mentioning because the equal-length collection is the one everybody pictures. A benchmark cut into fixed-size blocks, a set of records of one format, a corpus divided evenly for parallel processing: all of them have a uniform document array, and all of them are cases where an entire strand of compression buys zero.

It is also worth measuring because a check that only asked “is the wavelet tree smaller than n⌈log₂ d⌉” would pass whenever d is not a power of two, on the rounding alone. At d = 33 the plain array costs six bits a symbol and the entropy is 5.044, so a “saving” of 16% is reported for a collection that has no redundancy at all. A saving quoted without its collection is the rejection test that catches exactly that.

There is a further consequence of the null case that is easy to miss and decides whether the strand is worth anything at all. If the document array cannot be compressed on a uniform collection, then on a uniform collection the entire last step of this apparatus — putting D in a tree — is a cost rather than a saving, because the tree carries directories the plain array does not. The step is still worth taking, because it removes the range minimum, but the size argument for it is void and the query argument is the whole of it.

That is a different claim from the one this strand opened with, and it is the honest version. The last array in the apparatus reported the apparatus falling to 14.3% of the published one; on an equal-length collection the same comparison holds, and the fall is entirely the range minimum going rather than the array shrinking.

Where the saving actually is #

Real collections are not equal-length, and the departure is the whole of what there is to win.

Lengths falling as one over rank — the shape a directory of real documents tends to have, with a few long ones and a tail of short ones — gives an entropy of 4.15 against a ceiling of 5.00. The array falls to 83% of plain.

A few long documents and many short ones, at an eight-to-one ratio, gives 4.31 and 87%.

One document holding four fifths of the collection gives 1.69 and 40%.

So the range across realistic shapes is a factor of two and a half, and the extreme case is where the array nearly vanishes. That is not a coincidence: a collection dominated by one document is a collection where most rows carry the same symbol, and a code that spends one bit on the common symbol and many on the rare ones is exactly what a frequency-shaped tree is.

It is worth writing the extreme out, because it shows where the bound goes. A collection of d documents where one holds a fraction p of the characters and the rest split the remainder evenly has an entropy of H(p) + (1 − p) log₂(d − 1), where H is the binary entropy. At p = 0.8 and d = 32 that is 0.72 + 0.2 × 4.95 = 1.71, and the measured figure is 1.69 — the small gap being that the collection’s small documents are not exactly equal.

That closed form says something useful about which direction to look. The second term dominates unless p is near one, so a collection with one large document and many others is not especially compressible; it is a collection where the large document’s share is genuinely most of the text that wins. At p = 0.5 with thirty-one others the entropy is 3.5, which is 70% of the ceiling — a modest saving for a very lopsided-sounding collection.

Why the shape is enough, without a compressed vector #

The mechanism by which a wavelet tree reaches this bound is worth being explicit about, because it is often attributed to the wrong part of the structure.

A wavelet tree over a sequence, shaped by a prefix code, stores one bit per symbol per level of that symbol’s code. A symbol whose code is three bits long contributes three bits, once for each level its path passes through. Summed over the sequence, the tree’s total payload is Σ nᵈ · |code(d)| — the weighted path length of the code, which for a Huffman code is within a bit a symbol of the entropy.

That needs no compressed bit vector. Plain vectors, one bit per bit, and the right shape are the whole of it.

This is the opposite of the situation with the Burrows–Wheeler transform, where the shape buys nothing — the transform is a permutation, so its zeroth-order entropy is the text’s — and the compressed vector is what buys everything. Rank is the only thing it does is where that split was measured for the transform, and the document array is the mirror case: the shape does the work and the vector adds a little on top.

The reason for the difference is that the document array’s redundancy is zeroth-order. Its symbols are unevenly frequent and that is all. The transform’s redundancy is in its runs, which is a higher-order property that a frequency-shaped code cannot see.

What the tree costs beyond the entropy #

Two terms sit on top of the payload and both are in the o(n) that “n·H₀ + o(n)” hides.

The rank directories are the superblock and block counters that make a rank on each level constant-time. On this collection they are about 20% of the payload, and the share is remarkably stable across the four length distributions — 19.5%, 20.7%, 20.9%, 23.3%. That stability is not surprising: the directory is a function of the vector’s length rather than of its contents, and the levels’ total length is the payload.

The code table is one code length and one symbol per document, so d(2⌈log₂ d⌉) bits — a hundred and sixty bits per document at d = 32, which is negligible until d gets into the thousands and then is not.

So the honest figure for what the array costs is the payload plus a fifth, and on the equal-length collection that means the wavelet tree is 20% larger than the plain array. The compression is negative in the null case once the machinery is counted, which is the second reason the null case has to be drawn.

The distinction generalises past these two arrays, and it is a useful thing to carry when meeting a new sequence. Ask whether the redundancy being exploited is in the symbol frequencies or in their arrangement. Frequencies are what a code shape captures and what a plain-vector wavelet tree therefore captures for free. Arrangement is what a compressed vector, a run-length encoding or a copy-based parse captures, and no code shape reaches it.

The document array’s redundancy is frequency. The transform’s is arrangement. A collection’s own text has both. Three sequences in one structure, each wanting a different mechanism, which is why a single number for “how compressible is this index” has never been available here.

Two collections that look the same #

The four distributions above are constructed, and it is fair to ask whether the spread between them is an artefact of construction. It is not, and the reason is that the construction is exactly what a collection builder does.

A collection of d documents totalling n characters can have any length distribution summing to n. Nothing about the text constrains it. So two collections with identical texts, identical alphabets, identical entropies and identical document counts can have document arrays differing by a factor of two and a half in size, and the only thing separating them is a list of d integers.

That is a stronger version of the point a collection is a construction makes about boundary placement. There the separating quantity was the characters immediately before d positions; here it is the d lengths themselves. Both are properties of the partition rather than of the bag of characters, and both decide a size that a corpus description does not mention.

That framing also settles a question about which tree shape to use, at least on the size axis. A balanced tree spends ⌈log₂ d⌉ bits on every symbol regardless of frequency, so it costs exactly what the plain array costs and the whole saving is forgone. A Huffman-shaped tree spends the code length. On the one-over-rank collection the two are 49,593 bits and 41,589 — a 16% difference, which is the entropy deficit reappearing as a size.

So on the size axis the frequency-shaped tree wins by construction and there is nothing to weigh. What makes it a choice at all is the order the answer comes back in, which is a separate axis entirely and is the smaller tree hands it back unsorted.

The two shapes a real collection has #

It is worth being concrete about which of the four rows a reader is likely to be on, because the answer is usually the same one.

A collection of files in a directory — source code, documents, images’ metadata, log files — has lengths that are approximately log-normal, which for the purposes of an entropy is close to the one-over-rank row. Expect around 80–85% of plain.

A collection of records in a fixed format — rows of a table, fixed-length keys, protocol messages — is close to equal, and expect nothing.

A collection with one dominant member — a large document with a set of small annotations, an archive with one big file — is the fourth row, and the saving is large.

A collection cut into fixed-size blocks by an indexing system is exactly equal by construction, and the saving is exactly zero. That case is worth flagging because it is what happens to a collection on its way into an index, and a system that fragments its input into uniform blocks has destroyed the only redundancy the document array had.

One collection shape is missing from those four and is worth naming because it is common and behaves differently: a bimodal collection, where documents come in two sizes with nothing between. An archive of large data files and small manifests, a corpus of articles and their abstracts, a repository of source and tests. Its entropy is a mixture and its deficit depends on how the mass splits between the two modes rather than on either mode’s size.

The “a few long, many short” row above is a two-mode collection at an eight-to-one ratio, and its entropy of 4.31 against a ceiling of 5.00 is a 13% saving. Push the ratio and the saving grows; push the count ratio the other way and it shrinks. Neither the mean length nor the median predicts it, which is the reason a distribution rather than a summary is what this measurement needs.

What scaling the document count does #

Raising d raises the ceiling by log₂ of the factor, and the four rows respond differently.

The equal-length row rises exactly with the ceiling, always and by construction. Its saving stays at zero at every d.

The one-over-rank row gains nearly the whole increase, because quadrupling the document count quadruples the number of small documents and the distribution’s shape is preserved — a one-over-rank distribution is scale-invariant in the relevant sense.

The dominated row gains almost nothing, because its entropy is decided by the one large document and adding more tiny ones changes very little.

So the absolute saving — the gap between entropy and ceiling, times n — grows with the document count on every collection that is not uniform. That is the direction a reader wants, because the plain array is also getting wider, and it means the compression is worth most on the collections where the array is largest.

What this settles and what it does not #

It settles the size question completely: the document array’s compressibility is the collection’s length distribution’s entropy deficit, computable from a list of file sizes, with no measurement of the text required.

It does not settle the cost question, because a wavelet tree over the array is not merely a smaller array — it is a structure that answers different questions than an array does. The tree answers the question is where that becomes the point: the same tree that compresses D also enumerates the distinct symbols of an interval, which is the listing query, which removes the range minimum.

So the saving measured here is the smaller half of what the representation is worth. A collection getting 17% off its document array would probably not bother; a collection getting 17% off its document array and removing an entire range-minimum structure is a different proposition.

And it does not settle the floor, which is the subject of the next essay. A Huffman code word is at least one bit, so a plain-vector tree cannot cost less than n bits however low the entropy goes — and the dominated collection’s entropy of 1.69 is already close enough to that floor for the gap to be visible.

A collection that fragments its input into uniform blocks has also, incidentally, destroyed the property a collection is a construction found deciding the boundary cost: arbitrary block boundaries end at arbitrary characters, so the run count pays about a run per block on top of the array saving nothing. Two costs, from one decision, neither of them mentioned when the decision is made.

Where this sits against the earlier measurement #

This collection has met the length distribution once before, in a different role, and the two results are worth putting side by side.

Documents that are not the same length asked what uneven lengths do to a listing — whether a collection with one dominant document changes the cost of finding which documents hold a pattern. The answer there was about the query’s work.

This asks what the same distribution does to a size, and the answer is exact rather than empirical: the array’s entropy is the distribution’s entropy, full stop. There is no modelling step, no fitting, and no measurement of the text.

That exactness is rare in this collection and it is worth saying why it happens. Most size questions here need a measurement because they depend on a property of the text that has no closed form — the run count, the phrase count, the copy depth. This one depends on a property of the partition, and a partition is a list of integers whose entropy is arithmetic.

The general form is worth carrying because it says which measurements can be skipped. A quantity that depends only on the collection’s metadata — its file sizes, its document count, its alphabet — can be computed. A quantity that depends on the collection’s content has to be measured. Every size in the listing apparatus is now in the first category, and every size in the index below it is in the second.

The number to compute first #

The practical form is one line and it needs no code.

Take the collection’s file sizes, normalise them to a distribution, compute −Σ p log₂ p, and compare against log₂ d. The difference, times n, is the number of bits a compressed document array will save, to within Huffman’s redundancy and the directories.

If that number is zero the collection is uniform and the representation buys only the query. If it is large the collection is dominated by a few documents and the representation buys both. Either way the answer is available before any index exists, and it is a property nobody has to measure the text to obtain.