The optimum the flag took away

The index that is smaller than the text rebuilt a compressed index at five block lengths and found an interior optimum. Every block of a level’s bit vector was stored as a class, how many ones it holds, and an offset, which of the arrangements with that many ones it is. A short block pays for its class whatever is in it, so short blocks are dear. A long block’s offset, $\lceil\log_2\binom{b}{c}\rceil$ bits, approaches the block’s length as the block lengthens, because a long block is rarely uniform, so long blocks are dear too. The minimum fell at 63 bits, and every page in this line since has coded its levels at 63.

Two things then changed what a block costs. Six bits a class stored the class sequence as runs of one value, because two thirds of the blocks are uniform and they come in stretches. A flag for the blocks that change once let each mixed block choose between its arrangement’s index and a code of the gaps between its value changes, at one bit for the choice. A block that straddles one change of value then costs about eleven bits whatever its length. That essay’s closing section proposed rebuilding the levels at blocks of 15, 31, 63 and 127 bits to find the length the change points want. It predicted that English words’ best length would move from 63 to 127 bits, the repetitive collection’s further, and random letters’ nowhere. It could fail on the many-change blocks: a long block in a mixed stretch catches more stray changes, and if their cost grew faster than the one-change blocks’ fell, longer blocks would only spread the cost.

The same bits, cut at every length #

The levels are the index’s own, built once: every wavelet-tree node of both trees over four texts of 16,384 characters, DNA and protein drawn at random, English words, and a repetitive collection. Each node’s bit vector is read back and re-cut into blocks of $L$ bits, from 15 to 1,023, and costed as the flagged coding costs it. The classes are runs of one value, $\lceil\log_2(L+1)\rceil$ bits for the value and an Elias-gamma length, with a pointer into the run stream every superblock. A uniform block needs no offset. A mixed block costs a flag and the shorter of its arrangement’s index and its gap code, the first bit, the count of value changes and each gap, all in gamma. Superblocks of 32 blocks keep a rank and an offset pointer, as built.

At 63 bits the rebuild’s classes and offsets are the earlier essays’ to the bit, and its superblocks are the built vectors’ own. The total is 1.431 bits a character on English words, not the 1.45 the flag’s essay reported. The difference is a quirk of that accounting, which charged an arrangement index to each level’s short last block when it was all ones, a block that needs no offset; it is two hundredths of a bit and is left out here.

Beside the flagged coding, the same vectors are costed as first built: a fixed-width class for every block, and every mixed block’s offset its arrangement’s index. That is the coding the part every saving left alone introduced to these levels, at 63 bits, and the one a block, a class and an offset first priced on a smaller structure, where it found the payload’s penalty falling quickly as the block lengthened.

Where the optimum at 63 came from #

Under the coding as first built, English words’ levels have their least at 63 bits, 1.877 bits a character, and cost twice that at 1,023; under classes as runs and the flag they fall at every length, from 1.431 at 63 to 1.304 at 1,023. The earlier sweep’s optimum is reproduced on these levels, and it is a property of that coding. The repetitive collection does the same, its least at 63 under the first coding and none under the second.

The reason is in what each coding charges a long mixed block. An arrangement’s index for a block of 1,023 bits with a few hundred ones is several hundred bits, because it has to name one arrangement among astronomically many, even when the block’s ones sit in two long stretches. The gap code names the stretches: a first bit, a count and a gamma code for each gap, a few dozen bits for a block that changes value a handful of times. The flag takes whichever is shorter, and for a long block on a structured text that is usually the gaps.

The stretches exist because of the transform the levels are built over. A wavelet-tree level is a bit vector over the Burrows–Wheeler column of the text, and the column groups characters that share a following context, so a level’s bits come in long runs that change at the boundaries between groups. The transform that emits nothing showed that the transform changes no character’s frequency, only the order, and the order is exactly what a gap code is paid to describe. On English words and the repetitive collection those boundaries are sparse, and a gap code over a long block pays for a few of them. On random letters the column has no groups to speak of and the boundaries are everywhere.

