Coding and Compression

Origin. Shannon's source coding theorem (1948); Soviet contributions to arithmetic coding and universal coding; practical compression informed by Kolmogorov complexity ideas.

Mechanism. Data can be compressed to its entropy rate — the minimum average bits per symbol for lossless representation. Compression exploits structure: patterns, redundancy, dependencies. The compression ratio measures how much structure exists relative to the raw representation. Compression is learning: a good compressor has learned a good model of the data.

Procedure. Choose a compression method appropriate to the data type and structure. Compress the data. The compression ratio (compressed/original) measures redundancy. If compression is poor, either the data is high-entropy (truly random or encrypted), or the compressor's model doesn't match the data's structure. Try domain-specific compression; if that succeeds, you've identified relevant structure. Use compression as a proxy for understanding.

Applies to. Data storage and transmission, anomaly detection (incompressible data in a normally compressible stream), similarity measurement (compression-based distance), model evaluation.

Limitations. Compression conflates all structure, whether meaningful or not. Noise that happens to compress (by chance) is not structure. Also: compression algorithms have biases — they find the structure they're designed to find. Dictionary methods find repeated strings; transform methods find frequency structure; neural compressors find patterns like their training data.