The shape arrived early and the bytes late

The collections the saving was quoted for measured a document index’s document array on real collections. The array holds one entry per character, naming the document the character came from, and coded by document frequency it costs the entropy of the collection’s length distribution, weighted by characters. On one project’s 222 source files that came to a tenth smaller than the plain array of $\lceil \log_2 d \rceil$ bits a symbol. The files’ sizes were close to log-normal, with the logarithms spreading by a standard deviation of 0.90.

Every collection there was measured whole, and the essay’s closing section noted that real collections are not. The same directory had grown from twenty files to 222, documents added and documents growing. A document array’s code is fitted to the lengths it is built from. Rebuilt at every change it stays at the entropy. Kept, it must give a code word to every document it never saw, through an escape, and its old code words grow stale as documents change size. The section proposed replaying the directory’s history. It predicted that a code fitted once, when the directory held a quarter of its files, would lose under a tenth of a bit a symbol at the end against a code refitted at every version, because the log-normal shape of the sizes is set early and stays. It said the prediction could fail if the large modules arrived late.

The shape was set early, as predicted, and the prediction fails anyway. The large modules did not arrive late. What arrived late was most of the characters.

The replay, and two escapes #

The history has 47 versions, every one at which a source file was added, removed or resized, from the first with 20 files to the last with 222. The last version is exactly the collection the earlier essay measured. At each version the cost of the document array is computed from the file sizes alone, by the identity the array is the length distribution checked on built indexes: a code that gives document $i$ a code word of $\ell_i$ bits costs $\sum_i L_i \ell_i / \sum_i L_i$ bits a symbol.

Four codes are kept. Refitted at every version is a Huffman code built afresh from each version’s sizes, the best a code of this kind can do there. Fitted once is a Huffman code built at a chosen version over the files present then, plus one more symbol, an escape. A file added later is named by the escape’s code word followed by a balanced code over all files added since the fit, a subtree that needs no weights and grows by one leaf a file. A file present at the fit keeps its code word whatever its size becomes. The escape’s own weight has to be chosen at the fit, before anyone knows how much will be added. One version weights it as a single typical document, the collection’s mean size; the other weights it as the whole collection, which gives it a one-bit code word and budgets for the collection doubling. Subtree rebuilt is the second of these with the escape’s subtree rebuilt at each version as a Huffman code over the added files’ own sizes. That can be done without touching any entry the fit coded.

A tenth of a bit, missed by five to twenty times #

Fitted at 56 files, a quarter of the final 222, the fitted code costs 9.24 bits a symbol at the end with an escape weighted as one document and 7.67 with an escape weighted as the whole collection, against 7.16 for a code refitted there: losses of 2.08 and 0.50 bits, where the prediction was under 0.1. The first is worse than the plain array’s eight bits by more than a bit. The second is worse than the refitted code by half a bit, which is more than everything the frequency-shaped array saves on the plain one at the end, 0.84 bits.

The plate shows how the losses build. Just after the fit, every design but the refitted one starts above it: the escape has been given probability mass that nothing yet uses. A one-document escape costs little then, since one document among 56 takes about six bits of code space, but every file added later pays those six bits plus eight bits of balanced tail, fourteen bits a symbol for a file whose refitted code word would be seven or eight. As files arrive the cost climbs past the plain array’s, and is above it from 94 files on. A whole-collection escape takes one bit from every file present at the fit, so the old files start a bit worse off, and the added files pay one bit of escape and the balanced tail, eight or nine bits. It ends half a bit worse.

The shape was right #

The spread of the logarithms of the sizes is 0.88 at 56 files and 0.90 at 222: the shape the prediction relied on was set by the time the directory held a quarter of its files. The files present at 56 also kept their relative sizes. They grew, by 1.77 times in total over the rest of the history, but the logarithms of their sizes at 56 files and at 222 correlate at 0.81, and none of them was removed. A corpus that was not generated measured a real collection beside the model of it, because a generated one has whatever shape its generator chose. This real one’s shape is about as stable as a shape can be.

What the prediction did not separate is the shape from the identities. A code by document frequency is a code word per document, and the shape of the length distribution decides how long those code words are on average. It does not decide which documents get them. The files present at 56 hold 57% of the final bytes; the other 43% are in 166 files the fit never saw. Those characters have to be named somehow, and whatever the escape costs, they pay it.

The large modules arriving late would have been one way to fail, and it is not what happened. The five largest files at the end were all present at the fit, and the files added after it are smaller than the ones that were there, a median of 15.7 kilobytes at the end against 57.6. They are simply many. The prediction’s own failure condition was the right kind of thing, a statement about where the characters would be at the end, measured too narrowly.

Where the bits go #

With a one-document escape, the 166 added files cost 2.36 bits a symbol over the refitted code and the 56 old ones gain 0.29; with a whole-collection escape the old files lose 0.27 and the added files 0.23. The split shows what each escape is a bet on. A one-document escape bets that little will be added, keeps the old files’ code words short, and charges the added files fourteen bits a symbol. A whole-collection escape bets on the collection doubling, charges every old file a bit for the privilege, and names an added file in nine.

Rebuilding the escape’s subtree changes only the second half. The added files are then named by one bit of escape and a Huffman code over their own sizes, about as cheaply as a refit would name them, and their part of the loss becomes slightly negative, −0.10. The old files’ part, the bit the escape took from each of them, stays. The loss falls to 0.18 bits a symbol, and what is left of it is the escape’s tax on the files that were there first. A prefix code has a fixed budget of room, and reserving any of it for an unknown future makes the present code words longer; the reservation is paid by the documents that never use it. A code word is at least one bit met the same budget from the other end, a symbol that cannot be given less than one bit of it however rare it is.