Every text, against itself at 63 #

Lengthening the blocks from 63 to 127 bits saves on every text, 4.5% on English words, 9.6% on the repetitive collection, and 4.0% and 3.4% on DNA and protein, where the prediction expected nothing. And it goes on saving. English words and DNA are still falling at 1,023 bits, and the repetitive collection most steeply of all. Only protein turns, at 511 bits, and by four tenths of a per cent.

The random letters save for a reason that has nothing to do with change points. Their mixed blocks change value dozens of times, so a gap code rarely beats the arrangement’s index, and their offsets grow with length about as the first coding’s did. What falls is the directory: the classes and the superblocks are paid a block at a time, and a block of 127 bits has half as many of them to pay for. On DNA the classes fall from 0.258 bits a character at 63 to 0.154 at 127. The prediction treated the classes and superblocks as a cost on the long-block side of a balance; under run-coded classes they are only that.

English words, part by part #

From 63 bits to 1,023 the classes fall by 0.249 bits a character and the superblocks by 0.039, while the offsets rise by only 0.161. The offsets are where the first coding lost everything at long blocks, 1.297 bits a character at 63 rising to 3.612 at 1,023. Under the flag they rise by a sixth.

They rise by so little because a gap code’s cost is the cost of the change points it covers. A change of value inside a block costs a gamma code for the gap before it, about twice the logarithm of the gap. Cutting the vector into longer blocks does not change where the changes fall; it only changes which block each one is charged to and how long the gaps between them are measured, since a block’s first gap starts at the block’s edge. Longer blocks put fewer edges in the way, so the gaps are measured more nearly from change to change. The offsets converge on a code of the vector’s own change points, and that code does not depend on the block length at all.

The one-change blocks, which do not decide it #

The blocks the flag was built for are commonest at 127 bits on English words, 46% of mixed blocks, and grow scarce beyond, 9% at 1,023; the levels go on shrinking anyway. The prediction’s mechanism was right about the one-change blocks: each costs about the same whatever its length, 12.2 bits at 63 and 14.2 at 127, and a longer block straddles proportionally fewer boundaries. Its failure mode was right about the others: a long block in a mixed stretch catches more changes, and the many-change blocks’ cost doubles with each doubling of length, from 49.7 bits at 63 to 94.8 at 127.

Neither decides the total, because the number of mixed blocks falls as fast as their cost rises. At 63 bits English words have 885 mixed blocks; at 1,023 they have 145, and the 131 many-change blocks among them cost 288 bits each. A block of 1,023 bits that changes value thirty times is charged for thirty changes; at 63 bits the same thirty changes were spread over sixteen blocks, each with its class, its flag and its first gap. The count of changes is what the offsets pay for, at any length.

What a long block costs a rank #

A rank’s work rises from 15.7 entries and bits read at 63 bits to 23.6 at 127 and 104.4 at 1,023, and almost all the growth is inside the block. The directory’s share stays between four and nine, because a superblock spans 32 blocks whatever their length and a run of uniform blocks is one entry. The decoding inside a block is what grows. A block held by its arrangement must be decoded up to the rank’s position, half the block on average; a block held by its gaps must be read gap by gap until the position is passed. Both double with each doubling of length.

That is the cost the block length now trades against. Rank is the only thing it does found that a rank directory’s overhead and its reads are set by two integers and can be traded along a line; the block length of a coded level is a third integer on the same trade. Under the first coding there was nothing to trade, since a longer block cost both more bits and more work past 63. Under the flag every doubling buys bits with work.

Bits against work #

On English words, going from 63 to 127 bits saves 4.5% of the levels for 51% more work a rank, and going from 255 to 511 saves 1.1% for 67% more. Every text lies on a curve of the same shape: steep savings for little work at short blocks, a knee between 63 and 255, and then work bought for almost nothing. Where to stand on it depends on how often the index is asked a rank against how much its size matters, which bits and steps on one frame argued for the sampling rate in exactly these terms: neither line is the answer, the answer is a point on the pair.

