• Articles
  • Tutorials
  • Interview Questions
  • Webinars

What is Huffman Coding in DAA?

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:

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.

Want a comprehensive list of interview questions? Here are the Full Stack developer interview questions!

Steps in Huffman Coding

Consider an input string with character frequencies:

a=50, b= 10, c=30, d=5, e=3, f= 2

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 1 of Huffman Coding

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

Step 2 of Huffman Coding 

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.

Step3 of Huffman Coding 

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

Step 4 of Huffman Coding 

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

Step 5 of Huffman Coding

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

Huffman Tree

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

Assigned Huffman Tree

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:

CharacterBinary CodeNumber of bitsFrequency Total number of bits
a015050*1=50
b10031010*3=30
c1123030*2=60
d1010455*4=20
e10111533*5=15
f10110522*5=10

Total number of bits = 185

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

Get 100% Hike!

Master Most in Demand Skills Now !

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.

Want a comprehensive list of interview questions? Here are the Full Stack developer interview questions!

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:

FeatureHuffman CodingArithmetic Coding
Coding TechniqueVariable-Length Prefix CodesReal-Valued Cumulative Probability Ranges
Code EfficiencyNear-optimal, especially for symbols with distinct weightsTheoretically optimal, more efficient for correlated data
AdaptabilityAdapts well to changing symbol frequenciesHighly adaptive, suitable for dynamic and varied datasets
ComplexityGenerally simpler to implementMore complex, involving fractional arithmetic operations
Code LengthFixed number of bits for each symbolVariable-length codes based on probability distributions
Decoding ComplexityRelatively simpler decoding processMore complex decoding process, especially for beginners
Compression RatioEffective for symbols with distinct frequenciesSuitable for correlated data, may outperform in some cases
Usage AreasWidely used in text and file compression (e.g., ZIP files)Common in image and video compression (e.g., JPEG, MPEG)
Memory RequirementRequires storing Huffman tree structureRequires storing probability ranges for each symbol
Error SensitivityLess sensitive to errors due to its tree-based structureMore sensitive to errors as it relies on precise ranges
Real-Time ApplicationsSuitable for real-time applications, especially with static dataEfficient for real-time scenarios, especially with dynamic data

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.

Still, have queries? You can post your doubts on our Community page.

FAQs

What is Huffman Coding used for?

Huffman Coding is primarily used for lossless data compression, where it efficiently reduces the size of data by assigning variable-length codes to symbols based on their frequencies.

How does Huffman Coding achieve compression?

Huffman Coding achieves compression by assigning shorter codes to more frequent symbols and longer codes to less frequent symbols, optimizing the representation of information.

Is Huffman Coding suitable for all types of data?

While Huffman Coding is effective for various data types, its performance can be influenced by the distribution of symbol frequencies. It excels when there is a noticeable frequency disparity among symbols.

How is the Huffman Tree constructed?

The Huffman Tree is constructed by iteratively merging the two nodes with the lowest frequencies until a single root node is formed. This tree structure is then used to generate Huffman codes.

Can Huffman Coding be used for real-time applications?

Yes, Huffman Coding can be used in real-time applications due to its simplicity and efficiency. However, dynamic Huffman Coding may introduce additional overhead.

In Huffman’s coding and Airthematic coding, Which is better?

Between the two, Arithmetic Coding takes leverage due to improved efficiency. 

Course Schedule

Name Date Details
Python Course 22 Jun 2024(Sat-Sun) Weekend Batch
View Details
Python Course 29 Jun 2024(Sat-Sun) Weekend Batch
View Details
Python Course 06 Jul 2024(Sat-Sun) Weekend Batch
View Details

About the Author

Senior Consultant Analytics & Data Science

Presenting Sahil Mattoo, a Senior Consultant Analytics & Data Science at Eli Lilly and Company is an accomplished professional with 14 years of experience across data science, analytics, and technical leadership domains, demonstrates a remarkable ability to drive business insights. Sahil holds a Post Graduate Program in Business Analytics and Business Intelligence from Great Lakes Institute of Management.