C++ File Compression Tool Project

Intermediate•3–4 days•Huffman coding, priority queues, bit I/O

Shrink text files with a real Huffman encoder — and restore them losslessly.

What you will build

Implement Huffman coding: count letter frequencies, build a tree that gives short codes to common letters, and write a compressed bitstream your own decoder can perfectly restore. This is how ZIP's family of algorithms thinks, and building it end-to-end is a badge of honour.

What you will learn

Frequency analysis of input data
Building a Huffman tree with a priority queue
Prefix-free codes and tree traversal decoding
Writing and reading individual bits

Feature checklist

Compress a text file to a smaller .huf file
Decompress back to the exact original
Reports sizes and compression ratio
Stores the code table inside the file header
Handles any byte value, not just letters

Starter code

#include <iostream>
#include <queue>
#include <memory>
#include <map>

struct Node {
    int freq; unsigned char ch;
    std::shared_ptr<Node> l, r;
    Node(int f, unsigned char c) : freq(f), ch(c) {}
    Node(std::shared_ptr<Node> a, std::shared_ptr<Node> b)
        : freq(a->freq + b->freq), ch(0), l(a), r(b) {}
};

struct ByFreq {
    bool operator()(const std::shared_ptr<Node>& a,
                    const std::shared_ptr<Node>& b) const {
        return a->freq > b->freq;   // min-heap
    }
};

void buildCodes(const std::shared_ptr<Node>& n, const std::string& prefix,
                std::map<unsigned char, std::string>& codes) {
    if (!n->l && !n->r) { codes[n->ch] = prefix.empty() ? "0" : prefix; return; }
    buildCodes(n->l, prefix + "0", codes);
    buildCodes(n->r, prefix + "1", codes);
}

// Count byte frequencies, push one Node per byte into the
// priority queue, merge the two smallest until one tree
// remains, then buildCodes() gives every byte its bit string.

Full walkthrough

Step 1: Count byte frequencies first

Read the whole input file in binary and count occurrences of each of the 256 byte values into a long long freq[256]. Huffman coding spends its savings where the bytes actually are: a file of mostly 'e' and spaces deserves tiny codes for 'e' and space, and this table is how the algorithm knows.

Step 2: Build the tree with a priority queue

struct Node { byte, freq, left, right } — create a leaf per byte that occurs, push all leaves into a std::priority_queue with the ByFreq comparator that surfaces the SMALLEST frequency first (std::priority_queue is a max-heap, so the comparator must be inverted — this trips everyone once). Repeatedly pop the two smallest, join them under a parent whose freq is their sum, push it back. The last node standing is the root.

while (pq.size() > 1) {
    auto a = pq.top(); pq.pop();
    auto b = pq.top(); pq.pop();
    pq.push(std::make_shared<Node>(a->freq + b->freq, a, b));
}

Step 3: Walk the tree to assign codes with buildCodes()

buildCodes(node, prefix) recurses: going left appends '0', going right appends '1'; at a leaf, the accumulated prefix IS that byte's code, stored in a map/array codes[256]. Frequent bytes sit near the root and earn short codes automatically — you never assign lengths by hand.

Step 4: Write a header that makes the file self-describing

The .huf file must carry the frequency table (or the code table) in a header, because the decompressor has no other way to rebuild the SAME tree. Store the 256 frequencies (and the original byte count) first, then the encoded payload. A compressed file that needs the original program's memory to decode is not a format — it is a screenshot.

Step 5: Encode by packing bits, not characters

Translate every input byte into its code string and accumulate bits into a buffer byte, flushing each full 8 bits to the output. Writing the codes as literal '0'/'1' characters makes the 'compressed' file 8× BIGGER than the original — the single most common Huffman own-goal. The original byte count in the header tells the decoder when to stop, ignoring padding bits in the final byte.

Step 6: Decode by walking bits down the tree

Rebuild the tree from the header frequencies (identical construction = identical tree), then read bits one at a time, walking left/right from the root; reaching a leaf emits its byte and restarts at the root. Stop after exactly the original byte count. Decode is a state machine, not a lookup — that is why it can handle variable-length codes unambiguously (no code is a prefix of another, by construction).

Step 7: Measure and verify honestly

Print original size, compressed size, and ratio, then decompress and byte-compare against the original (diff/cmp). Test on English text (compresses well), on a random binary file (may not compress at all — Huffman cannot shrink incompressible data, and reporting that honestly matters), and on a one-byte file (the degenerate tree edge case).

Common mistakes

Writing codes as text '0' and '1' characters instead of packing bits — output balloons instead of shrinking.
Forgetting to store the tree/frequencies in the file, making decompression depend on re-running compression on the lost original.
A comparator that pops the LARGEST frequencies first, building a tree that gives frequent bytes the LONGEST codes.

Compile and run

g++ -std=c++17 -o huffman huffman.cpp

Sample run

$ ./huffman
Compress or Decompress (C/D):
> C
Input file:
> story.txt
Counting byte frequencies...
Building Huffman tree from 41 distinct bytes...
story.txt: 1024 bytes -> story.huf: 614 bytes (40.0% smaller)

$ ./huffman
Compress or Decompress (C/D):
> D
Input file:
> story.huf
Rebuilt the tree from the file header.
story.huf -> story_restored.txt (1024 bytes)
Verified: decompressed file is byte-for-byte identical to the original.

Try it in your browser

No browser demo is included for this project. Build the C++ version below — that is the real program.

Related Intermediate projects

← All 60 projects · Classic site (Learn & Sandbox)