The collections the saving was quoted for

The array is the length distribution found that a document index’s document array, one entry per character naming the document it came from, holds exactly one symbol distribution: the collection’s document lengths, weighted by characters. A wavelet tree shaped by document frequency stores the array in about the zeroth-order entropy of that distribution, and nothing about the text inside the documents changes it. On thirty-two documents of equal length there is nothing to save. On thirty-two where one holds four fifths of the text, most of the array goes.

A saving quoted without its collection then caught a check reporting a saving of sixteen per cent on a collection that had none. The plain array spends ⌈log₂ d⌉ bits a symbol, and whenever the number of documents is not a power of two, any code that spends log₂ d or less passes a comparison against it on the rounding alone. It closed by admitting what its four collections were: constructions, chosen to isolate a mechanism, none of them real. It guessed at what a real one would give. A directory of source files is roughly log-normal in its sizes, which by the arithmetic of entropy puts its array about a bit below log₂ d, “so around 17% off the array”. This page checks the guess on real collections.

The collections, and why lengths are enough #

Six real collections are measured, all frozen so the numbers do not drift. A project’s source files: every JavaScript file of one mid-sized project at one version, 222 of them, by size in bytes. The paragraphs of three fixed corpora kept for measurement — a corpus of essays, one of technical writing, and one of revisions of a single document — 522, 179 and 30 paragraphs. And the essays and technical corpora taken whole, 12 and 8 documents.

Nothing needs to be indexed to measure the array, because the array’s symbols are its lengths. The plain array costs ⌈log₂ d⌉ bits a symbol. The entropy of the character-weighted length distribution, H0, is what a perfect code would spend. A Huffman-shaped tree spends Σ L·|code| over the whole collection, at most a bit a symbol above H0. The earlier pages checked that identity on built indexes: the tree’s levels hold exactly the Huffman code’s bits. Here it is applied to lengths read off real collections.

The gap between the plain array and a frequency-shaped one has two parts that the earlier page separated and the estimate did not. The rounding, ⌈log₂ d⌉ − log₂ d, is what any code saves by not rounding the document number up to whole bits, and it needs no model of the collection at all. The skew, log₂ d − H0, is what the length distribution adds, and only a code that knows the lengths collects it.

About a tenth, not about a sixth #

On the project’s 222 source files the frequency-shaped array is 10.5% smaller than the plain one. The skew of their sizes is worth 0.66 bits a symbol, not about one, and a fifth of the saving, 0.21 bits, is the rounding of eight bits down to log₂ 222. The estimate’s number, 17%, was a skew of about a bit against eight bits a symbol and nothing else. The real directory’s skew is two thirds of that, and it saves a tenth, not a sixth.

The other collections make the split plain. The paragraphs of the essays corpus save 11.5%, and almost all of it is rounding. 522 paragraphs sit just above 512, so the plain array spends ten bits where 9.03 would do. Their lengths are skewed by 0.21 bits, a fiftieth of the array. The whole essays, twelve of them, save 9.1%, and every bit of it is rounding, since twelve essays of nearly equal length have almost no skew at all. A check that compared the frequency-shaped array with the plain one on either collection would report a healthy saving and be reporting the document count.

Only the revisions corpus, cut into its thirty paragraphs, approaches the estimate: 16.5%, nearly all of it skew. It is also the smallest real collection, and its paragraphs include whole sections of a document revised many times.

What the lengths look like #

The source files run from 377 bytes to 264,023, a factor of 700, and the middle half of them spans a factor of only 2.4. That is the shape of a log-normal distribution with a modest spread: a few very large files, a few very small ones, and most within a factor of two or three of the median. The essay paragraphs look the same at a smaller scale, from 14 characters to 984, with a middle half spanning 2.5. The extremes are what a reader notices in a directory listing. The middle is what decides the entropy, and the middle is narrow.

A corpus that was not generated recorded this collection’s unease about measuring mechanisms on constructed data, and the settlement it reached: constructed objects isolate a mechanism, real ones say whether it matters. The four constructed collections were chosen to span the range the mechanism can take, from nothing to most of the array. Real collections do not span it. They sit in a narrow band near the bottom.

