Huffman Coding Step by Step
About this app
The Huffman tree grows from the character frequencies of a text: the two lightest nodes leave the heap, fly under a new node carrying their sum, and the new node returns via heappush. The app computes exactly like the slide code (heapq with __lt__), also for your own text. Then read the codes, see 61 instead of 133 bits for KLEINERBEISPIELTEXT, and decode the bit stream without separators bit by bit through the tree. With a prediction question and a switch for a different choice on ties.
How Huffman codes are built
Huffman coding gives frequent characters short bit strings and rare characters long ones. You start with one node per character, weighted by its frequency. Then you repeatedly take the two lightest nodes, put them under a new node with the sum of their weights and put that node back. In the end a single tree remains; the path from the root to a leaf, left 0 and right 1, is that character's code. No code is the prefix of another, so the bit stream can be decoded unambiguously without separators.
What the app shows
At the top a forest of subtrees grows, and its top row is always exactly the content of the list heap. When merging, the two smallest nodes light up, leave the heap array via heappop, fly under a new node and return via heappush. The computation matches Python code with heapq and __lt__ exactly, also for your own text. A table then shows the codes and bit counts; for KLEINERBEISPIELTEXT it is 61 bits instead of 133 in 7-bit ASCII.
Try it yourself
Pick an example or enter your own text of up to 40 characters and step through counting, heapify, merging, reading off codes and encoding. Before each merge the app asks which two nodes come next. A switch shows how a different choice on ties gives different but equally good codes. In the decode panel you read a bit stream back through the tree one bit at a time.
Frequently asked questions
- How does Huffman coding work?
- You count how often each character occurs and repeatedly merge the two rarest nodes into a new node with the sum of their frequencies. The resulting tree gives the codes: every edge to the left is a 0, to the right a 1. Frequent characters sit close to the root and get short codes.
- Why does a Huffman code need no separators?
- Huffman codes are prefix-free: no code is the beginning of another, because every character sits in a leaf. To decode, you walk down the tree from the root bit by bit; when you reach a leaf, one character is done and you start again at the top.
- Is the Huffman code unique?
- Not necessarily. When frequencies are equal there are several choices, which lead to different trees and codes. The total length of the encoded message is the same for all of them, and it is minimal among prefix-free codes.
- What can I do in the Huffman app?
- Build the tree step by step for example texts or your own, predict which nodes merge next, read off codes, compare the bit count with fixed-length codes and ASCII, and decode a bit stream through the tree. The matching Python code is in the code panel.
Subject: Computer science
More from Computer science
- Ackermann function
- Elevator simulator
- Binary workshop
- Binary versus linear search
- The Collatz problem
- Inside a CPU
- Swap the inside
- One frame in 16 milliseconds — how a game engine renders an image (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps