1 Basic definitions

Compression length is the number of bits (or more generally, code symbols) needed to represent a particular data object when encoded using a specified compression method. In theoretical contexts it is treated as a measurable quantity that can be compared across different coding schemes, and it often corresponds to “code length” or “description length,” depending on the formalism.

1.1 Code length and representation length

Given an encoding rule that maps a data object \(x\) to a bit string, the code length \(L(x)\) is the number of bits in that representation. Representation length emphasizes what is actually transmitted or stored after encoding, including whatever structure the scheme uses to specify \(x\) in its compressed form.

1.2 Compression length as a function of the compressor

Compression length typically depends on the compressor. If a compressor \(C\) produces a codeword \(C(x)\), then the compression length is \(L_C(x)=C(x)\), where \(\cdot\) denotes the bit-length. Two compressors can yield different lengths for the same object because they adopt different dictionaries, models, or parsing conventions.

1.3 Optimal compression length and constraints

In many settings one seeks an optimal length: the smallest achievable length among encodings satisfying certain constraints. Constraints may include (i) a restricted class of compressors (e.g., computable schemes), (ii) the requirement that the decoder uniquely recovers \(x\), or (iii) limitations on model complexity or alphabet size. The resulting “optimal compression length” is the best possible within that framework, not necessarily absolute minimal length across all conceivable representations.

2 Information-theoretic foundations

Information-theoretic treatments connect compression length to probabilistic models and to fundamental limits on how short codes can be. The key idea is that the average length of a code is tied to how predictable the encoded outcomes are under an assumed distribution.

2.1 Relation to entropy and expected code length

Entropy provides a benchmark for expected code length when codes are designed for a probability distribution.

2.1.1 Entropy as a lower bound (intuition)

For a source producing symbols according to a distribution, entropy quantifies the inherent uncertainty. If an encoding assigns shorter codes to more probable outcomes, then on average the achievable length cannot systematically fall below what entropy dictates, because otherwise the encoding would compress “too well” relative to the uncertainty present in the distribution.

2.1.2 Expected vs. worst-case length

Expected code length averages over outcomes drawn from a distribution. Worst-case length considers the maximum possible length over all objects in the domain. A scheme may have near-optimal expected length yet still assign long codes to rare or atypical objects, so these notions should not be conflated.

2.2 Prefix codes and Kraft’s inequality

Prefix coding is a standard mechanism for assigning bit strings to outcomes such that decoding is unambiguous by reading bits sequentially.

2.2.1 Prefix-free encodings

An encoding is prefix-free if no valid codeword is the prefix of another codeword. This property enables instantaneous decoding: as soon as a codeword ends, the decoder knows which symbol was sent.

2.2.2 Kraft inequality interpretation

Kraft’s inequality characterizes which length assignments are feasible for prefix-free codes. In one form, if \(l_1,l_2,\dots,l_n\) are intended codeword lengths over a binary alphabet, then feasibility requires that \(\sum_{i=1}^n 2^{-l_i}\le 1\). The inequality can be read as a “budget” constraint ensuring that the code tree has enough room.

2.3 Average length and redundancy

Average length measures mean code length under a distribution. Redundancy is the excess over an information-theoretic benchmark (commonly the entropy). Redundancy captures inefficiency due to modeling error, finite-length effects, and the constraints of practical coding schemes.

3 Algorithmic and complexity-theoretic views

Algorithmic information theory extends the idea of description length beyond probabilistic sources by focusing on the minimal description length of individual objects.

3.1 Kolmogorov complexity and description length

Kolmogorov complexity assigns to each object \(x\) the length of the shortest effective program that generates \(x\).

3.1.1 Programs as descriptions

In this view, a “description” is a program, and “length” is the size of that program in bits under a chosen encoding of programs. The shortest program plays the role of an ideal compressor for that specific object, in an existence sense.

3.1.2 Invariance and constant offsets (high level)

Kolmogorov complexity depends on the choice of universal machine (or programming language formalism). Changing that underlying reference alters all complexities by at most an additive constant. This invariance means qualitative comparisons remain meaningful even though absolute values shift slightly.

