One doubling late

The shape arrived early and the bytes late replayed a project’s source directory through its history, from twenty files to 222, and kept the directory’s document array, one entry per character naming the file it belongs to, coded by a Huffman code over the files’ lengths. A code fitted at one version needs a way to name files that arrive later, and it has one: an escape, a code word that says “a file added since the fit”, followed by a small code over the added files. The essay found that the spread of the files’ sizes was settled early, and that the loss came from somewhere else. The files added after a fit hold most of the final bytes, and every one of their characters pays the escape’s code word.

A document array’s symbols are its documents and their frequencies are the documents’ lengths, so its entropy is the length distribution’s, which the array is the length distribution showed exactly; the collections the saving was quoted for measured what that saves on real collections, a tenth of the plain array on this directory taken whole. The best schedule the history essay measured refitted the Huffman code whenever the number of files doubled and rebuilt only the escape’s subtree in between, an average loss of 0.39 bits a symbol for rewriting 5.65 times the final array. Its closing section named the weak point. The escape’s weight decides its code word, and the right weight is the share of the characters that will arrive after the fit, which nobody knows. The history so far is the only evidence. So it proposed weighting each refit’s escape by the share of the current characters that arrived since the previous refit, the growth already seen, and predicted the mean loss would fall below a quarter of a bit, at under three times the final array rewritten. It could fail on spurts: a doubling that arrives in a few versions would be weighted by the slow growth before it, and the escape would always be one spurt behind.

Five weights for one schedule #

Every schedule here is the earlier essay’s best: refit at versions 0, 10, 22 and 44, where the files reach 20, 40, 81 and 175, and rebuild the escape’s subtree at every version in between from the added files’ own lengths. Only the escape’s weight at each refit differs, so every schedule reads exactly the same bytes, 5.65 times the final array. The prediction’s three times was about a schedule this one is not; the rewriting belongs to the refits, and no weight changes it.

The weights are given as the escape’s share of the coding space. As one document is the earlier essay’s default, the average file’s share. As half the coding space is the earlier essay’s other escape, weighted as the whole collection. By the growth seen is the proposal: at each refit, the share of the current characters held in files added since the previous refit; the first refit has nothing before it and takes the one-document weight. Growth seen, half at first is the same with the half weight at the first refit. By the growth to come is the weight nobody has: the share of the characters at the next refit held in files added after this one. It is the scale against which the others are measured.

The loss at a version is its bits a symbol against the Huffman code refitted at that version, the best a code of this kind can do there. With the one-document weight the schedule is the earlier essay’s to the bit at every version, which is the check that nothing else changed.

The loss through the history #

Weighted by the growth seen, the escape loses 0.518 bits a symbol on average over the history, more than the 0.389 of an escape that always takes half the coding space; the prediction was under a quarter of a bit. The weight nobody can know, the growth still to come, reaches 0.183, so the escape’s weight is worth about a fifth of a bit a symbol across the history. The growth seen captures none of it on its own, and with a half-weight start about a sixth.

The plate shows where. Before version 10 the growth seen has nothing to read and takes the one-document weight, and the loss climbs to 1.91 bits as the added files grow to two thirds of the directory. After the first refit it tracks the half-weight escape exactly for a stretch, and only in the last stretch, after version 44, does it pull clear of it.

The past is the future one refit late #

At the refits after the first, the growth seen says 71%, 50% and 27% of the characters are new; the doublings that followed brought 50%, 27% and 8% — the same numbers, one refit late. The proposal reasoned that the growth since the last refit was the best evidence of the growth to come. In this directory it is exactly the growth to come of the previous refit, and that is not a coincidence of the numbers. Each refit happens when the files double, so the share of characters in files added during the stretch just finished is the stretch’s growth; the next stretch is another doubling of files, and here each doubling brought a smaller share of the characters than the one before. Either the files added late are smaller than those already there, or the old files grew while new ones arrived, or both; the replay does not separate them.

The earlier essay’s closing section expected the share at each doubling to be a little under half, which would have made the past a good guess for the future. It is a little under half once, at the second refit. Before that it is more, after it much less, and a guess that is always the last stretch’s share is always too large on a directory whose stretches shrink.

Weights, in whole bits #

A Huffman code gives the escape a whole number of bits, so weights within a factor of two give the same code word: at the second and third refits the growth seen, 71% and 50%, and the half weight both give the escape one bit. That is why the two schedules have identical losses through the middle of the history. Getting the weight right within a factor of two buys nothing; only a weight that crosses a power of two changes the code word.

The ideal lengths say what crossing is worth. At version 44 the growth to come asks for 3.62 bits; the half weight gives 1, which over-pays the escape’s mass and starves every old file of a little code space, and the one-document weight gives 8, which over-charges every new character. The growth seen gives 2, closer than either, and that is the one stretch it wins. A code word is at least one bit found the same floor on the other side: an escape that should cost half a bit, as at the first refit, cannot cost less than one.

Why a fixed half does so well for so long #

The half weight looks naive, a guess that half the coding space belongs to files not yet seen, and it beats the rule built from evidence for most of the history. The plate of code words says why. A half weight gives the escape a one-bit code word at every refit. At the first two refits the growth to come asks for 0.50 and 1.00 bits, so one bit is the best a whole-bit code can do there, and the half weight is, by accident, the oracle’s code. It goes wrong only when the growth to come falls below a quarter, at the third refit, and badly when it falls below an eighth, at the fourth.

