Introduction
Huffman coding is the optimal prefix-free code for a known symbol distribution. David Huffman described it in his 1952 MIT term paper, and it beat out Fano-Shannon coding so decisively that it became the default textbook answer to "how do we compress symbols with variable-length codes." Every DEFLATE stream (gzip, PNG, HTTP gzip encoding) uses Huffman codes as the final entropy stage. This huffman coding visualizer builds the code from your input in real time, shows the merge tree, the per-symbol code table, and the encoded bitstream, then decodes it back to prove the round trip is lossless. No data leaves your browser.
What this tool does
- Builds a Huffman tree from input text by counting symbol frequencies and merging the two least-frequent nodes until one remains.
- Generates prefix-free binary codes for each symbol by walking the tree (0 for left, 1 for right).
- Shows the tree view with merge order and frequencies, the code table view with per-symbol codes, and the bitstream view with the encoded output and round-trip decode.
- Reports original size in bits (assuming 8-bit fixed encoding), encoded size in bits, and the percentage savings.
- Handles edge cases including single-symbol input (assigned code '0') and Unicode input.
- Updates in real time as you type. All processing happens client-side.
How this tool works
Type or paste text into the input field. The tool counts how often each character appears, builds a priority queue of single-node trees keyed by frequency, and repeatedly merges the two smallest trees into a parent whose frequency is the sum. When one tree remains, it walks from the root to each leaf, appending 0 for a left branch and 1 for a right branch, to produce the code for that symbol.
The Code Table view lists each symbol with its frequency, code length in bits, and the binary code. The Tree view draws the merge tree as an ASCII outline so you can see which symbols were paired first. The Bitstream view shows the encoded output as a string of 0s and 1s and the decoded round trip, which always matches the input exactly. The savings percentage compares the encoded bit count to the original assuming 8 bits per character.
How Huffman coding works
Huffman coding is a greedy algorithm that produces an optimal prefix-free code for a given symbol distribution. "Prefix-free" means no code is a prefix of another, so the decoder can read the bitstream left to right and know when a code ends without needing separators.
The algorithm: count symbol frequencies, put each symbol in a leaf node, then repeatedly extract the two nodes with the smallest frequencies and merge them into a parent node whose frequency is the sum. The result is a binary tree where each leaf is a symbol and each internal node represents a merge. Walking from the root to a leaf gives that symbol's code: 0 for left, 1 for right.
Huffman proved in his 1952 paper "A Method for the Construction of Minimum-Redundancy Codes" that this greedy merge produces a code with minimum expected code length for the given distribution. The expected length is bounded below by the Shannon entropy H = -sum p_i log2 p_i, and Huffman coding gets within one bit per symbol of that bound.
DEFLATE (RFC 1951) uses Huffman codes as its final stage after LZ77. PNG uses Huffman-coded DEFLATE. JPEG uses Huffman coding for the entropy coding of DCT coefficients. The Huffman construction is also the basis for canonical Huffman codes used in zlib, which constrain the code lengths to a canonical form so the decoder only needs the lengths, not the full tree.
How to use this tool
- Type or paste text into the input field. The tree builds instantly.
- Switch between Code Table, Tree, and Bitstream views using the buttons in the settings panel.
- The Code Table view shows each symbol, its frequency, code length, and binary code.
- The Tree view shows the merge tree as an ASCII outline with frequencies at each node.
- The Bitstream view shows the encoded output and the decoded round trip, which always matches the input.
- Read the savings percentage to see how much smaller the Huffman encoding is versus 8-bit fixed encoding.
Real-world examples
Compressing English text
Paste a paragraph of English prose. The letter 'e' (most common in English) gets a short code like '101' while 'z' gets a long code like '110110'. The savings percentage typically lands around 40-45% versus 8-bit ASCII because English text has roughly 4.5 bits of entropy per character. This is the same reason gzip's Huffman stage shaves bytes off after LZ77.
Visualizing the merge order
A student learning Huffman coding pastes "abracadabra" and switches to the Tree view. The tree shows that 'r' and 'd' (the least frequent symbols) were merged first, then 'b' and 'c', then those merged with 'a'. The code table confirms 'a' (frequency 5) has the shortest code and 'd' (frequency 1) has the longest. This makes the greedy merge concrete in a way pseudocode alone does not.
Verifying lossless round trip
A developer implementing a Huffman encoder for a class assignment wants to confirm the decode step works. They paste a test string, switch to the Bitstream view, and confirm the decoded output matches the input character for character. Because Huffman codes are prefix-free, the decoder can read the bitstream without separators and recover the original text exactly.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Huffman coding | O(n log n) per block, prefix-free | DEFLATE, PNG, JPEG entropy stage |
| Arithmetic coding | O(n), fractional bits per symbol | JPEG2000, higher ratio than Huffman |
| Asymmetric Numeral Systems | O(n), faster than arithmetic | zstd, Facebook, Apple LSE |
| Run-Length Encoding | O(n), trivial | Post-BWT in bzip2, fax machines |
Limitations or considerations
Huffman coding assigns an integer number of bits per symbol, so it cannot achieve fractional-bit precision. For skewed distributions where one symbol dominates, arithmetic coding and ANS do better because they can encode a symbol in less than one bit on average. Huffman coding is also optimal only for the exact symbol distribution of the input block; adaptive Huffman (FGK algorithm) handles streaming input but is not implemented here. The savings percentage assumes 8-bit fixed encoding as the baseline, which is fair for ASCII text but not for inputs that are already compressed or binary.
Frequently asked questions
Is Huffman coding lossless?
Yes. The codes are prefix-free, so the decoder can read the bitstream left to right and recover the original symbols exactly. The Bitstream view in this tool shows the round trip: encoded bits decode back to the original input character for character.
Why is Huffman coding called prefix-free?
No code is a prefix of any other code. That property lets the decoder know when a code ends without needing a separator. The tree construction guarantees prefix-freedom because every code ends at a leaf, and no leaf is an ancestor of another leaf.
How does Huffman coding relate to gzip and PNG?
Both use DEFLATE (RFC 1951), which is LZ77 followed by Huffman coding. The LZ77 stage finds repeated substrings and replaces them with back-references, and the Huffman stage encodes the resulting symbol stream with variable-length codes. This tool implements only the Huffman stage; the Gzip and Deflate tools implement the full pipeline.
Can Huffman coding make the output larger than the input?
Yes, for very short or very uniform input. If every symbol appears once, every code is the same length, and the overhead of storing the code table can exceed the savings. For a single symbol the code is '0', which is one bit per symbol, but you still need to store the table. Real compressors detect incompressible blocks and store them verbatim.
Conclusion
Huffman coding is the optimal prefix-free code for a known symbol distribution and the entropy stage of DEFLATE, PNG, and JPEG. This visualizer builds the tree, the code table, and the encoded bitstream in real time, and decodes the round trip to prove the transform is lossless. For the full DEFLATE pipeline, try the Gzip or Deflate tools. For a different entropy coder, the Brotli tool uses a modern context-modeled variant.