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

Model order — where it appears

How many preceding symbols a statistical model conditions on when it predicts the next one. A higher order can capture more structure in a source, but only structure the source actually has, and each extra symbol of context multiplies the number of contexts the model must learn.

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

H0H1H2H3H4model order — symbols of contextbits per symbol0.02.14.2Uniform over 8 symbolsOrder-1 Markov chainWords from a fixed vocabulary32,768 symbols · at H4 the deepest source has 709 contexts, 0 seen oncemodels: orders 0, 1, 2, 3, 42.06 bits found by one symbol of context

The model is the compressor

One stream of 32,768 symbols has an entropy of 3.886 bits per symbol, and 2.243, and 1.186, and 0.991, and 0.909. All five numbers are correct, all five are floors, and nothing about the data changed between them. The only thing that changed is how many preceding symbols the model was allowed to look at — which makes the entropy of a file a property of a decision rather than a property of a file.

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

Context modelEntropyAdaptive codingBits per symbolBurrows-wheeler transformConditional entropyCounting argumentEstimator biasHeader costHonest limitInvertibilityMeasurement design

All concepts