Computer Science · Simulator 100
Common letters deserve short codes and rare ones can have long codes. Type some text and watch a Huffman tree being built from the letter counts. Compare how many bits it needs with plain 8-bit text and the theoretical limit, then press Play to decode the bit stream one bit at a time by walking the tree.
Huffman coding (1952) builds an optimal prefix code from symbol counts. Start with one node per symbol, weighted by its count. Repeatedly join the two lightest nodes under a new parent whose weight is their sum, until one tree remains. Reading the path from the root to a leaf gives that symbol's code: 0 for left, 1 for right.
No code is the start of another (a prefix code), so the bit stream can be decoded without separators: walk from the root, follow each bit, and output a symbol whenever you reach a leaf.
The total length equals the sum of all the internal node weights. Shannon's entropy gives the lower limit on the average bits per symbol for any code that treats symbols independently:
H = − Σ pᵢ log₂ pᵢ H ≤ Huffman average < H + 1
A fixed-length code needs ⌈log₂ k⌉ bits per symbol for k different symbols; plain text uses 8 bits per character (ASCII or UTF-8 bytes).
Counts are taken from the text itself, and the code table would also have to be stored or sent, which this count ignores. Ties between equal weights are broken by a fixed rule, so other valid trees exist with the same total length. Real compressors (ZIP, PNG) combine Huffman coding with LZ77 repeat matching.
Four symbols appear with counts A 8, B 4, C 2, D 2. Build the Huffman code by hand. How many bits does the whole message need, and how does that compare with the entropy?
Join C and D (4), then that node with B (8), then with A (16). Codes: A = 1 bit, B = 2 bits, C and D = 3 bits each. Total = 8 × 1 + 4 × 2 + 2 × 3 + 2 × 3 = 28 bits, 1.75 bits per symbol. The probabilities are 1/2, 1/4, 1/8, 1/8, all powers of two, so the entropy is also exactly 1.75: Huffman is perfect here. Type AAAAAAAABBBBCCDD to check.