← Projects

Huffman
Compressor

Lossless file compression implementing Huffman coding from scratch in Go.

Stack Go · stdlib only · no compression libraries
Source github.com/sibteali786/huffman-compressor ↗
Challenge John Crickett · codingchallenges.fyi

Live Run

The Challenge

One algorithm.
Six CS fundamentals.

Huffman coding is a greedy compression algorithm that assigns shorter bit sequences to more frequent characters and longer ones to rarer characters, producing variable-length prefix-free codes that are guaranteed optimal for symbol-by-symbol encoding. I picked it from John Crickett’s Coding Challenges because it’s a vertical slice through several CS fundamentals at once: greedy algorithms, binary trees, priority queues, bit manipulation, and binary file I/O, all in a single coherent project with a clear correctness criterion.

That criterion is round-trip fidelity: compress a file, decompress it, and the bytes must match exactly. Any bug in bit ordering, padding, tree construction, or header encoding fails this test with no ambiguity. Go is the right language for it: generics for the priority queue, io.Reader/io.Writer for streaming I/O, and the standard library for binary encoding, without reaching for a compression library.

What I Built

Nine source files.
One binary.

Package structure

huffman-compressor/
├── cmd/
│   └── main.go
├── internal/
│   ├── huffman.go       frequency analysis
│   ├── tree.go          tree construction
│   ├── priority_queue.gogeneric min-heap
│   ├── encoder.go       code generation
│   ├── bitbuffer.go     bit writer
│   ├── bitreader.go     bit reader
│   ├── header.go        .hf file format
│   ├── compress.go      compression pipeline
│   └── decompress.go    decompression pipeline
└── test/
    └── *_test.go        30+ tests

.hf file format

┌──────────────────────────────────┐
│ Magic     "HF"         2 bytes   │
│ OrigSize  uint64       8 bytes   │
│ NumChars  uint8        1 byte    │
│ Padding   uint8        1 byte    │
│ Entries   N × 5 bytes           │
│   char    byte         1 byte    │
│   freq    uint32       4 bytes   │
└──────────────────────────────────┘
12 + (N × 5) bytes total

Algorithm Pipeline

Seven steps to compress.
Five to decompress.

Compress

AnalyzeFreqs

1 KB chunks · FreqTable[byte]

BuildTree

sort · leaf nodes · PQ merge

GenerateCodes

DFS · CodeTable[byte]

VerifyPrefixFree

all pairs · returns bool

WriteHeader

HF magic · paddingBits=0

WriteBits

BitBuffer · MSB-first

SeekAndPatch

Seek(11) · write PaddingBits

Decompress

ReadHeader

verify HF · recover FreqTable

BuildTree

identical algorithm · same sort

NewBitReader

cursor past header

DecodeBits

tree traversal · 1 KB buffer

VerifyDecomp

byte-for-byte comparison

Key Decisions

Four choices
worth explaining.

dec-01 lsb-first-storage-msb-first-transmission
Decision appendBit stores codes LSB-first: bit 0 is the root branch, higher positions are deeper. WriteBits loops i = 0..length-1 to emit in append order. WriteBit packs each bit MSB-first into the output byte.
Why LSB-first internal storage makes appendBit a simple OR + shift with no reversal at append time. MSB-first transmission is the natural bit-stream convention. The two meet at WriteBits. Pinning all three directions consistent required TestBitOrderingExplicit, a test that asserts the exact expected byte value of a known bit pattern.
dec-02 dummy-node-for-single-character-edge-case
Decision When len(freqTable) == 1, BuildHuffmanTree creates a dummy leaf (char = 0, frequency = 0) and pairs it with the real leaf under a synthetic root. GenerateCodes detects IsDummy() and assigns {bits: 1, length: 1} to the real character.
Why A single-leaf tree has no paths: GenerateCodes DFS finds a leaf at the root, stores a zero-length code, and WriteBits with length = 0 writes nothing. The dummy node is the minimal fix: one extra leaf, one real path. IsDummy() guards the decode loop from treating the dummy as a valid output character.
dec-03 write-padding-zero-seek-and-patch
Decision WriteHeader writes paddingBits = 0 as a placeholder. After the encode loop, compress.go calls outputFile.Seek(11, io.SeekStart) and overwrites the real value. This is the one place the streaming abstraction requires os.File rather than a generic io.Writer.
Why Padding is unknown until encoding finishes, but the header must be written before encoding begins. Buffering all output in memory to backfill it would destroy the O(1) memory property. Seek costs one syscall and keeps memory constant regardless of file size. The abstraction leak is contained: nothing else in the pipeline cares.
dec-04 generic-minheap-with-comparefunc
Decision MinHeap[T] and PriorityQueue[T] use Go generics with CompareFunc[T any]. The heap compares by PriorityItem.Priority int set at Enqueue time; it never calls methods on T directly.
Why The constraint is any: no interface methods required on the stored value. The same heap implementation works as min- or max-heap by swapping the comparator. For this project the comparator reads node.frequency, but the heap doesn’t need to know that. A concrete *HuffmanNode heap would have been faster to write and impossible to reuse.

