What is Huffman Coding Algorithm?

Last updated on January 5th, 2025 at 01:36 am

This article the what is Huffman coding algorithm, its pseudocode, steps, examples, and implementations in Java and Python.

1. What is Huffman Coding Algorithm?

Huffman Coding Algorithm is a common technique of encoding, including lossless data compression means reducing the size of files without losing any information. Huffman Coding is based on the frequency of occurrence of a data item (pixel in images). The main aim of Huffman coding is to encode the data that occurs frequently using less number of bits.

Huffman Coding Algorithm assigns shorter binary codes to frequently occurring characters and longer codes to less frequent ones. This ensures that the overall size of the encoded data is minimized.

Huffman codes can be constructed using the following two ideas:

1. For an optimum code, symbols that have high probability should be assigned shorter code words.
2. To make optimum prefix code, two symbols that occur least frequently should be assigned the same length.

2. How Does Huffman Coding Algorithm Work?

The Huffman Coding Algorithm works by creating a binary tree based on the frequency of characters in a dataset. The tree is constructed by recursively combining the two nodes with the lowest frequencies until only one node remains. The resulting tree is then used to generate prefix codes for each character.

3. Huffman Coding Algorithm Pseudocode

The pseudocode for the Huffman Coding Algorithm is as follows:

1. Count the frequency of each character in the input data.  
2. Create a priority queue (min-heap) and insert all characters as nodes with their frequencies.  
3. While the queue has more than one node:  
   a. Remove the two nodes with the smallest frequencies.  
   b. Create a new node with these two nodes as children.  
   c. Assign the new node a frequency equal to the sum of the two nodes.  
   d. Insert the new node back into the queue.  
4. The remaining node is the root of the Huffman Tree.  
5. Traverse the tree to assign binary codes to each character.  

4. Huffman Coding Algorithm Steps

The steps involved in implementing the Huffman Coding Algorithm are:

1. Data Collection: Gather the data to be compressed.
2. Frequency Analysis: Create a frequency table for the characters in the dataset.
3. Tree Construction: Build the binary tree using the frequency table.
4. Code Generation: Generate prefix codes for each character based on the binary tree.
5. Encoding: Use the prefix codes to encode the original data.

5. Huffman Coding Algorithm Example

Suppose we have a dataset with the following characters and frequencies:

A	15
B	7
C	6
D	5
E	3

Using the Huffman Coding Algorithm, we can construct the following binary tree:

    _______
   /       \
  A(15)    _______
           /       \
          B(7)    _______
                   /       \
                  C(6)    _______
                           /       \
                          D(5)    E(3)

The resulting prefix codes for each character are:

A	0
B	10
C	110
D	1110
E	1111

6. Code Implementation of Huffman Coding

6.1 Huffman Coding Algorithm Java Implementation

import java.util.PriorityQueue;
import java.util.HashMap;
import java.util.Map;

public class HuffmanCoding {
    public static void main(String[] args) {
        // Example input: characters and their frequencies
        char[] characters = {'A', 'B', 'C', 'D', 'E'};
        int[] frequencies = {15, 7, 6, 5, 3};

        // Build the Huffman Tree
        Node root = buildTree(characters, frequencies);

        // Generate and print the Huffman Codes
        System.out.println("Huffman Codes:");
        generateCodes(root, "");
    }

    // Node class representing a node in the Huffman Tree
    static class Node implements Comparable<Node> {
        char character; // Character (for leaf nodes)
        int frequency;  // Frequency of the character
        Node left;      // Left child
        Node right;     // Right child

        // Constructor for leaf nodes
        public Node(char character, int frequency) {
            this.character = character;
            this.frequency = frequency;
        }

        // Constructor for internal nodes
        public Node(int frequency, Node left, Node right) {
            this.character = '\0'; // Internal nodes don't represent a character
            this.frequency = frequency;
            this.left = left;
            this.right = right;
        }

