Huffman Coding in Python: Simple Implementation Tutorial

Think data compression is only for experts?
Think again.
This step-by-step guide walks you through building a full Huffman encoder and decoder in Python so you can compress text into a shorter bitstring and reconstruct the original exactly.
You’ll build the frequency table, define a Node class, use heapq to construct the tree, generate binary codes, encode the text, serialize the mapping, and decode the bitstream.
No external libraries—just Python’s standard modules and clear, testable functions.
By the end you’ll have working code and small checkpoints to confirm each step.

Complete Step-by-Step Workflow to Implement Huffman Coding in Python

You’ll walk through a full encoder and decoder that takes plain text, compresses it into a shorter bitstring, and reconstructs the original message exactly. This tutorial builds a complete, working Huffman implementation from scratch, showing you every data structure, every function, and the exact order in which to wire them together.

The core workflow moves through seven checkpoints: build a frequency table to count how often each character appears, define a Node class that holds characters and frequencies for the tree, use a min-heap to construct the Huffman tree by merging the two least-frequent nodes until one root remains, generate binary codes by traversing the tree (left edges get ‘0’, right edges get ‘1’), encode your input text by replacing each character with its code, store or transmit the code dictionary so the decoder knows the rules, and decode the bitstring by walking the tree until you hit a leaf for each symbol. Each checkpoint outputs something you can inspect, so you’ll know when you’ve got it right.

You’ll need Python’s heapq module for the priority queue, collections.Counter to build frequencies quickly, and a custom Node class with comparison support so the heap knows which nodes are smallest. No external libraries or complicated installs. Just standard library pieces you already have.

1. Build the frequency table using collections.Counter or a plain dictionary. Count how many times each unique character appears in your input text.
2. Define a Node class with four fields (char, freq, left, right) and implement __lt__ so nodes can be compared by frequency for heap operations.
3. Construct the Huffman tree by pushing all character nodes into a min-heap, then repeatedly popping the two smallest, merging them into a new internal node with frequency equal to the sum, and pushing the merged node back until only the root remains.
4. Generate binary codes by traversing the tree from the root, adding ‘0’ for every left branch and ‘1’ for every right branch, and storing each leaf’s final path as its code.
5. Encode the input text by replacing every character with its corresponding bitstring and concatenating them into one long encoded message.
6. Serialize the code dictionary or tree so the decoder can rebuild the same mapping. Without it, the decoder won’t know what ‘10110’ means.
7. Decode the bitstring by reading bits left to right, following tree branches (0 = left, 1 = right), emitting a character when you reach a leaf, then starting over at the root for the next symbol.

Understanding Huffman Coding Concepts Before Coding

Huffman coding is a greedy algorithm that assigns variable-length binary codes to characters. The most frequent symbols get the shortest codes. The least frequent get longer ones. The trick that makes it work is the prefix-free property: no code is the beginning of another code, which means you can decode a stream of bits without needing separators or markers. For example, if ‘a’ is 0 and ‘c’ is 10, you’ll never confuse the two because 0 doesn’t start 10.

The algorithm builds a binary tree by merging nodes. You start with one leaf node per unique character, each carrying its frequency count. Then you repeatedly pick the two smallest-frequency nodes, create a new internal node (no character, just the sum of the two frequencies), and attach the originals as left and right children. When only one node remains, that’s the root.

Leaves hold actual characters. Internal nodes just hold combined frequencies. Walking from the root to a leaf, you collect 0s and 1s along the edges, and that path becomes the character’s code. Because Huffman always merges the smallest pair, the final tree minimizes the total number of bits needed. It’s optimal among all prefix codes for those frequencies.

Building the Frequency Table in Python

A frequency table is a dictionary or Counter that maps each unique character to how many times it appears in your input. This table drives everything. Huffman uses these counts to decide which symbols deserve short codes and which get longer ones. If ‘a’ appears 100 times and ‘z’ appears once, ‘a’ will get a short code like 0 and ‘z’ might get something like 11110.

You can build the table manually with a loop and a plain dict. Or you can use collections.Counter(text) and get back a ready-made frequency map in one line. Counter is just a dict subclass that counts hashable items, so Counter("hello") returns {'h': 1, 'e': 1, 'l': 2, 'o': 1}. The function signature looks like build_frequency_table(text) → Counter, and the complexity is O(n) because you scan the input once.

