huffman-test-python

A single-file Huffman coding implementation for strings, with a small CLI that shows how many bits a piece of text saves and proves the round trip is lossless.

Why

I wrote this in December 2024 to understand Huffman coding properly instead of just reading about it: build the frequency table, merge the two lightest nodes until there is one tree, read the codes off the tree, encode, decode, compare sizes. It is a learning exercise and a reference, not a compression library. If you want to see the algorithm in about 60 lines of plain Python, or you need a quick way to show a student what a Huffman code table looks like for a given sentence, this is it.

Quickstart

git clone https://github.com/joelstephen97/huffman-test-python.git
cd huffman-test-python
python huff.py "hello hello hello this is a string encoded by huffman encoding"

Characters : 62
Unique symbols : 19
Original size : 496 bits (8 per character)
Encoded size : 245 bits
Saving : 50.6% (code table not counted)
Round trip OK : True

No dependencies beyond the standard library.

Usage

usage: huff.py [-h] [-f FILE] [-c] [-b] [text]
positional arguments:
text text to encode (default: a demo paragraph)
options:
-f, --file read the text from this file instead
-c, --codes print the code table
-b, --bits print the encoded bit string

python huff.py # demo paragraph
python huff.py "abracadabra" --codes # see the code for each symbol
python huff.py --file notes.txt # any text file
python huff.py "aab" --bits # 0 0 1 -> "001"

With --codes, frequent symbols get short codes and rare ones long codes:

Code table (symbol, count, code):
' ' 10 110
'e' 6 000
'l' 6 010
'h' 5 1111
...
'u' 1 101001
'm' 1 101000

From Python:

fromhuffimportcompress, decompressbits, tree=compress("some text")
assertdecompress(bits, tree) =="some text"

How it works

compress() counts characters with collections.Counter, then build_huffman_tree() pushes one Node per character onto a min-heap and repeatedly pops the two smallest, merging them into a parent, until a single root remains. build_codes() walks that tree, appending 0 for left and 1 for right, and records the path to each leaf as that character's code. Encoding is a string join of the codes; decompress() walks the tree bit by bit and emits a character every time it hits a leaf.

Status and limitations

Working. Verified with Python 3.12, including the edge cases (empty string, one distinct symbol, unicode).

• The output is a Python string of '0'/'1' characters, not packed bytes, so it is for looking at, not for saving disk space.
• The "saving" figure ignores the cost of storing the tree or code table, which a real format has to include.
• Nothing is written to disk; it is in-memory demonstration code.

License

MIT, see LICENSE.