A flag for the blocks that change once

Six bits a class took the classes out of a bidirectional index’s coded wavelet-tree levels. Every level is a bit vector cut into blocks of 63 bits, and each block is stored as its class, the number of ones it holds, and its offset, which of the arrangements with that many ones it is. A block of all zeros or all ones needs no offset. Coded by their runs, the classes fell from 0.48 bits a character to 0.32 on English words, and what was left of the levels was mostly offsets: about 1.3 bits a character of the 1.72, the rest being the superblocks’ counts and pointers.

An offset is stored in $\lceil \log_2 \binom{63}{c} \rceil$ bits for a block with $c$ ones, which is what it costs if every arrangement of $c$ ones is equally likely. The essay’s closing section doubted that. On English words a mixed block usually straddles a change of letter in the transform, so its ones should come in one or two stretches, not scattered, and blocks like that are a small fraction of all the blocks with that many ones. It proposed coding a mixed block’s offset as the positions where its bits change, a gamma code for each gap between changes, and predicted the offsets would fall by about a third on English words. On random letters, whose blocks change value about thirty times, the arrangement’s index is already the shortest description, and the gaps should cost more.

The first half of the reasoning is right about a third of the blocks and wrong about the rest, and the gap code it proposed loses on its own.

Three ways to hold an offset #

The index is the earlier essays’ throughout, at 16,384 characters of each of four texts: DNA and protein letters drawn at random, English words, and a repetitive collection. The classes are coded as runs, as the earlier essay left them, and only the offsets of mixed blocks change. The arrangement’s index is the offset as built. The gaps between changes stores the block’s first bit, the number of value changes $t$ in a gamma code, and the distance between each change and the one before in a gamma code. A block with one change costs its first bit, one bit for $t = 1$, and about $2 \log_2$ of the change’s position. The shorter behind a flag spends one bit a mixed block to say which of the two follows. Uniform blocks need no offset under any coding and no flag. Sizes are bits a character of text over both trees, the unit every earlier measurement of this index used.

Four per cent more, and then a fifth less #

On English words the gaps between changes cost 1.325 bits a character against the arrangement’s 1.277, 4% more, where the prediction was a third less. Behind a one-bit flag, each block taking whichever is shorter, the offsets cost 1.008, 21% less than the arrangement. On the repetitive collection the gaps alone take the offsets from 0.468 bits a character to 0.257, 45% less, and the flag takes them to 0.213, more than half off. On random letters the gaps cost 37% to 40% more and the flag about 2% more, the price of one bit for every mixed block on texts where the arrangement always wins.

The prediction was right about the repetitive collection and right about random letters. On English words it was wrong about which blocks it was describing. That is visible in how often the blocks change.

A third that change once, and the rest that change twenty times #

A third of the mixed blocks on English words change value exactly once, as the prediction pictured; only 2% more change two to four times and 4% five to nine, and 61% change ten times or more, a mean of 16.5 over all of them. The distribution is two populations, not one with a long tail. The blocks that change once are the ones the earlier essay described, straddling a boundary in the transform where one letter’s run ends and the next begins. The others sit in stretches of the transform where neighbouring contexts are preceded by different letters, and there a level’s bits change nearly as often as a coin’s.

The repetitive collection has the population the prediction assumed: 90% of its mixed blocks change at most four times, because its transform is long runs of a few letters with clean boundaries. Random letters have only the other population, every mixed block changing twenty or thirty times. English words have both, about one block in three of the first kind and two of the second, and a single coding for all of them suits neither.

Why English words have both kinds #

A level of the wavelet tree is a bit vector over the transform’s output: at the top level each position says which half of the alphabet its letter falls in, and each level below splits a half again. The transform that emits nothing found the Burrows–Wheeler transform changing no letter’s frequency and everything about their order, gathering the letters that precede each context into runs. A level’s bits change wherever the transform’s letter crosses from one half of the level’s alphabet to the other. Where the transform holds a long run of one letter, the level is uniform for the length of the run, and a block that straddles the run’s end changes once.

English words give the transform two kinds of stretch. Where a context is common and predicts its preceding letter well, as "he " is preceded most often by the “t” of “the”, the run is long and the level’s blocks are uniform or change once. Where contexts are rare or ambiguous, the preceding letters vary from one context to the next and the level changes value every few positions. The repetitive collection is long stretches of the first kind and almost nothing of the second. Random letters are all of the second.

So the two populations are not a quirk of this text. They are the two regimes of a context model, a context that predicts its letter and one that does not, seen through one bit of the letter at a time. The part every saving left alone found block coding taking English words’ levels below their zeroth-order entropy, because a block of one value costs no offset at all and the first regime makes many such blocks. The arrangement’s index then treats every mixed block as though it came from the second regime, and a third of English words’ mixed blocks come from the first.

What decides which code wins #

A block that changes value once costs 11.3 bits as gaps and 43.7 as an arrangement; one that changes sixteen times costs 56.8 as gaps and 38.0 as an arrangement. The two codes measure different things. The gaps grow with the number of changes, two to three bits for each. The arrangement’s index depends on the class: $\binom{63}{c}$ is largest when $c$ is near half the block, whatever the bits look like, and a block that changes once can have any class, since its one change can fall anywhere. Its arrangement then costs up to sixty bits to say something that needs seven, a first bit and a position. That is where the arrangement code’s waste is, and it is all in the blocks that change once.

In between, the arrangement’s cost follows the class, and blocks with few changes and a small class, a short stretch of ones in a block of zeros, are cheap as arrangements and dear as gaps: two changes cost 7.4 bits as an arrangement and 12.3 as gaps. Neither code is right for every block, and the flag is the obvious repair. It sends 35% of English words’ mixed blocks to the gaps, almost exactly the blocks that change once, and the rest to the arrangement. On the repetitive collection it sends 54%.

