Compression Limits

Introduction to compression limits

Lossless compression exploits dependencies and repetition in data, while lossy compression also reduces representation accuracy according to a chosen quality model. Self-information and entropy describe information content and the statistical unpredictability of a source. Redundancy can therefore be treated as description cost caused by repeated or predictable data. A lossless coder must preserve unambiguous reconstruction for every symbol, while code length may depend on its probability. The ratio measured on one file is therefore not the theoretical bound itself because it also includes headers, model data, and the chosen representation.

The next question concerns the limit of further size reduction. The answer follows from information theory and Claude Shannon's work. Shannon's source coding theorem gives the asymptotic average code length for a source with a specified probability distribution. The limit becomes visible when short-block overhead, model construction, and the complexity of an individual string are compared.

Shannon's source coding theorem

The source coding theorem, also called Shannon's first theorem, relates source entropy to the average length of a lossless code. In its standard form it concerns a discrete memoryless source and long blocks of symbols. One part gives a lower bound, while the other describes how codes can approach that bound. The average is taken over messages generated according to the source distribution. One file can differ from that average, especially when it is short or the source model is mismatched.

Lower bound on average code length

The first part of the theorem establishes a lower bound on average code length.

Under the source model, a lossless code cannot reduce the average number of bits per symbol below the source entropy. Entropy measures the average information determined by the symbol distribution. A lower value would require omitting distinctions between possible messages or adding an assumption about the source.

Approaching the asymptotic bound

The second part states that the lower bound can be approached asymptotically with sufficiently long blocks.

The phrase "arbitrarily close" refers to an asymptotic result. For short messages, headers, model data, and coding choices can increase the average length. With long blocks, a suitable code can approach entropy with an arbitrarily small gap. Arithmetic coding illustrates this principle by distributing the description cost across the message.

Why entropy sets the bound

A compressor must assign each input message an unambiguous description from which the decompressor can reconstruct the original. If two different messages received the same description, the decompressor could not distinguish them. This requirement limits the number of short descriptions available for the full set of messages.

Consider a source that produces messages of $L$ symbols. The number of possible messages grows exponentially, while their probabilities may differ. For a source satisfying the theorem's assumptions, most of the probability is concentrated, for large $L$, in a set of sequences called the typical set.

The number of sequences in this typical set is approximately $2^{L \cdot H(X)}$. All other "atypical" sequences have small total probability. To create a lossless compression scheme, we need to have at least enough unique compressed codewords to represent every sequence in this typical set. The minimum number of bits required to uniquely identify $2^{L \cdot H(X)}$ different items is, by definition, $\log_2(2^{L \cdot H(X)})$, which simplifies to $L \cdot H(X)$ bits. This is an asymptotic argument based on long blocks. A code must still handle sequences outside the typical set, usually with separate rules or a longer description.

If the total number of bits required for an $L$-symbol message is $L \cdot H(X)$, then the average number of bits required per symbol is $\frac{L \cdot H(X)}{L} = H(X)$. This relation follows from Shannon's theorem. Entropy determines how many "likely" messages must be distinguished during coding, which sets the minimum average number of bits per symbol.

Example source with four symbols

Consider a source that generates symbols A, B, C, and D.

For a uniform distribution, $H(X) = 2$. The code (A=00, B=01, C=10, D=11) has average length $L_{\text{avg}} = 2$ bits/symbol. Since $L_{\text{avg}} = H(X)$, the code reaches the bound for this source model.

Assume the distribution $P(A)=0.48, P(B)=0.26, P(C)=0.18, P(D)=0.08$. It gives $H(X) \approx 1.75$ bits/symbol; for this example, we use the rounded value $H(X) = 1.75$. The 2-bit code has average length $L_{\text{avg}} = 2$, so it remains above entropy. The two parts of the theorem describe separate bounds in this example:

1. A lossless code for this source cannot have an average length of 1.7 bits/symbol. The lower bound follows from entropy, about 1.75.
2. A Huffman code with lengths 1, 2, 3, and 3 for A, B, C, and D gives an average length of 1.78 bits/symbol, close to 1.75. Arithmetic coding can reduce the gap for a long block.

Practical coder constraints

Shannon's theorem describes an asymptotic result for a specified source model. An implementation must also estimate the distribution, encode model data, and handle finite blocks. A practical coder therefore approaches a bound that depends on the data and the format overhead.

Building a source model

Calculating entropy requires a probability distribution for the symbols. A model can be estimated from the data, selected in advance, or updated while coding.

• Two-pass compression: The first pass builds a statistical model, for example by counting character frequencies. The second pass uses that model for coding. The model must be stored or transmitted with the data, so its overhead can be a large part of a small file.
• Pre-defined models: A generic model can be selected for a data type, for example average letter frequencies in English text. The stream carries no separate model, while the result depends on how well the file matches the assumed distribution.
• Adaptive models: The compressor starts with an initial model and updates its statistics while processing the data. The decompressor performs the same updates to remain synchronized. LZMA used in 7z applies adaptive probability modeling. ZIP can use dynamic Huffman codes in Deflate blocks, while the details depend on the method and implementation.

Block length and integer code lengths

Shannon's theorem is asymptotic. For short files, a header, Huffman tree, or dictionary can offset the gain from coding the data. Prefix codes assign integer lengths to symbols, so an entropy of 1.75 bits/symbol requires an average-length approximation. Arithmetic coding can reduce this gap for a long message because the average cost is spread across many symbols.

The limit for one string and incompressibility

Shannon's theory describes average source compressibility. Algorithmic information theory and Kolmogorov complexity concern the description of a single, specific string.

For a fixed universal programming language, Kolmogorov complexity $K(s)$ is the length of the shortest program that generates string $s$. Its value changes with that choice by at most a constant independent of the string. It is a theoretical reference for a lossless description, including the program and decoder conventions. Kolmogorov complexity is not computable for every string, so it serves mainly as a limiting concept. A practical compressor can search only within a chosen family of models.

A string is called algorithmically random when its complexity is close to its length, up to a language-dependent constant. There is then no shorter description in the chosen model. For data of this kind, a lossless coder often adds a header or other metadata, so the result can be larger than the input. This is why repacking a lossy-compressed file such as JPEG, or random data, usually does not reduce its size.

Summary of compression limits

Shannon's theorem gives a statistical bound on the average code length for long blocks and a specified probability model. Huffman and arithmetic coding provide practical ways to approach that bound under different constraints. Kolmogorov complexity describes the shortest program for an individual string in a fixed description model. Together, these views show why results depend on source statistics, block length, and whether the measure concerns an average or one particular message. When evaluating a tool, data properties must be separated from format overhead. A file can have entropy close to the bound and still become larger after metadata is added. For prefix codes, Kraft's inequality connects codeword lengths with unique decodability. A Huffman code for individual symbols has integer codeword lengths, while block coding reduces the relative rounding overhead. For a source with memory, the entropy of one symbol may hide dependencies between symbols, so conditional or block entropy can be the relevant measure. The model used for a benchmark should match the data that the compressor will receive in its actual task. On short files, a header and code tables can outweigh the saving from the model. This limit concerns the particular format implementation as well as the source model.

A comparison requires the same alphabet, source model, and output format. The cost of representing the model and alphabet remains part of the practical result and should be included in the measurement.