names

• aymen benlamari
• Lebdi Med Fakher Eddine

teacher

Noureddine GHOGGALI

Huffman Coding Implementation

This project implements Huffman coding, a lossless data compression algorithm that assigns variable-length codes to characters based on their frequency of occurrence.

Overview

Huffman coding works by:

1. Counting character frequencies in the input text
2. Building a binary tree where frequently occurring characters have shorter code paths
3. Generating binary codes for each character
4. Encoding the text using these codes
5. Decoding the binary data back to the original text using the tree

Files

HM_coding.py - Encoding Script

This is the main encoding script that:

• Takes user input text
• Builds a Huffman tree from character frequencies
• Generates binary codes for each character
• Encodes the entire text into a binary string
• Saves the tree and encoded data to files for later decoding

Output files:

• tree.pkl - The Huffman tree (pickled for storage)
• encoded.txt - The encoded binary string

HM_decoding.py - Decoding Script

This script reverses the encoding process:

• Loads the saved Huffman tree from tree.pkl
• Loads the encoded binary string from encoded.txt
• Traverses the tree using the binary digits (0 = left, 1 = right)
• Reconstructs the original text

How It Works

1. Node Class

class Node:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char          # The character (None for internal nodes)
        self.freq = freq          # Frequency count
        self.left = left          # Left subtree
        self.right = right        # Right subtree

2. Building the Huffman Tree

The algorithm uses a min-heap to efficiently build the tree:

• Create leaf nodes for each character
• Repeatedly merge the two nodes with smallest frequencies
• Continue until only one node remains (the root)

Example:

Text: "hello"

Frequencies: h:1, e:1, l:2, o:1

Tree structure:
       (5)
      /   \
    (2)   (3)
    / \   / \
   l   h e   o

Codes: h→00, e→01, l→1, o→10
Encoded: "00 1 1 10 01" → "00111001"

3. Encoding Process

For each character in the text, the corresponding binary code is appended to create the encoded string.

Time Complexity: O(n log k) where n = text length, k = number of unique characters

4. Decoding Process

Starting from the root of the tree:

• Read each binary digit from the encoded string
• Go left for 0, right for 1
• When reaching a leaf node, append the character to the result
• Reset to root and continue

Time Complexity: O(m) where m = encoded text length

Usage

Step 1: Encode Text

Run the encoding script:

python HM_coding.py

Enter your text when prompted. This generates:

• tree.pkl - The Huffman tree
• encoded.txt - The compressed binary data

Step 2: Decode Text

Run the decoding script:

python decode_huffman.py

This will print the recovered original text.

Example

Input text: "huffman coding is awesome"

Output:

• Original size: 192 bits (24 characters × 8 bits)
• Compressed size: ~95 bits (approximately 50% compression)
• Codes generated for each unique character
• Encoded binary string saved to encoded.txt
• Tree saved to tree.pkl