#274 How it works, by example 6.4 min
How File Compression Works: Huffman Coding in 40 Lines
Huffman coding took a 102 character text from 816 bits to 349, before its code table, in about 40 lines of Python.
Try a single repeated letter
Copy the code folder first. In run.py replace the two lines that define TEXT with: TEXT = 'aaaaaaaaaa'. Predict the code for the letter a and the bits per character, then run python run.py. Look in huffman.py for the line that handles this case.
A hint
A tree with one leaf has an empty path. Look for the piece in walk that says path or '0'.
Eight different letters
Set TEXT to 'abcdefgh'. Predict whether any letter gets a shorter code than the others, and what the bits per character will be. Run python run.py and check. Why does Huffman coding give no shorter codes when every character is equally common? The saving the program prints against 64 plain bits comes only from there being just eight different letters.
A hint
When all counts are equal, the tree has no reason to be lopsided.
Decode by hand
Restore the original TEXT. After the line that sets bits, add: print(bits[:12]). Using the code table the program prints (space, e, t, h), split those twelve bits into codes by hand and write down the characters. Then check with decode(bits[:12], codes).
A hint
Read from the left and stop as soon as the bits so far match a code. No code starts another code, so there is only one way to read it.
Fewer copies against zlib
In the last lines of run.py change TEXT * 20 to TEXT * 2. Predict how each size changes when the number of copies goes down, and whether zlib is still smaller. Run python run.py to check. The printed label still says 20 copies, so read it as 2 copies, or change the label too. What does zlib know that this Huffman code does not?
A hint
Huffman here looks only at how often each letter appears. It cannot see that a whole sentence came before.
These tasks are for you to try on your own machine. Nothing is checked or saved.
What this does not show
The text is made up and tiny, and the table cost is my own rough estimate, not how deflate stores it.
Up next in How it works, by example
More in How it works, by example
Related videos
- #275 Bloom Filters Explained: Build One and Measure Errors How it works, by example
- #01 Local AI Agent in Python: No API Key (Ollama) AI agents and MCP
- #02 RAG From Scratch in Python: Chunk, Embed, Retrieve (Local) RAG and vector search
- #03 pgvector vs Chroma vs Qdrant: Same Data, Real Results RAG and vector search
