The index that replaces the text

A rate that reads the history

A growing collection's document array is coded by a Huffman code that goes stale, and a refit called when either of two charges passes the array — one on the characters stored, one on those just arrived — lost 0.070 bits a symbol for 5.31 arrays rewritten. The proposal was one stored charge whose exchange rate reads the history: scaled down when the characters that arrived since the last refit are a large share, so a burst raises the bar a stale code must clear. Every strength of that fall loses more than a fixed rate — 0.091, 0.097 and 0.163 bits a symbol at the pair's arrays against 0.077 — and the reason is the risk it named: a rate that falls in a burst refits later during it, and the worst version loses 0.58 bits a symbol. Turned the other way, the same charge with its rate rising in proportion to the arrived share loses 0.071, refits at eleven of the pair's thirteen versions, and loses the pair's three stretches over again. One charge can do what two did; the history it should read is the burst, and it should read it as a reason to refit sooner.

A document array names, for every character of a collection, the document the character belongs to, and the array is the length distribution found it best coded by a Huffman code over the documents’ lengths — a code whose every word, a code word is at least one bit noted, costs at least a bit. A collection that grows breaks that code a little with every version — the shape arrived early and the bytes late measured how — and one doubling late and refitting when the escape is wrong gave new documents an escape so the Huffman code could wait. A refit reads the whole array and rewrites it; not refitting costs the bits the stale code wastes and the escape’s subtree rebuilt at every version. The quarter was a lucky number set a priced rule against a clock read off the escape, and the strand since has been looking for the rule that decides when, charged as the choice is: refit when the reading the wait has cost, plus the waste a refit would remove times an exchange rate, passes the characters a refit reads.

A waste charged to what arrived found two ways to count the waste — on every character stored, or on the characters each version adds — and found them losing in opposite stretches of the history: the arrivals charge right in the early versions, where the directory grows by a third in some versions and not at all in others, the stored charge right in the quieter middle. A refit either charge can call kept both sums and refitted when either passed the array, and at rates of 2 and 32 it lost 0.070 bits a symbol over the history for 5.31 arrays rewritten, its three stretches 0.073, 0.060 and 0.074. Its gain over the better single charge was at most six thousandths of a bit.

That essay’s closing section looked at why each charge wanted the rate it had. Both rates are exchange rates between characters read and bits wasted, and its plates showed each wanting a different rate at different times: the arrivals charge’s 32 right early and too slow in the quiet middle, the stored charge’s 2 too eager early and right late. Nothing requires a rate to be constant. The proposal: set a single stored charge’s rate from what the history has done since the last refit — the share of the characters stored that arrived in that interval — scaling the rate down when arrivals have been a large share, so that a burst raises the bar a stale code must clear, and up when they have been small. The prediction: one such charge reaches the pair’s 0.070 at 5.3 arrays and its first stretch, 0.073, while refitting at version 15 in the middle where the pair waited until 17, bringing the middle stretch to about 0.055. The risk: a rate that falls during a burst refits later during the burst, exactly when the earlier essays found the Huffman code becoming wrong.

A rate set by the arrived share

The charge is the stored charge of the earlier essays with its rate made a function of one number. Let aa be the share of the stored characters that arrived since the last refit — near nought just after a refit, growing as versions arrive, and growing fastest in a burst. The rate at a version is r=r0⋅(0.1/a)αr = r_0 \cdot (0.1/a)^\alpha, floored at aa of a hundredth, so that at a tenth of the store arrived the rate is the base r0r_0. At α=0\alpha = 0 the rate is fixed and the charge is the stored charge alone, refit for refit, which is checked. Positive α\alpha is the proposal: the rate falls as the arrived share grows. Negative α\alpha is the other sign, the rate rising with the arrived share. Bases run from half to sixteen and α\alpha from −2 to 2.

Everything else is the earlier essays’. The same 47 versions of the same growing collection, the Huffman code over document lengths with its escape, the loss a version counted as bits a symbol beyond a code refitted at that version, arrays rewritten counted as the characters a rule reads over the history divided by the final array’s. The three stretches are versions 0 to 14, 15 to 29 and 30 to 46.

The hero plate is the measurement in one picture: the lower envelope of loss against arrays at four strengths, beside the pairs’ frontier. At the pair’s 5.31 arrays a fixed rate loses 0.077 bits a symbol. The proposal’s falling rate, at α of a half and one, loses 0.091 and 0.097. The rate rising with the arrived share, at α of one, loses 0.071, two thousandths from the pair.

