Huffman Coding Algorithm Tutorial

First, we import the necessary libraries and define the HuffmanNode class.

import heapq
from collections import defaultdict, Counter

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

• heapq: This is used to implement a priority queue.
• Counter: This is used to count the frequency of characters in the text.
• HuffmanNode Class: This class represents a node in the Huffman Tree.
  • __init__: Initializes a node with a character and its frequency. left and right are set to None initially.
  • __lt__: Defines the less-than operator to compare nodes based on frequency. This is necessary for the priority queue to work correctly.

Next, we define the function to build the Huffman Tree.

def build_huffman_tree(text):
    frequency = Counter(text)
    priority_queue = [HuffmanNode(char, freq) for char, freq in frequency.items()]
    heapq.heapify(priority_queue)
    
    while len(priority_queue) > 1:
        left = heapq.heappop(priority_queue)
        right = heapq.heappop(priority_queue)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(priority_queue, merged)
    
    return priority_queue[0]

• Frequency Calculation: Counter(text) creates a dictionary where the keys are characters and the values are their frequencies.
• Priority Queue Initialization: We create a list of HuffmanNode objects for each character-frequency pair and convert it into a heap using heapq.heapify().
• Building the Tree:
  • We repeatedly pop the two nodes with the smallest frequencies from the heap.
  • We create a new HuffmanNode with these two nodes as children and a frequency equal to their sum.
  • We push the new node back into the heap.
  • This process continues until there is only one node left in the heap, which is the root of the Huffman Tree.

Now, we define the function to assign Huffman codes to each character by traversing the tree.

def assign_codes(node, current_code, codes):
    if node is None:
        return
    if node.char is not None:
        codes[node.char] = current_code
    assign_codes(node.left, current_code + '0', codes)
    assign_codes(node.right, current_code + '1', codes)

• Base Case: If the current node is None, we return.
• Leaf Node: If the current node has a character (node.char is not None), we assign the current code to this character.
• Recursive Case: We recursively call the function for the left and right children, appending '0' for the left edge and '1' for the right edge.

Finally, we define the function to encode the input text using the Huffman Tree.

def huffman_encoding(text):
    root = build_huffman_tree(text)
    codes = {}
    assign_codes(root, '', codes)
    encoded_text = ''.join(codes[char] for char in text)
    return encoded_text, codes

• Build the Huffman Tree: We call build_huffman_tree to get the root of the tree.
• Assign Codes: We call assign_codes to get the Huffman codes for each character.
• Encode the Text: We create the encoded text by replacing each character in the input text with its corresponding Huffman code.
• Return: We return the encoded text and the dictionary of codes.

Here's how you can use the above functions in a complete program:

if __name__ == "__main__":
    text = "huffman coding example"
    encoded_text, codes = huffman_encoding(text)
    print("Encoded Text:", encoded_text)
    print("Huffman Codes:", codes)

• Input Text: "huffman coding example"
• Output:
  • Encoded Text: The binary representation of the input string.
  • Huffman Codes: A dictionary with characters as keys and their corresponding Huffman codes as values.