# Data Compression

Encoding data in fewer bits, losslessly by exploiting statistical redundancy or lossily by discarding perceptually unimportant detail.

**Rests on:** Shannon Entropy

**Leads to:** Autoencoders, Edge and Fog Computing, Huffman Compression, KL Divergence, Mutual Information, Quantization

*Mathematical Foundations · Information Theory*


## Why learn this

Imagine you are trying to send a high-resolution photo to a friend who has a slow mobile data connection. If you send the raw file, it might take ten minutes and cost your entire monthly allowance. But if you shrink the file just enough that it still looks perfect on their screen, it takes two seconds. This shrinking is compression. It is not just about saving storage space; it is about efficiency. When modern AI models read text or listen to audio, they are constantly compressing patterns. They ignore the predictable parts of a sentence (like "the" before a noun) and focus only on the surprising parts. Understanding compression gives you the key to understanding how these models save memory, how they learn quickly from limited data, and why some digital files look blurry while others stay sharp. It explains the fundamental trade-off between quality and speed that governs everything from your phone's battery life to the clarity of a Zoom call.


## The intuition

Think of a sentence in a novel: 'The quick brown fox jumps over the lazy dog.' If you had to send this to a friend over a very slow text connection, you would not send the whole thing letter by letter. You would find a way to shorten it. Maybe you and your friend have an agreement that common words can be replaced by shorter symbols: 'the' becomes 'th', 'fox' becomes 'fx', and 'lazy' becomes 'lz'. The message now reads 'th qk fx jumps over lz dog.' It carries the same meaning but uses fewer characters. That is compression — finding a shorter way to represent the same information.

Now think of a photo of a clear blue sky. Most of the pixels in that photo are almost exactly the same shade of deep blue. Instead of listing the color value for every single pixel, you could say 'Color B, repeated 1000 times.' You have made the data much smaller without losing any information at all. This is lossless compression: you can take that short instruction and reconstruct the exact original photo, pixel for pixel.

But sometimes you need to go further. Suppose you look closely at that blue sky. There are tiny variations in color that your eye cannot possibly notice. If you group those tiny differences together and average them out into a single 'medium blue,' the file size drops dramatically. The photo looks identical to a human observer, but mathematically, it is different. This is lossy compression: the file is much smaller, but you can never get the exact original pixel values back because that specific detail was thrown away.

Compression is everywhere: ZIP files on your computer shrink folders using lossless methods so nothing is lost; JPEG photos and MP3 music use lossy methods to save space by hiding details you won't miss. It is all about identifying what is redundant (repeating, predictable) or imperceptible, and removing it.


## An analogy

Imagine you are packing a suitcase for a week-long trip. You have a pile of clothes in your closet. If you simply throw every shirt and pair of pants into the bag, it won't close. But if you roll each item tightly, you fit more in. This is the basic principle of reducing space.

Now, consider what happens when you pack intelligently. You know you are going to a beach, so you expect to wear swimsuits every day. These appear frequently. You also know you have only one formal suit for one dinner. The formal suit appears rarely. A smart packing strategy is to organize the bag so that the swimsuits (the common items) are easy to access and grouped tightly together, perhaps even folded in a way that minimizes their footprint because they are identical or very similar. The formal suit can take up a strange, unused corner or be compressed further because it is unique.

This mirrors how data compression works: the 'common symbols' (frequently occurring data patterns) are handled with shorter, more efficient codes, while 'rare symbols' get longer, less efficient codes. The total amount of clothing you *must* pack is determined by the number of days and activities — this limit is like the minimum possible file size for that specific trip.

However, there is a catch: imagine you need to save even more space because your bag has a strict weight limit. You might decide that you don't actually need a backup pair of socks if they get dirty. You leave them out. The suitcase fits easily, but you have lost the option to have clean socks later. This is the trade-off in lossy compression: you sacrifice some quality or completeness to achieve a smaller size.

The suitcase is the compressed file, the clothes are the data, and your folding method is the algorithm. The limit of how little space you can use while keeping the trip functional is defined by the minimum number of shirts required, regardless of how cleverly you fold them.


## Definition

Data compression is the process of encoding information using fewer bits than the original representation, either by exploiting statistical redundancy to ensure perfect reconstruction (lossless) or by discarding perceptually unimportant detail to achieve greater shrinking (lossy).


## How it connects

This concept sits directly next to Information Theory, which is the branch of mathematics that measures how much 'surprise' or information is contained in a message. It also connects closely to Lossless Compression algorithms like Huffman Coding, which are practical methods that assign shorter codes to common symbols and longer codes to rare ones to approach the theoretical limits of efficiency.


