A flag that weighs the work as well as the bits

The optimum the flag took away rebuilt a bidirectional index’s wavelet-tree levels at block lengths from 15 to 1,023 bits and found that the length no longer has a best value. Every block of a level’s bit vector is stored as a class, how many ones it holds, and for a mixed block an offset that says which arrangement it is — the layout a block, a class and an offset built and the index that is smaller than the text first swept for its best length. A flag for the blocks that change once let each mixed block choose its offset’s code: the index of its arrangement among all arrangements with that many ones, or the gaps between its value changes, with one bit to say which. Under that flag a longer block costs fewer bits on every text — English words fall from 1.431 bits a character at 63-bit blocks to 1.304 at 1,023 — and the length is set instead by the one thing still growing with it, the work of a rank.

Its closing section noticed that the decoding has two costs and the flag sees neither. A rank inside a block held by its arrangement must decode the arrangement bit by bit up to the rank’s position, half the block on average. A rank inside a block held by its gaps reads gap by gap, and a block that changes value a few times is passed in a few steps. The flag chooses on bits alone. The proposal was to charge each code its bits plus a price for every unit of work a rank inside the block would cost, and take the cheaper. At a price of nought that is the flag as built; at a high enough price every mixed block takes its gap code, which on English words at 255 bits halves the in-block work, from 28.0 a rank to 12.9, for 0.186 bits a character. It predicted that sweeping the price would trace nearly the same curve as sweeping the length, so that no price beats simply choosing a shorter block by more than a hundredth of a bit a character, and named the case that would prove it wrong: arrangement blocks that cost the most work but whose gap codes are nearly as short.

The price, and what it is charged against #

The levels are the earlier pages’ exactly: both wavelet trees of an index over 16,384 characters of four texts — DNA and protein letters drawn at random, English words, and a repetitive collection of near-copies — cut into blocks of 31 to 1,023 bits, classes stored as runs as six bits a class stored them, superblocks every 32 blocks. The work of a rank — the one operation these levels exist for, as rank is the only thing it does put it — is the earlier pages’ unit: one for the superblock’s entry, one for every class run passed inside the superblock, and inside the block either every bit before the position for an arrangement or two plus every change passed for a gap code.

The flag now charges each code its bits plus the price times the in-block work a rank costs, averaged over the block’s positions. For a block of $m$ bits held by its arrangement that work is $(m-1)/2$ a position; held by its gaps it is two plus the changes passed, averaged. The price is in bits per unit of work. It is swept over 0, 0.01, 0.03, 0.1, 0.3, 1, 3 and 10, at every length, and each setting is charged in the same two numbers the earlier page drew: bits a character over both trees, and the work of an average rank.

On English words the length is the only dial #

On English words every price is dominated by a shorter block: 255-bit blocks at a price of 1 cost 1.484 bits a character for 22.9 units of work a rank, where 127-bit blocks on bits alone cost 1.367 for 23.6. Each length’s faint curve runs up and to the left from its point on the bold curve, toward less work and more bits, and every one of them stays above the bold curve the lengths draw. The prediction holds here and more strongly than it was stated: the price does not come within a hundredth of a bit of the length, it comes nowhere below it.

The earlier page’s number for the extreme holds to the bit. Forcing every mixed block at 255 bits to its gap code costs 1.512 bits a character against 1.325 on bits alone, 0.187 more, and cuts the in-block work from 28.0 to 12.9, as the proposal computed. But 1.512 bits for 21.6 units of work a rank is what 127-bit blocks almost achieve without any forcing, 1.367 for 23.6, and the price’s intermediate settings are spread along a curve between those two points that bows the wrong way. Buying work back by paying for gap codes is dearer, on English words, than buying it back by cutting the block in half.

On the repetitive collection it is not #

On the repetitive collection the weighed flag is a second dial worth having: 1,023-bit blocks at a price of 0.1 cost 0.458 bits a character for 9.7 units of work a rank, where 63-bit blocks on bits alone cost 0.607 for 10.5. The longest block, priced, does less work than every block length but the shortest and costs less than every one but itself. Its faint curve does not rise gently toward the bold one; it falls almost straight down in work, from 54.6 units a rank to 9.7, for 0.008 bits a character.

