Skip to content
A Method for the Construction of Minimum-Redundancy Codes 4 min

David A. Huffman · Proceedings of the IRE 1952

A Method for the Construction of Minimum-Redundancy Codes

Huffman's 1952 paper: give common symbols short codes and rare ones long codes. Build a code tree for your own text, one merge at a time.

Read the original paper

Algorithms · White Belt · Pro · 4 min read

A Method for the Construction of Minimum-Redundancy Codes

Every file you save and every page you load is a long run of bits. Most of them carry less information than they take up. In 1952 David Huffman showed a simple way to write messages in the fewest possible bits, using nothing but how often each symbol appears. His method is still inside the compression of ZIP and PNG files and of JPEG images.

The idea fits in one sentence. Give the symbols that appear often a short code, and the rare ones a long code. Morse code did the same thing by hand: a common letter such as E is a single dot. The hard part is doing it perfectly, and doing it so a receiver can read the bits back without any gaps between letters.

Huffman coding builds the best possible set of prefix codes for a set of symbols. Repeatedly join the two least common symbols into one, until a single tree remains. Read each symbol's code off the path from the top. No code is the beginning of another, so the bits can be decoded without separators.

The problem: shorter on average

Suppose a message uses only six letters. A fixed code spends the same number of bits on every letter. Six letters need 3 bits each, because 2 bits give only four combinations. That is simple, but it wastes bits when one letter is far more common than the rest.

Frequent letters get short codes and rare letters get long ones. The A that appears 45 times costs one bit. The F that appears 5 times costs four. The total is smaller than giving every letter three bits.

Huffman's paper calls a code with the smallest average length a minimum-redundancy code. Redundancy here means bits that carry no new information. The goal is a code whose average number of bits per symbol is as small as it can be.

Think of packing for a trip. The things you grab every day go in the outer pocket where they are quick to reach. Things you almost never need go deep in the bag. You spend little effort on the common case and more on the rare one.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

3 more sections, 1 more diagram and 2 interactive elements to play with

  • The rule that makes decoding possible
  • Building the tree, two pieces at a time
  • Where it lives today

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.