Huffman Compression

You send emails with attachments, stream videos, or save documents every day. All those files take up space on hard drives and require time to travel over networks. This technique explains exactly how software shrinks a large file—like a photo or a text document—so it becomes smaller, without losing any single word or pixel. It matters because it is the reason your email attachments arrive quickly and why you can store thousands of hours of music on a small device. You will see this mechanism every time you zip a folder or receive a compacted web page.

Imagine you have to send a message made of only four letters: A, B, C, and D. In a standard computer system, each letter is stored as a fixed number of bits (like binary digits). For example, A is 00, B is 01, C is 10, and D is 11. This means every letter takes exactly 2 bits to store. That is simple, but it is wasteful if some letters appear much more often than others.

Suppose you have a long text where A appears 50% of the time, B 25% of the time, C 12.5% of the time, and D 12.5% of the time. You are using 2 bits for every letter, but you could do better by giving shorter codes to frequent symbols and longer codes to rare ones.

If we give A the code '0' (1 bit), B the code '10' (2 bits), C the code '110' (3 bits), and D the code '111' (3 bits), the average number of bits per letter drops significantly.

But there is a catch. You must be careful about how you assign these codes. If you use '0' for A and '01' for B, then when you see the sequence '01', you cannot tell if it represents A followed by B (0 then 01) or just B alone (01). To prevent this confusion, we need a special rule: no code can be the beginning of another code. This ensures that every sequence of bits has only one possible interpretation. Huffman coding builds exactly such a code, step-by-step, to ensure it is as efficient as possible.

Think of a librarian organizing books who wants to make it fastest for patrons to reach the most popular titles. She knows how many people check out each book. She starts by taking the two least checked-out books and tying them together with a single string, creating a new 'bundle' that has the combined popularity of those two books. Then she looks at all the remaining individual books and bundles again, picks the two least popular items (whether they are single books or bundles), ties them together, and creates a larger bundle. She keeps doing this until there is just one giant bundle containing every book. The structure she builds looks like an upside-down tree. The most popular books end up closest to the trunk of the tree (short path from the top), while the least popular books are far out on the branches (long path). This works beautifully for organizing access, but the analogy breaks down in one way: in a library, you can just look at the spine to find a book. In this coding method, the instructions must be unambiguous—like saying 'turn left' versus 'turn left, then right.' If 'turn left' is a complete instruction, you cannot also use it as the start of another instruction, or people would never know when to stop following directions.

This analogy is limited because a librarian can see all the books at once, while this coding method builds the structure purely by comparing frequencies without seeing the entire text beforehand.

Huffman coding is a method for shrinking data without losing any information by creating variable-length codes where no code is the start of another, assigning shorter codes to more frequent symbols by repeatedly merging the two least frequent items into new groups.

This concept sits beside Shannon entropy, which calculates the theoretical minimum number of bits needed to represent each symbol in a message based on their probability. It also relates to the greedy algorithm strategy, where you make the best local choice at each step (merging the smallest frequencies) to build up to the overall solution.