A block, a class and an offset built the class-and-offset coding to reach the zeroth-order entropy of a block’s bits. The gaps reach for something else, the regularity inside a block, and they do it only where the regularity is there. The runs a permutation does not leave measured gamma-coded runs on a grid of a different kind and found them a loss below a mean run of about six. The same arithmetic is at work here: a block that changes once has runs averaging thirty-one bits, far above six, and one that changes twenty-four times has runs under three.

The levels, a quarter under where the classes left them #

With the flag, the levels on English words fall from 1.72 bits a character to 1.45, and on the repetitive collection from 0.88 to 0.63. That takes the English levels below the 1.5 the classes’ essay had hoped to reach by coding classes alone. On random letters the levels are a few hundredths larger with every refinement since six-bit classes, since each refinement adds a pointer or a flag that random text never repays.

The saving on English words, 0.27 bits a character, comes entirely from the third of the mixed blocks the flag sends to the gaps; the other two thirds each pay a bit for the flag and save nothing. A coding that wanted more would have to find structure in the blocks that change twenty times. Those are close to random at the level of a block, and the arrangement’s index is the shortest description of a random block with a known class. The level where compression stops paying found that choosing a coding level by level saved five hundredths of one per cent and cost more to describe than it saved; a choice made block by block, behind a single bit, is the version of that choice that pays, because the blocks differ far more than the levels did.

What the flag costs where it is not needed #

On random letters the flag is pure cost. Every mixed block pays one bit to say that the arrangement follows, and on random DNA that is 1,173 blocks, 0.036 bits a character over both trees; on random protein, 2,410 blocks and 0.074. The plates show it as the 2% the flag adds there. A code word is at least one bit met the same floor from the other side: a choice between two codes cannot be signalled in less than a bit with a prefix code, however lopsided the choice.

A text-wide switch would avoid it. The index could decide once, when it is built, whether any mixed block of a level would take the gaps, and spend the flag only on levels where some would. On random letters no block would, the flag would vanish, and the levels would cost what the arrangement costs. On English words nearly every level has some one-change blocks, and the switch would change nothing. Choosing codings level by level saved five hundredths of a per cent on the grid where it was measured; here a switch would matter only for texts with no long runs at all, and those are the texts where none of the codings since the arrangement has helped.

A cheaper flag is also possible. The class already says something about which code will win: a block whose class is near zero or near 63 has few arrangements and is cheap as an arrangement, while a block whose class is near half and whose bits change once is the arrangement’s worst case. A flag coded by class, short where the choice is predictable, would cost less than a bit a block on English words. It would cost nearly a bit on random letters all the same, since there the flag’s value is always the same and the class says so only weakly.

A rank reads less inside a block that changes once #

A rank inside a mixed block reads 31 bits on average when the block is decoded from its arrangement and read to the position, and 10.3 gap codes on English words when it is read as gaps, 3.1 on the repetitive collection. The earlier essays counted a rank’s work inside a block as the bits it reads up to its position, and a gap code says how many bits to skip at once. On a block that changes once, a rank reads the first bit, the change count and one gap, and knows the answer for every position in the block. On random letters the gaps still halve the reads, since each gap covers a couple of bits.

This is a count of code words, not of time. Bits and steps on one frame set a sampled structure’s size and its walk on one plate because neither alone is the answer, and decoding a gamma code is several machine operations where reading a bit of a decoded block is one. The flagged coding keeps the arrangement for the blocks where the gaps would be long, so the reads on English words are a mixture of the two, and nothing here measures the mixture’s cost on a machine.

Where the measurement stops #

One block length. Every block is 63 bits, as the earlier essays built them. A coding that rewards blocks with one change would favour longer blocks, which straddle fewer boundaries per bit, and the class and flag costs move with the length too.

Gamma codes only. The gaps are coded with Elias gamma, the same gamma code the classes’ runs used. A block that changes once needs only its first bit and a position, seven bits, where the gamma code spends about eleven; a code that treated one change as a special case would save about four bits on each of those blocks, about 0.04 bits a character on English words.

Pooled over levels. Every count is pooled over all the levels of both trees. Which levels hold the blocks that change once, and whether the two regimes divide by level as well as by stretch of the transform, was not measured.

Four texts of 16,384 characters. These are the four texts every measurement of these levels has used. On a longer English text the transform’s runs grow longer and the share of blocks that change once should rise, but that is an argument and not a measurement.

Still open: the block length the change points want #

The flag made one change in the levels’ economy. Under the arrangement’s index, a block that straddles one boundary of the transform costs as much as a block of the same class with its ones scattered, so a longer block was mostly a way to spend more bits on scattered ones. Under the flagged coding, a block that straddles a boundary costs about eleven bits whatever its length, and a longer block straddles proportionally fewer boundaries for its bits. The class and superblock costs, which favour long blocks, and the many-change blocks, which favour short ones, are the other side of the balance.

The measurement that follows rebuilds the levels with blocks of 15, 31, 63 and 127 bits, classes as runs and offsets coded the shorter way, and finds each text’s best block length. The prediction is that English words’ best length moves from 63 to 127 bits, because the one-change blocks become cheaper per bit as they grow and the many-change blocks cost about the same in arrangement bits at any length. The repetitive collection should move further, and random letters stay where they are. It could fail on the many-change blocks. A 127-bit block in a mixed stretch of the transform is twice as likely to catch a stray run, and if the many-change population grows faster than the one-change population shrinks, longer blocks only spread the cost.