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.
Video #274 ยท How it works, by example
Steps in the video
- 0:00 816 bits down to 349: Huffman coding in about 40 lines
- 0:37 The idea
- 1:14 Setup
- 1:39 Build the tree with a heap
- 2:08 Read off the codes
- 2:28 Encode and decode
- 2:46 Count the bytes, then ask zlib
- 3:58 Why zlib wins on repeats
- 4:32 What this does not show
- 4:57 Mistakes to avoid
- 5:22 My take and next steps
- 5:54 Recap
Files
- huffman.py (46 lines)
- run.py (27 lines)
Tested with
Python 3.12.15
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.
Sources
Learning IT by Example.