Huffman Tree Compressor

This was a university project for algorithms and data structures. I implemented a C++ Huffman compressor/decompressor capable of compressing and decompressing files without loss of information, working with binary trees, bit-level file reading/writing, and reconstruction of the encoded content.

Implemented technologies

Process and challenges

Library to read/write bits: for this I had to unset each character using the operators whose utility is to move. To write bits, I made an array where 1s and 0s were written, and when it reached the number of 8 converted it to ASCII using the typical decimal-to-binary algorithm (sum of 2 raised to that n position).
File walking: during the course we developed a library that read/write files using native c++ fread and fwrite (stdio.h)..
Save the bits in an array with their number of occurrences, then sort by number.
Create tree.
Write header so we can rebuild the tree.
As the file is read again, we must generate each key of each character with the tree and write it to another file..
To unzip: rebuild tree reading header.
Reading the content, figure out what character it is by looking in the huffman tree.
Write decrypted file.

Technical Decisions

Bit-level custom I/O
Wrote a custom bit read/write library using native C++ file I/O (fread/fwrite), packing bits into bytes manually via a decimal-to-binary accumulation approach.
Header-encoded tree reconstruction
Encoded the Huffman tree structure into a file header so the decompressor could rebuild the exact same tree before decoding.

Challenges

Bit-level file reconstruction
Getting lossless reconstruction right required carefully rebuilding the tree from the header and matching each decoded bit sequence back to its original character.

Current Status

Archived

Conclusion and next steps

I would like in the future to deploy this project to a lambda function and make a small site to make use of this algorithm.