Problems Hit

Three bugs
that needed tests.

lsb-msb-mismatch-corrupting-all-output

Symptom Decompression produced garbled output on every test file. Round-trip failed with no error: wrong bytes, no panic.
Root cause Three directions must be consistent: appendBit builds codes in one bit order; WriteBits must emit in append order (root decision first); WriteBit must fill bytes MSB-first so the reader reconstructs correctly. Any one direction wrong produces corrupted but structurally valid-looking output.
Fix Wrote TestBitOrderingExplicit: encodes a known bit pattern, asserts the exact expected byte value. Pinning the expected byte forced each direction to be correct rather than just internally consistent with each other.

non-deterministic-tree-corrupting-round-trip-on-tied-frequencies

Symptom Round-trip passed on most inputs but failed intermittently on inputs with tied character frequencies. No error, just wrong bytes.
Root cause Huffman trees are not unique when frequencies tie. Without a consistent tiebreaker, compression and decompression could build different trees from the same frequency table and silently assign different codes to each character.
Fix Sort characters by byte value before enqueuing, applied identically in BuildHuffmanTree and WriteHeader (which also sorts before writing frequency entries). Same sort, same input, same tree, every run.

single-char-file-zero-length-code-writes-nothing

Symptom Compressing a single-character file produced a non-zero output but decompression returned empty. The code table was empty.
Root cause One unique character → one leaf node → root with no branches. GenerateCodes DFS hit a leaf at the root, appended no bits, stored a zero-length code. WriteBits with length = 0 wrote nothing.
Fix Detect len(freqTable) == 1 in BuildHuffmanTree, create a dummy leaf, pair it with the real leaf under a synthetic root. GenerateCodes detects IsDummy() and assigns {bits: 1, length: 1} to the real character.

Test Coverage

8 test files.
30+ tests.

File Coverage
bitBuffer_test.go Bit writing, flush timing, padding, multi-byte, stress (1000 bits)
bitReader_test.go Bit reading, EOF, reconstruction, partial reads, multi-byte
compres_test.go Compress pipeline, empty file, single char, binary data, stats
decompress_test.go Round-trip fidelity, corrupt data, invalid magic, special chars
encoder_test.go Code generation, prefix-free property, Huffman ordering invariant
header_test.go Write/read symmetry, invalid magic, size calculation
tree_test.go Tree shape, leaf collection, frequency correctness, depth ordering
huffman_test.go AnalyzeFrequencies correctness (internal package)

Complexity

Phase Complexity
Frequency analysis O(m), m = file size. Streaming 1 KB chunks, constant memory.
Tree construction O(n log n), n = unique characters (≤ 255)
Code generation + encoding O(m): one table lookup per input byte
Decoding O(m · log n): one tree traversal per output byte

What I’d Do Differently

One honest
paragraph.

The NumChars uint8 field caps unique byte values at 255, enforced with a len(freqTable) > 255 check. The root cause isn’t the check; it’s the field width. Changing it to uint16 would support all 256 possible byte values at a cost of one extra header byte. The deeper fix is updating WriteHeader and ReadHeader to use binary.Write/Read with a uint16, updating CalculateHeaderSize accordingly, and bumping the magic number or adding a version byte so old and new formats don’t silently misdecode each other.

Have a problem worth
solving from first principles?

Get in touch See all projects GitHub ↗