The growth seen is the opposite kind of guess. It has nothing at the first refit and so takes a weight of one document, a code word of four bits for files that will hold two thirds of the characters. After that it is one doubling late, which on this directory means always too large, but too large by less than a factor of two until the end, and so one bit, like the half weight, until the last refit gives it two.

Neither guess is reading the right thing. The quantity that sets the escape’s code word is the power of two nearest the share still to come. A rule that cannot know that share does best by being right about its order of magnitude, and on a directory whose growth slows each time, a fixed guess is right at the start and the evidence of the past is right at the end.

Stretch by stretch #

Before the first refit the growth seen loses 1.043 bits a symbol where the half weight loses 0.280; in the two middle stretches they tie; in the last the growth seen loses 0.253 against the half weight’s 0.767. Started from the half weight, the growth seen takes the best of both and averages 0.356 over the history, the best mean any weight a store can compute reaches here. It is still above the quarter of a bit predicted, and the gap to the weight nobody knows, 0.183, is almost all in the stretch from version 22 to 43, where every rule a store can use gives the escape one bit and the growth to come asks for two.

In the first two stretches the half weight and the growth to come give the escape the same one-bit code word and lose exactly the same, 0.280 and 0.216 bits a symbol; knowing the future buys nothing there, because a whole-bit code cannot use what it knows. Everything the oracle gains, it gains in the last two stretches, where the share still to come falls below a quarter and its code word grows to two bits and then four.

The third stretch is the longest, 22 versions, and it carries the mean. There the directory grew from 81 files to 155 in a stretch where the share of characters in added files reached 23% at most. An escape weighted at a half or at 50% of the growth seen is a code word of one bit for a set of files holding under a quarter of the characters; the old files pay for it with code space they needed.

What the escape has to name #

What the escape names grows from nothing at each refit to 68%, 46% and 23% of the characters just before the next, and a weight is fixed for the whole stretch. Even the growth to come is right only at the stretch’s end. For most of each stretch the escape names fewer characters than its weight assumes. That is the doubling schedule’s own cost, and no weight removes it; choosing a growth factor found the same shape in an array that doubles its memory, where the space is right only at the moment before each doubling.

The growth seen sets each new weight from the stretch just finished, the curve’s peak before the refit, rounded into a step. It is right exactly when the next stretch grows like the last. In this directory no two stretches did.

Mean, worst and last #

No weight a store can compute reaches the quarter of a bit predicted; the best, the growth seen after a half-weight start, averages 0.356, and every one of them rewrites the same 5.65 times the final array. The two parts of the prediction fail for different reasons. The loss misses because the past is one refit behind on a directory whose growth slows, and because a whole-bit code word blurs every weight within a factor of two. The rewriting misses because it belongs to the schedule, refits at doublings and subtree rebuilds between, and the proposal kept that schedule.

What the measurement leaves is a small rule with a real gain: read the growth from the history, but do not trust it before there is any. Against the earlier essay’s best, 0.389 with the half weight, that is three hundredths of a bit a symbol less over the history, and 0.455 less at the last version. Against the weight nobody can know it is still twice the loss.

What the counts depend on #

One directory. The history is one project’s, 47 versions, and its growth slowed at every doubling. A corpus that was not generated chose real collections for exactly this reason, and it is also this result’s limit: on a collection whose growth speeds up, the growth seen would be too small rather than too large, and the half weight would err the other way.

Refits at doublings of the file count. The schedule refits when the number of files doubles, not the number of characters, and the versions it refits at are therefore fixed by the history before any weight is chosen. On this directory the two part company as files get smaller, and a schedule keyed to characters would refit less often late in the history.

One check on the arithmetic. The plain array, a fixed number of bits for every symbol, would cost the same at every weight and every version; a saving quoted without its collection showed how a comparison against it can report a saving the rounding made. The losses here are measured against the refitted Huffman code, not the plain array, so no rounding of the plain array’s width enters them.

Bits counted, not time. The loss is in bits a symbol of the array, measured at every version and averaged with every version weighted equally, and the rewriting in bytes read. Neither the time to rebuild a subtree nor the cost of finding the added files is counted.

Still open: refitting when the escape’s code word is wrong #

The schedule refits at fixed points, when the files double, and the escape’s weight is chosen at those points and held. But the store can see, at every version, how many characters its escape is naming, because the escape’s subtree is rebuilt at every version from the added files’ lengths. When that share crosses the power of two the escape’s code word assumes, the code word is wrong by a bit, and a refit then would correct it.

The measurement that follows refits whenever the share of characters behind the escape moves more than a factor of two from the share its code word stands for, with no doubling rule at all, and charges the rewriting as before. The prediction is that it refits about six times over this history instead of four, at different versions, and that its mean loss falls below a quarter of a bit for about the same rewriting, because it refits exactly where the plates show the escape’s code word going wrong, in the long third stretch. It could fail on the first stretch, where the share behind the escape climbs from nothing to two thirds in nine versions and would cross a power of two four times; a rule that refits at each crossing would rewrite the array four times for twenty files. The day a filter cannot grow rebuilt a filter from its store when its own count said its rate had passed a threshold, a clock read off the structure rather than off the calendar, and that is the kind of clock proposed here. The question is whether watching the escape is a better clock for refits than counting the files, or whether any clock that responds quickly to a young collection rewrites too often for the bits it saves.