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

Compression — where it appears

Writing a structure in fewer bits than its plain form, at some cost in what a query has to do to read it. What it can be worth is bounded by how far the plain form sits above the information-theoretic floor for the object — for a grid over a permutation that is about sixteen per cent.

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

a text that repeats itselfH0 4.01 · H3 0.236.291.48an order-1 sourceH0 3.00 · H3 0.895.151.67English-likeH0 3.89 · H3 0.976.162.25four symbols, uniformH0 2.00 · H3 1.994.102.59eight symbols, uniformH0 3.00 · H3 2.835.143.65bits per character of textupper bar: plain bit vectors · lower bar: compressed16,384 characters each · sample rate 64sigma 21, 8, 21, 4, 8

The index that is smaller than the text

The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.

indexes · Index 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 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.

MeasurementWavelet treeGridIndex sizePermutationRank directoryTrade offBit vectorControlEntropyBreak-evenSpace overhead

All concepts