Huffman Encoding in DSA Go - Build from Scratch

Huffman Encoding

📖 Scenario: You work for a company that compresses text messages to save space. Huffman encoding is a way to assign short codes to frequent letters and longer codes to rare letters. This helps reduce the total size of messages.

🎯 Goal: Build a simple Huffman encoding program in Go. You will create a frequency map of characters, set up a priority queue, build the Huffman tree, and then print the codes for each character.

📋 What You'll Learn

Create a map of character frequencies from a given string

Create a priority queue to hold tree nodes based on frequency

Build the Huffman tree by combining lowest frequency nodes

Traverse the tree to assign binary codes to each character

Print the Huffman codes for all characters

💡 Why This Matters

🌍 Real World

Huffman encoding is used in file compression formats 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 frequency map of characters

Create a variable called text with the value "go go gophers". Then create a map called freq of type map[rune]int to count how many times each character appears in text.

DSA Go

// Create variable text and map freq to count characters
// Your code here

Hint

Use a for loop with range on text to count characters.

2

Create priority queue for Huffman nodes

Define a struct called Node with fields char rune, freq int, left *Node, and right *Node. Then create a slice called nodes of type []*Node. Add one Node for each character in freq with the character and its frequency.

DSA Go

package main

import "fmt"

type Node struct {
    char  rune
    freq  int
    left  *Node
    right *Node
}

func main() {
    text := "go go gophers"
    freq := make(map[rune]int)
    for _, ch := range text {
        freq[ch]++
    }

    var nodes []*Node
    // Add nodes for each character in freq
    // Your code here
}

Hint

Define Node struct and create nodes for each character frequency.

3

Build Huffman tree by combining nodes

Write a loop that runs while the length of nodes is more than 1. Inside the loop, find two nodes with the smallest freq. Remove them from nodes, create a new Node with freq equal to their sum and left and right pointing to these two nodes. Append this new node back to nodes. After the loop, the only node left in nodes is the root of the Huffman tree.

DSA Go

package main

import "fmt"

type Node struct {
    char  rune
    freq  int
    left  *Node
    right *Node
}

func main() {
    text := "go go gophers"
    freq := make(map[rune]int)
    for _, ch := range text {
        freq[ch]++
    }

    var nodes []*Node
    for ch, f := range freq {
        nodes = append(nodes, &Node{char: ch, freq: f})
    }

    // Build Huffman tree by combining lowest frequency nodes
    // Your code here
}

Hint

Use a helper function to find and remove two smallest nodes, then combine them.

4

Print Huffman codes for each character

Write a recursive function called printCodes that takes a *Node and a string code. If the node is a leaf (both left and right are nil), print the character and its code. Otherwise, call printCodes on the left child with code + "0" and on the right child with code + "1". Call printCodes with the root node (the only node in nodes) and an empty string. This will print the Huffman codes for all characters.

DSA Go

package main

import "fmt"

type Node struct {
    char  rune
    freq  int
    left  *Node
    right *Node
}

func removeTwoSmallest(nodes []*Node) ([]*Node, *Node, *Node) {
    if len(nodes)  min2 {
        min1, min2 = min2, min1
    }
    nodes = append(nodes[:min1], nodes[min1+1:min2]...)
    nodes = append(nodes, nodes[min2+1:]...)
    return nodes, n1, n2
}

func main() {
    text := "go go gophers"
    freq := make(map[rune]int)
    for _, ch := range text {
        freq[ch]++
    }

    var nodes []*Node
    for ch, f := range freq {
        nodes = append(nodes, &Node{char: ch, freq: f})
    }

    for len(nodes) > 1 {
        var n1, n2 *Node
        nodes, n1, n2 = removeTwoSmallest(nodes)
        newNode := &Node{
            freq:  n1.freq + n2.freq,
            left:  n1,
            right: n2,
        }
        nodes = append(nodes, newNode)
    }

    // Write printCodes function and call it with root node
    // Your code here
}

Hint

Use recursion to print codes. Leaf nodes have no children. Append '0' for left and '1' for right.

Practice

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

easy

A. To sort characters alphabetically

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To assign shorter codes to more frequent characters

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by using variable-length codes based on character frequency.

2. Step 2: Identify code assignment rule

   More frequent characters get shorter codes to reduce overall data size.

3. Final Answer:

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

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

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

Common Mistakes:

• Thinking all codes have same length
• Confusing compression with encryption
• Assuming alphabetical order affects codes

