A price the levels share

A flag that weighs the work as well as the bits gave the coded levels of a bidirectional index a second dial. Each level is a bit vector cut into blocks, and a block whose bits are not all one value is stored either as the index of its arrangement among all blocks with that many ones, or as the gaps between its changes of value. A flag for the blocks that change once chose between them on bits alone. The weighed flag charged each code its bits plus a price for every unit of work a rank inside the block costs: an arrangement must be decoded bit by bit up to the position asked, a gap code only up to the change before it. On the repetitive collection that price reached 0.156 bits a character below anything a block length alone could reach at the same work. On English words it reached 0.002, on DNA and protein nothing.

Its closing section argued that the price was one number only because the proposal had made it one. A wavelet tree splits the alphabet in half at its root, so the root’s bit vector follows the text letter by letter, while near the leaves a node separates a few letters that often come in runs. A level whose blocks change often should want a different price from one whose blocks change rarely. It proposed choosing the price for each level separately, by an exchange rate between bits and work, and predicted that on English words the deep levels would gain a few tenths of a bit of work for 0.02 to 0.04 bits a character below the curve of lengths, while the repetitive collection would gain little over its single price. It named the risk that the deep levels are short, so that a gain confined to them would be a gain on a small share of the index.

None of the three holds. The deep levels are not short, they want the price the root wants, and a price for each level reaches exactly as far as one price for all of them.

One price for each depth #

The index, the texts and the coding are the earlier essays’: both wavelet trees of a bidirectional index over 16,384 characters of each text, every node’s bit vector re-cut into blocks of 31 to 1,023 bits, the classes coded as runs, the superblocks every 32 blocks. A node’s depth is its distance from its tree’s root. The trees are balanced over the alphabet, so English words and the repetitive collection, with 21 letters each, have five depths, as does protein with 20; DNA has three.

The coding of a block depends only on its own bits and its own level’s price, so each depth’s bits and work can be read separately, each depth a point on the pair of axes bits and steps on one frame first drew, and they sum to the index’s: the sum is checked at every price and length. For an exchange rate $\lambda$, each depth takes the price that minimises its own bits plus $\lambda$ times its own work, and the index’s point is the sum over depths. Prices are drawn from a grid of twenty, from 0 to 10, finer than the earlier essay’s eight, so that no depth is denied the price it wants by the grid’s spacing; the single price is measured on the same grid. Every set of per-level prices chosen is then run through the coding as one array, and its totals must equal the summed point. The work unit is the earlier essays’: one unit for each directory entry or class run a rank reads and for each bit or gap it decodes inside the block.

The same frontier on English words #

On English words a price chosen for each level reaches 0.0023 bits a character below the curve the block lengths draw, at 255-bit blocks; one price for every level, on the same fine grid, reaches 0.0024. The prediction said 0.02 to 0.04. The two frontiers lie on top of each other at every work a rank from 9 units to 100, and where the per-level frontier has a point of its own, between two of the single price’s, it is better by at most three ten-thousandths of a bit a character. At the scale of the plate the three curves are two, the lengths’ and the prices’, and the prices’ curve is one curve whichever way it is priced.

The prices the levels choose, when they can choose, are nearly the prices they would have been given. At an exchange rate of 0.02, where English words’ levels first start buying work with bits, four of the five depths take a price of 1 and depth 3 takes 0.9. At every rate above it, four take 1.5 and depth 3 takes 0.9. Below 0.01 the levels choose prices from nought to 0.3 whose effect on bits and work is too small to separate on any plate here. A level that takes a slightly different price is a level whose blocks happen to straddle the grid’s steps slightly differently, and the index’s total does not move.

The same frontier on the repetitive collection #

On the repetitive collection a price for each level reaches the single price’s 0.156 bits a character below the lengths’ curve, at the same point: 1,023-bit blocks costing 0.458 bits a character for 9.7 units of work a rank. The prediction expected little gain here, since this text’s cheap blocks are cheap at every level, and that is what the plate shows; it shows it on English words too, which was not expected.

The repetitive collection’s whole advantage was a single move: at a price of a tenth, almost every arrangement block in a 1,023-bit level flips to its gap code, the work of a rank falls by a factor of five and a half, and the bits rise by eight thousandths of a bit a character. That move happens at the same price at every depth, which is why a price for each level finds the same point, at prices of 0.03 to 0.1 across the five depths. Any price in that range flips the same blocks.

Five levels that bend together #

At 255-bit blocks on English words every depth of the tree gives up half of its in-block work between prices of 0.6 and 0.8, and every depth holds exactly a fifth of the index’s positions. Two levels give it up at the step to 0.6 and three at the step to 0.8. The curves differ in where they start: depth 3, whose blocks change value least often, costs 0.174 bits a character and 4.9 units of work where depth 0 costs 0.332 and 10.2. They do not differ in where they bend, and the bend is all a per-level price could exploit.

The rate at which each level trades is the plainer statement of the same fact. Taking a level from price nought to a price of 10 costs depth 0 another 0.053 bits a character for 4.0 units of work removed, depth 1 0.033 for 2.3, depth 2 0.044 for 3.8, depth 3 0.025 for 2.4 and depth 4 0.032 for 2.5. Every depth pays between 0.010 and 0.014 bits a character for each unit of work it gives up. An exchange rate between bits and work is a price on that trade, and when every level offers the trade on the same terms, the best response of every level to any rate is the same, which is one price.

The second fact disposes of the risk the closing section named. A balanced wavelet tree sends every symbol through every depth until its code ends, which is why a search asks a rank at every level of it, so each depth’s nodes together hold one bit for every character of the text, and with codes of equal length every depth holds the same share. On English words, with 27 symbols on five-bit codes, that is a fifth each. A deep level would be short in a tree shaped by the symbols’ frequencies, where a common letter’s code ends near the root, which is the shape a code word is at least one bit measured; in the tree this index uses it is as large as the root.

