Huffman Encoding in DSA Python - Build from Scratch

Huffman Encoding

📖 Scenario: You work for a company that wants to compress text messages to save space. Huffman encoding is a way to assign shorter codes to frequent letters and longer codes to rare letters, making the message smaller.

🎯 Goal: Build a simple Huffman encoding program that creates a frequency dictionary, builds a Huffman tree, generates codes for each character, and prints the codes.

📋 What You'll Learn

Create a dictionary with exact character frequencies

Create a priority queue using a list of tuples

Build the Huffman tree by combining nodes with lowest frequencies

Generate Huffman codes using a recursive function

Print the final Huffman codes dictionary

💡 Why This Matters

🌍 Real World

Huffman encoding is used in file compression formats like ZIP and image formats like JPEG to reduce file size by encoding frequent data with fewer bits.

💼 Career

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

1

Create the frequency dictionary

Create a dictionary called freq with these exact character frequencies: 'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45.

DSA Python

# Your code here

Hint

Use curly braces to create a dictionary with the exact keys and values.

2

Create the priority queue list

Create a list called priority_queue that contains tuples of (frequency, character) for each item in freq.items(). Use a list comprehension.

DSA Python

freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
# Your code here

Hint

Use a list comprehension to create tuples of (frequency, character).

3

Build the Huffman tree

Use a while loop that runs while len(priority_queue) > 1. Inside the loop, sort priority_queue, pop the two smallest items, combine them into a new node with summed frequency, and append the new node back to priority_queue. Use tuples where the first element is frequency and the second is either a character or a tuple representing a subtree.

DSA Python

freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
priority_queue = [(freq[char], char) for char in freq]
# Your code here

Hint

Sort the list by frequency, pop two smallest, combine, and append back.

4

Generate and print Huffman codes

Define a recursive function called generate_codes that takes node and prefix (default empty string). If node[1] is a character (string), add prefix to a dictionary codes with key node[1]. Otherwise, recursively call generate_codes on left and right children with prefix + '0' and prefix + '1'. Call generate_codes on the root node in priority_queue[0]. Finally, print the codes dictionary.

DSA Python

freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
priority_queue = [(freq[char], char) for char in freq]

while len(priority_queue) > 1:
    priority_queue.sort(key=lambda x: x[0])
    left = priority_queue.pop(0)
    right = priority_queue.pop(0)
    combined_freq = left[0] + right[0]
    new_node = (combined_freq, (left, right))
    priority_queue.append(new_node)

# Your code here

Hint

Use recursion to assign '0' to left and '1' to right branches. Store codes in a dictionary and print it.

Practice

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

easy

A. To encrypt data for security

B. To assign equal length codes to all characters

C. To assign shorter codes to more frequent characters

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total bits used by assigning shorter codes to characters that appear more often.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal. Options B, C, and D do not describe Huffman Encoding's purpose.

3. Final Answer:

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

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 Huffman with encryption
• Assuming it sorts characters alphabetically

2. Which Python data structure is commonly used to build the Huffman tree efficiently?

easy

A. List

B. Heap (priority queue)

C. Dictionary

D. Queue

Solution

1. Step 1: Identify data structure for minimum frequency extraction

   Huffman tree construction repeatedly extracts two nodes with the smallest frequencies.

2. Step 2: Choose data structure supporting efficient min extraction

   A heap (priority queue) allows quick access to the smallest element, making it ideal.

3. Final Answer:

   Heap (priority queue) -> Option B

4. Quick Check:

   Min extraction = heap (priority queue) [OK]

Hint: Use a heap for fast smallest frequency access [OK]

Common Mistakes:

• Using a list without sorting repeatedly
• Choosing a queue which is FIFO, not min-based
• Assuming dictionary stores order

3. What is the output of the following Python code snippet that builds a Huffman tree for characters with frequencies {'a': 5, 'b': 9, 'c': 12}?

import heapq
freq = [('a', 5), ('b', 9), ('c', 12)]
heap = [(f, ch) for ch, f in freq]
heapq.heapify(heap)
while len(heap) > 1:
    f1, ch1 = heapq.heappop(heap)
    f2, ch2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, ch1 + ch2))
print(heap[0])

medium

A. (26, 'cab')

B. (26, 'abc')

C. (26, 'cba')

D. (26, 'bac')

Solution

1. Step 1: Initialize heap with frequencies

   Heap contains (5,'a'), (9,'b'), (12,'c'). After heapify, smallest frequency is (5,'a').

2. Step 2: Combine two smallest nodes repeatedly

   Pop (5,'a') and (9,'b'), combine to (14,'ab'), push back. Heap now has (12,'c') and (14,'ab'). Pop (12,'c') and (14,'ab') and combine to (26,'cab').

3. Final Answer:

   (26, 'cab') -> Option A

4. Quick Check:

   Sum freq = 5+9+12 = 26, combined chars 'cab' [OK]

Hint: Sum frequencies and combine chars in order popped [OK]

Common Mistakes:

• Mixing character order in combined string
• Adding frequencies incorrectly
• Not heapifying before popping

4. Identify the error in this Huffman tree building code snippet:

import heapq
freq = {'a': 3, 'b': 2, 'c': 6}
heap = []
for ch, f in freq.items():
    heapq.heappush(heap, (ch, f))
while len(heap) > 1:
    f1, ch1 = heapq.heappop(heap)
    f2, ch2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, ch1 + ch2))
print(heap[0])

medium

A. Incorrect loop condition in while

B. Heap elements pushed with frequency first, character second

C. Using heappush instead of heapify

D. Heap elements pushed with character first, frequency second

Solution

1. Step 1: Check heap element structure

   Heap elements must be tuples with frequency first for correct min-heap behavior.

2. Step 2: Identify error in heappush order

   Code pushes (ch, f) instead of (f, ch), so heap compares characters, not frequencies.

3. Final Answer:

   Heap elements pushed with character first, frequency second -> Option D

4. Quick Check:

   Frequency must be first in heap tuple [OK]

Hint: Push (frequency, character) tuples to heap [OK]

Common Mistakes:

• Swapping frequency and character order
• Not using heapify for initial heap
• Wrong while loop condition

5. Given the frequencies {'x': 4, 'y': 7, 'z': 8, 'w': 15}, what is the Huffman code for character 'w' after building the tree? Assume left edge is '0' and right edge is '1'.

hard

A. '0'

B. '11'

C. '1'

D. '10'

Solution

1. Step 1: Build Huffman tree with given frequencies

   Initial heap: (4,'x'), (7,'y'), (8,'z'), (15,'w'). Combine smallest: (4,'x') + (7,'y') = (11,'xy'). Heap now (8,'z'), (11,'xy'), (15,'w'). Combine (8,'z') + (11,'xy') = (19,'zxy'). Heap now (15,'w'), (19,'zxy'). Combine (15,'w') + (19,'zxy') = (34,'wzxy').

2. Step 2: Assign codes from root to leaves

   Root splits into left child (15,'w') and right child (19,'zxy'). 'w' is left child, so code is '0'.

3. Final Answer:

   '0' -> Option A

4. Quick Check:

   'w' is left child of root = '0' [OK]

Hint: Largest freq often gets shortest code at root edge [OK]

Common Mistakes:

• Assigning 'w' code as '1' instead of '0'
• Confusing left/right edges
• Not building tree stepwise