Six bits a class

The part every saving left alone coded every level of a bidirectional index’s wavelet trees in blocks of 63 bits. Each block became its class, the number of ones it holds, in six bits, and its offset, which of the arrangements with that many ones it is. On English words that took the levels from nearly six bits a character to under two, because the Burrows–Wheeler transform groups letters and a level’s blocks are often all zeros or all ones. Once the offsets had shrunk, the classes had not. They are six bits for every block whatever the block holds, and on English words, with the superblock counts beside them, they had become a quarter of the levels.

Its closing section proposed coding the class sequence itself. On a text whose blocks are mostly uniform, most classes are 0 or 63, and runs of one class value could be stored as the value and a length. A pointer into the run stream at every superblock would let a rank still find its place. The prediction was that on English words and the repetitive collection the classes would fall by more than half, taking the levels from 1.90 bits a character to about 1.5. On random letters, whose classes are spread, nothing would be saved.

Three ways to hold the classes #

The index and its offsets are the earlier page’s, untouched. The superblock counts and offset pointers stay as they were. Only the classes change, three ways. Six bits a class, as built: a rank finds block j’s class at a known position and sums the classes before it in its superblock. One entropy code: a single Huffman code over the class values of every level in the index, its table stored once. Runs of a class: the class sequence as runs, each run its value in six bits and its length in an Elias-gamma code, which the runs a permutation does not leave priced for a grid’s bits.

Both variable-length codings lose something the fixed one has: a class can no longer be found by its position. A rank must start where its superblock’s classes begin and decode forward. So each superblock gets one more entry, a pointer into the class stream, and it is charged to both. The texts are the earlier page’s four, 16,384 characters each: DNA and protein letters at random, English words and a repetitive collection. Sizes are bits a character, averaged over the two halves. Reads are vector entries read an extension of 64 exact backward searches of eight characters.

A third off, not half #

On English words the classes fall from 0.480 bits a character to 0.323 as runs and 0.344 under one entropy code: a third off, not the half predicted. The repetitive collection does better under the entropy code, 0.266, which is the half the prediction asked for, and less well as runs, 0.295. On random protein the entropy code saves a little, 0.481 to 0.461, and runs make the classes larger, 0.535. On random DNA both save a little.

The prediction’s premise was right about the values and wrong about their arrangement. Most classes on English words are 0 or 63, and that is what the entropy code uses. They do not come in long runs, and runs were what the proposal meant to use.

Uniform blocks, in short stretches #

On English words 45% of the blocks are all zeros and 21% all ones, two thirds uniform, yet a run of one class value lasts 2.17 blocks on average. A block of 63 bits in one level is uniform when 63 consecutive characters of the transform all go the same way at that level’s split. The transform’s runs of one letter are often that long on English words, and often not. A stretch of the transform where one letter repeats gives a few uniform blocks, then a block that straddles the change of letter is mixed, then the next letter’s uniform blocks may be zeros or ones. The uniform blocks are common, and they are broken up.

The bits underneath say the same thing more exactly. In the forward tree on English words, a level’s stretches of one bit value of at least 63 bits — the only ones that can make a block uniform — number 189, average 340 bits and hold 78.5% of all the levels’ bits. A stretch of 340 bits covers five or six blocks, but its first and last blocks usually straddle its ends and are mixed, so it yields a run of about four uniform blocks. Between those runs sit the mixed blocks, a third of all blocks, whose classes are whatever counts of ones they happen to hold and rarely equal their neighbours’. Each of those is a run of one. The mean of 2.17 is long uniform runs averaged with many runs of a single mixed block.

The transform’s own runs are shorter still. Its runs of one letter on English words average 3.43 characters, and a level’s bit runs are longer only because a level merges letters on the same side of its split: a run of the bit 0 at the top level is any stretch of letters from the alphabet’s first half. The transform that emits nothing measured the clustering as runs of letters. The levels see it as runs of halves, quarters and eighths of the alphabet, and a block of 63 bits sees it at a resolution of 63 characters.

A run code pays six bits for the value and a gamma length for every run. A run of one block costs seven bits, more than the six it replaces. A run of two costs nine where twelve were spent, and a run of four costs eleven against twenty-four. At a mean of 2.17 blocks the saving is about a third, which is what was measured. The prediction assumed runs as long as the transform’s own, and a class run is a run of 63-character blocks, which is a much coarser thing.

A block, a class and an offset found the same kind of distinction on a grid. Its blocks’ classes were spread, and the coding saved there what the spread of the bits allowed. Here the bits are grouped, and the question is whether the grouping survives being cut into blocks of 63. On English words it partly does.

The class values themselves #

On random protein the classes pile up in the middle, and their entropy is 5.01 bits where six are spent. On English words they pile up at both ends, and their entropy is 3.51. No coding of a fixed width can be right for both. Six bits allows for every count from 0 to 63 equally, and no text produces that. A random block’s count of ones clusters around its mean like any sum of coin flips, so even random letters leave a bit a class on the table. English words leave two and a half.

The entropy code reads those distributions directly, which is why it does well on the repetitive collection, the most bimodal of the four, and why it saves something on protein where runs lose. Runs read a different property, how the values follow one another. On English words the two properties are worth about the same. On the repetitive collection the distribution is worth more. On random letters only the distribution is worth anything.

Random DNA sits between. Its balanced tree has three levels for four letters and the end marker. The last letter, t, gets a code whose second and third bits are always zero, so the two nodes below it hold nothing but zeros, and the end marker, which occurs once, shares a node with a, so that node is nearly all ones. Those three nodes are DNA’s 17% all-zero blocks and 8% all-one, and both codings find something to save, 0.010 bits a character under the entropy code and 0.029 as runs. It is the same waste of the balanced shape that the earlier page found the block code taking back, seen again in the classes: a node that says almost nothing still has a class for every block, and coding the classes is what finally makes it cost almost nothing.