Empty input strings should return an empty Counter. Handle that edge case early so later steps don’t break.

Unicode characters work fine with Counter. Don’t assume ASCII-only unless your spec requires it.

Case sensitivity matters. ‘A’ and ‘a’ are different symbols unless you normalize first.

Whitespace and punctuation count as characters too. Decide upfront whether to strip or keep them.

Zero-frequency symbols never appear in the table, which is correct. Only count what’s actually present.

Designing the Node Class for the Huffman Tree

The Node class is the building block for your tree. Each node stores char (the character, or None for internal nodes), freq (an integer count), left (a Node or None), and right (a Node or None). When you create a leaf node, you set char and freq and leave left and right as None. When you merge two nodes, you create an internal node with char=None, freq equal to the sum of the children’s frequencies, and left and right pointing to the merged pair.

You must implement __lt__(self, other) so the heap can compare nodes. The heap needs to know which node is “smaller.” In Huffman, smaller means lower frequency. A simple implementation is return self.freq < other.freq. Without this method, heapq will fail when it tries to order nodes. Internal nodes never carry a character, so always check node.char is None to tell them apart from leaves.

Constructing the Huffman Tree with heapq

You start by creating one leaf node per unique character and pushing it into a min-heap as a tuple (freq, node). Python’s heapq module gives you heappush and heappop to maintain the smallest element at the front. Once all leaves are in the heap, you enter a loop: while the heap has more than one item, pop the two smallest, create a new internal node with frequency equal to their sum, and push the merged node back. Each iteration reduces the heap size by one, so if you start with N unique characters, the loop runs N minus 1 times and you’re left with a single root node.

Tie-breaking can matter. If two nodes have the same frequency, heapq will try to compare the nodes themselves. That’s where your __lt__ method kicks in. For full determinism across runs, you can add a secondary key (like a unique insertion counter) to the tuple: (freq, counter, node). That way, ties always break the same way, and your codes stay consistent.

Merging Two Smallest Nodes

Every merge pops two nodes (call them A and B), creates a new node with freq = A.freq + B.freq, sets left = A and right = B (or vice versa), and pushes the new node back into the heap. This process ensures that the two least-frequent symbols end up deepest in the tree, meaning longer codes, while frequent symbols rise toward the root and get shorter codes.

The iterative merging continues until only one node remains. That becomes the tree’s root. That final node has a frequency equal to the total character count of your input, and its left and right children represent the two largest sub-clusters. Because you always merge the smallest pair, the algorithm guarantees an optimal prefix code for those frequencies.

Generating Huffman Codes by Traversing the Tree

Once you have the root, you generate codes by walking the tree recursively. Start at the root with an empty code string. Every time you go left, append ‘0’ to the current code. Every time you go right, append ‘1’. When you reach a leaf (a node where char is not None), store the accumulated code in a dictionary mapping char → code. Then backtrack and explore the other branch.

The recursion naturally handles the entire tree. A typical function signature is generate_codes(node, code="") → dict. If node.char is not None, you’ve hit a leaf: save codes[node.char] = code. Otherwise, recurse on node.left with code + "0" and on node.right with code + "1".

This ensures that every code is built left-to-right from the root down, and no code is a prefix of another because each leaf stops the path. The prefix-free property is automatic. If one leaf is at depth 2 and another at depth 4, their codes will be different lengths and structurally non-overlapping.

Encoding Text into a Bitstring Using Huffman Codes

The encode function takes your original text and the codes dictionary, then replaces every character with its bitstring and concatenates them all into one long encoded message. For example, if codes = {'a': '0', 'b': '10', 'c': '11'} and your input is “abc”, the encoded output is "0" + "10" + "11" = "01011". The function signature looks like encode(text, codes) → str where the returned string is a sequence of ‘0’ and ‘1’ characters.

In a real compression scenario, you’d convert this bitstring into actual bytes. You’d pack eight bits at a time into a byte and handle the final partial byte by padding with zeros and recording how many bits are real versus padding. For this tutorial, keeping the bitstring as a plain string is fine for learning and testing.

Padding for byte alignment: if the total bit count isn’t divisible by 8, you need to add trailing zeros and store the padding count so the decoder knows when to stop.

