Huffman Codes

In a fixed-length encoding, every character uses the same number of bits (e.g., ASCII uses 8 bits per character). Huffman coding assigns variable-length codes: frequent characters get shorter codes, rare characters get longer ones. This can dramatically reduce total encoding size.

Huffman codes are prefix-free: no code is a prefix of another, allowing unambiguous decoding.

1. Build a frequency table for all characters
2. Create a leaf node for each character
3. Repeatedly merge the two lowest-frequency nodes into a new internal node (sum of frequencies)
4. The final tree defines the encoding: left edges = 0, right edges = 1

This is greedy because at each step we merge the two cheapest nodes, minimizing the total encoding cost from the bottom up.

The visualization follows the full pipeline: an input string, the frequency table from counting symbols, then greedy merges. During construction the forest (every subtree currently in the priority queue) stays on screen at all times—two smallest trees are highlighted when extracted, then merged and re-inserted. The last step shows the final tree and prefix codes.

Encoding walks the plaintext left to right. For each character, look up its bit sequence in the Huffman table (from the tree) and append those bits to the stream. Frequent symbols contribute fewer bits per occurrence, so the total length can be much smaller than a fixed-width code.

This uses the same input string as Step-by-Step Huffman Coding above. Step through to see each symbol replaced and the bitstream grow.

Decoding uses the same tree. Start at the root; for each incoming bit, go left on 0 and right on 1. When you hit a leaf, output that symbol and jump back to the root. Prefix-free codes ensure you never need lookahead.

The bitstream is exactly what Huffman encoding produces for the same string as in Step-by-Step Huffman Coding, so stepping through recovers the original plaintext.

The algorithm uses a min-priority queue (min-heap) and runs in O(n log n) time.

Building the initial heap is O(n). Each of the (n-1) merge operations involves two extract-min and one insert, each O(log n). Total: O(n log n).

Enter a string or frequency table to build a custom Huffman tree. Compare the encoded size against fixed-length encoding.