Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Rank directory — where it appears

The stored counts that turn a bit vector into something answering rank in bounded time. Its size is a function of the vector's length rather than of its contents, so it does not shrink when the payload is compressed — and a total that omits it reports a structure several times smaller than the one being queried.

Named by 6 essays across 5 fields — each of them below, with the objects they name alongside it.

0000200121200the parenthesis sequencethe minimum excess of each block of 213 blocks · lookup table 72 bits, sharedblock 2 · 24 parentheses13 blocks

The table that fits inside a block

A block of six parentheses has sixty-four possible shapes and twenty-eight questions can be asked about each, so all 1,792 answers fit in a table of 9,408 bits — computed once, shared by every structure of that block length, and never counted in any of their sizes.

machine · Range plain51,600block-coded47,6687.6%run-coded60,805-17.8%plain, uniform51,600block-coded, uniform50,2422.6%run-coded, uniform67,121-30.1%bits · the lower three are a permutation with no structure3,612 points7.6% against 2.6%

A block, a class and an offset

Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.

indexes · Grid parentheses131,07216.7%select support115,71214.8%superblock minima16,3982.1%superblock table80,97010.3%block minima147,46518.8%block tables291,25537.2%the partsbitstotal 782,872 · the segment tree 2,228,224shared lookup table 82,944, not counted65,536 values · openings in index order, found by select2.85x smaller

Two bits a value, and what undoes them

The parentheses of a range minimum over 65,536 values are 131,072 bits. Everything that makes them answerable is 651,800 more — five times the payload — and one encoding choice nobody quotes accounts for a sixth of it on its own.

space · Range 00.2500.5000.750101234567891011level of the wavelet treebits a bitthe parse's grida uniform permutation3,612 points · 12 levels0.997 bits a bit

A bit for every bit

A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.

space · Grid 024601234567891011level of the wavelet treemean runthe parse's grida uniform permutationbreak-even3,612 points · 12 levels1.23x chance

The runs a permutation does not leave

A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.

structures · Grid 02e+34e+36e+301234567891011level of the wavelet treebitsplainblock-codedrun-coded3,612 points · 12 levels24 copies of 2048 characters

The level where compression stops paying

Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.

wrong · Grid

Named alongside it

The objects these essays reach for when they reach for this one.

MeasurementTrade offCompressionGridIndex sizePermutationSpace overheadWavelet treeControlBit vectorBreak-evenCartesian tree

All concepts