Data Compression
Encoding data in fewer bits by removing redundancy — with entropy as the unbreakable floor.
Data Compression
Data compression (formally, source coding) is the art of describing the same data in fewer bits. It works by exploiting redundancy: real data is not random. Letters in text follow predictable frequencies, pixels resemble their neighbors, audio samples vary smoothly. Wherever a source is predictable, a clever code can name its outcomes more cheaply than the naive fixed-width encoding.
There are two regimes. Lossless compression (ZIP, PNG, FLAC) reconstructs the original bit-for-bit by recoding redundancy. Lossy compression (JPEG, MP3) goes further by discarding detail the recipient will not miss. Information theory governs the lossless case exactly.
Entropy is the floor
The central fact, Shannon's source-coding theorem, is brutal and beautiful: no lossless code can use fewer than H bits per symbol on average, where H is the Entropy of the source. You can approach that floor as closely as you like, but never beat it.
A skewed Probability Distribution has low entropy and compresses well; a uniform one is already at the maximum and cannot be squeezed. This is why an already-compressed file barely shrinks when you ZIP it again — its redundancy is already gone.
How codes beat the fixed-width baseline
Spend short codewords on frequent symbols and long ones on rare symbols, and the average length drops below the fixed-width \log_2 n. The chart contrasts a flat 3-bit-per-symbol encoding with a variable-length code matched to symbol frequencies — the same trick Huffman Coding makes optimal.
The ultimate limit
Entropy bounds compression for a given probability model. But what is the shortest description of one specific string, with no model at all? That is its Kolmogorov Complexity — the length of the smallest program that prints it. A string is incompressible exactly when no program shorter than the string itself can generate it, which is the algorithmic definition of randomness. Practical compressors are finite, fast approximations to this uncomputable ideal.