Non-ASCII characters: as long as your frequency table and tree include them, encoding works the same way. Just map the character to its code.

Large inputs: encoding is O(n) because you loop through the text once, but building the bitstring can use memory proportional to input size times average code length.

Partial byte handling: when flushing bits to bytes, keep a buffer and flush every 8 bits. At the end, pad the buffer and write the final byte with a note of how many bits are valid.

Decoding Bitstreams Back to Original Text

Decoding reverses encoding by reading the bitstring left to right and walking the Huffman tree. Start at the root. Read one bit: if it’s ‘0’, move to node.left. If it’s ‘1’, move to node.right. When you land on a leaf (where node.char is not None), append that character to your output and jump back to the root to decode the next symbol. Repeat until you’ve consumed all bits.

Padding can trip you up. If the encoder added trailing zeros to fill the last byte, those zeros might push you down branches that don’t correspond to real symbols. To avoid that, either store the exact bit count in a header or mark the end of the real data explicitly. A common fix is to encode the original text length and stop decoding once you’ve emitted that many characters.

Without careful padding handling, you might decode garbage characters at the end or crash when the tree walk doesn’t land on a leaf. The function signature is typically decode(bitstring, root) → str, and the complexity is O(m) where m is the bitstring length.

Worked Example: Building and Using Huffman Codes

Let’s compress the string “aaaabcc”. First, build the frequency table: ‘a’ appears 4 times, ‘c’ appears 2 times, ‘b’ appears 1 time. Push three leaf nodes into the heap: (1, ‘b’), (2, ‘c’), (4, ‘a’). Pop the two smallest, ‘b’ (freq 1) and ‘c’ (freq 2), and merge them into an internal node with freq 3. Now the heap holds (4, ‘a’) and (3, internal). Pop both, merge into a root with freq 7.

The tree looks like this: root (7) has left child ‘a’ (4) and right child internal (3), which itself has left child ‘c’ (2) and right child ‘b’ (1).

Traverse the tree to assign codes. Going left from the root lands on ‘a’, so ‘a’ gets code “0”. Going right lands on the internal node. From there, left reaches ‘c’ (code “10”) and right reaches ‘b’ (code “11”). Now encode “aaaabcc”: replace each ‘a’ with “0” (four times = “0000”), each ‘c’ with “10” (two times = “1010”), each ‘b’ with “11” (once = “11”). Concatenate: “0000” + “11” + “10” + “10” = “00001110​10”. That’s 10 bits total.

The original string has 7 characters. Assuming 8-bit ASCII encoding, that’s 7 × 8 = 56 bits. The Huffman encoding uses only 10 bits, saving 46 bits. Compression ratio: (56 − 10) / 56 ≈ 0.8214, or about 82.14% size reduction. That’s a huge win for such a short, skewed input. If the input were longer or less skewed, the savings would change, but the method stays the same.

Time and Space Complexity of the Huffman Implementation

Building the frequency table is O(n), where n is the length of the input text. You scan every character once. Constructing the Huffman tree involves N unique symbols (N ≤ n). You push N nodes into the heap (O(N log N) total) and then pop and merge N minus 1 times (each pop and push is O(log N)), so tree construction is O(N log N). Generating codes traverses the tree once, visiting every node, which is O(N). Encoding the text walks through the original n characters and looks up each code (O(1) per lookup if codes is a dict), so encoding is O(n). Decoding reads m bits and follows tree paths, which is O(m).

Overall, the dominant term is O(N log N) for tree construction when N is large, but in practice n (text length) is often much larger than N (unique symbols), so scanning the text can dominate.

Space complexity: the frequency table holds N entries (O(N)), the Huffman tree has 2N minus 1 nodes (N leaves plus N minus 1 internal nodes, which is O(N)), the codes dictionary stores N entries (O(N)), and the heap temporarily holds up to N nodes (O(N)). Total space is O(N). When N is small (like 256 for extended ASCII), space is negligible. When N is huge (millions of unique Unicode symbols), memory becomes a real consideration, but most practical use cases sit comfortably in the O(N) range.

Handling Edge Cases and Common Implementation Pitfalls

