Huffman Encoding in DSA C - Build from Scratch

Huffman Encoding

📖 Scenario: You work for a company that compresses text files to save storage space. Huffman encoding is a method to compress data by assigning shorter codes to frequent characters and longer codes to rare characters.In this project, you will build a simple Huffman encoding setup in C. You will start by creating a frequency table for characters, then build the Huffman tree structure, and finally print the Huffman codes for each character.

🎯 Goal: Build a program that creates a frequency table for characters, builds a Huffman tree, and prints the Huffman codes for each character.

📋 What You'll Learn

Create a frequency table for given characters

Define a struct for Huffman tree nodes

Build a simple Huffman tree using the frequency table

Print the Huffman codes for each character

💡 Why This Matters

🌍 Real World

Huffman encoding is used in file compression tools like ZIP and image formats like JPEG to reduce file size.

💼 Career

Understanding Huffman encoding helps in roles related to data compression, storage optimization, and efficient data transmission.

1

Create the frequency table

Create an integer array called freq of size 5 and initialize it with these exact values: 5, 9, 12, 13, 16. These represent the frequencies of characters 'A', 'B', 'C', 'D', and 'E' respectively.

DSA C

# Create the frequency array freq with values 5, 9, 12, 13, 16
// Your code here

Hint

Use int freq[5] = {5, 9, 12, 13, 16}; to create the frequency array.

2

Define the Huffman tree node struct

Define a struct called Node with these exact members: char ch, int freq, struct Node *left, and struct Node *right.

DSA C

#include 

// Define the struct Node with members ch, freq, left, right
// Your code here

int main() {
    int freq[5] = {5, 9, 12, 13, 16};
    return 0;
}

Hint

Use struct Node { char ch; int freq; struct Node *left; struct Node *right; }; to define the node.

3

Create leaf nodes for each character

Create an array called nodes of 5 Node structs. Initialize each node with characters 'A', 'B', 'C', 'D', 'E' and their corresponding frequencies from freq. Set left and right pointers to NULL.

DSA C

#include 

struct Node {
    char ch;
    int freq;
    struct Node *left;
    struct Node *right;
};

int main() {
    int freq[5] = {5, 9, 12, 13, 16};

    // Create nodes array and initialize with characters and frequencies
    // Your code here

    return 0;
}

Hint

Initialize each node with {'A', freq[0], NULL, NULL} style syntax.

4

Print the characters and their frequencies

Use a for loop with variable i from 0 to 4 to print each node's ch and freq in the format: Character: X, Frequency: Y.

DSA C

#include 

struct Node {
    char ch;
    int freq;
    struct Node *left;
    struct Node *right;
};

int main() {
    int freq[5] = {5, 9, 12, 13, 16};

    struct Node nodes[5] = {
        {'A', freq[0], NULL, NULL},
        {'B', freq[1], NULL, NULL},
        {'C', freq[2], NULL, NULL},
        {'D', freq[3], NULL, NULL},
        {'E', freq[4], NULL, NULL}
    };

    // Print characters and frequencies
    // Your code here

    return 0;
}

Hint

Use for (int i = 0; i < 5; i++) and printf("Character: %c, Frequency: %d\n", nodes[i].ch, nodes[i].freq);.

Practice

1. What is the main goal of Huffman Encoding in data compression?

easy

A. To assign equal length codes to all characters

B. To assign shorter codes to more frequent characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by giving shorter codes to characters that appear more often.

2. Step 2: Compare options with this purpose

   Only To assign shorter codes to more frequent characters matches this goal; others describe different concepts.