The escape’s weight is a forecast #

The escape’s weight is the one number the fit has to guess, and the replay can say what the right guess was. Fitted at 56 files with the escape’s subtree rebuilt, the loss at the end is 1.75 bits a symbol with the escape weighted as one document, a six-bit code word. Weighted as an eighth of the collection, it gets three bits and the loss is 0.57. A quarter or a half of the collection gets it two bits and a loss of 0.29, and three quarters or more one bit and 0.18. The bytes that arrived after the fit came to three quarters of the bytes present at it, so the whole-collection escape was, by luck, the right forecast. A Huffman code gives the escape a whole number of bits, and one is the fewest. 0.18 bits a symbol is the floor of this design for a fit made at a quarter of the files, and it is reached only by a forecast that happened to be right.

The forecast has a second cost the bits a symbol do not show. A wavelet tree shaped by the Huffman code puts each document’s symbols at the depth of its code word, and the tree answers the question lists the documents in a range by descending through it. An added file’s symbols sit below the escape node, one level for the escape and as many more as its subtree needs, so every query that reaches them reads that much further down. A one-document escape puts 43% of the final characters six levels deeper than their refitted code words would.

How late a fit has to be #

With a one-document escape, the loss at the end falls below a tenth of a bit only for a code fitted once the directory held 91% of its files. With a whole-collection escape it never does. The whole-collection escape is best for an early fit and worst for a late one: fitted at 202 files, it charges every file a bit to reserve room for a doubling that does not come, and loses 0.82. The one-document escape is the reverse. Neither weight is right for a fit made at an unknown point in a collection’s growth, because the right weight is the share of the final characters that will arrive after the fit, and at the fit that share is not known.

The subtree-rebuilt design is best at every early fit, 0.15 to 0.38 bits up to half the files, and it inherits the whole-collection escape’s tax on late fits. Its curve is not monotone, and neither is any other here. The history is one directory’s, with growth in spurts: from 135 files to 202 in three versions over four days near the end, nearly a third of the final count.

What keeping a fitted code costs #

Refitting at every version keeps the array’s code within 0.026 bits a symbol of the best on average and rewrites the array 21 times over the history; refitting only when the number of files doubles rewrites it 1.6 times and loses 0.55 to 0.79 bits on average. A refit of a document array is not a matter of reading lengths. Every entry whose code word changes has to be rewritten, and with a wavelet tree shaped by a Huffman code that is nearly every entry. The schedule is then the classic one for a structure that has to be rebuilt as it grows. Choosing a growth factor measured a dynamic array’s trade between copying and wasted space, and doubling bounded the copying at a constant factor of the final size. Here it does the same, 1.6 times the final array, and the waste is in bits a symbol instead of empty slots.

The doubling schedule’s average loss is large because it spends most of each doubling with a code fitted to half the files. Rebuilding the escape’s subtree between doublings, which rewrites only the added files’ entries, takes the average to 0.39 at 5.65 times the final array. No schedule measured gets both the refit’s 0.026 and the doubling’s 1.6. The day a filter cannot grow found the same choice for a fingerprint table, between rebuilding when its own count says it has drifted and paying in advance for growth that may not come.

What this changes about the estimate #

The earlier essay’s saving, a tenth of the plain array on this directory, is the saving of a code fitted to the collection it is used on. On a collection that grows, that saving has to be paid for in rebuilds, and the rebuilds that keep it cost twenty times the array over this history. With rebuilds only at doublings, the average code is half a bit worse than the best and, for a third to a half of the history’s versions depending on the escape, worse than the plain array it was meant to beat. On this directory’s history, a frequency-shaped document array that is not rebuilt often is not smaller than a plain one.

That is a statement about this directory’s growth, which put 43% of the final characters into files that did not exist at a quarter of the way through. A saving quoted without its collection caught a saving reported on a collection that did not have it, and the saving here has the same weakness one level up. It was measured on a collection that had stopped growing at the moment of measurement, and a document index is built on one that will not.

Where the measurement stops #

One directory’s history. The 47 versions are one project’s, and its growth came in spurts, from 135 files to 202 in three versions near the end. A collection that grows by a steady trickle of documents would give an early fit fewer surprises, and one that grows by bulk imports more.

Code lengths, not built indexes. Every cost is computed from the sizes by the identity the earlier essays checked; no index was built at any version. A wavelet tree’s rank directories add the same share to every code and are not counted.

Two fixed escapes. The escape’s weight is chosen once, as one document or as the whole collection. An escape weighted by how fast the files had grown so far was not built.

Bytes for characters, as in the earlier essay: the files are measured in bytes, and a few typographic marks in comments make a file’s bytes slightly more than its characters.

Still open: an escape weighted by the growth already seen #

The right weight for the escape is the share of the characters that will arrive after the fit, and the history so far is the only evidence of it. A code refitted at a doubling could weight its escape by the share of the current characters that arrived since the previous refit. In this directory’s history that share is a little under half at each doubling, which is the weight the whole-collection escape guessed.

The measurement that follows refits at doublings, weights each new escape by the growth since the last refit, and rebuilds the escape’s subtree between refits, then compares the mean loss and the entries rewritten with every schedule here. The prediction is that the mean loss falls below a quarter of a bit at under three times the final array rewritten. Most of the doubling schedule’s loss is the escape’s weight being wrong in one direction or the other, and a weight read from the history should be wrong by less. It could fail on the spurts. A doubling that arrives in a few versions, as the last one nearly did here, would be weighted by the slow growth before it. Then the escape’s estimate is always one spurt behind, and no weight read from the past can do better than the fixed guess.