Huffman Encoder / Decoder

Overview

HuffZip is a pair of C++ command-line programs for lossless compression and decompression of text or binary files. It builds a frequency-based Huffman tree, stores enough information to reconstruct it, and verifies restored data with automated byte-for-byte round-trip tests.

Motivation

The project began as a first-year university assignment about trees, priority queues, binary files, and bitwise operations. Building both an encoder and a decoder connects the algorithm to a complete file format: a compact representation is only useful if the original bytes can be recovered exactly.

How it works

The encoder counts byte frequencies in a 256-entry histogram, then repeatedly combines the two least frequent nodes using a priority queue. Tree paths become variable-length bit codes. The output contains a signature, tree size, original file size, a serialized tree, and packed data bits. The decoder reconstructs the tree and follows those bits to recover the original bytes.

Architecture

Separate ENCODER_app and DECODER_app entry points share Node, Code, and HuffmanTree classes. Node represents the tree structure, Code manages bit sequences, and HuffmanTree builds the tree, generates the lookup table, and handles reconstruction. CMake produces huffman_encode and huffman_decode; a Python test runner exercises both executables through CTest.

Implementation decisions

The tree is serialized in post-order: a leaf marker is followed by its byte value, while an interior marker joins two subtrees. This lets the decoder rebuild the structure with a stack. Storing the original size distinguishes useful data from padding in the final byte. Input is loaded into memory before encoding, keeping the implementation simple at the cost of memory scaling with file size.

Challenges

A lossless codec must handle more than ordinary text. Tests cover empty input, repeated bytes, all 256 byte values, deterministic binary data, and bytes that match the tree markers. Invalid signatures and truncated payloads are rejected, and tree reconstruction validates marker structure before building nodes. Correctness is checked by comparing decoded output directly with the original bytes.

What I learned

The tree algorithm and the binary format have to agree at every boundary: symbol values, bit order, tree structure, and end-of-file handling. Building the full round trip connects abstract data structures to practical serialization. It also makes clear why automated tests need unusual byte patterns and malformed files, not just a successful example with readable text.

Repository