The sign that decides it

The sign decides it: at the pair's 5.31 arrays the history charge loses least with its rate rising in proportion to the arrived share, α of 1, at 0.071 bits a symbol, and every strength of the proposed fall loses more than a fixed rate — 0.091, 0.097, 0.163 at α of 0.5, 1, 2 against 0.077Mean loss at 5.31 arrays rewritten, read off each strength's lower envelope, for the stored charge with rate base × (0.1 / a)^α: α -2: 0.0807, α -1: 0.0710, α -0.5: 0.0745, α 0: 0.0772, α 0.5: 0.0913, α 1: 0.0967, α 2: 0.1626. The pair of charges at rates 2 and 32: 0.0696.the pair, 0.070rises with arrivals, α 20.081rises with arrivals, α 10.071rises with arrivals, α 0.50.075fixed rate0.077falls with arrivals, α 0.50.091falls with arrivals, α 10.097falls with arrivals, α 20.163at 5.31 arraysmean loss, bits a symbol
Fig. 1 Mean loss at the pair’s 5.31 arrays, read off each strength’s lower envelope, for every α from rising at 2 to falling at 2, beside the pair’s 0.070. Rising at one: 0.071. Fixed: 0.077. Falling at a half, one and two: 0.091, 0.097 and 0.163.

The sign decides it: at the pair’s 5.31 arrays the history charge loses least with its rate rising in proportion to the arrived share, at α of one, 0.071 bits a symbol, and every strength of the proposed fall loses more than a fixed rate — 0.091, 0.097 and 0.163 at α of a half, one and two, against 0.077. The proposal’s direction is wrong at every strength measured, and the further the rate falls in a burst the worse it does. That a dependence on the history helps is right: the best rising rate is six thousandths under the fixed one at the same arrays, about what the pair gained.

The rising rate is not an arbitrary repair. A rate proportional to the arrived share charges the removable loss on every stored character times a share that is the arrivals over the store, which is to say on the arrivals: the arrivals charge of the earlier essay, counted since the last refit rather than version by version. At α of one the single charge is a blend of the two charges the pair kept separately, and the plate shows it doing what the pair did.

Steeper rising rates are worse again — α of two loses 0.081 — because a rate that rises as the square of the arrivals refits on any burst at all, and the middle stretch, where the stored charge was right, then refits too eagerly. Half and one are the only rising strengths near the pair.

When each rule refits

When each rule refits: the rising rate at base 2 refits at 11 of the pair's 13 versions — 0, 2, 3, 6, 9, 11, 13, 17, 22, 25, 35, 40, 44 against 0, 2, 3, 6, 9, 11, 13, 17, 22, 25, 35, 42, 45 — while the falling rate at base 2 refits later through the early burst (0, 3, 7, 11, 15, 21) and so waits longest where the Huffman code goes wrong fastestThe versions at which each rule refits, over 47 versions: the pair, 2 and 32: 0, 2, 3, 6, 9, 11, 13, 17, 22, 25, 35, 42, 45 (5.31 arrays, loss 0.0696); rising, base 2: 0, 2, 3, 6, 9, 11, 13, 17, 22, 25, 35, 40, 44 (5.28 arrays, loss 0.0713); fixed, base 2: 0, 3, 6, 9, 12, 15, 21, 25, 35, 42, 45 (5.04 arrays, loss 0.0800); falling, base 2: 0, 3, 7, 11, 15, 21, 25, 35, 44, 46 (5.07 arrays, loss 0.1040).0101420294046version at which the Huffman code is refittedthe pair, 2 and 32rising, base 2fixed, base 2falling, base 2ticks: refitsversions
Fig. 2 The versions at which each rule refits over the 47 versions: the pair at 2 and 32, the rising rate at base 2, the fixed rate at base 2 and the falling rate at base 2. The rising rate shares eleven of the pair’s thirteen refits.

