Huffman Encoding in DSA Rust - Build from Scratch

Huffman Encoding

📖 Scenario: You work for a company that wants to compress text messages to save space when sending them over the network. Huffman encoding is a way to assign shorter codes to more frequent letters, making the message smaller.

🎯 Goal: Build a simple Huffman encoding program in Rust that counts letter frequencies, builds a Huffman tree, assigns codes, and shows the encoded message.

📋 What You'll Learn

Create a frequency dictionary for letters in a given text

Define a struct for Huffman tree nodes

Build the Huffman tree using a priority queue

Generate Huffman codes by traversing the tree

Encode the original text using the generated codes

Print the encoded message

💡 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 assigning shorter codes to frequent data.

💼 Career

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

1

Create frequency dictionary for letters

Create a variable called text with the string "hello huffman". Then create a mutable HashMap called freq to count the frequency of each character in text. Use a for loop with variable ch to iterate over text.chars() and update freq accordingly.

DSA Rust

let text = "hello huffman";
use std::collections::HashMap;
let mut freq = HashMap::new();
// Your code here

Hint

Use HashMap::new() to create the frequency map. Loop over each character and increase its count.

2

Define Huffman tree node struct and priority queue

Define a struct called Node with fields freq: usize, ch: Option, left: Option>, and right: Option>. Then create a mutable Vec called nodes. For each entry in freq, push a Node with the character and its frequency into nodes.

DSA Rust

struct Node {
    freq: usize,
    ch: Option,
    left: Option>,
    right: Option>,
}

let mut nodes = Vec::new();
// Your code here

Hint

Define the Node struct with frequency and optional children. Then convert each frequency entry into a leaf node.

3

Build Huffman tree and generate codes

Implement a loop that builds the Huffman tree by repeatedly sorting nodes by frequency, removing the two smallest nodes, creating a new parent node with their combined frequency, and pushing it back into nodes. Then define a recursive function build_codes that takes a Node reference, a mutable HashMap called codes, and a String called prefix. It should assign codes to characters by traversing left with prefix + "0" and right with prefix + "1".

DSA Rust

// Your code here

Hint

Sort nodes by frequency, combine two smallest nodes, and repeat until one node remains. Then recursively assign codes by traversing the tree.

4

Encode text and print result

Create a variable encoded by iterating over each character ch in text.chars() and collecting the corresponding code from codes. Then print encoded.

DSA Rust

// Your code here

Hint

Use map on text.chars() to replace each character with its code, then collect into a string. Print the encoded string.

Practice

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

easy

A. To assign shorter codes to more frequent characters

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding compresses data by giving 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; others describe different concepts.

3. Final Answer:

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

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 Rust data structure is best suited to implement the priority queue needed for Huffman Encoding?

easy

A. BinaryHeap<T>

B. HashMap

C. Vec<T>

D. LinkedList<T>

Solution

1. Step 1: Identify priority queue requirement

   Huffman Encoding needs a structure to get the smallest frequency element quickly.

2. Step 2: Match Rust structures to priority queue

   BinaryHeap<T> is Rust's built-in priority queue supporting efficient min/max operations.

3. Final Answer:

   BinaryHeap<T> -> Option A

4. Quick Check:

   Priority queue = BinaryHeap in Rust [OK]

Hint: Use BinaryHeap for priority queues in Rust [OK]

Common Mistakes:

• Using Vec without sorting for priority queue
• Choosing HashMap which is for key-value pairs
• Using LinkedList which is inefficient here

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

use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Node {
    freq: usize,
    char_opt: Option<char>,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.freq.cmp(&self.freq) // min-heap behavior
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Node { freq: 5, char_opt: Some('a') });
    heap.push(Node { freq: 9, char_opt: Some('b') });
    heap.push(Node { freq: 12, char_opt: Some('c') });

    let first = heap.pop().unwrap();
    let second = heap.pop().unwrap();

    println!("{} {}", first.freq, second.freq);
}

medium

A. 9 5

B. 12 9

C. 5 9

D. 5 12

Solution

1. Step 1: Understand BinaryHeap with custom Ord

   The cmp reverses order to make a min-heap by frequency, so pop() returns smallest freq first.

2. Step 2: Pop two smallest frequencies

   Frequencies are 5, 9, 12. First pop returns 5, second pop returns 9.

3. Final Answer:

   5 9 -> Option C

4. Quick Check:

   Min-heap pops smallest first = 5 9 [OK]

Hint: Custom Ord reverses cmp for min-heap pop order [OK]

Common Mistakes:

• Assuming BinaryHeap is max-heap by default
• Mixing order of popped elements
• Ignoring custom Ord implementation

4. Identify the bug in this Rust code snippet that tries to build a Huffman tree node by combining two nodes:

struct Node {
    freq: usize,
    left: Option,
    right: Option,
}

fn combine_nodes(left: Node, right: Node) -> Node {
    Node {
        freq: left.freq + right.freq,
        left: Some(Box::new(left)),
        right: Some(Box::new(right)),
    }
}

fn main() {
    let n1 = Node { freq: 3, left: None, right: None };
    let n2 = Node { freq: 4, left: None, right: None };
    let parent = combine_nodes(n1, n2);
    println!("Parent freq: {}", parent.freq);
}

medium

A. Cannot use Box::new with struct Node

B. Missing lifetime annotations for Box<Node>

C. Function should take references, not owned Nodes

D. No bug, code compiles and runs correctly

Solution

1. Step 1: Check ownership and Box usage

   Function takes owned Nodes and boxes them correctly for left and right fields.

2. Step 2: Verify code compiles and runs

   Code compiles and prints combined frequency without errors.

3. Final Answer:

   No bug, code compiles and runs correctly -> Option D

4. Quick Check:

   Ownership and Box usage correct = no bug [OK]

Hint: Owned nodes boxed correctly means no bug here [OK]

Common Mistakes:

• Assuming lifetime needed for Box<Node> here
• Thinking references required instead of ownership
• Believing Box::new cannot wrap structs

5. Given character frequencies {'x': 7, 'y': 3, 'z': 2, 'w': 6}, which of the following Huffman codes is valid and optimal?

hard

A. x: 11, y: 10, z: 0, w: 1

B. x: 0, y: 10, z: 110, w: 111

C. x: 10, y: 0, z: 111, w: 110

D. x: 0, y: 1, z: 10, w: 11

Solution

1. Step 1: Order characters by frequency

   Frequencies: z=2, y=3, w=6, x=7. Huffman assigns shortest codes to highest freq.

2. Step 2: Check code lengths and prefix property

   x: 0, y: 10, z: 110, w: 111 assigns shortest code '0' to x (freq 7), longer codes to lower freq chars, and codes are prefix-free.

3. Final Answer:

   x: 0, y: 10, z: 110, w: 111 -> Option B

4. Quick Check:

   Shortest code to highest freq = x: 0, y: 10, z: 110, w: 111 [OK]

Hint: Shortest code goes to highest frequency char [OK]

Common Mistakes:

• Assigning short codes to low frequency chars
• Ignoring prefix-free property
• Confusing code length order