The part every saving left alone

An earlier essay made a bidirectional index smaller one change at a time, on 16,384 characters of protein text. Both halves locating, it was 250,584 bits. With the reverse half reduced to counting, which a bidirectional search needs from it and nothing more, 226,504. With the forward half’s sample marks held as an Elias–Fano array, 210,934. A fourth change spent the saving on a denser sampling and landed at 96% of where it had started, locating several times faster. Bits and steps on one frame then drew the two currencies together, because a saving in bits that costs steps is a trade and not a win.

That essay ended by naming what it had not touched. The largest part of the structure is the wavelet trees, one for each half, whose levels are two thirds of it. Every change so far had been made to the parts around them. The section named a representation that reaches a text’s higher-order entropy rather than its zeroth: code each level’s bit vector in blocks, storing for each block how many ones it holds and which of the possible arrangements it is. It said this composes with every other change, since it alters a different part.

The index and what changes in it #

The index is the smallest of those structures, unchanged in every other respect: a balanced wavelet tree for each half, which keeps the leaves in alphabetical order so that one descent can report every symbol an interval holds; the reverse half counting only; the forward half sampling one position in 32, with Elias–Fano marks. The only change is to the vectors inside the trees. A plain level holds its bits as they are, with a rank directory beside them: a count at every 512 bits and a count within each block of 64. A coded level replaces each block of 63 bits by its class, the number of ones, in six bits, and its offset, the arrangement’s index among all arrangements of that class, in as many bits as there are arrangements to tell apart. A superblock entry every 32 blocks holds the running count and where the offsets resume. It is the same class-and-offset vector that a block, a class and an offset put under the phrase index’s grids.

Four texts are measured, each 16,384 characters: DNA and protein letters drawn uniformly at random, English words, and a repetitive collection of near-copies of one passage. Every size is counted from the structure’s own fields. Searches are exact backward searches of eight characters taken from the text, 64 of them, run through both halves. A search on coded levels must count exactly the occurrences a search on plain levels counts, and does on every text.

One change, larger than the two before it #

Coding the levels takes the protein index from 210,934 bits to 167,707: 43,227 bits, more than the 39,650 the first two changes took together. The parts the earlier changes worked on were small, about a fifth of the structure between them. The levels are most of what is left, and a change to most of a structure moves it more than a larger change to a small part.

The composition the earlier essay predicted holds exactly. The coded levels change no part the earlier changes touched, so the saving adds: the counting-only reverse half, the Elias–Fano marks and the coded levels are three savings on three parts, and the whole is their sum. That is the opposite of what three savings on one structure found for two operation savings that turned out to be one saving counted twice.

The earlier fourth change spent its saving on sampling, and so can this one. At one sampled position in eight instead of one in 32, the coded index is 198,258 bits, 79.1% of the start. At one in four it is 236,273, 94.3%, about where the plain index landed when it spent its saving, with a sampling twice as dense again. The locating cost falls with the sampling: a walk to a sampled position averages about half the sampling interval, the dial every occurrence at the same price set against a sampling at the run boundaries.

An ordered tree, coded, against an unordered one #

On English words the coded levels hold 1.90 bits a character, below the text’s zeroth-order entropy of 3.89 and far below the 4.72 that a plain Huffman-shaped tree holds. A Huffman shape compresses the levels to about the zeroth-order entropy by giving frequent letters short codes, but its leaves are in no order. The interval enumeration this index depends on needs them ordered, and one set, three orders found what goes wrong when they are not. The coded balanced tree keeps the order and goes much further.

It goes below the zeroth-order entropy because the levels are not the text. They are the Burrows–Wheeler transform of the text, and the transform that emits nothing found that the transform changes no count of letters, only their order, grouping together letters followed by the same context. On English words a stretch of the transform is often the same letter many times, so a level’s blocks are often all zeros or all ones, and a block of one class has one arrangement and costs its class alone. That is the higher-order entropy the earlier essay named: the coding sees the grouping the transform made, and a code for letters by frequency cannot. On the repetitive collection the effect is larger still, 1.07 bits a character.

