Articles

Huffman Coding Explained: How Lossless Compression Works

Huffman coding gives frequent symbols short bit codes and rare symbols long ones, producing an optimal prefix code. How the tree is built and decoded.

The Lycoris Team The Lycoris Team · · 6 min read
Mathematical equations written on a chalkboard

Huffman coding is a lossless compression algorithm that assigns variable-length binary codes to symbols based on how often they appear: the most frequent symbols get the shortest codes, and the rarest get the longest. The codes form a prefix code — no code is the beginning of another — so a stream of bits can be decoded unambiguously without separators. For a given set of symbol frequencies, Huffman’s method produces the shortest possible average code length among all prefix codes that encode one symbol at a time.

It was devised by David Huffman in 1952, and it still sits inside formats you use every day. DEFLATE (the engine behind gzip, zlib, and PNG) uses it as its final stage, and so do JPEG and many other codecs.

Why fixed-length codes waste space

Plain ASCII spends 8 bits on every character, whether it is e or z. Even a tighter fixed-length scheme — say, 5 bits for an alphabet of 26 letters plus a few extras — still spends the same number of bits on common and rare symbols alike.

Real data is not uniform. In English text, spaces and vowels dominate. In a log file, a handful of keywords repeat endlessly. If you could spend 2 or 3 bits on the common symbols and 10 bits on the rare ones, the total would shrink. That is exactly the trade Huffman coding makes, and it is the same intuition behind Morse code, where E is a single dot.

The catch with variable-length codes is ambiguity. If A = 0 and B = 01, then the bits 01 could be B or A followed by something else. Prefix codes remove that problem: because no codeword is a prefix of another, the decoder always knows when one symbol ends.

Building the Huffman tree

The algorithm builds a binary tree from the bottom up. Each leaf is a symbol, and the path from the root to a leaf spells its code: going left appends 0, going right appends 1.

  1. Count the frequency of every symbol in the input.
  2. Create a leaf node for each symbol, weighted by its frequency, and put all of them in a min-priority queue.
  3. Remove the two nodes with the lowest weights.
  4. Create a new internal node whose children are those two nodes and whose weight is their sum. Insert it back into the queue.
  5. Repeat steps 3 and 4 until only one node remains. That node is the root.

The priority queue is usually a binary heap, which makes each insert and extract-min an O(log n) operation. With n distinct symbols, the whole build runs in O(n log n) — see Big O notation if that notation is unfamiliar.

Huffman’s method is a textbook greedy algorithm: at each step it merges the two cheapest subtrees without looking ahead, and that local choice is provably optimal overall.

A worked example

Take the string ABRACADABRA. The frequencies are:

SymbolCount
A5
B2
R2
C1
D1

Building the tree:

  • Merge C (1) and D (1) into a node of weight 2.
  • Merge B (2) and R (2) — or the new CD node; ties can go either way — into a node of weight 4.
  • Merge the remaining weight-2 node with the weight-4 node into a node of weight 6.
  • Merge A (5) with the weight-6 node to form the root, weight 11.

One resulting code table:

SymbolCodeBits per symbol
A01
B1003
R1013
C1103
D1113

Encoding the string costs 5×1 + 2×3 + 2×3 + 1×3 + 1×3 = 23 bits. A fixed 3-bit code for five symbols would cost 33 bits, and 8-bit ASCII would cost 88. Different tie-breaking produces different trees, but every valid Huffman tree for these frequencies yields the same 23-bit total.

How decoding works

The decoder needs the same tree (or code table) the encoder used. It then reads bits one at a time, starting at the root: 0 moves left, 1 moves right. When it reaches a leaf, it outputs that symbol and jumps back to the root.

Because the code is prefix-free, there is never a moment of doubt about where a symbol ends. Production decoders avoid walking the tree bit by bit; they use lookup tables indexed by the next several bits, which decodes a whole symbol in one step.

Shipping the tree: canonical Huffman codes

The compressed output is useless without the code table, so the encoder has to transmit it. Sending a full tree structure is wasteful, which is why real formats use canonical Huffman codes.

The idea is that only the code lengths matter. Given each symbol’s length, both sides can assign codes deterministically: sort symbols by length, then by symbol value, and hand out consecutive binary numbers. The encoder sends just a list of lengths — compact, and itself compressible. DEFLATE does exactly this, even Huffman-coding the list of code lengths.

Strengths and limits

Strengths:

  • Optimal for symbol-by-symbol coding. No prefix code that maps each symbol to a whole number of bits does better for a given frequency distribution.
  • Fast. Table-driven decoding is extremely cheap, which matters for formats decoded far more often than encoded.
  • Simple. The algorithm fits in a few dozen lines and is easy to reason about.

Limits:

  • Whole-bit granularity. Every code is at least 1 bit. If one symbol makes up 99% of the data, its ideal cost is a tiny fraction of a bit, but Huffman still spends a full bit. Arithmetic coding and asymmetric numeral systems (ANS) can spend fractional bits per symbol and compress skewed data better.
  • No context. Huffman coding only exploits symbol frequency, not patterns. It cannot see that the repeats as a unit. That is why it is almost always paired with a dictionary or modeling stage.
  • Two passes or an adaptive variant. Static Huffman needs the frequencies up front. Adaptive versions update the tree as they go, at the cost of speed and complexity.

Where Huffman fits in real compressors

Modern compressors are pipelines. DEFLATE first runs LZ77, which replaces repeated byte sequences with back-references (“copy 12 bytes from 300 bytes ago”), and then Huffman-codes the resulting literals, lengths, and distances. The LZ stage removes repetition; the Huffman stage squeezes the leftover statistics.

Newer formats swap in more sophisticated entropy coders. Our comparison of gzip vs Brotli shows how a better dictionary and context modeling change the results, but the core split — find repetition, then entropy-code what remains — is the same.

Huffman coding is also a useful contrast to fixed-width encodings like UTF-8, which is variable-length too but assigns lengths by code point range rather than by frequency in your particular data.

The takeaway

Huffman coding turns symbol frequencies into an optimal prefix code by repeatedly merging the two least-frequent nodes into a tree. Frequent symbols land near the root with short codes; rare ones sink deep with long codes. It is fast, simple, and provably optimal among whole-bit, symbol-at-a-time codes — which is why it remains the final stage of gzip, PNG, and JPEG, usually paired with a dictionary stage that handles repetition and sometimes replaced by arithmetic or ANS coders when every fraction of a bit counts.

The Lycoris Team The Lycoris Team · · 6 min read

Gap Buffer vs Piece Table: Text Editor Data Structures

A gap buffer keeps free space at the cursor; a piece table never edits the original text. How editors store documents, compared side by side.

#Computer Science #Data Structures #Algorithms
The Lycoris Team The Lycoris Team · · 5 min read

Kadane's Algorithm Explained: Maximum Subarray in O(n)

Kadane's algorithm finds the maximum-sum contiguous subarray in one O(n) pass. How it works, why it's correct, code, edge cases, and common variations.

#Algorithms #Computer Science #Data Structures
The Lycoris Team The Lycoris Team · · 4 min read

The Rope Data Structure: Editing Huge Strings Efficiently

A rope is a binary tree of string chunks that makes inserting, deleting, and slicing huge strings fast, which is why text editors use it over plain arrays.

#Computer Science #Data Structures #Algorithms