3.2 Universal coding intuition

Universal coding attempts to mimic unknown distributions by using coding schemes that adapt to the data. The intuition is that the code length should approach the ideal length for the best-fitting model, while paying a penalty for not knowing the model in advance.

3.3 Lower bounds via incompressibility

Incompressibility arguments show that many objects cannot be substantially shorter than their own “natural” description length. Since there are only so many short programs, most strings require long programs to describe them. Such results provide theoretical limits on how much compression is possible for arbitrary data.

4 Compression models and notation

Formal studies specify what counts as a compressor, what the model is, and how lengths are computed. Notation typically distinguishes between deterministic encoding rules and probabilistic coding schemes.

4.1 Deterministic vs. probabilistic compressors

A deterministic compressor maps each object to a fixed codeword. A probabilistic compressor may involve randomness either in selecting a code or in describing a stochastic model. In probabilistic settings, one often studies expected code length (expectation over both the randomness of the compressor and the distribution of inputs).

4.2 Model-based coding (two-part codes)

Two-part codes describe how to encode a model and then encode the residual data given that model. This framework is common in learning theory and model selection.

4.2.1 Coding the model and the residual

The total length is the sum of (i) the bits needed to specify the model parameters or structure and (ii) the bits needed to encode the data using that model. The trade-off arises because richer models typically reduce the residual uncertainty but increase the cost of describing the model.

4.3 Block coding and symbolwise coding

Block coding compresses sequences as whole objects, producing lengths for entire blocks. Symbolwise coding compresses elements one at a time, often using conditional distributions updated sequentially. While both frameworks are related, they differ in what is treated as a single “object” and how dependencies are exploited.

5 Measuring compression length in practice (formal framing)

Practical measurement can be formal as well as empirical: one defines what is being counted, how headers or overhead are treated, and how side information alters the length.

5.1 Length in bits vs. in symbols

If the underlying code alphabet is binary, lengths are measured in bits. With other alphabets (e.g., base-\(q\) symbols), lengths are measured in code symbols and converted to bits using \(\log_2 q\) when making information comparisons. Care is needed to avoid mixing units.

5.2 Finite-length effects and overhead

Real compressors use finite alphabets, finite block sizes, and protocol elements such as headers, dictionaries, or delimiters. These add overhead that can dominate compression for small inputs. In formal treatments, overhead is often separated from the “core” code length of the payload.

5.3 Measuring trade-offs with side information

Side information captures additional knowledge available to both encoder and decoder, such as context, a shared model, or previously transmitted data. Including side information changes the effective description problem.

5.3.1 Conditional compression length

Conditional compression length quantifies how many bits are needed to encode \(x\) given that the decoder already has access to another object \(y\). It aligns with conditional entropy in probabilistic settings and with conditional description length in algorithmic settings.

6 Mathematical properties

Many useful properties of compression length follow from basic constraints on codes and concatenation. These properties help verify whether a proposed measure behaves like a proper “length function.”

6.1 Monotonicity under refinement of encodings

If one refines an encoding scheme—e.g., allows additional codewords, provides more modeling flexibility, or grants extra side information—then the minimal achievable length should not increase. At the level of a particular compressor, length may change in either direction, but optimal or constrained-optimal quantities typically improve monotonically under relaxation of constraints.

6.2 Subadditivity and concatenation behavior

Subadditivity describes how the length of encoding a concatenation relates to the lengths of the parts. Intuitively, one can often encode two objects separately and concatenate their encodings, yielding an upper bound on the combined length. Under appropriate definitions, this provides a general inequality showing that combined compression is not worse than treating components independently.

6.3 Bounds under specific coding classes

Bounds depend on what class of codes is permitted: for example, prefix-free codes, uniquely decodable codes, computable encoders, or codes with restricted memory. Each class imposes structural limits that translate into corresponding lower or upper bounds on achievable compression length.

“Compression length” connects to several closely related notions used in different communities, especially in statistics, learning theory, and rate–distortion frameworks.

7.1 Expected description length

Expected description length averages the code length over a distribution of inputs or over randomness in the encoding. It is often the primary objective in probabilistic model selection, where expected performance better reflects typical cases.

