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 2 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

Named alongside it

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

Bits per symbolBurrows-wheeler transformCounting argumentEntropyInvertibilityMeasurement designMove to frontPermutationContext modelHonest limitInformation-theoretic boundLower bound

All concepts