The rising rate at base 2 refits at eleven of the pair’s thirteen versions — 0, 2, 3, 6, 9, 11, 13, 17, 22, 25, 35, 40 and 44 against the pair’s 0, 2, 3, 6, 9, 11, 13, 17, 22, 25, 35, 42 and 45 — while the falling rate at base 2 refits later through the early burst, at 0, 3, 7, 11, 15 and 21, and so waits longest where the Huffman code goes wrong fastest. The schedules show the mechanism directly. In the first fourteen versions the directory grows in bursts, each version adding a large share; the pair refits at versions 2, 3, 6, 9, 11 and 13, and the rising rate at the same six. The falling rate refits at 3, 7 and 11, every gap a version or two longer, because the burst that made the Huffman code stale also lowered the rate at which its staleness was charged.

The prediction’s specific claim was about the middle: a refit at version 15 where the pair waited until 17. No rule near the pair’s arrays makes that refit. The rising rate waits until 17 as the pair did, because between 13 and 17 the arrived share is small and its rate is low; the fixed rate refits at 12 and 15, but at the cost of the early versions, refitting at 3, 6 and 9 and not at 2 and 11.

What the rising rate changes from the pair is the tail: refits at 40 and 44 where the pair refitted at 42 and 45. Those are the versions where its first stretch and its middle stretch match the pair’s and its last stretch differs by five thousandths.

The rate through the history

The rate itself at base 2: rising with the arrived share it climbs between refits as arrivals accumulate and drops to its least just after one; falling with it, it starts each interval high and decays — so in the first fourteen versions, where each version adds a large share, the falling rate drops as low as 0.40 and the stale code is charged least where it costs mostThe stored charge's rate at each version for base 2, r = 2 × (0.1 / a)^α with a the arrived share since the last refit (floored at a hundredth; drawn capped at 40): rising with arrivals: 1 0.20, 2 5.66, 3 6.00, 4 2.37, 5 2.42, 6 6.04, 7 2.69, 8 2.69, 9 4.93, 10 2.19, 11 4.75, 12 2.44, 13 4.70, 14 0.20, 15 1.52, 16 2.60, 17 2.57, 18 0.20, 19 0.20, 20 1.35, 21 2.93, 22 4.28, 23 0.20, 24 1.87, 25 3.06, 26 0.20, 27 0.20, 28 0.20, 29 0.20, 30 0.20, 31 0.20, 32 0.20, 33 1.93, 34 2.01, 35 3.00, 36 1.00, 37 2.30, 38 3.18, 39 3.56, 40 4.22, 41 0.68, 42 1.38, 43 2.28, 44 3.13, 45 1.07, 46 1.71; falling with arrivals: 1 20.00, 2 0.71, 3 0.40, 4 1.69, 5 1.65, 6 0.66, 7 0.51, 8 20.00, 9 1.55, 10 0.89, 11 0.59, 12 1.64, 13 0.85, 14 0.85, 15 0.68, 16 3.42, 17 3.50, 18 3.50, 19 3.50, 20 1.65, 21 1.02, 22 2.53, 23 2.53, 24 1.21, 25 0.91, 26 20.00, 27 20.00, 28 20.00, 29 20.00, 30 20.00, 31 20.00, 32 20.00, 33 2.07, 34 1.99, 35 1.33, 36 3.99, 37 1.74, 38 1.26, 39 1.13, 40 0.95, 41 0.84, 42 0.75, 43 0.66, 44 0.60, 45 3.73, 46 2.34.0510152001020304046versionthe stored charge's ratefalling with arrivalsrising with arrivalsbase 2 · ticks at the foot: refitsrate
Fig. 3 The stored charge’s rate at each version for base 2, rising and falling with the arrived share, drawn capped at 40, with each rule’s refits ticked at the foot. In the first fourteen versions the falling rate drops as low as 0.40.

At base 2 the rising rate climbs between refits as arrivals accumulate and drops to its least just after one; the falling rate starts each interval high and decays, so in the first fourteen versions, where each version adds a large share, it drops as low as 0.40 and the stale code is charged least where it costs most. The plate is the risk drawn. Just after a refit the arrived share is small and the falling rate is at its highest, 20 at the floor — but just after a refit the Huffman code is fresh and there is nothing to charge. By the time a burst has made the Huffman code stale, it has also made the arrived share large and the rate low; in the early versions it falls to a fifth of its base, 0.40, at version 3, two versions after a refit, when half the store has arrived since.

The rising rate has the opposite shape and the right one. It is lowest when the Huffman code is freshest and highest when a burst has piled arrivals on a code fitted before them, so the charge grows fastest exactly when the Huffman code is going wrong. In the quiet middle, where versions add little, the arrived share grows slowly, the rate stays near its base, and the charge behaves as the stored charge did there — which is where the stored charge was right.

