Huffman code
Fixed-length code
Saved
Entropy

Symbol Count Code Bits Bits in all

More information about Huffman coding

Huffman coding builder

Why should a common letter like e take as many bits as a rare one like z? Huffman coding gives frequent symbols short codes and rare ones long codes, and does it in the best possible way. Type a text or pick an example and build its Huffman tree one step at a time: the two lightest trees join under a new node, again and again, until one tree is left. Then every path from the top spells out a code, and you can follow each symbol through the encoded bits. Type a text or pick an example. Every symbol starts as a leaf with its count. Step through the build: each step joins the two lightest trees under a new node with their sum, until one tree is left. Then the path from the top to a leaf gives its code, 0 for left and 1 for right. Click a leaf, a row or a piece of the bits to follow one symbol, and compare the total with a fixed-length code and with the entropy.

How it works

  1. Type or paste a text, or choose an example such as ABRACADABRA or MISSISSIPPI RIVER.
  2. Step through the build with Next step, or press Play: each step joins the two lightest trees under a node with their sum.
  3. When the tree is complete, click a leaf, a row of the table or a piece of the bits to follow one symbol, and compare the totals in the tiles.

How the tree is built

Count how often each symbol occurs and make each one a tree of a single leaf, weighted by its count. Then repeat one simple step: take the two trees with the smallest weights and hang them under a new node whose weight is their sum. Every step leaves one tree fewer, so after n − 1 steps for n symbols a single tree remains. The rare symbols were joined first and sit deep down; the common ones were joined late and sit near the top.

Reading the codes

Walk down from the top: a step to the left adds a 0, a step to the right a 1. The path to a leaf is that symbol's code. Because symbols only sit at the leaves, no code is the beginning of another, so a string of bits can be decoded without any separators: follow the bits down the tree, and whenever you reach a leaf, write its symbol and start again at the top. For ABRACADABRA, Huffman needs 23 bits, against 33 for a fixed code of 3 bits per letter.

Frequently asked questions

Why is the Huffman code the best possible?

Among all codes that give each symbol its own string of whole bits, none has a shorter total for the given counts. The proof follows the construction: in an optimal code the two rarest symbols can always be made siblings at the deepest level, and joining them leaves a smaller problem of the same kind. The total number of bits equals the sum of the weights of all the inner nodes of the tree.

What is a prefix code?

A code in which no code word is the beginning of another one, such as 0, 10, 110 and 111. That property lets a decoder read a stream of bits without separators, because it always knows where a code word ends. Every Huffman code is a prefix code: the symbols sit only at the leaves of the tree.

Is the Huffman tree unique?

Not quite: when two trees have the same weight, either may be taken first, and left and right can be swapped. Different choices give different codes, but always the same total number of bits. The builder always breaks ties the same way, so a text always gives the same tree.

How close does Huffman get to the entropy?

The average code length is at least the entropy and less than one bit above it. It equals the entropy when every probability is a power of one half, such as the halving counts example. Arithmetic coding and modern range coders avoid the whole-bit limit and come even closer.

Is my text sent anywhere?

No. The tree and the codes are computed in your browser, and your text stays in this browser's local storage.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor