Generalized Huffman Compression

A file-based implementation of Huffman Coding for lossless data compression.
This project can compress and decompress any binary file type. It works best on uncompressed or redundant data formats such as .txt, .csv, or .bmp.
Already-compressed formats like .png, .mp4, .zip, and .pdf should be avoided since they will not yield size reduction.

---

How Huffman Coding Works

Huffman coding is a lossless compression algorithm that assigns variable-length bit codes to characters based on their frequencies.
Frequent symbols receive shorter codes; infrequent symbols get longer ones.
This results in a reduced total number of bits required to represent the same information.

Steps:

1. Frequency Map Construction

   • Read the entire input file byte by byte.
   • Count the frequency of each byte value (0–255).

2. Building the Huffman Tree

   • Create leaf nodes for each unique byte.
   • Insert them into a min-heap ordered by frequency.
   • Repeatedly extract the two smallest nodes, combine them into a new internal node, and reinsert until one node (the root) remains.

3. Generating Huffman Codes

   • Traverse the tree recursively:
     • Append '0' for left branches
     • Append '1' for right branches
   • Store the resulting bit string as the Huffman code for each symbol.

4. Encoding

   • Replace each byte in the input file with its Huffman bit sequence.
   • Bits are accumulated into bytes (8 bits at a time) and written to the encoded output file.
   • Metadata such as original file size is stored at the start of the file for decoding.

5. Decoding

   • Read the stored original size.
   • Traverse the Huffman tree bit by bit, writing decoded bytes to the output file until the original size is restored.

---

File Structure

Folder	Description
inputs/	Contains source files to compress
encoded/	Stores compressed .huf files
outputs/	Contains decompressed output files

---

Compilation and Usage

1. Compile

g++ huffman.cpp -o out

2. Run

./out

The program will prompt for a filename which must be located inside inputs/ folder.

It produces:

• Encoded output in encoded/filename.huf
• Decoded output in outputs/decoded-filename

Important Notes

1. Best results On: .txt, .csv, .bmp, or .raw files — due to redundancy and repeated patterns.

2. Avoid Using: .png, .mp4, .pdf, .zip — these are already compressed and optimized internally; Huffman coding cannot reduce them further.

3. Metadata Overhead: A small header (8 bytes) is written at the beginning of each encoded file to store original file size. This may slightly affect compression ratio for very small inputs.

4. Bit Padding: The final byte of the encoded output may include up to 7 padding bits to complete the last byte boundary.

Output Statistics

After compression and decompression, the program prints:

• Frequency and bit-length per symbol
• Total bits used in compressed data
• Original size
• Final compression ratio (% of original size)