This is the case the proposal named as the way it could fail. On this text the blocks the flag holds by their arrangement are the ones whose gap codes are nearly as short, and they are also the ones that cost the most work, because an arrangement is decoded bit by bit and these blocks are long. A small price moves all of them to their gap codes at once: at a price of 0.1 the in-block work at 1,023 bits falls from 50.6 units a rank to 5.6. What is left of a rank’s work is the superblock and the class runs, which grow with the length much more slowly. The best setting is the longest block, priced.

The two other texts #

On protein, and on DNA, the price moves each length along a curve that lies on or above the curve the lengths draw. Random letters give the levels blocks that change value many times, so their gap codes are long, and the flag already holds almost every mixed block by its arrangement for good reason. A price moves a few of them to their gap codes and pays for each in full. On DNA at 1,023 bits a price of 0.03 removes 10.6 units of in-block work a rank for a thousandth of a bit — the few cheap flips there are — and then nothing more is cheap.

These two texts are the earlier page’s controls. Random letters were the text whose best length the earlier essays found least affected by any coding change, and here too nothing in the price separates them from the lengths. If the price bought anything on these levels it would be suspicious.

How far below the curve #

Measured against the curve the block lengths draw, the price reaches below it on one text of four: on the repetitive collection by 0.156 bits a character, at 1,023-bit blocks and a price of 0.1; on English words by 0.002, and on DNA and protein not at all. The curve here joins the measured lengths, linear in the logarithm of work, so a priced point is credited only for what no length between two measured ones could be expected to do. On English words the 0.002 is one point at 255 bits and a price of 0.1, under the curve by less than the curve’s own interpolation could be trusted to.

A simpler measure overstates the price. Asking for the fewest bits within a fixed budget of work credits protein with 0.15 bits a character at a budget of 40 units, because the 63-bit blocks do 41.8 units on bits alone and 39.2 at a price of 1, just inside the budget, while the next length down is far outside it. That is the price filling a gap between two measured lengths, which a 47-bit block would fill as well, and the distance below the curve does not credit it.

Why one text and not the others #

At 255-bit blocks the price buys work cheaply on the repetitive collection and dearly on English words: taking ten units of in-block work off a rank costs 0.010 bits a character on the one and 0.096 on the other. Each text has about 125 blocks the flag codes by their arrangement at this length, 126 on English words and 124 on the repetitive collection, and they are entirely different blocks.

On English words they change value 96 times on average. They are the blocks in the mixed stretches of a level, where a node’s bit vector alternates on almost every character, and a gap code for 96 changes costs 48 bits more than the arrangement’s index, so turning one of them to its gap code costs 48 bits to save the work of decoding up to a position. On the repetitive collection they change value 3.6 times on average, and 64 of the 124 change exactly twice: a single short run of ones in two hundred and fifty-five bits, most likely the mark a near-copy leaves where it differs from the others. For such a block the arrangement’s index is a few bits shorter than its gaps, so the flag takes it, and decoding it means reading up to half the block to find two changes. Its gap code costs 10.5 bits more and is read in three steps. The repetitive collection’s arrangement blocks are the cheapest possible case for the price and English words’ are the dearest.

A flag for the blocks that change once found that a block straddling one change of value costs about eleven bits however long it is, under the flag; this is the other half of that finding. The blocks that change twice are just short enough to stay with their arrangement on bits, and they are exactly the blocks a rank pays most to enter. A flag that counts only bits makes the wrong choice for them, and on a text full of them, a collection of near-copies, the wrong choice is most of the work.

Where a rank’s work goes once the price is paid #