## The mathematics

The mathematics behind compression is about counting and probability. The branch is information theory, but the operations are simple arithmetic. The core idea is that some symbols occur more often than others. If a symbol occurs often, you want to give it a short code — like '1' for the most common letter. If it occurs rarely, you can give it a long code — like '111011001'. 

To understand why this works, we need a way to measure how much information a symbol carries. We use a function called the logarithm base 2, written as log₂. When we say -log₂(p), where p is the probability of a symbol, we are calculating the number of bits needed to represent that symbol in an ideal system. 

Let us look at what this formula does. The term log₂(p) takes a probability (a number between 0 and 1) and tells us how many times we must multiply 2 by itself to get p. Because p is less than 1, the result is negative. We put a minus sign in front to make the result positive. 

For example, if a symbol has a probability of 0.5 (or 1/2), log₂(0.5) equals -1. The negative sign makes it +1. This means we need 1 bit to represent it. If a symbol has a probability of 0.25 (or 1/4), log₂(0.25) equals -2. With the minus sign, it is +2 bits. Notice that 0.25 is half as likely as 0.5, and it requires twice as many bits. This confirms the rule: if something is twice as likely, it should use half the bits.

The average number of bits per symbol, weighted by how often each appears, is called entropy. It is the theoretical minimum — no matter how clever you are, you cannot compress below this average. For example, if a text has only two letters, A and B, and A appears 3 out of 4 times, you could use code: A='0', B='1'. That gives 1 bit per symbol on average. But you could do better: A='0', B='10', and then '11' as a separator — but that complicates things. The point is that the entropy is a number between 0 and log₂(number of symbols). If all symbols are equally likely, you get the maximum entropy and you cannot compress at all. If one symbol is dominant, entropy is low and you can compress a lot.

The formula for entropy is:

Entropy H = -∑ pᵢ log₂(pᵢ)

Here is what each part means:
- H is the entropy, measured in bits per symbol.
- The symbol ∑ (sigma) means 'sum'. It tells you to add up a list of numbers.
- pᵢ is the probability of the i-th symbol. For example, if there are 4 symbols, i goes from 1 to 4.
- log₂(pᵢ) is the logarithm base 2 of that probability.
- The negative sign in front ensures the final result is a positive number, because probabilities are fractions less than 1, and their logs are negative.

To calculate H, you take each symbol's probability, multiply it by its own bit-length (which is -log₂(pᵢ)), and add all those products together.


## A worked example

Suppose you have a text with four letters: A, B, C, D. Their probabilities are: A: 0.5, B: 0.25, C: 0.125, D: 0.125. That means out of 1000 letters, A appears 500 times, B 250 times, C and D 125 each. We will compute the entropy and then see a simple code.

Step 1: Calculate the bit-length for A.
The probability of A is p₁ = 0.5.
We need -log₂(0.5).
Since 2 to the power of 1 is 2, and 1/2 is 0.5, log₂(0.5) = -1.
With the negative sign, the bit-length is 1 bit.

Step 2: Calculate the bit-length for B.
The probability of B is p₂ = 0.25.
We need -log₂(0.25).
Since 2 to the power of 2 is 4, and 1/4 is 0.25, log₂(0.25) = -2.
With the negative sign, the bit-length is 2 bits.

Step 3: Calculate the bit-length for C.
The probability of C is p₃ = 0.125.
We need -log₂(0.125).
Since 2 to the power of 3 is 8, and 1/8 is 0.125, log₂(0.125) = -3.
With the negative sign, the bit-length is 3 bits.

Step 4: Calculate the bit-length for D.
The probability of D is p₄ = 0.125.
This is the same as C, so the bit-length is 3 bits.

Step 5: Calculate the weighted average (Entropy).
We multiply each probability by its bit-length and add them up.
For A: 0.5 * 1 = 0.5
For B: 0.25 * 2 = 0.5
For C: 0.125 * 3 = 0.375
For D: 0.125 * 3 = 0.375
Sum: 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits per symbol.

Step 6: Compare with a fixed code.
If we used a fixed code of 2 bits per symbol (00, 01, 10, 11), we would use 2 bits per symbol. With Huffman code (A='0', B='10', C='110', D='111'), the average is 1.75 bits.

Result: The minimum average number of bits per symbol is 1.75. That is the entropy. No lossless code can do better than that for this distribution.


## From scratch, in Python

