Huffman Encoding Visualizer

Enter text to see how Huffman coding assigns shorter codes to frequent characters.

Worked example — Huffman Encoding Visualizer

Original (8-bit ASCII)	88
Huffman-encoded bits	32
Savings	63.6%
'l' (3×)	10
'␣' (1×)	000
'w' (1×)	001
'r' (1×)	010
'd' (1×)	011

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Huffman can never spend less than one bit 🖖

Huffman codes are optimal, but only within a rule that costs them: every symbol must get a whole number of bits. Shannon’s limit says a symbol appearing 90% of the time is worth about 0.15 bits, and a source that is 90% one character and 10% another carries just 0.469 bits of entropy per symbol. Huffman has no way to write a fraction of a bit, so it assigns 1 and 1 — spending more than twice what the information is worth. That gap is why heavily skewed data compresses disappointingly here, and why arithmetic and range coders exist: they encode the whole message as one number and are free to spend fractional bits. Huffman is optimal among whole-bit codes, which is a narrower claim than optimal.

Built by always merging the rarest 🖖

The tree grows from the bottom up: list every character by how often it appears, then repeatedly glue the two least-frequent items into a small subtree and treat it as one bundle. Repeat until a single tree remains, then read each code by walking down from the top — left is 0, right is 1. This "greedy" habit of always combining the two smallest looks short-sighted, yet it provably produces the shortest possible codes.

A term paper that beat the professor 🖖

David Huffman devised this in 1951 as an MIT graduate student, when professor Robert Fano offered the class a choice between a final exam and a paper on finding the most efficient code. Fano and Claude Shannon had already tried, building their trees top-down. Huffman almost gave up, then realised building bottom-up — merging the rarest symbols first — was optimal, beating his own teacher's method.

HUFFMAN CODING — WHEN DOES IT HELP, AND HOW CLOSE TO OPTIMAL IS IT?

Which Compression Case Are You In?

Huffman gives frequent symbols short codes and rare ones long codes, and it is provably the best you can do while every symbol gets a whole number of bits. What it saves depends entirely on how uneven the frequencies are. Perfectly even, and there is nothing to exploit; wildly uneven, and it wins big — until the point where whole-bit codes become the limit rather than the frequencies.

Lopsided frequencies — exactly what the method is for p_i ↑ ⇒ ℓ_i ↓

Every symbol equally common — nothing to exploit p_i = 1/n ⇒ ℓ = log₂n

Ordinary text — within a bit of the theoretical floor H ≤ ℓ < H + 1

One symbol only — the floor Huffman cannot go below n = 1 ⇒ ℓ = 1

Lopsided frequencies — exactly what the method is for

What you know: A few symbols dominate the text. Those get the shortest codes, and the total falls well below a fixed-length encoding.

Cost: p_i ↑ ⇒ ℓ_i ↓

Worked example: "mississippi": 11 characters, 4 distinct symbols, coded in 21 bits against 88 for 8-bit characters — a saving of 76.1%

Open this case: mississippi

Lopsided frequencies — exactly what the method is for. The two most frequent symbols get the shortest codes, and the total drops accordingly. A few symbols dominate the text. Those get the shortest codes, and the total falls well below a fixed-length encoding. — The two most frequent symbols get the shortest codes, and the total drops accordingly.

Every symbol equally common — nothing to exploit

What you know: With a flat distribution there are no frequent symbols to reward. Huffman degenerates into something very close to a fixed-length code.

Cost: p_i = 1/n ⇒ ℓ = log₂n

Worked example: "abcdef": 6 distinct symbols each appearing once, coded in 16 bits. A plain 3-bit code for six symbols would take 18.

Open this case: uniform

A flat distribution gives a nearly uniform tree, and the codes are all much the same length.

Ordinary text — within a bit of the theoretical floor

What you know: A realistic mix of repeated and one-off symbols. This is the everyday case, and the result sits just above the entropy bound.

Cost: H ≤ ℓ < H + 1

Worked example: "hello world": 11 characters over 8 distinct symbols, coded in 32 bits against 88 — 63.6% saved, with the entropy floor at 31.3 bits

Open this case: hello world