The work of a rank has two parts, the directory — the superblock’s entry and the class runs passed inside its superblock — and the decoding inside the block, and the price acts only on the second. On the repetitive collection at 63-bit blocks on bits alone, a rank does 10.5 units of work: 3.5 inside the block and 7.1 in the directory. At 1,023-bit blocks priced at 0.1 it does 9.7: 5.6 inside the block and 4.1 in the directory. The longest block wins on both parts at once. Its blocks are sixteen times longer, so a superblock of 32 of them spans sixteen times more of the level, but on a collection of near-copies most of those blocks are uniform and their classes come in long runs, so a rank passes fewer runs than at 63 bits, not more. The in-block part rises a little, from 3.5 to 5.6, because a priced long block still holds a few arrangements whose gap codes really are long.

On English words the same split goes the other way. At 127-bit blocks on bits alone a rank does 23.6 units: 14.4 inside the block and 9.2 in the directory. At 255 bits priced at 1 it does 22.9: 14.3 inside and 8.6 in the directory — the price has brought the in-block work of a block twice as long down to the shorter block’s, and paid 0.117 bits a character to do it, because the blocks it had to flip were the many-change blocks the supply curve priced dearly. The directory barely moves. So on English words the length governs both parts of a rank’s work together, and on the repetitive collection the long block removes the directory’s share while the price removes the decoding’s, which is why the two dials are independent there and redundant here.

What the flag is for #

The proposal asked whether the block length is the only dial the levels have left. On three texts it is: the length sets where on the curve of bits against work the levels stand, and the flag, charged for work, only moves along that curve or above it. On the fourth, the price is a second dial, and a strong one — it lets the longest block, whose bits are lowest, do less work than blocks a sixteenth of its length.

Bits and steps on one frame put an index’s size and its operations on one plate so that neither could be quoted without the other, and these plates are four more of that kind. Their lesson is the earlier pages’ in a narrower setting: an encoding chosen on space alone makes a choice about time without pricing it, and whether that choice is costly depends on the text. A flag that weighs both can be set once, with a price of about a tenth of a bit a unit of work, and it costs nothing on English words or random letters — it never reaches below the curve there by more than 0.002 bits a character — while on a repetitive collection it takes the work a rank does at the longest blocks from 54.6 to 9.7.

What these levels do not settle #

One price for every level. The price is one number for the whole index. Levels near the root and levels near the leaves have different blocks — the deep levels of a repetitive collection’s tree are where its near-copies’ differences are — and a price set per level, or per superblock, could do better where the blocks differ.

One unit of work. The work is counted in the earlier pages’ unit, every bit decoded and every gap read counted as one. A real decoder reads arrangements by table lookup, several bits at a time, which would cut the arrangement’s work in this unit on every text and shrink the price’s advantage on the repetitive collection with it; the gap code’s steps would not shrink.

One size of text. Every level is from 16,384 characters. A larger repetitive collection whose copies differ at the same rate would have blocks of the same kinds, but its superblock and class-run work would grow, and the share of a rank’s work the price can remove would fall with it; the collection decides which index is small is the reminder that how a collection repeats decides more than its size does.

Still open: a price set for each level #

The price was one number because the proposal made it one, and the plate of supply curves says it should not be. A text’s arrangement blocks are cheap or dear to flip according to how often they change, and how often a block changes depends on its level: near the root a wavelet tree splits the alphabet in half and its bit vector alternates with the text’s letters; near the leaves it separates a few letters that often come in runs.

The measurement that follows sets the price separately for each level of the tree, choosing for each the price that minimises that level’s bits plus a common exchange rate times its work, and sweeps the exchange rate. The prediction is that on English words the per-level prices find what the single price could not, a few tenths of a bit of work at the deep levels where words repeat their endings, and reach 0.02 to 0.04 bits a character below the curve of lengths; and that on the repetitive collection they add little to the single price’s 0.156, since its cheap blocks are cheap at every level. It could fail on the levels’ sizes: the deep levels are short, a few hundred bits, and a gain confined to them is a gain on a small share of the index. The question is whether the levels of one index differ enough in their blocks that a price fitted to each beats a price fitted to the text, or whether a text’s character is the same at every depth of its tree.