7.2 Minimum description length (MDL)

Minimum description length formalizes model selection by choosing the model that yields the shortest total code length for “model plus data.” MDL interprets learning as compressing data using the most concise explanation within a model class. It generalizes the two-part coding view and is widely used for balancing fit and complexity.

7.3 Rate–distortion style compression length (overview)

Rate–distortion theory studies the relationship between the number of bits (rate) and how accurately a compressed representation reproduces the original (distortion). Rather than requiring exact reconstruction, the framework allows controlled error, leading to compression length notions expressed through achievable rate–distortion trade-offs.

7.4 Distinguishing “length” vs. “cost”

In practice and in theory, one may count different quantities: bit-length, computational cost, or even energy usage. While “length” in information-theoretic contexts refers to the number of transmitted symbols, “cost” can incorporate resources such as runtime or memory. Mixing these can lead to incorrect comparisons if an objective function uses something other than bit-length.

8 Worked examples and canonical constructions

Concrete calculations clarify what compression length means and how common constructions yield computable lengths.

8.1 Example: run-length style length computation

Consider a simple run-length scheme for a binary string where one encodes runs of identical bits. If a string has runs with lengths \(r_1,r_2,\dots,r_k\), and the scheme uses fixed-size codes for the run values and a specified method for coding each \(r_i\), then the total compression length is the sum of the code lengths for all run descriptors. Changes in string pattern alter the number and sizes of runs, directly affecting total length.

8.2 Example: mapping probabilities to ideal code lengths

For an alphabet with probabilities \(p_i\), an “ideal” code length assignment uses \(l_i \approx -\log_2 p_i\). Under prefix-free coding, constructions such as Huffman coding produce integer lengths close to these targets. The expected length becomes \(\sum_i p_i l_i\), which is near entropy \(-\sum_i p_i \log_2 p_i\) when the coding scheme aligns well with the distribution.

8.3 Example: two-part code length breakdown

Suppose one compresses data \(x\) using a model class parameterized by \(\theta\). A two-part code length can be written as \(L(\theta)+L(x\mid \theta)\), where \(L(\theta)\) encodes the chosen model and \(L(x\mid \theta)\) encodes the data given that model. Comparing models amounts to trading a shorter residual code against a longer model description, with the optimal choice depending on which term dominates for the dataset at hand.

9 Applications in formal sciences

Compression length serves as a bridge between data description, probabilistic reasoning, and computational constraints. Its applications are primarily formal and analytical.

9.1 Theoretical data analysis and model selection

In model selection, compression length provides a criterion for preferring models that describe observed data concisely. This reframes statistical fit as a coding problem: the best model is one that yields a short joint description of model and data.

9.2 Coding-based views of learning and inference

Learning can be interpreted as searching for an encoding strategy that performs well on new data. If training data helps select an encoding or model, the resulting description length becomes a proxy for generalization, because efficient compression of training structure often reflects genuine regularities rather than noise.

Connections exist between compression length and probabilistic measures (via entropy), statistical inference (via MDL and related criteria), and computational models (via description length in terms of programs). In automata-theoretic settings, encoding lengths can also reflect how succinctly a formal system represents strings or behaviors.

10 Common misconceptions and pitfalls

Misunderstandings often arise from not specifying which notion of length is being used, or from ignoring overhead and feasibility conditions.

10.1 Confusing optimal length with a specific compressor’s length

Optimal compression length is defined relative to an admissible set of encodings, whereas a specific compressor’s length is just what that particular method produces. A compressor can be suboptimal, even if its output appears short on a given dataset.

10.2 Overlooking overhead and headers

Many apparent compression gains vanish once one counts all transmitted bits, including dictionaries, code tables, delimiters, and model parameters. Formal comparisons therefore need a consistent accounting method for overhead.

10.3 Mixing worst-case, expected, and optimal measures

Worst-case length, expected length, and optimal length answer different questions. Worst-case guarantees can be far larger than expected performance, and “optimal” typically means optimized over a specified class or under constraints. Clear distinctions prevent incorrect conclusions about the quality of a coding scheme.