What is Huffman Coding in DAA?

Let’s uncover how this algorithm transforms data into compact wonders, as in this blog we go through the definition, workings, complexities, and some advantages and disadvantages.

Table of Contents:

• What is Huffman Coding?
• Steps in Huffman Coding
• Implementation of Huffman Coding
• Complexities of Huffman Coding
• Advantages and Disadvantages of Huffman Coding
• Huffman Coding vs. Arithmetic Coding
• Wrap-up
• FAQs

Learn Data Structures and Algorithms in this comprehensive video course:

What is Huffman Coding?

Huffman coding in Design and Analysis of Algorithms (DAA) is a widely employed technique for lossless data compression, devised by David A. Huffman in 1952. The fundamental objective of Huffman coding is to reduce the amount of data needed to represent a set of symbols efficiently. 

It achieves this by assigning shorter binary codes to more frequently occurring symbols and longer codes to less common ones.

The process begins with a frequency analysis of the input data, determining the occurrence frequency of each symbol. Subsequently, a binary tree, termed the Huffman tree, is constructed based on these frequencies.

Symbols with higher frequencies are positioned closer to the root of the tree, while those with lower frequencies are located farther away. Binary codes are then assigned to each symbol according to the path from the root to the corresponding leaf in the tree. The result is a compressed representation of the original data, with shorter codes for more common symbols, facilitating efficient storage and transmission. 

Huffman coding finds widespread application in data compression, file formats, image compression, and various networking protocols due to its simplicity and effectiveness in achieving optimal compression under certain conditions.

Steps in Huffman Coding

Consider an input string with character frequencies:

The total number of characters is 100. Using ASCII coding within the range 0-127, we find that to represent a single character, 7 bits are needed. For 100 characters, this results in 700 bits.

The objective of Huffman coding is to compress data, aiming for smaller bit sizes. Let’s get into the steps of the Huffman Coding algorithm.

Step 1: Determine the frequency of each character and sort them in ascending order.

Step 2: Take two elements with the lowest frequency and merge them as shown in the figure.

Make sure to place the character with the lowest frequency on the left side and the character with the highest frequency on the right side.

Step 3: Add the merged element to the list and repeat the process by choosing elements with lower frequencies.

Step4: Repeat steps 2 and 3 for all other characters.

As 30 is greater than 20, it is placed on the right side of 20. 

After following all these steps, the Huffman Tree is formed.

Now, for each left tree node, assign 0, and for the right tree, assign 1.

Here’s a breakdown of the characters, their binary codes, the number of bits needed, and the total number of bits required for encoding using Huffman Coding:

Total number of bits = 185

This means that the total number of bits required for encoding this message using Huffman Coding is 185.

Implementation of Huffman Coding

Here’s a practical implementation of Huffman coding in Python programming language:

import heapq
from collections import defaultdict, Counter
class Node:
    def __init__(self, symbol, frequency):
        self.symbol = symbol
        self.frequency = frequency
        self.left = None
        self.right = None
    def __lt__(self, other):
        return self.frequency < other.frequency
def build_huffman_tree(data):
    frequency_counter = Counter(data)
    priority_queue = [Node(symbol, frequency) for symbol, frequency in frequency_counter.items()]
    heapq.heapify(priority_queue)
    while len(priority_queue) > 1:
        left_child = heapq.heappop(priority_queue)
        right_child = heapq.heappop(priority_queue)
        internal_node = Node(None, left_child.frequency + right_child.frequency)
        internal_node.left = left_child
        internal_node.right = right_child
        heapq.heappush(priority_queue, internal_node)
    return priority_queue[0]
def generate_huffman_codes(node, current_code="", codes=None):
    if codes is None:
        codes = {}
    if node is not None:
        if node.symbol is not None:
            codes[node.symbol] = current_code
        generate_huffman_codes(node.left, current_code + "0", codes)
        generate_huffman_codes(node.right, current_code + "1", codes)
    return codes
def huffman_encode(data):
    root = build_huffman_tree(data)
    codes = generate_huffman_codes(root)
    encoded_data = ''.join(codes[symbol] for symbol in data)
    return encoded_data, codes