Coding and shape compose, so a coded Huffman-shaped tree is smaller still: 1.79 bits a character on English words, 4.63 on protein. The interesting number is the difference. Plain, keeping the leaves in order costs 1.25 bits a character on English words, the gap between the balanced tree’s 5.97 and the Huffman tree’s 4.72. Coded, it costs 0.11, the gap between 1.90 and 1.79. Most of what the balanced shape wasted was in blocks the coding compresses anyway, so once the levels are coded the order the enumeration needs is nearly free. The earlier essays chose the balanced shape for its order and accepted its size. The coded levels take most of that price back.

On random letters there is no grouping to see, and the coded tree lands above the entropy: 2.23 bits a character on DNA against 2.00, and 4.69 on protein against 4.32. It still beats the plain Huffman tree on both, and the reason is in the shape of the balanced tree.

Where the coding saves on random letters #

A balanced tree over twenty letters and the transform’s end marker has five levels, and its top level splits the twenty-one symbols sixteen against five. A quarter of that level’s bits are ones, and the coded level holds 14,350 bits where the plain one holds 19,475. A level whose bits are a biased coin carries less than a bit a bit, 0.81 at a quarter ones, and a block code stores about that. The second level splits unevenly too. The balanced shape wastes exactly this: it gives every symbol five bits where the alphabet needs 4.39 on average, and the uneven splits are where the waste sits. A Huffman shape removes it by choosing different code lengths. Block coding removes it without changing the shape.

The bottom levels hold half ones and still shrink, for two reasons that are not compression of the text. Two of the bottom level’s nodes are nearly constant: one pairs the end marker, which occurs once, with the first letter, and one holds the last letter with no partner to tell it from. Each is about a thousand bits plain and about a hundred and fifty coded. And the coded vector’s directory is lighter. A plain level’s rank directory adds about a fifth to its bits. The coded level’s classes and superblocks add about a tenth. On a node whose bits are a fair coin the offsets cost slightly more than the bits themselves, and the lighter directory more than pays for that.

Across both trees the protein index’s coded levels save 43,227 bits, and the split says how much of that is compression. The offsets and the bits they replace fall from 163,850 to 133,993, a saving of 29,857, and all of it comes from levels and nodes that are not a fair coin: the biased top levels and the nearly constant nodes. The directories fall from 31,344 to 19,228, a saving of 12,116, which is 28% of the whole and has nothing to do with the text. A plain vector with a sparser directory, block counts every 256 bits instead of every 64, would have taken part of it without coding a single block, at the price of longer scans. On English words the directory’s share of the saving is under a tenth, and nearly all of it is the transform’s grouping seen through the offsets.

That distinction matters for any further change built on this one. A saving that comes from the directory is a choice of layout and can be had by other layouts. A saving that comes from the offsets is a property of the text and can be had only by a coding that sees it. On random letters a quarter of this saving is the first kind. On English words almost none of it is.

The level where compression stops paying found the block code gaining almost nothing on a phrase index’s grid, whose levels are close to random at every depth. Here the random-letter texts gain a fifth from the shape and the directory, and the texts with structure gain two thirds or more from the transform. The difference is what the levels hold. A grid’s levels are a permutation. These are a transform built to group.

What a coded rank reads #

An extension of an exact search reads 1.37 to 1.42 times as many vector entries on coded levels as on plain ones, on every text. A plain rank reads two directory counts and the bits of its block up to the position. A coded rank reads its superblock’s count, then the class of every block before its own in the superblock, sixteen on average, then its own block. The reads follow the layout, not the data, so the ratio is the same on random letters as on English words. The number of ranks an extension makes is unchanged, since the tree’s shape is unchanged: ten on the twenty-letter texts, six on DNA.