Read the other way, the curve says what a fixed budget of work allows. An index that can afford about sixteen units of work a rank on English words stands at 63 bits, which is where the first coding put its optimum; one that can afford a hundred stands at 1,023 bits, with levels 8.9% smaller. So the old optimum survives as one point on the new curve rather than as its minimum: it is what the levels cost when a rank may read about as much as it did before the flag.

The repetitive collection’s curve is the most generous. Its levels are long uniform stretches broken by a few changes, its mixed blocks change value rarely, and a gap code walks them quickly, so at 1,023 bits its rank work is 54.7 against English words’ 104.4, and its levels are a quarter smaller than at 63.

What each doubling buys #

Each doubling saves less than the one before on English words, DNA and protein, and on protein the last one costs 0.4%; on the repetitive collection doubling still saves 5.5% at 1,023 bits. The bits never ask for a shorter block on three of the four texts, and on protein they ask at 511, by a sliver. Every reason to stop lengthening is the rank’s.

Protein turns because its blocks almost never change value once and a gap code rarely wins there, so at long blocks its offsets grow much as the first coding’s did, and at 1,023 that growth finally outruns the directory’s last savings. The prediction placed random letters where protein ends up, unmoved by length. It placed them for the right kind of reason and at the wrong length.

What the counts depend on #

One size of text. Each text is 16,384 characters, and its levels are a few hundred thousand bits; at 1,023 bits a block a level holds a few hundred blocks and the directory’s share is small. A longer text would have more blocks at every length and the same per-character costs, except where the last block’s rounding matters, which is at the longest lengths.

A unit of work, not a time. The rank’s work counts entries and bits read in the earlier pages’ unit. A machine decodes a gap code and an arrangement at different speeds and reads bits a word at a time; the doubling of in-block work with length is the shape that would survive, not the numbers.

One length for every level. Every level of both trees is cut at the same length. The levels differ in how often they change value, and a length chosen per level would sit at a different point of each level’s curve. The level where compression stops paying found that choosing the coding level by level saved five hundredths of a per cent on another structure; choosing the length level by level was not measured.

Superblocks of 32 blocks at every length. The superblock count falls with the block length because a superblock is a number of blocks. A superblock fixed in bits instead would keep the directory’s cost and change the work; it was not swept.

Still open: a flag that weighs the work as well as the bits #

The block length now trades bits for the work of decoding inside a block, and the decoding has two costs. A block held by its arrangement must be decoded bit by bit up to the rank’s position, half the block on average; a block held by its gaps is read gap by gap, and a block that changes value a few times is passed in a few steps. The flag chooses between them on bits alone. On English words at 255 bits it holds 126 mixed blocks by their arrangement and 259 by their gaps, and the arrangement blocks are most of the in-block work.

A flag could weigh both. Charge each mixed block its bits plus a price for every unit of work a rank inside it costs, and take whichever code is cheaper at that price. At a price of nought this is the flag measured here; at a high enough price every mixed block takes its gaps. That end is already countable: on English words at 255 bits, giving every mixed block its gap code halves the in-block work, from 28.0 a rank to 12.9, and costs 0.186 bits a character. At 63 bits the same forcing costs 0.344.

The measurement that follows sweeps the price at every block length and draws each length’s curve of bits against work beside the curve this essay drew by changing the length. The prediction is that the two families of curves nearly coincide, so that a 255-bit block with a work-weighted flag reaches the 127-bit block’s work for about the 127-bit block’s bits, and no setting of the price beats simply choosing a shorter block by more than a hundredth of a bit a character. It could come out otherwise if the arrangement blocks that cost the most work are the ones whose gap codes are nearly as short: then a small price would buy most of the halving for little, and a long block with a weighed flag would dominate the short blocks on both counts. The question is whether the block length is the only dial the levels have left, or whether the flag, which took the optimum away, can also set where on the curve the levels stand.