Give frequent symbols shorter codewords
Huffman coding is a lossless method that assigns variable-length bit strings according to symbol frequencies or probabilities. Shorter words for frequent symbols can reduce average length. Arbitrary short assignments are insufficient: no codeword should be a prefix of another, allowing decoding without a delimiter between symbols. Assigning zero and zero-one to separate symbols illustrates the ambiguity that such a rule prevents. In a Huffman binary tree, symbols occupy leaves rather than internal decision points. The tree therefore provides both a way to construct codewords and a precise rule for recognizing when one decoded symbol has finished.
Repeatedly merge the two lightest trees
Make each symbol a weighted leaf. Remove the two lightest trees, join them beneath a parent weighted by their sum, and repeat until only one tree remains. Assign zero and one to the two branches; a root-to-leaf path gives a codeword. Equal-weight choices and left/right assignments can produce different bit strings. Optimal weighted length does not imply a unique code table. Compression and decompression must share the table, so a real format also defines how the tree, code lengths, or another agreed representation is communicated. The construction algorithm alone is not a complete interoperable compressed-file format.
Calculate a four-symbol example
For an illustrative input, let A occur five times, B twice, and C and D once each. Merge C and D into weight two, merge that tree with B into weight four, and finally merge it with A’s five. The code lengths are one for A, two for B, and three for C and D. Payload cost is five times one plus two times two plus three plus three, or fifteen bits. Fixed two-bit codes for nine symbols cost eighteen bits. The three-bit payload saving excludes tree metadata and original-length information, which can exceed the saving on a tiny input.
Decode at leaves and restart from the root
One valid table assigns A=0, B=10, C=110, and D=111. The bit string010110111 splits into those four words and decodes to ABCD. Emit a symbol on reaching a leaf, then restart traversal from the root. A decoder also needs behavior for truncated input, invalid metadata, and unsupported sizes. Empty input and an alphabet containing only one symbol require explicit format conventions because ordinary repeated merging alone does not specify their entire representation. A small successful example is not a justification for accepting arbitrary malformed trees or lengths without validation. Correct decoding includes format-boundary handling as well as the main tree walk.
State the scope of optimality
Huffman optimality concerns weighted code length for symbol-by-symbol binary prefix codes with the supplied frequencies. It does not claim the smallest file among every compression method and representation. Methods exploiting symbol sequences or different coding models can obtain different results. If actual frequencies change, a previously selected table can also become less effective. Decide whether symbols are bytes, characters, or another unit. A visible Unicode character is not necessarily one stored byte. These boundaries explain why a correct Huffman implementation can still increase total file size or compare unfavorably with another compressor without contradicting the construction’s optimality within its stated model.
Implement with a priority queue and test boundaries
For k distinct symbols, repeatedly extracting two minimum-weight trees from a priority queue gives a typical O(k log k) construction. Frequency counting over the input and emitting code bits add other costs. Evaluate the complete compressed representation, including metadata and padding, and verify round-trip equality after decompression. Equal frequencies, empty input, single-symbol input, and truncation exercise boundaries missed by an ordinary example. The fifteen-bit figure above is a payload calculation, not the measured file size of a specific compression tool. Separating construction, representation overhead, and decoder validation makes both correctness and compression claims easier to assess.