learning-it by example

Back to the video

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

  1. 0:00 816 bits down to 349: Huffman coding in about 40 lines
  2. 0:37 The idea
  3. 1:14 Setup
  4. 1:39 Build the tree with a heap
  5. 2:08 Read off the codes
  6. 2:28 Encode and decode
  7. 2:46 Count the bytes, then ask zlib
  8. 3:58 Why zlib wins on repeats
  9. 4:32 What this does not show
  10. 4:57 Mistakes to avoid
  11. 5:22 My take and next steps
  12. 5:54 Recap

Files

  • huffman.py (46 lines)
  • run.py (27 lines)

Download the code (zip)

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.