Huffman Coding — Saying the Most with the Fewest Bits

Every day, we send images, audio, and text across the internet, and almost all of these files are compressed before transmission. How does compression actually work? Why can a compressed file be restored to its original state?

In the previous article on JPEG compression, we mentioned that Huffman coding is the final step in the JPEG compression pipeline. In this post, let’s take a deeper dive into Huffman coding itself.

Frequency and Encoding

Suppose you want to transmit a piece of text that contains only four letters: A, B, C, and D. The most intuitive approach is to use fixed-length binary encoding:

Character	Code
A	00
B	01
C	10
D	11

Each character takes 2 bits—simple and straightforward. But what if A appears 1,000 times, while D appears only once? Using codes of the same length for characters with such vastly different frequencies feels rather wasteful.

This is precisely the problem Huffman coding aims to solve:

Assign shorter codes to high-frequency characters and longer codes to low-frequency ones.

This concept is very similar to Morse code—the most frequent letter in English, E, is represented by just a single dot ., while the rarely used Q requires four symbols: --.-.

Information Content and Entropy

Before diving into compression, let’s consider a question: How do we actually measure the “information content” of an event?

If someone tells you, “The sun will rise in the east tomorrow,” you won’t feel like you’ve learned anything new—it’s practically certain. But if someone says, “It will hail tomorrow,” you’d be quite surprised because the probability of that happening is extremely low.

Claude Shannon introduced a mathematical definition for information content in 1948. For an event with a probability of occurrence $p$ , its information content is:

I = -\log_2(p)

The lower the probability, the greater the information content. This makes intuitive sense—the more surprising an event is, the more information it carries. The entropy of an information source is the average information content across all symbols:

H = -\sum_{i} p_i \log_2(p_i)

What entropy tells us is: for this information source, what is the theoretical minimum number of bits needed on average to encode each symbol. The brilliance of Huffman coding is that it can get remarkably close to this theoretical lower bound.

The Huffman Coding Algorithm

David A. Huffman proposed this algorithm in 1952. The algorithm itself is quite easy to understand and simple to implement, yet its effectiveness is remarkable—Huffman coding is still widely used today.

Steps

Count frequencies: Calculate the occurrence count of each character.
Build a Priority Queue: Order all characters by frequency from lowest to highest.
Merge repeatedly: Extract the two nodes with the lowest frequencies, merge them into a new node (with a frequency equal to their sum), and insert it back into the queue.
Repeat until only one node remains: This node becomes the root of the Huffman tree.
Generate the code table: Traverse from the root, assigning 0 when moving left and 1 when moving right.

A Walkthrough Example

Let’s use the string "aabbbcccc" as an example:

Step 1 — Count frequencies:

a: 2, b: 3, c: 4

Step 2 — Merge the two smallest:

a(2) + b(3) → ab(5)

Step 3 — Merge the two smallest again:

c(4) + ab(5) → root(9)

The final Huffman tree:

        (9)
       /   \
     0       1
    c(4)   (5)
           /   \
         0       1
        a(2)   b(3)

Code table:

Character	Code	Length
c	0	1
a	10	2
b	11	2

Originally encoded in ASCII: $9 \times 8 = 72$ bits. After Huffman coding: $4 \times 1 + 2 \times 2 + 3 \times 2 = 14$ bits.

Why Huffman Coding Works So Well

Huffman coding is a type of prefix code. A prefix code is defined such that no code is a prefix of any other code.

For example, if A = 0 and B = 01, when the decoder reads 01, it cannot tell whether it represents “A followed by a 1” or “B”.

Huffman coding guarantees this will never happen because all characters are located at the leaf nodes—the path from the root to any leaf node can never be a prefix of another path. This property also makes decoding straightforward. Among all prefix codes, Huffman coding produces the shortest average code length.

Code Implementation

Here is an implementation in JavaScript:

function buildTree(freqMap) {
  const nodes = [...freqMap.entries()]
    .map(([char, freq]) => ({ char, freq, left: null, right: null }))

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq)
    const left = nodes.shift()
    const right = nodes.shift()
    nodes.push({
      char: null,
      freq: left.freq + right.freq,
      left,
      right,
    })
  }

  return nodes[0]
}

function buildCodeTable(node, prefix = '', table = {}) {
  if (node.char !== null) {
    table[node.char] = prefix || '0'
    return table
  }
  buildCodeTable(node.left, prefix + '0', table)
  buildCodeTable(node.right, prefix + '1', table)
  return table
}

buildTree repeatedly takes the two smallest nodes and merges them until only a single root node remains. buildCodeTable recursively traverses from the root, appending 0 for each step to the left and 1 for each step to the right.

The decoding process is just as intuitive—starting from the root node, traverse left upon reading 0, traverse right upon reading 1, output the corresponding character once a leaf node is reached, and then return to the root to continue:

function decode(encoded, root) {
  let result = ''
  let current = root

  for (const bit of encoded) {
    current = bit === '0' ? current.left : current.right
    if (current.char !== null) {
      result += current.char
      current = root
    }
  }

  return result
}

Interactive Demo: Huffman Encoder

Try entering any text below to see the Huffman coding results in real time. You can hover your mouse over a character in the code table to highlight its corresponding bits in the encoded output.

載入霍夫曼編碼器中…

Try entering different texts and observe a few interesting phenomena:

If you enter text with only a single character (e.g., aaaa), each character requires only 1 bit.
If all characters have identical frequencies, the code lengths tend toward a fixed length.
The greater the variance in character frequencies, the higher the compression ratio.

Limitations of Huffman Coding

Huffman coding is not a silver bullet, and it comes with several practical limitations:

Every symbol requires at least 1 bit. Even if the theoretically optimal code length for a character is 0.3 bits, Huffman coding can only assign an integer number of bits—at least 1 bit. This causes efficiency loss under certain skewed distributions.

Frequencies must be known in advance. Before encoding, you must either scan the data once to count frequencies or use a predefined frequency table. In JPEG, the standard defines default Huffman tables while also allowing custom ones.

The code table must be transmitted alongside the data. The decoder needs the code table to reconstruct the original data, so the table itself takes up space. For small inputs, this code table overhead might completely offset the benefits of compression.

Where Is Huffman Coding Used?

JPEG — Huffman coding is the final step in image compression.
DEFLATE (ZIP, gzip) — Combines LZ77 and Huffman coding.
MP3 — Huffman coding is also used in audio compression.
HTTP/2 — HPACK header compression uses static Huffman tables.

Closing Thoughts

Huffman coding is one of those algorithms that feels completely obvious once you understand it. Its core concept is exceptionally simple—represent common things with short codes, and rare things with long ones. Yet turning this intuition into a general algorithm took remarkable ingenuity.

More than seventy years later, this algorithm remains alive and well in the file formats we use every day.

I wonder what these pioneers could have achieved with AI assistance by their side?

Categories

Pages

Side Projects