Frequency Counting

Compression is fundamentally about redundancy: if some symbols appear more often than others, we can represent them with fewer bits.

The first step is just counting:

input: "the quick brown fox jumps over the lazy dog"

frequency table:
  ' ': 8
  'o': 4
  'e': 3
  't': 2
  ...

For typical English text, the letter 'e' appears ~13% of the time, while 'z' is under 0.1%. ASCII encoding uses 8 bits per char regardless. If we used shorter codes for common letters, we'd save space — that's the core of Huffman coding (next chapter).

The information-theoretic lower bound is Shannon entropy:

H(X) = -sum( p(x) * log2(p(x)) )

For uniformly random bytes (all 256 equally likely), H = 8 bits/byte — incompressible. For English text, H is closer to 4-5 bits/byte; for source code, often under 4. The compression ratio you can achieve is bounded by entropy.

Important: compressed data has high entropy. You can't compress already-compressed data effectively. That's why nesting tar.gz inside .zip doesn't shrink it.