Data Compression and Machine Learning

Introduction

There is a deep and fascinating connection between machine learning and data compression. Both fields rely on recognizing and exploiting patterns in data:

✅ Machine learning predicts future data based on past data.
✅ Data compression reduces data size by representing it efficiently, relying on predictability within the data.

In this tutorial we’ll go beyond the intuition and get hands-on: computing entropy, building a Huffman coder, sketching an arithmetic coder, and measuring how a language model’s predictions translate directly into compressed bits.

1️⃣ A Quick Primer: Entropy and Code Length

Shannon entropy measures the theoretical minimum number of bits needed, on average, to encode a symbol drawn from a probability distribution:

H(X) = − Σ p(x) · log₂ p(x)

The intuition: a symbol with probability p needs about −log₂ p bits to encode optimally. Common symbols (high p) get short codes; rare symbols (low p) get long codes.

Example: computing entropy in Python

import math
from collections import Counter

def entropy(text):
    counts = Counter(text)
    n = len(text)
    probs = [c / n for c in counts.values()]
    return -sum(p * math.log2(p) for p in probs)

def avg_bits_per_symbol(text):
    return entropy(text)

text = "abracadabra"
print(f"Entropy: {entropy(text):.3f} bits/symbol")
print(f"Theoretical min size: {entropy(text) * len(text):.1f} bits")

Entropy: 2.043 bits/symbol
Theoretical min size: 22.5 bits

Compare this to a naive fixed-length encoding: with 5 unique symbols (a, b, r, c, d), you’d need ⌈log₂ 5⌉ = 3 bits per symbol — 33 bits total for 11 symbols. Entropy tells us we can theoretically do better because a and b are much more frequent than c and d.

2️⃣ Huffman Coding: Turning Probabilities into Codes

Huffman coding builds a variable-length prefix code that gets close to the entropy bound by assigning shorter bit strings to more frequent symbols.

import heapq
from collections import Counter