The log-normal arithmetic, checked #

For log-normal lengths the arithmetic is exact in the limit: if the natural logarithms of the lengths spread with standard deviation σ, the character-weighted distribution falls short of log₂ d by $\sigma^2/(2 \ln 2)$ bits. The source files’ σ of 0.90 predicts 0.58 bits, and they fall short by 0.66. The estimate’s “about a bit” needs σ near 1.2, the spread of a directory whose middle half spans a factor of five. This one spans 2.4.

The formula comes from one observation about weighting. The document array counts each document once per character, so a document twice as long appears twice as often, and the distribution the array’s entropy is taken over is the length distribution tilted towards long documents. For log-normal lengths that tilt moves the mean of the logarithms up by $\sigma^2$ and leaves their spread alone. The plain array is a code for the untilted, uniform choice of a document, and the gap between the two is the information the tilt adds: half of $\sigma^2$ in natural units, $\sigma^2/(2 \ln 2)$ in bits. Nothing in it depends on d, which is why the formula is a limit. A small collection rarely contains the long documents that carry the tilt.

The paragraph collections fall short by less than the formula predicts, and the reason is the shape of their logarithms. The essays corpus’s paragraph lengths lean left: 41 of its 522 paragraphs are very short, headings and one-line transitions, and they widen σ while holding 1.5% of the characters. The deficit is set by the characters, so paragraphs that barely hold any hardly move it, while σ counts each paragraph once. On the technical paragraphs the lean is milder and so is the overstatement. A formula fitted to the spread of document counts is answering a different question from the one the array asks.

Fewer files, the same files #

Drawn eight at a time, the source files fall 0.44 bits short of log₂ d. All of them fall 0.66 short, and the saving moves the other way, from 13.0% at eight files to 9.0% at 128. A small sample of a skewed distribution rarely includes its largest members, so its deficit is smaller, and the formula’s value is a limit approached as the directory grows. The saving is a share of ⌈log₂ d⌉ bits, and that denominator grows with d while the deficit levels off. So the same files, in a directory of a different size, would be quoted at a different percentage.

The revisions corpus’s thirty paragraphs show the effect from the other side. Its skew of 0.76 bits is the largest of any real collection here, and it comes from a collection small enough that one long section is a large share of the whole. Thirty paragraphs is where the constructed collections lived, at thirty-two documents, and it is where the most striking savings are found, because a small collection can be dominated by one member in a way a large one rarely is.

That is the earlier page’s warning in a new form. It found a check passing on the rounding whenever d was not a power of two. Here even the part of the saving that is real depends on d, falling as a share as a collection grows. A sixth of what, exactly found the same dependence in a reverse half’s saving, which was a different fraction at every sampling rate. A percentage quoted without its collection’s size, and without separating what the rounding gave, cannot be carried to another collection.

The rounding, taken without a model #

The rounding is real bits, and a plain array can take it back without knowing anything about the lengths. It spends ⌈log₂ d⌉ bits on every entry because it stores each document number on its own. Store them in groups instead, k numbers as one integer below d^k, and each group needs ⌈k log₂ d⌉ bits. For the 522 essay paragraphs that is ten bits a symbol one at a time, 9.33 in groups of three and 9.13 in groups of eight, against log₂ 522 = 9.03. Grouping by eight takes back nine tenths of the rounding, about 9% of the array, with no model of the collection at all, at the price of decoding a group to read one entry.

For the 222 source files grouping does less. Log₂ 222 is 7.79, so groups of up to four still need eight bits a symbol, and groups of five reach 7.80. The rounding there was a fifth of the saving, and grouping by five takes almost all of it. For thirty paragraphs, log₂ 30 = 4.91, and no group of eight or fewer gets under five bits. Whether the rounding can be taken cheaply depends on how close d lies to a power of two, which is the earlier page’s point turned around: a power of two leaves nothing to round, and a number just above one leaves almost a whole bit.

A frequency-shaped tree takes the rounding and the skew together, and a code word is at least one bit found the price: a Huffman code cannot spend under one bit a symbol, which on these collections costs 0.03 to 0.06 bits above the entropy. Grouping the plain array costs no model and no redundancy, and gets only the rounding. The skew, the part that is about the collection, needs the shape.