That is the whole reading of the history the pair had been doing with two sums. The proposal reasoned that a burst should raise the bar for refitting, because a burst is expensive to refit after; the measurement says the bar that matters is the stale code’s, and a burst lowers it.

The pair’s history over again

Stretch by stretch, the rising rate at base 2 is the pair's history over again — 0.073, 0.060, 0.079 against 0.073, 0.060, 0.074 — and the settings near these arrays that bring the middle stretch under the predicted 0.055, the fixed and falling rates at base 2 (0.051 and 0.051), pay for it in the first stretch, 0.116 and 0.168, the burst the falling rate was meant to handleMean loss over the three stretches of the history, for the pair at rates 2 and 32 and for the single history charge nearest its arrays at each sign: the pair, 2 and 32 (5.31 arrays): 0.0734, 0.0604, 0.0744; rising, base 2 (5.28 arrays): 0.0734, 0.0604, 0.0791; fixed, base 2 (5.04 arrays): 0.1156, 0.0507, 0.0744; falling, base 2 (5.07 arrays): 0.1685, 0.0507, 0.0941.the pair, 2 and 32rising, base 2fixed, base 2falling, base 2versions 0–140.0730.0730.1160.16815–290.0600.0600.0510.05130–460.0740.0790.0740.094mean loss in each stretchbits a symbol
Fig. 4 Mean loss over the three stretches of the history, for the pair at 2 and 32 and for the single history charge nearest its arrays at each sign. The rising rate at base 2: 0.073, 0.060 and 0.079. The pair: 0.073, 0.060 and 0.074.

Stretch by stretch, the rising rate at base 2 is the pair’s history over again — 0.073, 0.060 and 0.079 against 0.073, 0.060 and 0.074 — and the settings near these arrays that bring the middle stretch under the predicted 0.055, the fixed and falling rates at base 2, at 0.051 each, pay for it in the first stretch, 0.116 and 0.168, the burst the falling rate was meant to handle. The prediction’s second number was a middle stretch of 0.055 with the first stretch kept at 0.073, and the plate says the two do not go together at these arrays. Every rule spends about five arrays; it can spend them early, in the burst, or in the middle, and the middle stretch falls only when the early one rises.

The rising rate makes the pair’s choice — spend them early, where the Huffman code goes wrong fastest — and loses five thousandths more than the pair in the last stretch, where its schedule differs. That is the price of one sum instead of two: the pair’s arrivals sum and stored sum fire at slightly different moments in the tail, and a single blended sum fires at one.

The fixed rate at base 2 is the stored charge of the earlier essays exactly, and its stretches — 0.116, 0.051, 0.074 — are that essay’s. The falling rate at base 2 is the fixed rate made worse where the fixed rate was already weak, a first stretch of 0.168.

Where the Huffman code goes wrong

Version by version, the falling rate's worst version loses 0.578 bits a symbol (version 6), against 0.250 for the rising rate (version 46) and 0.245 for the pair (version 21): a rate that falls in a burst lets the Huffman code go furthest wrong exactly thereBits a symbol beyond a code refitted at each version, at all 47 versions: the pair, 2 and 32: 0.092, 0.092, 0.087, 0.048, 0.102, 0.101, 0.044, 0.117, 0.117, 0.048, 0.069, 0.047, 0.092, 0.022, 0.022, 0.086, 0.223, 0.023, 0.023, 0.023, 0.063, 0.245, 0.023, 0.023, 0.115, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.193, 0.195, 0.011, 0.015, 0.050, 0.087, 0.099, 0.113, 0.138, 0.011, 0.059, 0.196, 0.006, 0.056; rising, base 2: 0.092, 0.092, 0.087, 0.048, 0.102, 0.101, 0.044, 0.117, 0.117, 0.048, 0.069, 0.047, 0.092, 0.022, 0.022, 0.086, 0.223, 0.023, 0.023, 0.023, 0.063, 0.245, 0.023, 0.023, 0.115, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.193, 0.195, 0.011, 0.015, 0.050, 0.087, 0.099, 0.011, 0.008, 0.065, 0.196, 0.006, 0.125, 0.250; falling, base 2: 0.092, 0.092, 0.299, 0.048, 0.102, 0.101, 0.578, 0.043, 0.043, 0.103, 0.319, 0.047, 0.092, 0.284, 0.284, 0.023, 0.027, 0.027, 0.027, 0.027, 0.170, 0.023, 0.053, 0.053, 0.274, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.012, 0.193, 0.195, 0.011, 0.015, 0.050, 0.087, 0.099, 0.113, 0.138, 0.198, 0.329, 0.006, 0.125, 0.006.00.2000.4000.6000101420294046versionloss at the version, bits a symbolrising, base 2the pair, 2 and 32falling, base 2rules mark the three stretchesloss by version
Fig. 5 Bits a symbol beyond a code refitted at each version, at all 47 versions, for the pair, the rising rate at base 2 and the falling rate at base 2. The falling rate’s worst version, 6, loses 0.578; the rising rate’s worst, 0.250; the pair’s, 0.245.

