learning-it by example

#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.

1. When building the Huffman tree, which two nodes are joined at each step?
2. In a Python Huffman coding demo, how many bits did Huffman coding need for a made-up 102 character text, before its code table?
3. In a Python demo, a made-up text was repeated twenty times. zlib needed 85 bytes and the Huffman code 873 bytes, before its table. Why is zlib so much smaller?
4. A Python Huffman coding demo adds a code table cost of two bytes per character to its byte count. What is that figure?
5. In a Python Huffman coding script that builds its tree with heapq, why does each heap entry carry a tick as well as the count?

Practice only: nothing is saved and no score counts towards anything. Each answer comes with the reason.

  1. 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'.

  2. 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.

  3. 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.

  4. 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

All How it works, by example videos

Related videos