def huffman_decode(encoded_data, codes):
    reversed_codes = {code: symbol for symbol, code in codes.items()}
    current_code = ""
    decoded_data = ""
    for bit in encoded_data:
        current_code += bit
        if current_code in reversed_codes:
            decoded_data += reversed_codes[current_code]
            current_code = ""
    return decoded_data
# Example usage:
if __name__ == "__main__":
    input_data = "Intellipaat Software Solutions!"
    encoded_data, huffman_codes = huffman_encode(input_data)
    print(f"Original Data: {input_data}")
    print(f"Encoded Data: {encoded_data}")
    decoded_data = huffman_decode(encoded_data, huffman_codes)
    print(f"Decoded Data: {decoded_data}")

Output:

Original Data: Intellipaat Software Solutions!

Encoded Data:

1011110101001110000000110011011001001100010101111111010011000100000110110111001010111
1111000110101001100111110100110101100

Decoded Data: Intellipaat Software Solutions!

This implementation defines a Node class to represent nodes in the Huffman tree and includes functions for building the tree, generating Huffman codes, and encoding/decoding data. The example usage demonstrates encoding and decoding a simple string.

Complexities of Huffman Coding

The complexities of Huffman Coding involve both time and space considerations. Here are the key complexities associated with Huffman Coding:

• Time Complexity: Time complexity is the measure of how long an algorithm takes to run as the input size increases.
  • Building the Huffman Tree: The time complexity for building the Huffman tree is O(n log n), where n is the number of unique symbols in the input data. This is because, in each iteration, we perform operations (heap push and pop) that take O(log n) time, and we do this n times.
  • Generating Huffman Codes: The time complexity for generating Huffman codes after building the tree is O(n), where n is the number of unique symbols. This is because we traverse the Huffman tree once to assign binary codes to each symbol.
  • Encoding and Decoding: The time complexity for encoding and decoding is O(m), where m is the length of the input data. This is because, for each symbol, we perform constant-time operations (looking up the code or decoding it).
• Space Complexity: Space complexity is the amount of memory required by an algorithm to execute.
  • Huffman Tree: The space complexity for storing the Huffman tree is O(n), where n is the number of unique symbols. This accounts for the nodes in the tree.
  • Code Storage: The space complexity for storing Huffman codes is O(n), where n is the number of unique symbols. This is because, in the worst case, each symbol has its own unique binary code.
  • Encoded Data: The space complexity for the encoded data is O(m), where m is the length of the input data. This is the space required to store the binary representation of the original data.

Advantages and Disadvantages of Huffman Coding

Understanding the advantages and disadvantages of Huffman coding is crucial,  as its importance lies in its efficiency in data compression, making it a widely used algorithm in various applications.  Below are some advantages and disadvantages of the Huffman Coding algorithm:

• Advantages
  • Efficient data compression occurs through variable-length codes.
  • Lossless compression, allowing perfect reconstruction of the original data.
  • Adaptability to diverse input data characteristics for optimal compression.
  • Relatively simple implementation, accessible for a wide range of applications.
  • No preprocessing is required, making it suitable for streaming and on-the-fly compression.

• Disadvantages
  • Variable-length codes may introduce decoding challenges.
  • Sensitivity to changes in the distribution of symbol frequencies.
  • Overhead for small datasets, potentially offsetting compression benefits.
  • Not always the most efficient compression method in all scenarios.
  • Compression and decompression overhead, especially for dynamic Huffman Coding.

Huffman Coding vs Arithmetic Coding

The main difference between Huffman coding and Aithematic coding is that Huffman coding uses statistical methods that do not provide optimum results while Airthematic coding provides optimum results.
For example, if x,y,z are messages, separate codes will be used for them in Huffman’s coding while in Airthematic coding, only one code will represent these.
Here’s a tabular difference between Huffman coding and arithmetic coding:

Wrap-up

Huffman Coding is a data compression fundamental that excels at effectively representing information with the least amount of redundancy. It accomplishes optimal compression and makes resource conservation easier by giving shorter codes to frequently occurring symbols. The algorithm is a useful tool in many different fields because of its simplicity and adaptability, even though it is sensitive to changes in symbol frequencies. Huffman Coding is important in the ever-changing field of data management because it influences networking, multimedia applications, and file compression. Because of its ability to strike a balance between simplicity and efficiency, this algorithm is both elegant and widely used in the field of information technology.

FAQs