Ordinary text — within a bit of the theoretical floor. A mixed distribution gives a lopsided tree, and the total lands just above the entropy bound. A realistic mix of repeated and one-off symbols. This is the everyday case, and the result sits just above the entropy bound. — A mixed distribution gives a lopsided tree, and the total lands just above the entropy bound.

One symbol only — the floor Huffman cannot go below

What you know: A text with no variety at all. Its entropy is zero, but Huffman must still emit at least one bit per symbol, because there is no shorter code than a single bit.

Cost: n = 1 ⇒ ℓ = 1

Worked example: "aaaaaaaaaa": 10 characters, one distinct symbol, coded in 10 bits. The entropy of the text is 0 bits.

Open this case: single char

One symbol only — the floor Huffman cannot go below. One symbol, one bit each: no distribution to exploit and no shorter code available. A text with no variety at all. Its entropy is zero, but Huffman must still emit at least one bit per symbol, because there is no shorter code than a single bit. — One symbol, one bit each: no distribution to exploit and no shorter code available.

References (1)

Insight block 3 — the term paper itself: D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9), 1098–1101, 1952.

Problem solved in full

The saving from encoding "hello world" with Huffman coding 5 steps
Encode "hello world" with Huffman coding. Find the saving — then find the limit that says how much better any code could possibly do.
1. Fixed-width ASCII spends the same eight bits on every character, however often it appears. That is the waste Huffman removes: frequent symbols get short codes, rare ones get long codes.
  
  $"hello world" : 11 chars \times 8 bits = 88 bits$
2. Count the symbols first, because the code is built from the counts. Only 'l' and 'o' repeat; the other six characters appear once each.
  
  $ℓ = 3, o = 2, others = 1 each (8 distinct symbols)$
3. Shannon entropy is the average information per symbol, and it is a hard floor: no uniquely decodable code can beat it on average. Three distinct probabilities do all the work: 3/11 for 'l', 2/11 for 'o', and 1/11 for each of the other six, so the sum is (3/11)(1.8745) + (2/11)(2.4594) + (6/11)(3.4594).
  
  $H = - i \sum p_{i} lo g_{2} p_{i} = 2.845 bits/symbol$
4. Multiply by the string length for the floor in bits. Huffman must come out at or above this, and it cannot generally reach it, because code lengths are whole numbers of bits while the entropy is not.
  
  $11 \times 2.845 = 31.3 bits (entropy floor) \leq 32 (Huffman)$
5. Build the tree for the actual length. Huffman merges the two smallest weights each time: 1+1, 1+1, 1+1, then 2+2, then 2+2, then 3+4, then 4+7. Every merge adds one bit to every symbol beneath it, so the encoded length is the sum of the merged weights, 2+2+2+4+4+7+11 = 32, which is what the visualiser prints.
  
  $Huffman = 32 bits ⟹ saving = 1 - \frac{32}{88} = 63.6%$
Answer

88 bits down to 32 — a 63.6% saving. The entropy floor for these frequencies is 31.3 bits, and Huffman produced 32 — 0.7 bits above optimal, spent on rounding eight code lengths up to whole bits. The guarantee is the sandwich H ≤ average length < H + 1: Huffman is never more than one bit per symbol above optimal. That single-bit gap is exactly why arithmetic coding exists.

$88 \to 32 bits (63.6%) H \leq \overset{ˉ}{ℓ} < H + 1$

Learning path

Compression by hand

Leads to LZ77 codes of unequal length, with the short ones spent on the frequent symbols.

By the 42Math team · Updated 2026-07-27

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

hello world - 88 bits of ASCII down to 32, a 63.6% saving - and only 0.7 bits above the entropy floor of 31.3.
mississippi - Four distinct characters in eleven: 88 bits down to 21, with s earning a single-bit code. It is also the widest gap here from the entropy floor, 0.95 bits.
uniform - Six symbols, each appearing once, so there is nothing to exploit - and it still comes to 16 bits against a fixed code's 18, because six symbols do not fill three bits.
single char - Ten identical characters carry exactly 0 bits of information, and Huffman still spends 10 of them: one per symbol, because it cannot write less than one.