Every file you save and every page you load is a long run of bits. Most of them carry less information than they take up. In 1952 David Huffman showed a simple way to write messages in the fewest possible bits, using nothing but how often each symbol appears. His method is still inside the compression of ZIP and PNG files and of JPEG images.
The idea fits in one sentence. Give the symbols that appear often a short code, and the rare ones a long code. Morse code did the same thing by hand: a common letter such as E is a single dot. The hard part is doing it perfectly, and doing it so a receiver can read the bits back without any gaps between letters.
Huffman coding builds the best possible set of prefix codes for a set of symbols. Repeatedly join the two least common symbols into one, until a single tree remains. Read each symbol's code off the path from the top. No code is the beginning of another, so the bits can be decoded without separators.
The problem: shorter on average
Suppose a message uses only six letters. A fixed code spends the same number of bits on every letter. Six letters need 3 bits each, because 2 bits give only four combinations. That is simple, but it wastes bits when one letter is far more common than the rest.
Huffman's paper calls a code with the smallest average length a minimum-redundancy code. Redundancy here means bits that carry no new information. The goal is a code whose average number of bits per symbol is as small as it can be.
Think of packing for a trip. The things you grab every day go in the outer pocket where they are quick to reach. Things you almost never need go deep in the bag. You spend little effort on the common case and more on the rare one.
