Scribd
Upload
2 views3 pages

4 Compression Reference

The document discusses the concept of compression algorithms that exploit patterns in real data to create shorter encodings, using examples like gzip and zstd. It explains that while compression can significantly reduce file sizes, it cannot guarantee shrinkage for all types of data due to the pigeonhole principle. The document also encourages practical experimentation with compression ratios between structured and random data.

Uploaded by

terrificdatabytes
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views3 pages

4 Compression Reference

The document discusses the concept of compression algorithms that exploit patterns in real data to create shorter encodings, using examples like gzip and zstd. It explains that while compression can significantly reduce file sizes, it cannot guarantee shrinkage for all types of data due to the pigeonhole principle. The document also encourages practical experimentation with compression ratios between structured and random data.

Uploaded by

terrificdatabytes
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Concept 4 of 5

Compression + Reference
Letting an algorithm find the shortest practical encoding for real data

Page 1 — The Core Idea


Real files usually aren't random — they contain patterns: repeated bytes, predictable structure,
redundant headers. Compression algorithms find and exploit that structure to produce a smaller
stream of bytes, which is itself just a (smaller) huge number.

The idea from concept 1 (Kolmogorov complexity) in practical form: instead of a human-written
formula, an algorithm like gzip or zstd automatically finds a shorter encoding plus a small, standard
decoder that already exists on every computer.

Two ingredients you actually store


• The compressed bytes (short, if the data has structure)
• A reference to the decoder (gzip, zstd, etc. — already installed everywhere)
Page 2 — Worked Example
Compressing a big binary file in a few lines
import zstandard as zstd with open('[Link]', 'rb') as f: data =
[Link]() compressed = [Link](level=19).compress(data)
print(len(data), '->', len(compressed), 'bytes')

A file that's mostly zeros, repeated patterns, or predictable text might shrink from gigabytes down to
kilobytes. The compressed blob is what you store or send; decompressing it regenerates the exact
original number.

decompressed = [Link]().decompress(compressed) assert


decompressed == data
Page 3 — The Catch, and Why It Matters
Compression can never guarantee shrinkage for every possible input — this is the pigeonhole
principle: there are more possible files of length N than of length less than N, so some inputs must get
larger or stay the same after compression.

High-entropy data — already-compressed files, encrypted data, cryptographic hashes, sensor noise — will
not shrink further, and can even grow slightly due to format overhead. Compression is a bet on structure,
not a universal shrink-ray.

Try it yourself
• Compress a text file and a random-bytes file of the same size.
• Compare compression ratios — the text file should shrink far more.
• This difference is a direct, hands-on demonstration of entropy.

You might also like