How concentrated the characters are #

The largest fifth of the project’s source files hold 56.5% of its bytes. The largest fifth of the essay paragraphs hold 35.1% of their characters. Both sit between the diagonal of equal lengths and the constructed collection with lengths falling as one over rank, which held 63.9% in its largest fifth. Source files are more concentrated than prose paragraphs. A handful of large modules hold much of a project’s text, where no paragraph can run to many times the median without becoming a section. But neither comes near the constructed collection with one document holding most, whose largest fifth held 84.2%.

A curve like this is what a system would want to see before it relied on a document array’s saving, and it is cheap: one pass over the lengths. The entropy that decides the saving is the same pass, and the rounding needs only the count.

Real collections beside the constructed ones #

Every real collection falls between the constructed collection of equal lengths and the one with lengths as one over rank, 0.005 to 0.76 bits short of log₂ d against 0.85; the constructed collection with one document holding most falls short by 3.31, a shape nothing real here approaches. The four constructed collections were right to span the mechanism’s range. The measurement said what the range is. They were not a sample of what collections are like, and the one that produced the most dramatic plate is the one farthest from anything measured here.

The model is the compressor found five correct entropies for one stream, each a floor under a different model. The document array has one model, the length distribution, and one floor. What these collections show is where that floor sits in practice: a fraction of a bit below log₂ d, rarely more.

What the saving is a share of #

The document array is, by the earlier pages’ accounting, the whole of the listing apparatus that is left. The apparatus three times smaller again took it from 839,000 bits to 120,000, and what remained was the one array that was ever information: the previous-occurrence chain went, the range minimum went, and the smaller tree hands it back unsorted measured what the frequency shape costs a listing query in sorting. So a tenth of the document array is a tenth of the apparatus that answers which documents hold a pattern. Beside the self-index that finds the occurrences, it is smaller again: on a collection where every character is indexed, the document array is one symbol per character of a few bits, where the self-index is several bits per character on its own.

That puts the real collections’ saving in proportion. On the project’s source files, coding the document array by its lengths would save about a tenth of a structure that is itself a fraction of the index. It is worth doing, since it costs one pass over the lengths and changes nothing about the answers. It is not the change that decides whether a document index is small, and an estimate of a sixth made it sound closer to that than it is.

The limits of the measurement #

Six collections, one project’s sources. The source files are one project’s, written in one style by one set of habits. A directory of vendored libraries, generated code or data files would be more skewed, and a directory of small tests less. The measurement says what these collections give. It does not say what directories give in general.

Lengths, not indexes. The saving is computed from the lengths by the identity the earlier pages checked on built indexes. No document index over these collections was built, and the tree’s rank directory, which adds the same share to every shape, is not counted.

Bytes for characters. The source files are measured in bytes and the corpora in characters. A file with many characters outside the basic Latin range has more bytes than characters, and a document array over its characters would see it slightly smaller than its size here. In these files those characters are a few typographic marks in comments, and the difference to any file’s share is under a per cent.

Paragraphs are one way to cut. The paragraph collections split each corpus at blank lines. Cut at sections, or at sentences, the same text would be a different collection with a different distribution, and the saving belongs to the cut as much as to the text.

Still open: a collection that grows by appending #

Every collection here is measured whole, and a real document collection changes. Documents are added, some large, most typical, and the array’s code has to follow its lengths or be rebuilt. The project’s source files grew from twenty to 222 over a few months, and their subsets show the deficit climbing as a directory grows.

The measurement that follows replays the same directory’s history, each file entering at the version where it first appeared and growing as it grew. It keeps a document array coded with the lengths as they stood at each rebuild, and charges each rebuild and each document added between rebuilds, which a code fitted earlier has to name with an escape. The prediction is that a code fitted once, when the directory held a quarter of its files, loses less than a tenth of a bit a symbol against one refitted at every version, because the log-normal shape of the sizes is set early and stays. It could fail if the large modules arrived late. Then a code fitted early would give them long codes, and the characters they hold would pay for it on every lookup.