What the pointers cost #

On random protein the entropy code’s own bits are 0.422 a character against six bits a class at 0.481, a saving of 12%. The pointers it needs, 0.039, take that to 4%. A pointer is the position of a superblock’s classes in the stream, about twelve bits for every 32 blocks, and it is the price of decoding forward instead of indexing. On English words and the repetitive collection the entropy code saves enough for the pointers not to matter. On random letters they consume most of the saving, and an implementer would reasonably keep six bits a class there.

This is the same kind of cost the structure paid for before the first query found in a grid’s rank directory: bits that answer nothing on their own and exist so that a query can start in the middle. Every variable-length coding of a sequence that must be searched pays some version of it. The fixed-width classes paid none because their position was their pointer.

What a rank reads #

Walking runs instead of classes, an extension on English words reads 365 vector entries against 429, 15% fewer. A rank sums the ones in every block before its own in its superblock. With fixed classes it reads each of those classes, sixteen on average. With runs it reads each run, and a run of three blocks is one read. So the coding that saves bits on English words also saves reads, which is rarer than it sounds: the earlier page’s block coding cost 1.4 times the reads of the plain levels for its saving.

An entropy-coded class stream saves no reads. Its classes are still read one at a time, and decoding a variable-length code is, if anything, slower per class than reading six bits at a known offset. So on English words the two codings that cost about the same bits differ in what they do to a search. Runs save 15% of the reads, and the entropy code nothing. On the repetitive collection, where the entropy code is 0.03 bits a character smaller, runs still save 18% of the reads, and the choice depends on which currency the index is short of.

Bits and steps on one frame set the rule that a size saving is drawn beside its cost in operations. Here, for once, the two move the same way on the texts where either moves at all.

The levels as a whole #

On English words the levels go from 1.877 bits a character to 1.720 with runs, a twelfth off, where about 1.5 was predicted. The classes were a quarter of the levels, and a third off a quarter is a twelfth. On the repetitive collection the entropy code takes the levels from 1.068 to 0.853, a fifth off, because there the classes were nearly half of what remained.

Against the plain levels these are refinements. The block coding took English words from 5.97 bits a character to 1.88, and the class coding takes another 0.16. What it changes is the shape of what is left. The offsets are now 1.40 bits a character on English words, the classes 0.32 and the superblock counts and pointers the rest. The offsets are the part that reflects the text, and the next saving has to come from them. The level where compression stops paying found the point on a grid where further coding cost more than it saved. This index is near that point for its directory, and still some way from it for its offsets.

Which coding, for which text #

The four texts give three different answers. On random letters, keep six bits a class. The entropy code’s saving there is real but the pointers take most of it, and runs make the classes larger because a mixed block’s class almost never repeats. On English words, use runs: they save the most bits, 0.157 a character against the entropy code’s 0.136, and they are the only coding that also saves reads. On the repetitive collection the entropy code saves more bits, 0.214 a character against runs’ 0.185, and runs save the reads, so the answer depends on which the index is short of.

None of this can be decided without looking at the text, and all of it can be decided by looking at the class sequence once, at build time. A builder that counted the class values and their runs for each level could choose per level. A level whose classes are spread keeps six bits, a level of long uniform stretches takes runs, and a bimodal level without long stretches takes the entropy code. The measurements here chose one coding for the whole index, and a choice per level would do at least as well. A code word is at least one bit is one reason the choice is not obvious even per level: an entropy code cannot spend under a bit on a class, however common, so on a level that is almost all one class the run code wins by a margin the class distribution alone does not show.

The limits of the measurement #

One block length, one superblock. Blocks of 63 bits and superblocks of 32 blocks are the earlier page’s. With longer blocks a uniform stretch is fewer, longer classes. With shorter ones there are more classes and the class coding matters more. Neither was swept.

One code for every level. The entropy code is shared by all the levels of both trees. Levels differ: the top level of a balanced tree over English words is biased differently from its bottom level. A code per level would fit better and cost a table each, which on these sizes was found to cost more than it saved.

Two pointers where one might do. Each superblock already holds a pointer into the offsets, and the variable-length class stream adds a second. A layout that stored each superblock’s classes and offsets together, classes first, would need only one pointer, and on random protein that would recover most of the 0.039 bits a character the second pointer costs. It was not built.

Reads, not time. Decoding a gamma length or a Huffman code word costs more per entry than reading six bits at a fixed position, and the reads count every entry the same.

Still open: the offsets, read as a stream #

With the classes coded, the offsets are what is left of the levels on English words: 1.40 bits a character out of 1.72. An offset says which arrangement of its class a block is, and for a uniform block it is empty. For a mixed block it is ⌈log₂ C(63, c)⌉ bits, as if every arrangement were equally likely. On English words a mixed block usually straddles a change of letter, and its ones come in one or two stretches, not scattered. Those arrangements are a small fraction of all arrangements with that many ones.

The measurement that follows codes a mixed block’s offset as the positions where its bits change, a gamma code for each, instead of the index of its arrangement, and counts bits and reads on the four texts. The prediction is that on English words the offsets fall by about a third, because most mixed blocks change value only once or twice. On random letters they should grow, since a random block changes value about thirty times and its arrangement index is the shortest description it has. The question is whether a coding of a block’s own runs, inside the block code, recovers the grouping that cutting the transform into blocks of 63 threw away.