If some letters appear far more than others, why give them all the same-length code? Huffman’s trick (1952, as a student): give COMMON symbols short codes and rare ones long codes, built by repeatedly merging the two least-frequent nodes into a tree. The result is the optimal prefix code — no code is a prefix of another, so it decodes with no commas. It’s inside ZIP, JPEG, MP3. Slide to build the tree.
Huffman coding builds an optimal prefix (comma-free) code: treat each symbol as a leaf weighted by frequency, repeatedly merge the two lowest-weight nodes into a parent, and read each leaf’s code from the root path (0=left, 1=right). Frequent symbols end up near the root with short codes; the average code length equals the weighted depth and is provably minimal among prefix codes (it approaches the Shannon entropy). No codeword is a prefix of another, so decoding is unambiguous. A fail-loud self-check throws unless the code is prefix-free and frequent symbols are no longer than rare ones. ◆ real information theory, node-verified.
Optimal among symbol-by-symbol PREFIX codes (arithmetic/range coding can beat it by fractions of a bit); the tree construction and prefix-free property shown are exact. Frequencies here are the classic textbook set.