Huffman Coding & Compression Algorithm

A modern, object-oriented Python implementation of the Huffman Coding lossless data compression algorithm.

---

Overview

Huffman Coding is a widely used algorithm for lossless data compression. First developed by David A. Huffman in 1952 (A Method for the Construction of Minimum-Redundancy Codes), the technique constructs optimal prefix codes based on character frequencies:

• Frequent characters receive shorter binary codes.
• Rare characters receive longer binary codes.
• Prefix-Free Guarantee: No code is a prefix of any other code, ensuring deterministic decoding without special delimiters.

---

Key Features

• Lossless Compression & Decompression: Complete pipeline for encoding arbitrary strings into bitstrings and reconstructing the original text without data loss.
• Custom Native Data Structures: Standalone, lightweight implementations of a Binary Heap (Heap) and a Circular Queue (Queue).
• Detailed Analytics: Real-time computation of compression percentage ratio, tree depth, and total node count.
• Pure Python: Zero external runtime dependencies for core algorithm operations.
• Developer-Friendly: Full type annotations, clean English docstrings, and comprehensive test suite compatible with pytest and Python's built-in unittest.

---

How It Works

flowchart TD
    A["Input Text"] --> B["1. Character Frequency Counting"]
    B --> C["2. Min-Heap Priority Queue"]
    C --> D["3. Build Binary Tree (Iterative Node Merge)"]
    D --> E["4. Generate Prefix Code Table (0: Left, 1: Right)"]
    E --> F["5. Encode to Bitstring"]
    F --> G["6. Decode via Tree Traversal to Restored Text"]

Loading

1. Frequency Analysis

The frequency of every distinct character in the text is measured:

Character	Frequency
space	3
a	3
m	2
i	2
p	2
s	2
o	2
r	2
n	1
e	1
g	1

2. Huffman Tree Construction

Nodes are inserted into a priority heap and merged iteratively by combining the two lowest-frequency nodes until a single root remains:

               [Root: Total Weight]
                   /         \
              (0) /           \ (1)
                 /             \
            [Left Child]   [Right Child]

3. Binary Code Table

Traversing from root to leaf generates the unique binary code for each character:

Character	Huffman Code
space	000
r	001
e	01000
n	01001
o	0101
g	0110
s	0111
a	100
p	101
i	110
m	111

---

Installation & Environment Setup

This project uses pyenv for managing Python versions and standard virtual environments.

1. Prerequisites

Ensure you have pyenv installed and configured in your shell.

2. Set Python Version with pyenv

Set the local Python version (e.g., Python 3.12+):

# Optional: install the Python version if not already installed
pyenv install 3.12.13

# Set the local Python version for this project
pyenv local 3.12.13

This creates/uses the .python-version file in the project root.

3. Create and Activate Virtual Environment

# Create virtual environment
python -m venv .venv

# Activate virtual environment
# On Linux / macOS:
source .venv/bin/activate

# On Windows (PowerShell):
.venv\Scripts\Activate.ps1

4. Install Dependencies

Install development and test dependencies:

pip install --upgrade pip
pip install -r requirements.txt

(Optional) Install the package locally in editable mode:

pip install -e .

---

Usage Guide

1. Quick Demonstration

Run the included demonstration script to verify functionality:

python example.py

2. Python API Usage

Basic Encoding & Decoding

from huffman import HuffmanCoding, HuffmanDecoding

# Sample input text
text = "Lossless compression with Huffman coding!"

# 1. Initialize encoder and encode text
encoder = HuffmanCoding()
encoded_bits = encoder.encode(text)

print("Encoded bits:", encoded_bits)
print("Code Table:  ", encoder.get_table())
print("Summary:     ", encoder.get_summary())

# 2. Initialize decoder and restore text
decoder = HuffmanDecoding()
restored_text = decoder.decode(encoded_bits, encoder.get_tree())

print("Restored:    ", restored_text)
assert text == restored_text

Exporting Binary Output to File

You can optionally write the encoded bitstream directly to a binary file:

encoder = HuffmanCoding()
encoded_bits = encoder.encode("Text to compress", output_path="compressed.bin")

---

Project Structure

├── .python-version              # Local Python version managed by pyenv
├── huffman/                     # Main algorithm package
│   ├── __init__.py              # Package exports
│   ├── huffmanbinarytree.py     # Binary tree node and traversal methods
│   ├── huffmancoding.py         # Huffman encoder & frequency table builder
│   ├── huffmandecoding.py       # Huffman decoder
│   ├── heap.py                  # Custom binary heap implementation
│   └── queue.py                 # Custom circular queue implementation
├── resources/                   # Sample benchmark and test files
├── tests/                       # Automated test suite
│   ├── test_huffman.py          # End-to-end compression test cases
│   └── test_huffmanTree.py      # Binary tree unit tests
├── example.py                   # Quickstart demo script
├── requirements.txt             # Development and test dependencies
├── setup.py                     # Package setup metadata
├── LICENSE                      # MIT License
└── README.md                    # Project documentation

---

API Reference

HuffmanCoding

• encode(text: str, output_path: Optional[str] = None) -> str: Encodes the input string into a binary bitstring. Optionally writes raw binary bytes to output_path.
• get_tree() -> HuffmanBinaryTree: Returns the constructed Huffman binary tree root node.
• get_table() -> Dict[str, str]: Returns the dictionary mapping characters to prefix bitstrings.
• get_summary() -> Dict[str, object]: Returns summary metrics (percentage_compression, depth_tree, quantity_nodes).

HuffmanDecoding

• decode(text: str, tree: HuffmanBinaryTree) -> str: Decodes a binary bitstring back into the original plain text using the tree.

HuffmanBinaryTree

• get_number_key() -> int: Returns the numeric frequency, or -1 if it is a character leaf node.
• get_left() -> Optional[HuffmanBinaryTree]: Returns the left child node.
• get_right() -> Optional[HuffmanBinaryTree]: Returns the right child node.
• calculate_depth() -> int: Computes the maximum height/depth of the tree.
• count_nodes() -> int: Computes the total number of nodes in the tree.

---

Running Tests & Linting

Run Tests with pytest

pytest -v

Run Tests with Python's Built-in unittest

python -m unittest discover tests -v

Code Quality Check with ruff

ruff check .

---

License

This project is licensed under the MIT License.