This project implements Huffman coding for lossless data compression and decompression in C++.
It includes building a Huffman tree, compressing input text into binary code, serializing the tree, and reconstructing the tree to decompress back to the original text.
- Count character frequencies and build a min-heap priority queue
- Construct a Huffman tree using a custom
HeapQueue - Generate prefix codes for each character
- Compress input strings into binary representation
- Serialize the Huffman tree into a compact string
- Reconstruct the tree and decompress encoded strings
- Includes unit tests with Catch2 across multiple large test cases
├── HeapQueue.hpp # Custom heap-based priority queue
├── HuffmanBase.hpp # Abstract base class for Huffman coding
├── HuffmanBase.cpp # Node implementation details
├── HuffmanTree.hpp # Huffman tree implementation
├── HuffmanTree.cpp # Compression, serialization, decompression
├── TestStrings.hpp # Large test input strings and expected outputs
├── PP3Test.cpp # Unit tests using Catch2
├── catch.hpp # Catch2 single-header test framework
The project uses Catch2 for unit testing.
g++ -std=c++17 -Wall *.cpp -o huffman
./huffman -s🖥️ Expected output
All tests passed (12 assertions in 1 test case)
🎯 Learning Outcomes
-
Applied data compression techniques using Huffman coding
-
Gained experience with trees, heaps, and priority queues
-
Practiced recursive algorithms (tree traversal, serialization)
-
Implemented and validated using automated unit tests
📜 Authors
Daud Ahmad Nisar
Computer Science Student at the University of South Florida