Huffman Coding Calculator

A Huffman code is optimal among prefix codes for a known symbol distribution. It is not the smallest possible encoding of your data, and it is not unique. Both halves of that sentence matter, and the panels above are built around them.

The idea is to stop spending the same number of bits on every symbol. A fixed-width encoding gives MISSISSIPPI the same allowance for the single M as for the four Is; a Huffman code gives the common symbols short codewords and pays for it with longer ones on the rare symbols, which is a win exactly when the distribution is uneven. Here that is 21 bits against 22 for a two-bit fixed code over the same four symbols.

It is the opposite move to a Hamming code, which adds redundancy so that errors can be repaired. A real system compresses first and adds error correction afterwards, in that order, because correcting redundancy you are about to throw away is wasted work.

Every symbol sits at a leaf of the tree, so no codeword is a prefix of any other. That is what makes a variable-length code decodable without delimiters: a decoder reads bits one at a time, walks down from the root, and emits a symbol the moment it lands on a leaf — then starts again at the root.

With I = 0, M = 100, P = 101, S = 11, the string MISSISSIPPI encodes to 100011110111101011010. Walk it: 100 reaches M; the next 0 is already a leaf, so I; 11 gives S, and so on to the end, with no separator anywhere and no ambiguity about where one codeword stops.

A code that is notprefix-free can still be decodable, but only with lookahead — and if one codeword is a prefix of another with nothing to distinguish them, the stream is genuinely ambiguous. Huffman’s construction cannot produce that case, because symbols are only ever placed at leaves.

Place every symbol in a priority queue keyed by weight; repeatedly remove the two lightest nodes and insert a new node whose weight is their sum and whose children they are; stop when one node remains. That node is the root.

For MISSISSIPPI the counts are I 4, M 1, P 2, S 4, and three merges finish the tree: M(1) with P(2) makes a node of 3; that node with S(4) makes 7; I(4) with 7 makes the root at 11. Every merge is listed above with the weights it saw, so the sequence can be checked step by step rather than taken on trust.

The reason it is optimal is an exchange argument: in some optimal tree the two least frequent symbols are siblings at the deepest level, so merging them first loses nothing, and the same argument applies to the smaller problem that remains. The total cost is the sum of every internal node’s weight, which is why the merge order and the cost are the same fact seen twice.

When two nodes weigh the same, the algorithm has a genuine choice, and different choices give different trees with identical cost. That is the single most common reason a student decides a Huffman tool is broken. So the rule is stated rather than left implicit:

Moffat (2019) §2.2: symbols are numbered 0…m−1 in ascending code-point order, and the heap is keyed on the tuple (weight, isInternal ? 1 : 0, tieRank) with tieRank = −symbolIndex for leaves and the creation sequence number for internal nodes. So: on a tie between leaves the higher-numbered symbol is preferred; on a tie between a leaf and an internal node the leaf is preferred; on a tie between internal nodes the one formed earlier is preferred. The first node popped becomes the 0 (left) child.

Of the 3 merges on MISSISSIPPI, the merge log above marks 1 step as decided by this rule rather than by the weights: I and S both weigh 4 at that point, and the leaf-order clause settles it. If your textbook shows different bit patterns for the same weights, compare the lengths before assuming one of you is wrong — they are probably identical, and both codes are then equally correct.

Array.prototype.sort has been stable since ES2019, but a binary heap is not. The tuple key is mandatory, not an optimisation — without it the same input gives different codes on different runs. That is why the key carries the creation sequence number and the symbol index, and not merely the weight.

Walk from the root to a leaf and write 0 for every step to the left child and 1for every step to the right; the string you have written is that symbol’s codeword, and its length is the leaf’s depth. The choice of which child is 0 is a convention, not a result: swapping the two children of any node flips one bit in every codeword below it and changes nothing about the cost.

With n leaves the tree has n − 1 internal nodes, each of which can be flipped independently, so at least 2^(n−1) distinct labellings of the same shape exist. All of them are correct Huffman codes.

For any binary prefix code the codeword lengths satisfy Σ 2^(−ℓᵢ) ≤ 1, and a set of lengths satisfying that inequality can always be realised as a prefix code. It is a statement about the lengths alone; the bit patterns never enter it.

A sum of exactly 1 means the code is complete: every leaf of the binary tree is used and no bit pattern is wasted. A sum below 1 means the code is prefix-free but incomplete — some of the code space is unreachable, which happens for a one-symbol alphabet, where this page emits the one-bit codeword 0 and the sum is 1/2. A sum above 1 is impossible for a prefix code; if you compute one, the lengths you have are not the lengths of any prefix code.

Once the lengths are known the bit patterns can be assigned by a rule instead of by the tree. RFC 1951 §3.2.2 states it in two clauses: “All codes of a given bit length have lexicographically consecutive values, in the same order as the symbols they represent” and “Shorter codes lexicographically precede longer codes.” Sort by length and then by symbol, start at 0, add 1 per codeword and shift left by one whenever the length increases.