3. Final Answer:

   To assign shorter codes to more frequent characters -> Option B

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes in Huffman [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing compression with encryption
• Assuming sorting is the main goal

2. Which data structure is primarily used to build the Huffman tree?

easy

A. Priority Queue (Min-Heap)

B. Stack

C. Queue

D. Hash Table

Solution

1. Step 1: Identify data structure for selecting smallest frequencies

   Huffman tree construction repeatedly picks two smallest frequency nodes.

2. Step 2: Match with data structure that supports this

   Priority Queue (Min-Heap) efficiently provides smallest elements first.

3. Final Answer:

   Priority Queue (Min-Heap) -> Option A

4. Quick Check:

   Smallest freq nodes from Min-Heap [OK]

Hint: Huffman uses Min-Heap to pick smallest frequencies fast [OK]

Common Mistakes:

• Choosing Stack or Queue which don't sort by frequency
• Confusing Hash Table with frequency sorting
• Ignoring the need for smallest frequency extraction

3. What is the output Huffman code for characters with frequencies: A=5, B=9, C=12, D=13, E=16, F=45?

Assuming standard Huffman tree construction, what is the code for character 'F'?

medium

A. 0

B. 10

C. 110

D. 111

Solution

1. Step 1: Build Huffman tree with given frequencies

   Combine smallest pairs: (A=5,B=9)=14, (C=12,D=13)=25, then combine 14 and 16 (E) = 30, then 25 and 30 = 55, finally combine 45 (F) and 55 = 100.

2. Step 2: Assign codes from root; 'F' is combined last and placed on left branch

   Since 'F' has highest frequency, it gets the shortest code '0'.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Highest freq char gets shortest code '0' [OK]

Hint: Highest frequency char gets code '0' in Huffman [OK]

Common Mistakes:

• Assigning longer codes to highest frequency character
• Mixing up left/right branch codes
• Not building tree step-by-step

4. Consider this C code snippet for building a Huffman tree:

struct Node {
  char data;
  int freq;
  struct Node *left, *right;
};

// Function to create a new node
struct Node* newNode(char data, int freq) {
  struct Node* temp = malloc(sizeof(struct Node));
  temp->data = data;
  temp->freq = freq;
  temp->left = temp->right = NULL;
  return temp;
}

// Code to combine two nodes
struct Node* combineNodes(struct Node* left, struct Node* right) {
  struct Node* parent = newNode('$', left->freq + right->freq);
  parent->left = left;
  parent->right = right;
  return parent;
}

// Usage:
struct Node* n1 = newNode('A', 5);
struct Node* n2 = newNode('B', 9);
struct Node* parent = combineNodes(n1, n2);

printf("Parent freq: %d\n", parent->freq);

What is the output of this code?

medium

A. Parent freq: 5

B. Parent freq: 9

C. Compilation error

D. Parent freq: 14

Solution

1. Step 1: Understand node creation and combination

   n1 has freq 5, n2 has freq 9; combineNodes sums frequencies: 5 + 9 = 14.

2. Step 2: Print parent frequency

   parent->freq is 14, so printf outputs "Parent freq: 14".

3. Final Answer:

   Parent freq: 14 -> Option D

4. Quick Check:

   5 + 9 = 14 frequency sum [OK]

Hint: Sum frequencies when combining nodes for parent freq [OK]

Common Mistakes:

• Printing child node frequency instead of parent
• Forgetting to sum frequencies
• Assuming compilation error due to struct usage

5. You have characters with frequencies: X=3, Y=3, Z=3, W=3. Using Huffman Encoding, what is the minimum total number of bits needed to encode the string "XYZWXYZW" (8 characters)?

hard

A. 12 bits

B. 24 bits

C. 16 bits

D. 8 bits

Solution

1. Step 1: Build Huffman tree for equal frequencies

   All characters have equal frequency (3), so Huffman codes will have equal length, typically 2 bits each (since 4 chars need 2 bits minimum).

2. Step 2: Calculate total bits for 8 characters

   Each character uses 2 bits, total bits = 8 * 2 = 16 bits.

3. Step 3: Re-examine options and problem

   Options include 16 and 24 bits. Since each char is 2 bits, total is 16 bits, but 24 bits is 24 bits. The string length is 8, so 8*2=16 bits is correct.

4. Final Answer:

   16 bits -> Option C

5. Quick Check:

   4 chars need 2 bits each, 8 chars total = 16 bits [OK]

Hint: Equal freq chars get equal length codes; multiply length by count [OK]

Common Mistakes:

• Assuming 1 bit per char incorrectly
• Multiplying frequency instead of code length
• Choosing 24 bits thinking 3 bits per char