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

The thread: Compression is prediction

A coder spends −log₂ p bits on a symbol it thought had probability p, so the only way to spend fewer is to have expected the symbol more. Every compressor here is therefore a predictor wearing different clothes — a frequency table, a context, a window of recent text — and its bit count is the scorecard of how well it guessed.
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 data that is not a number

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.

 H₀ = 3.8916642561k4k16kwindow, in symbolsbits per symbol0.04.38.6LZSSmean symbols covered per match4.65.15.76.98.79.6model: a window of recent text, no probabilities2.13 bits/symbol at a window of 16,384 What the libraries do

The dictionary that builds itself

LZSS contains no probability, no frequency table and no entropy calculation. Its entire model is a window of recent text and its only move is to say "the next nine symbols are the ones that appeared 1,200 positions ago". On a stream whose zeroth-order floor is 3.89 bits per symbol it spends 2.11, and widening its window past 4,096 makes it worse rather than better.

 1,00010,00010³10⁴bits · runs12481632characters in the collection · copies aboven·H₃, bitsr, runs in thetransformEnglish-like · base 512 · divergence 0n·H₃ x15.8 · r x1.00 The data that is not a number

The entropy that cannot see a copy

Two copies of a text have exactly the same symbol statistics as one, so every entropy on this site doubles when the second copy arrives and the second copy carries no information at all. The number of runs in the Burrows-Wheeler transform is 224 at two copies and 224 at thirty-two.

 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 What is taught wrongly

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.

 is·holds·no·the·the·of·of·rather·count·class·that·is·algorithm·o1111111211111151141131111111211122213111111212phrase lengths below each block · a shaded block is a literalEnglish-like · 64 charactersz = 46 · 17 literals The data that is not a number

The phrases a text copies from itself

Four thousand characters of English-like text hold 604 phrases in the greedy parse and 1,219 runs in the transform. Thirty-two copies of one text hold 156 phrases and 233 runs. Two measures of repetition, neither of them an entropy, and they do not agree about which text is the more repetitive.

 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% The index that replaces the text

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.

 a fixed-length code97,718 bits5.00 ranks · in orderthe best ordered tree77,890 bits3.98 ranks · in orderthe best tree of any shape76,789 bits3.92 ranks · unorderedσ 21 · the ordered tree is 1.43% above the unordered optimum16,384 characters of englishorder costs 1.43% Structures

The tree the operation insists on

The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small.

All threads