StringMash.com

Huffman coding

Type a text and watch it get its own shortest code, with the tree drawn.

Conversion
11 characters
Updates as you type
Huffman code0 110 111 0 100 0 101 0 110 111 0
Huffman bits23
8-bit ASCII88 (74% saved)
Bits per character2.091 (entropy 2.040)
Code tableA=0 C=100 D=101 B=110 R=111

The tree is drawn below

Show the steps
01001101A5C1D12B2R24611
  1. Counted 5 different characters in 11: A 5, B 2, C 1, D 1, R 2.
  2. Merge "C" 1 and "D" 1 into a node of 2.
  3. Merge "B" 2 and "R" 2 into a node of 4.
  4. Merge (2) 2 and (4) 4 into a node of 6.
  5. Merge "A" 5 and (6) 6 into a node of 11.
  6. Reading the tree from the top, every left branch is 0 and every right branch is 1. A common character ends up near the top with a short code, and no code is the start of another, so the bits decode without separators.
  7. The average is 2.091 bits per character, against a theoretical minimum (the Shannon entropy) of 2.040.

Using it

Type or paste any text, up to 5,000 characters. The code for each character appears in the output, the rows give the total bits, the saving against 8-bit ASCII and the code table, and the tree is drawn below with every left branch as 0 and every right branch as 1. Text with accents or emoji isn't ASCII, so it's compared with its size in UTF-8 instead. The steps list every merge in order, so you can follow along on paper.

To decode, swap the boxes and give the code table, a | or a blank line, then the bits: a=0 b=10 c=11 | 0100110. The Code table row is already in the right form to paste.

How the tree is built

Count how often each character appears. Each one starts as a leaf with that count. Take the two lightest and join them under a new node whose weight is their total, then put that node back with the rest. Repeat until only one node is left: that's the root.

Each character's code is the path from the root to its leaf, 0 for left and 1 for right. Characters that appear often were merged late and sit near the top, so their codes are short; rare ones sit deep down with long codes. Because every character is a leaf, no code is the start of another, which is why the bits can be read back without any separators.

Ties, and why your answer may differ

When two nodes weigh the same, either can be taken first, so two correct Huffman trees for the same text can look different and give different codes. They always give the same total number of bits. This page breaks ties the same way every time: the node made earlier goes first, and single characters are made in alphabetical order, so a class working from the same rule gets the same tree.

Where it's used

David Huffman worked out the method as a student at MIT and published it in 1952, and it's still inside everyday formats: ZIP files and gzip compression use it as one stage of DEFLATE, and JPEG images and MP3 audio use the same kind of prefix code. On its own it's a teaching favorite, because the whole method fits on one page and the tree can be drawn by hand.

In the classroom

Ages 14 and up, about 30 minutes. Each pupil counts the letters in their own name or a short sentence, builds the tree by hand by joining the two smallest counts each time, and reads off the codes. The tool checks the tree and the total bits.

Take it further: compare the bits used against 8 per letter, and ask which kinds of text compress well and which don't.

Questions

How many bits does ABRACADABRA take?

23 with Huffman coding, against 88 in 8-bit ASCII.

Is Huffman coding the best possible compression?

It's the best code that gives each character its own fixed pattern of bits. Methods that code groups of characters, or use fractions of a bit, can do better.

Why is my tree different from my textbook's?

Ties can be broken either way. The total bits will match even when the codes don't.

Sources

Added . Last updated and reviewed . What's new