How to use the huffman coding calculator
- Type or paste the text to encode. Every character counts, including spaces and line breaks.
- Read the encoded size in bits, the space saved against ordinary UTF-8 text and the average code length.
- Study the code table, with each symbol's count, its code and the bits it uses in total.
- Follow the steps table to see which two nodes were joined at each step of building the tree.
Formula
join the two lightest nodes until one is left; the first taken gets 0, the second 1
total bits = sum over symbols of count x code length
entropy = - sum of p x log2 p, with p = count / length
The average code length is always at least the entropy and less than the entropy plus one bit. Equal weights are taken in the order the nodes were made, so the same text always gives the same codes.
abracadabra
The 11 letters have counts a 5, b 2, r 2, c 1 and d 1. The tree gives a = 0, c = 100, d = 101, b = 110 and r = 111, so the text needs 5 x 1 + 2 x 3 + 2 x 3 + 3 + 3 = 23 bits.
Plain UTF-8 text uses 11 x 8 = 88 bits, so the saving is 73.9%. The average code is 23 / 11 = 2.09 bits against an entropy of 2.04, which fits the rule that it falls within one bit above entropy.
Why frequent symbols get short codes
A code in which no code is the start of another can be read without separators. Among such codes, giving the shortest codes to the commonest symbols produces the shortest total, and Huffman's method does that exactly. The saving is greatest when a few symbols dominate, and nil when all symbols are equally common.
A real file would also have to store the code table, and for a very short text that can cost more than the saving. A text with only one kind of symbol is given the code 0 so each symbol still takes a bit. For a method that finds repeated phrases instead, see the LZW Compression Stepper; to count bytes in other encodings use the Text Byte Size Calculator.
Several correct answers
Different choices at ties give different but equally short sets of codes. The total number of bits is the same for all of them. The page fixes one rule so that the output can be checked and repeated.
Assumptions and limits
- A symbol is one Unicode character, and the comparison size is the UTF-8 byte length x 8.
- The code table and tree are not counted in the encoded size.
- Up to 5,000 characters are accepted.
- Only the first 40 merge steps and the first 240 encoded bits are displayed; Copy gives all of the bits.
- Decoding the bits with the table returns the original text, which the tests confirm.
Frequently asked questions
Why is 23 bits the smallest possible for abracadabra?
No code in which no code starts another can do better for these counts. Huffman's method is optimal among such codes.
Can the codes differ from another Huffman tool's?
Yes, when counts tie. The total size will be the same, but the 0 and 1 branches and the order of equal items may differ.
What is entropy here?
It is the least average number of bits per symbol any code could achieve if symbols are coded one at a time. Huffman comes within one bit of it.
Why is one symbol given a one bit code?
A code of zero bits would leave nothing to read. Using 0 keeps the length countable.