Huffman Compressor

A simple Python implementation of Huffman coding – a loss‑less data compression algorithm. This project provides a command‑line tool that can compress any text file into a custom binary format (.huffman) and later decompress it back to the original text.

---

Table of Contents

1. What is Huffman Coding?
2. How the Project Works
3. Installation & Requirements
4. Usage
5. File Format Details
6. Step‑by‑Step Walkthrough (Beginner Friendly)
7. Visualization & Flowchart
8. Example
9. Testing
10. License

---

What is Huffman Coding?

Huffman coding is a prefix‑free binary encoding that assigns shorter bit‑strings to more frequent characters and longer bit‑strings to less frequent ones. The resulting binary stream is usually smaller than the original text because the average bits per character drops below the original 8‑bits per character.

Key properties:

• Loss‑less – Original data can be perfectly reconstructed.
• Prefix‑free – No code is a prefix of another, guaranteeing unambiguous decoding.
• Optimal for a given character frequency distribution.

---

How the Project Works

1. Read input text and count the frequency of each character.
2. Build a min‑heap of Node objects (each node holds a character and its frequency).
3. Iteratively merge the two lowest‑frequency nodes until a single root node remains – this forms the Huffman tree.
4. Traverse the tree to generate a binary code for every character (left = 0, right = 1).
5. Encode the original text using the generated codes, producing a long bit string.
6. Pack bits into bytes (adding padding as needed) and write a .huffman file that stores:
   • Size of the frequency table (4‑byte header)
   • The JSON‑encoded frequency table (needed for reconstruction)
   • One byte for the padding length
   • The compressed byte payload
7. Decompression reads the header, rebuilds the Huffman tree from the stored frequency table, and decodes the bit stream back to the original text.

---

Installation & Requirements

• Python 3.8+ (standard library only – no external dependencies)
• No third‑party packages required; the project uses heapq, json, and built‑ins.

# Clone repository (if not already done)
git clone <repo‑url>
cd "Huffman Compression"
# Run directly – no virtualenv needed
python3 huffman.py

---

Usage

When you run the script, you get an interactive menu:

Huffman Compression
1. Compress a file
2. Decompress a file
Enter your choice: 

Compress a file

1. Choose option 1.
2. Provide the full path to the plain‑text file you want to compress.
3. The program creates compressed.huffman in the current directory.
4. It prints the original size, compressed size, and compression percentage.

Decompress a file

1. Choose option 2.
2. Provide the path to a previously generated .huffman file.
3. The program writes the recovered text to decompressed.txt.

---

File Format Details

The .huffman binary file layout (all integers are big‑endian):

Bytes	Meaning
4	Length of the JSON‑encoded frequency table (uint32)
n	Frequency table JSON (UTF‑8)
1	Padding bits added to the final byte (uint8)
m	Compressed payload (packed bytes)

During decompression the program reads the first 4 bytes to know how many bytes to read for the frequency table, reconstructs the Huffman tree, then extracts the padding value and finally decodes the payload.

---

Step‑by‑Step Walkthrough

1. Input Text → Frequency Table

   for char in text:
       frequency_table[char] = frequency_table.get(char, 0) + 1

   Why? The algorithm needs to know how often each character appears.

2. Create Nodes & Heap

   nodes = [Node(ch, freq) for ch, freq in frequency_table.items()]
   heapq.heapify(nodes)   # turns list into a min‑heap

   Why? The smallest frequencies are always at the top, enabling efficient merging.

3. Build Huffman Tree

   while len(heap) > 1:
       left = heapq.heappop(heap)
       right = heapq.heappop(heap)
       merged = Node(freq=left.freq + right.freq, left=left, right=right)
       heapq.heappush(heap, merged)
   root = heap[0]

   Why? Merging the two lowest‑frequency nodes creates the optimal prefix tree.

4. Generate Codes (Depth‑First Traversal)

   def build_codes(node, prefix=""):
       if not node.left and not node.right:
           encoding_tbl[node.char] = prefix
           return
       if node.left:
           build_codes(node.left, prefix + "0")
       if node.right:
           build_codes(node.right, prefix + "1")

   Why? Left edge = 0, right edge = 1; the path from root to leaf becomes that character’s binary code.

5. Encode Text

   encoded = "".join(encoding_tbl[ch] for ch in text)

   Why? Replace each character with its binary code.

6. Pack Bits → Bytes

   # pad to full byte
   padding = (8 - len(encoded) % 8) % 8
   encoded += "0" * padding
   # convert every 8 bits to a byte
   byte_array = bytearray(int(encoded[i:i+8], 2) for i in range(0, len(encoded), 8))

   Why? Files store bytes, not individual bits. Padding ensures the final byte is complete.

7. Write Header & Payload (see File Format Details above).

8. Decompression mirrors steps 1‑7 in reverse: read header → rebuild tree → convert bytes back to bit string → strip padding → walk the tree to recover characters.

---

Visualization & Flowchart

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '20px', 'fontFamily': 'arial'}, 'flowchart': {'nodeSpacing': 120, 'rankSpacing': 120, 'padding': 20, 'curve': 'basis'}}}%%
flowchart TD
    subgraph Compression
        A["<b>1. Read Input File</b>"] --> B["<b>2. Count Frequencies</b>"]
        B --> C["<b>3. Create Nodes &amp; Min-Heap</b>"]
        C --> D["<b>4. Build Huffman Tree<br/>(merge smallest nodes)</b>"]
        D --> E["<b>5. Generate Encoding Table</b>"]
        E --> F["<b>6. Encode Text</b>"]
        F --> G["<b>7. Pack Bits into Bytes</b>"]
        G --> H["<b>8. Write Header + Payload</b>"]
        H --> I["<b>Compressed .huffman File</b>"]
    end

    subgraph Decompression
        K["<b>9. Read Header &amp; Frequency Table</b>"] --> L["<b>10. Rebuild Huffman Tree</b>"]
        L --> M["<b>11. Read Payload Bytes</b>"]
        M --> N["<b>12. Remove Padding</b>"]
        N --> O["<b>13. Walk Tree to Decode</b>"]
        O --> P["<b>14. Write Decompressed Text</b>"]
    end

Loading

---

Example

# Compress a large text file (e.g., the Harry Potter novel)
python3 huffman.py
# Choose 1 and provide the path to the novel
# Output (example)
Compressed size: 254732 bytes
Uncompressed size: 442694 bytes
Compression Percentage: 57.5 %

# Decompress the result
python3 huffman.py
# Choose 2 and give path to compressed.huffman
# Output
Decompression complete. Decompressed file saved as decompressed.txt

You can compare decompressed.txt with the original file – they should be identical (use diff or checksum).

---

Testing

The repository includes two sample files:

• Harry Poter and the Philospher's Stone.txt (original text)
• compressed.huffman (generated by a previous run)
• decompressed.txt (result of decompression)

Run the script and verify:

python3 huffman.py   # compress
python3 huffman.py   # decompress
diff "Harry Poter and the Philospher's Stone.txt" decompressed.txt && echo "✅ Identical"

If the diff prints nothing and the final echo appears, the algorithm works correctly.

Happy coding!