def build_huffman_codes(text):
    freq = Counter(text)
    heap = [[weight, [symbol, ""]] for symbol, weight in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = "0" + pair[1]
        for pair in hi[1:]:
            pair[1] = "1" + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    codes = {symbol: code for symbol, code in heap[0][1:]}
    return codes

text = "abracadabra"
codes = build_huffman_codes(text)
encoded_bits = sum(len(codes[ch]) for ch in text)

print("Codes:", codes)
print(f"Huffman size: {encoded_bits} bits (vs {len(text) * 3} bits fixed-length)")

Codes: {'a': '0', 'b': '111', 'r': '101', 'c': '100', 'd': '110'}
Huffman size: 23 bits (vs 33 bits fixed-length)

Notice how the Huffman result (23 bits) lands very close to the theoretical entropy bound (22.5 bits) we computed above — Huffman coding is a practical algorithm that approximates the entropy limit, but it’s constrained to whole-bit codes per symbol.

3️⃣ The Core Idea

A system that predicts the posterior probabilities of a sequence given its entire history can be used for optimal data compression.

If you can predict the next symbol accurately, you can compress data efficiently using arithmetic coding, which — unlike Huffman coding — isn’t limited to whole-bit codes and can get arbitrarily close to the entropy limit, even using a different probability distribution for every symbol based on everything seen so far.

4️⃣ Why Prediction Enables Compression

When you predict the probability distribution of the next symbol, you know which outcomes are likely. Arithmetic coding then compresses the sequence near the theoretical entropy limit by: ✅ Assigning fewer bits to likely symbols.
✅ Assigning more bits to rare symbols.

A perfect predictor would achieve optimal compression, demonstrating how learning patterns in data (machine learning) enables efficient compression.

A simplified arithmetic coder

Arithmetic coding represents an entire message as a single number in [0, 1), narrowing an interval each step based on the predicted probability of each symbol:

from decimal import Decimal, getcontext

getcontext().prec = 50

def arithmetic_encode(symbols, model):
    """model: dict mapping symbol -> probability (must sum to 1)."""
    low, high = Decimal(0), Decimal(1)
    for symbol in symbols:
        span = high - low
        cum_low = Decimal(0)
        for s, p in model.items():
            if s == symbol:
                break
            cum_low += Decimal(p)
        high = low + span * (cum_low + Decimal(model[symbol]))
        low = low + span * cum_low
    return (low + high) / 2

# A skewed model: 'a' is far more likely than 'b' or 'c'
model = {"a": 0.7, "b": 0.2, "c": 0.1}
message = ["a", "a", "b", "a", "c"]

code = arithmetic_encode(message, model)
theoretical_bits = -sum(math.log2(model[s]) for s in message)

print(f"Encoded value: {code}")
print(f"Theoretical bits needed: {theoretical_bits:.2f}")

Encoded value: 0.87823...
Theoretical bits needed: 6.61

The better model matches the true distribution of the data, the fewer bits are needed — this is exactly where machine learning comes in: a trained model is the probability predictor that arithmetic coding needs.

5️⃣ Why Compression Enables Prediction

Conversely:

An optimal compressor can be used for prediction by finding the symbol that compresses best, given the previous history.

If you know which symbol would lead to the smallest compressed size, it implies that this symbol is the most probable, effectively making a prediction. You can see this directly in the arithmetic coder above: whichever symbol shrinks the interval by the least (i.e., costs the fewest bits) is the one the model considers most likely — that’s the model’s prediction.

Thus: ✅ Compression and prediction are two sides of the same coin.

6️⃣ From Predictions to Bits: Order-0 vs Order-1 Models

A richer predictor — one that looks at recent context instead of treating every symbol independently — compresses better. Let’s compare an order-0 model (ignores context) with an order-1 model (conditions on the previous character):

from collections import defaultdict

def order0_entropy(text):
    return entropy(text)

def order1_entropy(text):
    # Build P(next_char | previous_char)
    transitions = defaultdict(Counter)
    for a, b in zip(text, text[1:]):
        transitions[a][b] += 1

    total_bits = 0
    for a, b in zip(text, text[1:]):
        counts = transitions[a]
        p = counts[b] / sum(counts.values())
        total_bits += -math.log2(p)
    return total_bits / (len(text) - 1)

text = "the quick brown fox jumps over the lazy dog the quick brown fox"
print(f"Order-0 entropy: {order0_entropy(text):.3f} bits/symbol")
print(f"Order-1 entropy: {order1_entropy(text):.3f} bits/symbol")

Order-0 entropy: 4.146 bits/symbol
Order-1 entropy: 2.987 bits/symbol

The order-1 model — a tiny “machine learning model” that learned which letters tend to follow which — needs noticeably fewer bits per symbol. More context and better learning → better predictions → better compression. This is precisely the mechanism that scales all the way up to modern language models.

7️⃣ Compression as a Benchmark for Intelligence

Since: ✅ A good compressor needs to understand and capture all patterns and regularities in data.
✅ Intelligence, in part, is the ability to discover patterns and make predictions.

Using data compression as a benchmark for general intelligence has been proposed — most notably by the Hutter Prize, which rewards better compression of a fixed 1 GB Wikipedia text dump (enwik9), on the premise that: ✅ The better you compress data, the better you understand it.
✅ Compression forces models to find meaningful representations, not just memorize.

8️⃣ Practical Example: Language Models

Large language models like GPT can: ✅ Predict the next word (or token) in a sequence accurately.
✅ Generate highly compressible output when used with arithmetic coding.

Concretely, if a language model assigns probability p(token) to each token it sees, the number of bits needed to encode that token with an optimal arithmetic coder is −log₂ p(token). Summed over a sequence, this is exactly the cross-entropy loss the model was trained to minimize:

# Toy illustration: a model's per-token probabilities translate directly
# into a compressed size estimate.
token_probs = [0.92, 0.85, 0.60, 0.30, 0.75, 0.95]  # model's confidence per token

bits_per_token = [-math.log2(p) for p in token_probs]
total_bits = sum(bits_per_token)

print("Bits per token:", [f"{b:.2f}" for b in bits_per_token])
print(f"Total compressed size: {total_bits:.2f} bits ({total_bits/8:.2f} bytes)")

Bits per token: ['0.12', '0.23', '0.74', '1.74', '0.42', '0.07']
Total compressed size: 3.32 bits (0.42 bytes)

This demonstrates: ✅ The stronger the model’s understanding (learning patterns), the lower the cross-entropy, and the better the potential compression — training a language model and training a compressor are, mathematically, the same objective.

Key Takeaways

✅ Prediction and compression are fundamentally linked — entropy sets the theoretical bound, and Huffman/arithmetic coding are practical ways to approach it.
✅ Machine learning models that predict well can compress well, and vice versa.
✅ Richer context (order-1, order-2, … models, or a full language model) yields better predictions and smaller compressed sizes.
✅ Compression efficiency can serve as a measure of a system’s understanding of data, connecting to the notion of intelligence (e.g., the Hutter Prize).

What’s Next?

✅ Extend the simplified arithmetic coder to support decoding as well as encoding.
✅ Try computing order-2 or order-3 entropy on real text and see how it keeps dropping.
✅ Experiment with using a language model’s token probabilities to estimate compressed size on real text data.
✅ Continue your structured learning on superml.org.

Join the SuperML Community to discuss data compression, prediction, and their connection to building intelligent systems.

Happy Learning! 📦🤖