2. Which of the following Go code snippets correctly declares a priority queue for Huffman nodes using container/heap?

easy

A. type HuffmanNode struct {char string; freq float64}; var pq []HuffmanNode

B. var pq []int = make([]int, 0)

C. type HuffmanNode struct {char rune; freq int}; type PriorityQueue []*HuffmanNode

D. var pq map[rune]int = make(map[rune]int)

Solution

1. Step 1: Identify correct struct for Huffman node

   HuffmanNode should have a character (rune) and frequency (int).

2. Step 2: Check priority queue declaration

   PriorityQueue should be a slice of pointers to HuffmanNode for heap operations.

3. Final Answer:

   type HuffmanNode struct {char rune; freq int}; type PriorityQueue []*HuffmanNode -> Option C

4. Quick Check:

   Priority queue = slice of HuffmanNode pointers [OK]

Hint: Use slice of pointers for priority queue [OK]

Common Mistakes:

• Using map instead of slice for priority queue
• Using wrong data types for char or freq
• Declaring slice of values instead of pointers

3. Given the frequencies: {'a': 5, 'b': 9, 'c': 12, 'd': 13}, what is the Huffman code for 'a' after building the tree?

medium

A. 10

B. 00

C. 111

D. 110

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5('a') + 9('b') = 14, then combine 12('c') + 13('d') = 25, then combine 14 + 25 = 39.

2. Step 2: Assign codes from tree

   'a' is in the left subtree of the first combined node, so it gets code '10' (left-right).

3. Final Answer:

   10 -> Option A

4. Quick Check:

   'a' = code '10' [OK]

Hint: Lowest freq chars get codes starting with 1 or 0 depending on tree [OK]

Common Mistakes:

• Assigning longer codes to lowest freq chars
• Mixing up left and right branches
• Ignoring tree structure when assigning codes

4. Identify the error in this Go snippet for building a Huffman tree:

func buildTree(freq map[rune]int) *Node {
  pq := &PriorityQueue{}
  heap.Init(pq)
  for c, f := range freq {
    heap.Push(pq, &Node{char: c, freq: f})
  }
  for pq.Len() > 1 {
    left := heap.Pop(pq).(*Node)
    right := heap.Pop(pq).(*Node)
    merged := &Node{freq: left.freq + right.freq, left: left, right: right}
    heap.Push(pq, merged)
  }
  return heap.Pop(pq).(*Node)
}

medium

A. PriorityQueue must implement heap.Interface methods

B. freq map keys should be string, not rune

C. heap.Init should be called after pushing elements

D. Cannot push pointers to heap

Solution

1. Step 1: Check PriorityQueue usage with heap

   Go's heap requires the PriorityQueue type to implement heap.Interface methods Len, Less, Swap, Push, and Pop.

2. Step 2: Identify missing implementation

   If PriorityQueue does not implement these methods, heap.Init and heap.Push will cause runtime errors.

3. Final Answer:

   PriorityQueue must implement heap.Interface methods -> Option A

4. Quick Check:

   heap.Interface implementation required [OK]

Hint: Always implement heap.Interface for priority queues [OK]

Common Mistakes:

• Using wrong key type in freq map
• Calling heap.Init too early or late
• Trying to push non-pointer values

5. You have a string "aaabbc" and want to encode it using Huffman Encoding. Which of the following steps correctly describes how to build the Huffman tree and generate codes?

hard

A. Sort characters alphabetically, assign fixed-length codes, encode string

B. Count frequencies, build min-heap, merge nodes until one tree, assign codes from tree

C. Assign random codes to characters, then compress string

D. Use frequency to assign codes but skip building tree

Solution

1. Step 1: Count character frequencies

   For "aaabbc", frequencies are: 'a':3, 'b':2, 'c':1.

2. Step 2: Build min-heap and merge nodes

   Create nodes for each char, push into min-heap, merge two smallest nodes repeatedly until one tree remains.

3. Step 3: Assign codes from the tree

   Traverse tree assigning '0' for left and '1' for right edges to generate prefix codes.

4. Final Answer:

   Count frequencies, build min-heap, merge nodes until one tree, assign codes from tree -> Option B

5. Quick Check:

   Huffman = freq count + min-heap + merge + code assign [OK]

Hint: Follow frequency -> min-heap -> merge -> code assign steps [OK]

Common Mistakes:

• Skipping tree building step
• Assigning fixed-length codes ignoring frequency
• Using random codes without structure