Version by version, the falling rate’s worst version loses 0.578 bits a symbol, at version 6, against 0.250 for the rising rate and 0.245 for the pair: a rate that falls in a burst lets the Huffman code go furthest wrong exactly there. The mean losses on the earlier plates hide how uneven the losses are. Most versions lose a few hundredths under every rule — the median version about five hundredths under all three; a handful lose a quarter of a bit or more, and those are the versions a refit rule exists for. Under the falling rate the worst of them is more than twice as bad as under the pair, in the middle of the early burst, where the directory has grown by a third since the Huffman code was fitted and the rule, having just lowered its rate, has not yet refitted.

The rising rate’s worst version is late, at version 46, the last, where it is a version away from its final refit; the pair’s is at 21. Both are about a quarter of a bit. For a reader of the collection, who pays the loss at every version, the shape matters as much as the mean: the pair never lets a version lose more than a quarter of a bit and the rising rate does so once, by a ten-thousandth, while the falling rate does in seven versions.

A price that cannot see the array found that a refit rule can only charge what it can measure when it acts, and every rule here measures the same two things. What differs is the weight each puts on the arrivals, and the plate shows what the weight is for.

Whether the rate belongs to the store or the history

The question the proposal closed on was whether the exchange rate between reading and waste is a property of the store, fixed once, or of the history the store has been through. It is of the history — the best rule here sets its rate from the arrivals since the last refit, and is six thousandths better than any fixed rate at the same arrays — but it reads the history the other way from the proposal. A burst is a reason to refit sooner, because a burst is what makes a Huffman code fitted before it wrong; the rate should rise with it.

That also answers, in part, the strand’s long question about the pair. Two charges did better than either alone because one read the store and the other read the arrivals, and a single charge whose rate is the arrivals’ share of the store reads both at once and does nearly as well. The pair’s extra two thousandths are the difference between firing on two sums and on one blend of them, and they are paid in the tail.

What the measurement leaves out

One collection, one history. Forty-seven versions of one growing collection; a history whose bursts came late, or never, would weigh the stretches differently.

One form of dependence. The rate is a power of the arrived share since the last refit, at one reference share; a rate read from the last version’s arrivals alone, or from the Huffman code’s own escape traffic, was not measured.

Mean loss as the measure. The plates report the mean over versions and, once, the worst; a reader who weighted recent versions more would rank the rules differently in the tail.

Still open: a rate that reads the Huffman code’s own escapes

The rising rate reads arrivals, and arrivals stand in for what actually makes the Huffman code wrong: documents the Huffman code has never seen, which it can only name through its escape. The Huffman code knows how much of the array goes through the escape at every version — that share is part of the cost the earlier essays charged as fresh bytes — and a document that arrives inside an existing length class makes the Huffman code no more wrong, while one that arrives as a new length makes it wrong at once. A rate set from the escape’s share of the array since the last refit would rise only on the arrivals that matter.

The measurement that follows sets the stored charge’s rate as base × (escape share ÷ a tenth) to the powers measured here, on the same history, and compares it to the rising rate and the pair. The prediction is that it reaches the pair’s 0.070 at five arrays rather than 5.3, because it does not refit after arrivals the Huffman code already names, and that its last stretch improves on the rising rate’s 0.079, since the tail’s arrivals are mostly documents of familiar lengths. It could fail where the escape share lags: a new length class is escaped only until the next refit names it, and if the escape’s share is small in a burst of new lengths — many documents, each small — the rate would rise too late. The question is whether the right history to read is what arrived or what the Huffman code could not say.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

AmortisationCorpusDocument arrayHuffman codingIndex sizeTime space tradeoff