GoHuff - Huffman Coding in Go

A learning project to understand lossless data compression using Huffman coding, built from scratch in Go.

Based on Coding Challenge #3 — compressing and decompressing text files using Huffman codes. Test data: Les Misérables from Project Gutenberg.

What I Learned

Huffman Coding

Characters in text don't appear equally often. Huffman coding exploits this by assigning shorter bit codes to frequent characters and longer codes to rare ones.

For example, given "aaabbc":

Character frequencies: a=3, b=2, c=1
Huffman codes:         a="1", b="01", c="00"
Original:              6 bytes (48 bits)
Compressed:            "111010100" → 9 bits + padding → 2 bytes

The codes are prefix-free — no code is a prefix of another — so the encoded stream can be decoded unambiguously without delimiters.

Min-Heap / Priority Queue

Building the Huffman tree requires always picking the two lowest-frequency nodes. A min-heap (priority queue) makes this efficient — O(log n) per pop instead of O(n) with a sorted list.

Go provides container/heap which requires implementing the heap.Interface:

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int            { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool   { return pq[i].freq < pq[j].freq }
func (pq PriorityQueue) Swap(i, j int)        { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{})  { *pq = append(*pq, x.(*Node)) }
func (pq *PriorityQueue) Pop() interface{}     { /* remove last element */ }

Building the Tree

1. Count frequency of each character in the file
2. Create a leaf node for each character, push all onto the min-heap
3. Repeatedly pop the two smallest nodes, merge them under a new parent, push the parent back
4. The last remaining node is the root

Bit Packing

The encoded data is a string of '0's and '1's — but each character takes a full byte. To actually compress, we pack 8 bit-characters into 1 real byte:

String:  "1 1 0 1 0 0 1 1"  →  8 bytes in memory
Packed:   0b11010011         →  1 byte in memory

If the bit string isn't a multiple of 8, we pad with zeros and store the padding count so we can strip them during decompression.

Compressed File Format

┌─────────────────────────────────┐
│ Header (frequency table JSON)   │
├─────────────────────────────────┤
│ \n delimiter                    │
├─────────────────────────────────┤
│ Padding count (1 byte)          │
├─────────────────────────────────┤
│ Packed compressed data          │
└─────────────────────────────────┘

Usage

go build -o gohuff .
./gohuff
# Enter filepath: test.txt
# → produces compressed.bin and decompressed.txt

Project Structure

├── main.go                        # CLI entry point
├── internal/
│   └── huffman_coding.go          # All Huffman logic
├── test.txt                       # Test data (Les Misérables)
├── compressed.bin                 # Compressed output
└── decompressed.txt               # Decompressed output

Core Functions

Function	Purpose
calculateFreqInFilePath	Read file, count frequency of each rune
BuildTreeFromFreq	Build Huffman tree from a frequency map using a min-heap
BuildHuffmanTreeFromFilePath	Convenience wrapper: file → freq → tree
GenerateHuffmanCodes	Walk the tree recursively to produce prefix codes
Encode	Replace each character with its Huffman code
Decode	Walk the tree bit-by-bit to recover original text
CompressToFile	Full pipeline: read → encode → bit-pack → write with header
DecompressToFile	Full pipeline: read header → rebuild tree → unpack → decode → write