For MISSISSIPPI the tree gives I = 0, M = 100, P = 101, S = 11 and the canonical rule gives I = 0, S = 10, M = 110, P = 111. Both encode the message in 21 bits — 100011110111101011010 against 110010100101001111110. The codes change; the lengths — and therefore the total size — do not.

The payoff is that a decoder no longer needs the tree. Send the code lengthsand the canonical rule rebuilds the identical codebook, which is why every deployed format below transmits lengths. Run the RFC’s own printed example through this page’s implementation — lengths A 3, B 3, C 3, D 3, E 3, F 2, G 4, H 4 — and it reproduces the RFC’s answer exactly: F = 00, A = 010, B = 011, C = 100, D = 101, E = 110, G = 1110, H = 1111.

Every optimal code for these weights costs exactly 21 bits. That is the part that is unique, and it is the only part this page claims. The tree, the bit patterns, and in some cases even the individual lengths are not.

For MISSISSIPPI the divergence is easy to name. This page produces I = 0, M = 100, P = 101, S = 11; many textbooks and most online tools produce the mirror assignment with S = 0 and I = 10, because they broke the weight-4 tie the other way. Both cost 21 bits and both are correct Huffman codes.

Sometimes the disagreement is deeper than the bit patterns: two distributions shipped as worked examples reach different length multisetsat equal cost. Moffat’s rule has the useful side effect of minimising the longest codeword, which is the choice this page makes and the better one to teach, because a shorter maximum length is what a table-driven decoder actually cares about.

Take the weights 8, 7, 6, 5, 4, 3. Huffman merges 3 + 4 = 7, then 5 + 6 = 11, then 7 + 7 = 14, then 8 + 11 = 19, then 14 + 19 = 33, for a cost of 84 bits and the length vector (2, 2, 3, 3, 3, 3). The canonical re-assignment of those lengths is 00, 01, 100, 101, 110, 111, and it costs the same 84 bits.

But the treethat assignment describes places the two heaviest symbols, 8 and 7, under a shared parent of weight 15 — and Huffman never forms that node, because it always merges the two lightest first and 3 + 4 = 7 comes long before any pair involving 8. So the canonical code here is a minimum-redundancy code that Huffman’s algorithm cannot construct, even though its lengths are ones Huffman does reach. “Minimum-redundancy code” is a strictly larger set than “Huffman code”.

Three numbers answer that, and all three are above. A fixed-length code over m symbols spends ⌈log₂ m⌉ bits each; the Huffman code spends Σ f·ℓ; and no code of any kind can go below the entropy floor N × H. For MISSISSIPPI that is 22 bits fixed, 21 bits Huffman, and a floor of 1.8231 bits per symbol — so the code is within about a tenth of a bit per symbol of the theoretical minimum, and the entropy floor explains why that gap cannot be closed by a better tree.

The gap can be much worse. With weights 96, 1, 1, 1, 1 the entropy is 0.3223 bits per symbol but the Huffman code averages 1.08 — 235% above the floor, and nothing is wrong with the code. A prefix code cannot spend less than one whole bit on a symbol, and this source wants to spend about 0.06 bits on its dominant symbol. Arithmetic coding and range coding do spend fractional bits, at the cost of no longer being a table lookup. The loss is worst exactly when one symbol dominates, which is where a naive reading of “Huffman is optimal” misleads.

The other end is just as instructive: over a uniform alphabet Huffman gives every symbol the same length and saves nothing, and the entropy of that distribution is exactly log₂ m, which says the same thing in one number.

All three of the formats below transmit canonical codes, for the reason in the section above: lengths are enough to rebuild the codebook, and lengths are far cheaper to send than a tree.

• Left edges are 0 and right edges are 1; a codeword is read from the root to the leaf.
• The node popped first becomes the left (0) child; the node popped second becomes the right (1) child.
• Symbols are numbered in ascending Unicode code-point order, and the tie-break above is stated in terms of that numbering.
• Weights may be counts or probabilities and are never normalised before the merge. Only the reported p column is normalised.
• A one-symbol alphabet is given the one-bit code 0, so its Kraft sum is 1/2 rather than 1.
• ℓ is a codeword length in bits and L = Σ pᵢℓᵢ is the average codeword length; H is the Shannon entropy of the same distribution, in bits per symbol.
• Whitespace is counted as a symbol unless the switch above is turned off, because that choice changes every number on the page.

• D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes” (opens in a new tab), Proceedings of the IRE 40(9):1098–1101, September 1952 — the algorithm and its optimality proof.
• C. E. Shannon, “A Mathematical Theory of Communication” (opens in a new tab), Bell System Technical Journal 27:379–423 (July 1948) and 623–656 (October 1948) — entropy, and the bound the cost panel compares against.
• A. Moffat, “Huffman Coding” (opens in a new tab), ACM Computing Surveys 52(4), Article 85, August 2019 — §2.2 for the tie-break rule used here, §2.6 for canonical codes and the minimum-redundancy-but-not-Huffman result.
• P. Deutsch, “DEFLATE Compressed Data Format Specification version 1.3” (opens in a new tab), RFC 1951, May 1996 — §3.2.2, the canonical construction quoted above and its worked example.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press — the six-symbol instance shipped as a worked example, so the 224-bit result can be checked against the book.