```python
import math

def entropy(probabilities):
    total = 0
    for p in probabilities:
        if p > 0:
            total -= p * math.log2(p)
    return total

def huffman(symbols):
    nodes = [[p, s] for s, p in symbols]
    nodes.sort(key=lambda x: x[0])
    while len(nodes) > 1:
        low1 = nodes.pop(0)
        low2 = nodes.pop(0)
        new_node = [low1[0] + low2[0], [low1, low2]]
        nodes.append(new_node)
        nodes.sort(key=lambda x: x[0])
    root = nodes[0]
    codes = {}
    def assign(node, code):
        if isinstance(node[1], str):
            codes[node[1]] = code
        else:
            assign(node[1][0], code + '0')
            assign(node[1][1], code + '1')
    assign(root, '')
    return codes

symbols = [('A',0.5), ('B',0.25), ('C',0.125), ('D',0.125)]
print(entropy([p for s,p in symbols]))
print(huffman(symbols))
```


## The same thing, with a framework

```python
import zlib
data = b'Hello world hello world hello world'
compressed = zlib.compress(data)
print(len(data), len(compressed))
```


## What the code does

The entropy function loops through each probability, computes -log2(p), and adds it to a total. That is exactly the formula we worked by hand. The huffman function builds a binary tree. It starts with each symbol as a node with its probability. It repeatedly takes the two least probable nodes and merges them into a new node whose probability is their sum. When only one node remains, that is the root. Then we walk down the tree, assigning '0' for a left branch and '1' for a right branch. Leaf nodes get the codes. The key is the `while` loop and the sorting — that is the greedy merge.


## Common misconceptions

**Compression always loses information** — If I compress a file, I can never get the original back.

That is only true for lossy compression. Lossless compression (like ZIP) reconstructs the exact original. In fact: Lossless compression is exactly reversible; lossy compression discards information by design.

**Entropy is the file size** — Entropy is just the size of the file after compression.

Entropy is the theoretical minimum average bits per symbol, not a file size. You can approach it but never beat it. In fact: Entropy is the lower bound, not the actual size.

**Compressing random data always works** — I can compress any file, even random numbers.

If the data is truly random (uniform distribution), it has maximum entropy — there is no redundancy to exploit, so any compression will actually make it bigger. In fact: Only data that has statistical structure can be compressed.

**Lossy compression is bad because it loses data** — Why would I ever use lossy compression? I would rather have the original.

In many cases, the lost detail is imperceptible to humans (like high-frequency sounds or slight colour variations), and the huge size reduction is worth it. In fact: Lossy compression is a deliberate trade-off between fidelity and size, chosen because the discarded detail is not important to the user.

**All codecs are the same** — Any compression algorithm works equally well on any data.

Different algorithms exploit different kinds of redundancy — text compresses differently than images or audio. Huffman works for symbols; JPEG uses lossy transforms for images; MP3 uses perceptual masking. In fact: The right codec depends on the type of data and the trade-off you want.


## In short

Data compression is about removing redundancy to use fewer bits. The theoretical limit is entropy, which depends on how predictable the data is. Lossless compression preserves all information, lossy compression discards what is not important. A good compressor is a good probabilistic model of the data. This idea connects directly to how AI models are trained and how they represent information.


## Where this is used

In AI and machine learning, compression is not just about saving disk space — it is at the core of how models represent and transmit information. For large language models (LLMs) like GPT-4, the model is trained to predict the next token in a sequence. That is exactly a compression task: the better the model predicts, the shorter the encoding of the text. The training loss is cross-entropy, which measures the average number of bits needed to encode the tokens. In retrieval-augmented generation (RAG), embeddings are compressed representations of text — a sentence becomes a vector of numbers, and that vector is a lossy compression of the meaning. The quality of that compression determines how well the retrieval works. In small models running on devices (like your phone's keyboard), the model is compressed to fit in memory — using techniques like quantization, which reduces the number of bits per weight. In agentic systems that plan and call tools, the agent often has to compress its memory — keeping only the most relevant past steps, which is a form of lossy compression of the conversation history. In everyday applied ML, compression is used in recommendation systems to store user preferences compactly, in fraud detection to reduce the feature space, and in speech recognition to encode audio efficiently (e.g., MP3 for music, or spectrograms for the model). Developers reach for libraries like `zlib`, `brotli`, or `numpy` to handle data; when they build models, they use techniques like weight pruning and quantization (in PyTorch) to compress the model without losing much accuracy. If done badly, compression can ruin the model — for example, over-compressing the input data loses important patterns, and under-compressing wastes memory and compute. A good compressor is a good probabilistic model: the better you understand the data, the smaller you can make it.


---

Read this on the web: https://basavapurushottam.com/learn-ai/data-compression