This is the other currency, and it belongs beside the bits. On protein text the coded levels save 20% of the index for 37% more reads an extension. On English words they save 64% for 39% more. Whether either is worth it depends on how the index is used: one searched rarely and stored for a long time wants the bits, one searched constantly may not.

The coded levels’ own dial #

With a superblock of four blocks instead of 32, a coded rank reads as much as a plain one, 308 entries an extension on English words, and the levels hold 2.30 bits a character instead of 1.89, still under two fifths of the plain 5.97. The superblock is the coded vector’s dial between the two currencies. Every block before a rank’s own in its superblock is read, so a small superblock reads little, and every superblock is an entry of running count and offset pointer, so a small superblock stores many. At four blocks the reads match the plain levels exactly, and the coded levels keep most of their saving.

On protein text the same setting gives 5.12 bits a character against the plain 5.97, a 14% saving for no extra reads, where a superblock of 32 gave 21% for 37% more reads. Bits and steps on one frame found the sampling dial moving size and locate cost together, with the answer a point on the pair. The superblock is a second dial of the same kind, and it moves a different part of the structure, so the two can be set independently.

What is left once the levels are coded #

On English words, once the levels are coded, the counts, marks and samples the earlier changes shrank are 14,096 of 76,054 bits, 18.5% of the index, where on the plain index they were 7.3%. The coded levels’ own directory, classes and superblocks, is another 19,020, a quarter. The earlier changes worked on a part that looked small beside the levels. With the levels coded, that part is no longer small, and the next saving is as likely to be found in the directory or the samples as in the levels.

An index that cannot locate removed the reverse half’s sampled positions and marks, and found a third of that half gone. On a coded index the same removal would be a larger share, since the rest has shrunk around it. Every saving in this sequence has been measured against whatever the structure was before it, and the shares move as the structure does.

The limits of the measurement #

One block length. Every coded level uses blocks of 63 bits, the length an earlier strand measured as best for these vectors. Shorter blocks spend more on classes and less on offsets. On English words, where most blocks are uniform, a longer block would store more of each run in one class, and was not tried.

Vector reads, not time. A coded rank’s class reads are sequential bytes and its offset decode is table work, and a real implementation would weigh them differently from a plain rank’s popcount. The reads are the unit the grid strand used, kept so the two can be compared.

Random letters are uniform. The DNA and protein texts draw every letter with equal chance. Real protein sequences have skewed letter frequencies and short-range structure, and would sit between the random texts and English words.

Exact searches only. The reads are counted on exact backward searches. A search with errors enumerates every symbol an interval holds, one descent through the tree for each interval, and would pay the coded levels’ class reads on every rank of every descent: the ratio should be the same, and the totals several times larger, as the budget grows.

One size. At 16,384 characters, every superblock holds 2,016 bits, and the directory’s share is set by that. At a million characters the shares of the parts would move and the plain directory’s fifth would stay a fifth.

Still open: the directory that is now a quarter of the levels #

On English words the coded levels hold 42,498 bits of offsets and 19,020 of classes and superblocks. The classes are six bits for every block of 63, and on a text whose levels are mostly uniform blocks, most classes are 0 or 63 and say the same thing over and over. A class sequence can itself be coded, by runs or by a small entropy code, as the runs a permutation does not leave tried for a grid’s bits.

The measurement that follows codes the class sequence of each level by its runs, keeping a sample every superblock so a rank can still find its place, and counts bits and reads on the four texts. The prediction is that on English words and the repetitive collection the classes fall by more than half, taking the coded levels from 1.90 bits a character to about 1.5. On random letters it should save nothing, since their classes are spread. A rank would read the class runs rather than the classes, fewer on uniform stretches and more elsewhere. The question is whether the directory can be made to follow the data as the offsets do, or whether some fixed part of any rank structure is the price of answering in a bounded number of reads.