Huffman coding

To store text compactly you can give each character a binary code, and frequent characters deserve shorter codes — like Morse code giving 'E' a single dot. But the codes must be decodable without separators, which means no code may be a prefix of another (a prefix code). Huffman coding builds the prefix code that makes the total encoded message as short as possible, given how often each character appears.

It is a greedy bottom-up merge. Put every character in a pool, each weighted by its frequency. Repeatedly take the TWO smallest-frequency items in the pool, merge them into a single new node whose frequency is their sum, and put that node back. Keep going until one node remains — a binary tree. Reading the tree from the root, label left branches 0 and right branches 1; each leaf's path spells its code. Rare characters end up deep (long codes), frequent ones shallow (short codes). The greedy choice — always merge the two least frequent — is justified by an exchange argument: in some optimal tree the two least-frequent symbols are siblings at the deepest level, because if a deeper leaf held a more frequent symbol you could swap it upward and shorten the total length. Optimal substructure then says merging those two into one symbol leaves a smaller instance with the same structure, so induction finishes the proof. With a min-heap the whole construction is O(n log n).

Huffman codes are provably optimal among all prefix codes for symbol-by-symbol coding, and they sit inside real formats like DEFLATE (ZIP, PNG, gzip) and JPEG. Two honest limits: optimality is only relative to coding each symbol independently — methods that model context or code whole blocks (arithmetic coding, modern compressors) can beat it — and Huffman needs to know the frequencies, so it either makes two passes over the data or ships the code table alongside the compressed output.