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

Side information — where it appears

Data a decoder needs besides the coded stream itself to reconstruct the original. A transform that sends several inputs to one output must be followed by enough side information to say which input it was, and that cost belongs in any accounting of what the transform saved.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

thousands of bits · the floor is 31.9kthe text as it is34.0k streamto undo itnothinga shuffle agreed in advance34.4k streamto undo itnothingthe characters sorted0.3k streamto undo it31.8kthe Burrows–Wheeler transform14.8k streamto undo itnothingmodel: order 0 after move-to-front · Words from a fixed vocabularydashed: coding the text as it stands

What a reordering costs to undo

Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.

floors · Bits 01234characters of context the sort reads, kbits a symbol after move-to-front012481632the full transform, 1.802ties kept in text orderties sorted by symbol: the stream alonethe text's own floormodel: order 0 after move-to-front · Words from a fixed vocabularyexactly the transform from k = 24

The order inside a tie

Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.

floors · Bits words drawn independentlymean +0.0038 ± 0.011ahead on 10 of 16next word set by the last lettermean +0.0064 ± 0.011ahead on 12 of 16no difference−0.0176+0.0000+0.0251bits a symbol the short context savesthe stream reported beforek = 4 · 16 streams a source · bands: ±1 standard deviationone draw, not a result

A result the size of its own noise

Sorting rotations by their first four characters beat the full Burrows–Wheeler transform by 0.022 bits a symbol. On sixteen streams of the same source the mean difference is 0.004 with a standard deviation of 0.011, and the short context is ahead on ten of them. The 1.2% was one draw. What survives is sharper than the result it replaces: from four characters upwards, every run break either rule makes is at a word boundary, and nothing above four characters decides anything at all.

floors · Bits

Named alongside it

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

Bits per symbolBurrows-wheeler transformEntropyInvertibilityMeasurement designMove to frontPermutationContext modelCounting argumentHonest limitModel orderFalsification

All concepts