Huffman Coding Algorithm

In computer systems, a large amount of data is generated every day in the form of text, images, audio, and videos. Storing and transmitting this data efficiently is an important challenge because larger data requires more storage space and more transmission time.

Data compression is a technique used to reduce the size of data by representing the same information using fewer bits. Compression helps in saving storage space and improving data transfer speed.

There are two main categories of data compression:

1. Lossy Compression
2. Lossless Compression

Lossy compression reduces the size of data by removing some information that may not be noticeable. Examples include image and video compression.

Lossless compression reduces the size of data without losing any information. After decompression, the original data can be perfectly recovered.

Huffman Coding is one of the most important lossless data compression techniques used in computer science.

It uses the frequency of characters to create an efficient binary encoding scheme where frequently occurring characters are assigned shorter codes and less frequently occurring characters are assigned longer codes.

What is Huffman Coding?

Huffman Coding is a greedy algorithm used for lossless data compression. It generates variable-length binary codes for characters based on their frequency of occurrence.

The main idea behind Huffman Coding is:

• Characters that appear more frequently should have shorter binary codes.
• Characters that appear less frequently should have longer binary codes.

This reduces the total number of bits required to represent a given message.

Huffman Coding was developed by David A. Huffman in 1952 while he was a PhD student at MIT. It became one of the most widely used techniques for constructing optimal prefix codes.

Need for Huffman Coding

To understand why Huffman Coding is required, first consider how characters are normally stored.

Computers represent data using binary values (0 and 1). Every character must be converted into a sequence of bits.

A simple method is fixed-length encoding.

Step-by-Step Algorithm

The process of generating Huffman codes involves five distinct phases:

• Step 1: Create a Priority Queue (Min-Heap): Every character is turned into a node containing its frequency and placed into a min-heap.
• Step 2: Build the Huffman Tree:
  • Extract the two nodes with the smallest frequencies.
  • Create a new internal node with a frequency equal to the sum of the two.
  • Insert this new node back into the heap.
  • Repeat until only one node (the root) remains.
• Step 3: Generate Codes: Traverse the tree from the root. Assign '0' for left branches and '1' for right branches until a leaf node is reached.
• Step 4: Calculate Total Encoded Length: Multiply each character's frequency by its code length and sum the results.
• Step 5: Calculate Average Code Length: Divide the total bits by the total frequency of all symbols.

Huffman Coding Calculation

Here’s a step-by-step explanation to calculate the Huffman code, length of the encoded data, and the average code length for the following frequency table: { A = 45, B = 13, C = 12, D = 16, E = 9, F = 5 }

Step 1: Build a Min-Heap (Priority Queue)

Start by placing all characters as leaf nodes in a priority queue, sorted by frequency: [F:5, E:9, C:12, B:13, D:16, A:45]

Step 2: Build the Huffman Tree

We repeatedly remove the two nodes with the lowest frequency, combine them into a new node, and reinsert it into the queue.

Iteration 1:

• Remove F (5) and E (9) → New node FE = 5 + 9 = 14
• Heap: [C:12, B:13, D:16, A:45, FE:14]

Iteration 2:

• Remove C (12) and B (13) → New node CB = 12 + 13 = 25
• Heap: [D:16, A:45, FE:14, CB:25]

Iteration 3:

• Remove FE (14) and D (16) → New node FED = 14 + 16 = 30
• Heap: [A:45, CB:25, FED:30]

Iteration 4:

• Remove CB (25) and FED (30) → New node CBFED = 25 + 30 = 55
• Heap: [A:45, CBFED:55]

Final Iteration:

• Remove A (45) and CBFED (55) → New node Root = 45 + 55 = 100
• Now, the tree is complete. Let’s move on to generating codes.

Step 3: Assign Huffman Codes (by Tree Traversal)

Assign

• 0 when going left
• 1 when going right

Start from the root and trace to each character.

             (100)
            /     \
         A(45)   (55)
                /    \
            (25)      (30)
           /   \      /   \
        C(12) B(13)  (14)  D(16)
                     /  \
                  F(5)   E(9)

Now, trace each character

Step 4: Calculate Encoded Data Length

Multiply each character's frequency by its code length.

Total Encoded Bits Data Length = 45 + 39 + 36 + 48 + 36 + 20 = 224 bits

Step 5: Calculate Average Code Length

Use the formula

• Average Code Length (bits per symbol) = (Total Encoded Data Length) / (Total Frequency)
• Total Frequency = 45 + 13 + 12 + 16 + 9 + 5 = 100
• Average Code Length (bits per symbol) = 224 / 100 = 2.24 bits/character

Final Results:

Huffman Codes

• A: 0
• B: 101
• C: 100
• D: 111
• E: 1101
• F: 1100

Total Encoded Length: 224 bits

Average Code Length: 2.24 bits per character

Applications of Huffman Coding

1. File Compression

Huffman Coding is used in compression algorithms to reduce file size.

Examples:

• ZIP files
• GZIP files

2. Image Compression

Huffman Coding is used as a part of image compression techniques.

Example:

• JPEG compression

3. Multimedia Compression

It helps reduce the size of:

• Audio files
• Video files
• Documents

4. Data Transmission

Compressed data requires fewer bits, reducing network bandwidth usage.

Advantages of Huffman Coding

1. Lossless Compression

The original data can be completely recovered.

2. Efficient Storage

It reduces the number of bits required to store information.

3. Optimal Prefix Code

Huffman Coding generates an efficient prefix-free code.

4. Simple Greedy Approach

The algorithm is easy to implement using a priority queue.

Disadvantages of Huffman Coding

1. Frequency Calculation Required

The algorithm requires character frequency information before compression.

2. Extra Storage for Tree

The Huffman Tree must be stored for decoding.

3. Not Suitable for All Data Types

Some already compressed formats may not benefit significantly.

Time and Space Complexity

Time Complexity: O(n log n) where n is the number of unique characters (due to priority queue operations).

Space Complexity: O(n) for storing the tree and the codes.

The Huffman Algorithm is a classic example of how greedy strategies and tree structures can be combined to solve real-world problems efficiently. It's not just theoretical it powers everyday technologies we use to store and transmit data.

By understanding how Huffman trees are built and how codes are assigned, you gain insights into both compression and algorithmic thinking.

Numerical Question

1. Given the following characters and their frequencies:

Tasks

• Build the Huffman tree.
• Generate the Huffman code for each character.
• Calculate the total encoded data length.
• Find the average code length.

2. Given these frequencies: {M: 35, N: 30, O: 20, P: 10, Q: 5}

Tasks

• Create the Huffman tree step-by-step.
• Show how the codes are generated.
• Calculate the total bits used to encode the data.
• Compute the average bits per symbol.

3. You are given the following symbols with their frequencies:

Tasks:

• Construct the full Huffman tree.
• Assign codes to each character.
• Find the total encoded data length.
• Compare it with fixed-length encoding (3 bits per symbol). How many bits are saved?

Summary

Huffman Coding is a fundamental lossless data compression algorithm that reduces data size by assigning shorter binary codes to frequently occurring characters and longer codes to less frequent characters.

It uses a greedy approach to construct a Huffman Tree, which generates prefix-free binary codes.

The main concepts behind Huffman Coding are:

• Frequency-based encoding
• Variable-length codes
• Prefix-free property
• Binary tree representation

Because of its efficiency and simplicity, Huffman Coding remains one of the most important compression techniques used in computer science and information technology.