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

Bits per symbol — where it appears

A coder's output length divided by the number of symbols it coded, which is the unit a compression claim is naturally stated in. Stating a compressor's output this way makes two texts of different lengths comparable, and makes the gap to a floor a number rather than a feeling.

Named by 4 essays across 2 fields — 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 bits per symbolhuffman3.9371.01× the floorarithmetic (adaptive)3.8981.00× the floorLZSS (window 4096)2.1130.54× the floorLZ783.1470.81× the floorH₀ = 3.89216,384 symbols · alphabet 21 · floor shown is H0 = 3.892 bits/symbolmodel: order 0 · Words from a fixed vocabularybest here: 2.113 bits/symbol

The bits a coder emits

A stream of 16,384 symbols with a zeroth-order entropy of 3.891 bits per symbol was coded by a Huffman coder into 3.937 and by an arithmetic coder into 3.898, and neither went under 3.891 because neither can. That floor is a third kind of limit, the first that is a property of a model rather than of a question, and the same stream has a different one under every model of it.

floors · Bits 0.1250.30.50.70.80.90.99probability of the dominant symbolbits per symbol0.01.63.2one bit per symbolHuffmanArithmeticEntropy H₀model: order 0 · 16,384 symbols per point8.7× at p = 0.99

The optimal code that is beaten

Huffman's code is optimal, the proof is correct, and on a stream where one symbol arrives 99 times in a hundred it spends 1.030 bits per symbol against an arithmetic coder's 0.119. Both facts hold. The word "optimal" in the theorem has a precondition attached that almost nobody quotes with it, and everything interesting about coding lives on the other side of that precondition.

wrong · 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.

EntropyArithmetic codingBurrows-wheeler transformCounting argumentHuffman codingInformation-theoretic boundInvertibilityMeasurement designMove to frontPermutationPrefix codeSide information

All concepts