        // Compare nodes based on their frequency (for PriorityQueue)
        @Override
        public int compareTo(Node other) {
            return this.frequency - other.frequency;
        }
    }

    // Build the Huffman Tree
    public static Node buildTree(char[] characters, int[] frequencies) {
        // Create a priority queue to store nodes
        PriorityQueue<Node> queue = new PriorityQueue<>();

        // Add all characters as leaf nodes to the priority queue
        for (int i = 0; i < characters.length; i++) {
            queue.add(new Node(characters[i], frequencies[i]));
        }

        // Build the Huffman Tree
        while (queue.size() > 1) {
            // Remove the two nodes with the smallest frequencies
            Node node1 = queue.poll();
            Node node2 = queue.poll();

            // Create a new internal node with these two nodes as children
            Node newNode = new Node(node1.frequency + node2.frequency, node1, node2);

            // Add the new node back to the queue
            queue.add(newNode);
        }

        // The remaining node is the root of the Huffman Tree
        return queue.poll();
    }

    // Generate and print Huffman Codes
    public static void generateCodes(Node root, String code) {
        if (root == null) {
            return;
        }

        // If this is a leaf node, print the character and its code
        if (root.left == null && root.right == null) {
            System.out.println("Character: " + root.character + ", Code: " + code);
            return;
        }

        // Traverse the left and right subtrees
        generateCodes(root.left, code + "0");
        generateCodes(root.right, code + "1");
    }
}

6.2 Huffman Coding Algorithm Python

import heapq

# Node class to represent a node in the Huffman Tree
class Node:
    def __init__(self, data, freq):
        self.data = data  # Character
        self.freq = freq  # Frequency of the character
        self.left = None  # Left child
        self.right = None  # Right child

    # Overriding the less-than operator for priority queue comparison
    def __lt__(self, other):
        return self.freq < other.freq

# Function to print the Huffman Codes by traversing the tree
def printCodes(root, code):
    if root is None:
        return

    # If this is a leaf node, print the character and its code
    if root.data != '$':  # '$' is used as a placeholder for internal nodes
        print(f'{root.data}: {code}')

    # Traverse the left and right subtrees
    printCodes(root.left, code + '0')
    printCodes(root.right, code + '1')

# Function to build the Huffman Tree and generate codes
def HuffmanCodes(data, freq):
    # Create a priority queue (min-heap) to store nodes
    minHeap = []

    # Add all characters as leaf nodes to the priority queue
    for i in range(len(data)):
        heapq.heappush(minHeap, Node(data[i], freq[i]))

    # Build the Huffman Tree
    while len(minHeap) > 1:
        # Remove the two nodes with the smallest frequencies
        left = heapq.heappop(minHeap)
        right = heapq.heappop(minHeap)

        # Create a new internal node with these two nodes as children
        top = Node('$', left.freq + right.freq)
        top.left = left
        top.right = right

        # Add the new node back to the priority queue
        heapq.heappush(minHeap, top)

    # The remaining node is the root of the Huffman Tree
    root = heapq.heappop(minHeap)

    # Print the Huffman Codes by traversing the tree
    print("Huffman Codes:")
    printCodes(root, '')

# Example input: characters and their frequencies
arr = ['A', 'B', 'C', 'D', 'E']
freq = [15, 7, 6, 5, 4]

# Generate Huffman Codes
HuffmanCodes(arr, freq)

7. Advantages of Huffman Coding

1. Optimality: Huffman coding is optimal for a set of symbols with known probabilities.
2. Lossless Compression: Ensures no loss of data.
3. Efficiency: Suitable for compressing data with variable-length encoding.

8. Disadvantages of Huffman Coding

1. Complexity: More complex to implement compared to simpler methods like run-length encoding.
2. Dependency on Data: Performance depends on the frequency distribution of the data.
3. Decompression Speed: Decompression can be slower as each bit needs to be checked against the tree.

9. Time Complexity of Huffman Coding

The Overall Time Complexity of Huffman’s algorithm is O(n log n).

FAQs