On the repetitive collection every depth gives up half its in-block work at the same step of the price, to 0.1, and nearly all it will give up by 0.4. Each depth pays 0.0016 to 0.0022 bits a character for every unit of work it removes, a sixth of English words’ rate and the same at every depth. Here the curves are steep and short. A block of this collection that is coded as an arrangement is nearly always a long stretch of one value with a few changes, a gap code is barely longer, and the work a gap code saves is most of the block. That is as true at depth 4 as at the root, because the collection’s repeats are copies of whole stretches of text, and a copy repeats its letters at every depth of the tree at once.

The price a block wants #

The price at which a block of English words would rather be a gap code has a median of 0.60 to 0.79 at every depth, against 0.08 to 0.10 for the repetitive collection and 0.73 to 0.85 for protein. Each block has such a price: its gap code’s extra bits over its arrangement’s, divided by the work a rank inside it would save per position. A price for each level could help only if the levels’ blocks wanted different prices, and the plate shows that they want the same one within a factor of 1.3 on each text, while the texts want prices a factor of eight apart.

The reason is in what a block’s choice depends on. An arrangement costs about $\log_2 \binom{L}{c}$ bits for a block of $L$ bits with $c$ ones and charges a rank for every bit before its position; a gap code costs about two logarithms a change and charges a rank for every change before it. A block’s price is therefore set by how many times its bits change value, against how many ones it holds, and that is a property of how the text’s letters alternate between the two halves of the alphabet each node separates. In English, that alternation is about as frequent at every depth, because a word’s letters fall on both sides of almost any division of the alphabet. In the repetitive collection it is rare at every depth. Protein’s letters are drawn at random, so its blocks change value as often as random bits do at every depth, nearly all of them are best as arrangements, and the few that could flip want about the price English words’ blocks want, 0.73 to 0.85.

The other number on the plate is how much of each level is still on the table. On English words 52% to 77% of every depth’s mixed blocks are already gap codes at price nought, because a gap code is shorter than its arrangement whenever a block changes value only a few times. The price acts on the remaining quarter to half. The optimum the flag took away measured how the flag moved the best block length, and the plate here explains why one dial on top of the length is enough: what is left for a price to act on looks the same from every depth.

How far below the curve, on every text #

A price for each level reaches 0.0023 bits a character below the lengths’ curve on English words, 0.156 on the repetitive collection, 0.0002 on protein and nothing on DNA, and on no text more than a ten-thousandth of a bit beyond one price for every level. The finer grid adds a ten-thousandth on English words over the earlier essay’s eight prices and nothing anywhere else. Whatever a price does to these levels it does through one number.

DNA and protein confirm the plate from the other side. Their letters are drawn at random, so every level’s blocks are random bits, arrangements are as short as anything can be and gap codes are long; a price high enough to flip a block costs more bits than any length change does, and no setting of the price at any depth reaches below the lengths’ curve. That is the earlier essay’s result for one price, and per level it holds the same way.

What the prediction got right #

The closing section predicted that English words’ deep levels, which separate a few letters that come in runs, would want a lower price than the root, and that pricing them separately would reach 0.02 to 0.04 bits a character below the curve of lengths. The deep levels do not want a different price. Their blocks cost fewer bits and less work than the root’s, as the levels plate shows, but they trade the two at the same rate, so the price that bends one bends all. A per-level price reaches 0.0023, the same as one price.

It predicted the repetitive collection would gain little over its single price’s 0.156. It gains nothing, which is little. And it named the risk that deep levels are short. In a balanced tree they are exactly as long as the root, a fifth of the index each on English words, so a gain at the deep levels would have been a gain on most of the index had there been one.

What the measurement settles is the question the section asked: whether a text’s levels differ enough in their blocks that a price fitted to each beats a price fitted to the text. On these four texts, a text’s character is the same at every depth of its tree, in the one respect the flag reads.

What these levels do not settle #

One tree shape. Both trees are balanced over the alphabet. A tree shaped by symbol frequencies has short deep levels holding the rare letters, whose blocks may well want a different price, and none was built.

One size of text. Every text is 16,384 characters, and on English words each depth at 255-bit blocks has about seventy-five mixed blocks, a quarter to a half of them arrangement-coded. A per-level price on a text a hundred times longer would be fitted to many more blocks, but it would be fitted to the same distribution, and nothing here suggests the distributions would separate.

One unit of work. A bit decoded, a gap passed and a directory entry read each cost one unit. If decoding an arrangement were cheaper per bit than reading a gap, the price at which blocks flip would move, by the same factor at every depth.

Still open: a price that follows the block #

A level’s blocks want prices spread over a factor of two or three between the first and third quartile, and the spread within a level is wider than the difference between levels. A price set for the level treats its blocks as one market; the flag already makes a decision block by block, and could make this one too.

The measurement that follows gives every arrangement block its own decision: flip it to its gap code exactly when its own price, extra bits over work saved per position, is below the exchange rate. That is what one price does already, since one price flips exactly the blocks whose own price is under it, so the prediction is that it reaches the same frontier, on all four texts, as one price does now. What could move is the work unit. A rank that lands in a block decodes up to the position asked, and positions are asked unevenly when the queries that reach a level come from a text’s commonest patterns. The measurement therefore weights each block’s work by how often a pattern search’s ranks land in it, counted on the earlier essays’ pattern sets, and asks whether a block that is often asked should be priced differently from one that is rarely asked. The question is whether the price a block wants is a property of the block’s bits, which every level shares, or of the queries that reach it, which they do not.