Edge cases reveal whether your implementation is robust or fragile. An empty input string should return an empty frequency table, an empty tree (or skip tree building entirely), and produce an empty encoded output without crashing. A single-character input, say “aaaa”, creates a frequency table with one entry. You can’t build a tree by merging (there’s nothing to merge), so either assign a dummy code like “0” or handle it as a special case where the “tree” is just one leaf and the code is a single bit.

Tied frequencies can cause non-deterministic behavior if your heap breaks ties arbitrarily. If ‘x’ and ‘y’ both have frequency 5, the heap might order them differently across runs. To fix this, add a stable tie-breaker, either a counter that increments with each node creation or sort by character value. Padding is another trap: if you pad the final byte with zeros and don’t track the real bit count, the decoder might interpret those padding zeros as actual symbols and append garbage. Always store either the original text length or the exact bit count.

Forgetting to serialize the code dictionary: the decoder needs the tree or codes mapping. If you only send the encoded bitstring, decoding is impossible.

Inconsistent tie-breaking: using different tie-breaking rules between encoder and decoder produces different trees and incompatible codes.

Ambiguous bitstream rules: if you don’t define whether left is ‘0’ or ‘1’, or how padding works, encoder and decoder won’t agree.

Skipping edge-case tests: always test empty input, single-character input, and highly skewed distributions (one symbol at 99%, others at <1%).

Mismatched frequency model: if the encoder uses one set of frequencies and the decoder rebuilds the tree from a different set, codes won’t match.

Ignoring memory limits: for huge alphabets (like full Unicode), storing every node and code can consume gigabytes. Consider fallback strategies or frequency caps.

Full Python Script: End-to-End Encoder and Decoder

The complete script bundles all functions into one runnable file. You’ll have build_frequency_table(text) that returns a Counter, build_huffman_tree(freq_table) that returns the root node, generate_codes(root) that returns a dict of character-to-code mappings, encode(text, codes) that returns the encoded bitstring, and decode(bitstring, root) that returns the original text. Each function is self-contained, takes clear inputs, and produces a testable output, so you can run and inspect them step by step.

Include assertions or small unit tests at the bottom of the script. For example, encode “abc”, then decode the result and assert it equals “abc”. Try edge cases: encode “”, encode “aaaa”, encode a long string with mixed frequencies. These round-trip tests catch bugs early and prove your implementation works. The script should support any Unicode characters your frequency table can count, so don’t hard-code ASCII assumptions unless you need to.

1. build_frequency_table(text) scans the input, returns a Counter mapping each character to its count. Handles empty strings by returning an empty Counter.
2. build_huffman_tree(freq_table) creates leaf nodes, pushes them into a min-heap, merges smallest pairs until one root remains, returns that root. Handles single-character inputs by returning a lone leaf or assigning a dummy code.
3. generate_codes(root) recursively traverses the tree, accumulates ‘0’ for left and ‘1’ for right, returns a dict of char→code. Handles empty trees by returning an empty dict.
4. encode(text, codes) replaces each character in text with its code, concatenates into one bitstring, returns the encoded string and the codes dict for later decoding.
5. decode(bitstring, root) walks the tree bit by bit, appends characters when hitting leaves, resets to root, returns the reconstructed text. Stops when all bits are consumed or when a known length is reached.

Final Words

You now have a full Huffman encoder and decoder in Python, from frequency table to tree to bit-level encode/decode. You built the Node class, used heapq to merge nodes, and generated prefix-free codes.

We walked the core workflow: Counter for frequencies, heap-based merges, DFS to assign codes, encoding with padding, and decoding by traversing the tree. The worked example and complexity notes show practical costs and benefits.

If you follow this step by step guide to implement Huffman coding in Python you’ll finish with a working, testable script and a clear path to extend it. Nice work. Keep experimenting.

FAQ

Q: How to implement Huffman coding in Python?

A: Implementing Huffman coding in Python involves building a frequency table, implementing a Node class, merging the two smallest nodes with heapq to build the Huffman tree, generating codes via DFS, then encoding and decoding with the codebook.

Q: Is Huffman coding still relevant today?

A: Huffman coding is still relevant today as a fast, lossless, prefix-free compressor; it’s optimal among prefix codes, used inside some formats and teaching, though other compressors often outperform it on complex data.