Huffman Encoding in DSA Java - Build from Scratch

Huffman Encoding

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

Huffman encoding is used in file compression tools 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 related to data compression, storage optimization, and efficient data transmission in software engineering and data science.

1

Create frequency map of characters

Create a String variable called text with the value "hello huffman". Then create a Map<Character, Integer> called frequencyMap and fill it with the count of each character in text using a for loop with variable ch.

DSA Java

String text = "hello huffman";
Map frequencyMap = new HashMap();
// Your code here

Hint

Use text.toCharArray() to get characters. Use frequencyMap.getOrDefault(ch, 0) to get current count or 0.

2

Create Node class and priority queue

Create a static inner class Node with char ch, int freq, Node left, and Node right. Then create a PriorityQueue<Node> called pq that orders nodes by freq. Add all characters from frequencyMap as nodes to pq.

DSA Java

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanEncoding {
    public static void main(String[] args) {
        String text = "hello huffman";
        Map frequencyMap = new HashMap();
        for (char ch : text.toCharArray()) {
            frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
        }

        PriorityQueue pq = new PriorityQueue((a, b) -> a.freq - b.freq);
        // Your code here
    }

    static class Node {
        char ch;
        int freq;
        Node left, right;

        Node(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }

        Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
    }
}

Hint

Use a lambda to order nodes by frequency in the priority queue. Add each character and frequency as a new Node.

3

Build Huffman tree and generate codes

Build the Huffman tree by removing two smallest nodes from pq, creating a new parent node with their combined frequency, and adding it back to pq. Repeat until one node remains. Then create a Map<Character, String> called huffmanCodes. Write a recursive method buildCodes(Node node, String code, Map<Character, String> huffmanCodes) to fill huffmanCodes by traversing the tree. Call it with the root node and empty string.

DSA Java

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanEncoding {
    public static void main(String[] args) {
        String text = "hello huffman";
        Map frequencyMap = new HashMap();
        for (char ch : text.toCharArray()) {
            frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
        }

        PriorityQueue pq = new PriorityQueue((a, b) -> a.freq - b.freq);
        for (Map.Entry entry : frequencyMap.entrySet()) {
            pq.add(new Node(entry.getKey(), entry.getValue()));
        }

        // Build Huffman tree
        // Your code here
    }

    static class Node {
        char ch;
        int freq;
        Node left, right;

        Node(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }

        Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
    }

    static void buildCodes(Node node, String code, Map huffmanCodes) {
        // Your code here
    }
}

Hint

Combine two smallest nodes until one remains. Use recursion to assign '0' for left and '1' for right paths.

4

Print Huffman codes

Use a for loop with variables ch and code to iterate over huffmanCodes.entrySet(). Print each character and its code in the format ch + ": " + code.

DSA Java

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanEncoding {
    public static void main(String[] args) {
        String text = "hello huffman";
        Map frequencyMap = new HashMap();
        for (char ch : text.toCharArray()) {
            frequencyMap.put(ch, frequencyMap.getOrDefault(ch, 0) + 1);
        }

        PriorityQueue pq = new PriorityQueue((a, b) -> a.freq - b.freq);
        for (Map.Entry entry : frequencyMap.entrySet()) {
            pq.add(new Node(entry.getKey(), entry.getValue()));
        }

        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq, left, right);
            pq.add(parent);
        }

        Node root = pq.poll();
        Map huffmanCodes = new HashMap();
        buildCodes(root, "", huffmanCodes);

        for (Map.Entry entry : huffmanCodes.entrySet()) {
            // Your code here
        }
    }

    static class Node {
        char ch;
        int freq;
        Node left, right;

        Node(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }

        Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
    }

    static void buildCodes(Node node, String code, Map huffmanCodes) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            huffmanCodes.put(node.ch, code);
            return;
        }
        buildCodes(node.left, code + "0", huffmanCodes);
        buildCodes(node.right, code + "1", huffmanCodes);
    }
}

Hint

Use System.out.println(ch + ": " + code) inside the loop to print each character and its Huffman code.

Practice

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

easy

A. To sort characters alphabetically

B. To assign shorter codes to more frequent characters

C. To encrypt data for security

D. To assign equal length codes to all characters

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 goal

   Only To assign shorter codes to more frequent characters matches this goal. Options A, B, and C do not describe Huffman Encoding correctly.

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 [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing Huffman with encryption
• Assuming it sorts characters alphabetically

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

easy

A. PriorityQueue

B. HashMap

C. ArrayList

D. Stack

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: Match data structure to this need

   A PriorityQueue efficiently provides the smallest element each time, making it ideal for this task.

3. Final Answer:

   PriorityQueue -> Option A

4. Quick Check:

   Minimum extraction = PriorityQueue [OK]

Hint: Use PriorityQueue for smallest frequency extraction [OK]

Common Mistakes:

• Using ArrayList which is not efficient for min extraction
• Choosing HashMap which stores key-value pairs, not order
• Selecting Stack which is LIFO, not suitable here

3. What is the output Huffman code for characters given frequencies: A=5, B=9, C=12, D=13, E=16, F=45? (Assuming standard Huffman algorithm)

medium

A. A: 111, B: 110, C: 101, D: 100, E: 0, F: 11

B. A: 0, B: 111, C: 110, D: 10, E: 101, F: 100

C. A: 100, B: 101, C: 110, D: 111, E: 0, F: 11

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

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (A=5, B=9) -> 14, then combine with C=12, etc., building tree with F=45 as root's child.

2. Step 2: Assign codes from tree paths

   F gets shortest code '0' (highest freq). A and B get longer codes starting with '1100' and '1101' respectively.

3. Final Answer:

   A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 -> Option D

4. Quick Check:

   Lowest freq get longest codes = A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 [OK]

Hint: Lowest freq get longest codes, highest freq shortest [OK]

Common Mistakes:

• Assigning shortest codes to low frequency chars
• Mixing code assignments without tree structure
• Ignoring frequency order in code lengths

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

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node('a', 5));
pq.add(new Node('b', 9));
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(null, left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.add(parent);

medium

A. Node class must implement Comparable for PriorityQueue

B. Cannot add null character to Node

C. PriorityQueue should be initialized with capacity

D. Must poll three nodes before creating parent

Solution

1. Step 1: Check PriorityQueue usage

   PriorityQueue requires elements to be comparable or a comparator provided to order nodes by frequency.

2. Step 2: Verify Node class implementation

   If Node does not implement Comparable or no comparator is given, pq.poll() will throw runtime error.

3. Final Answer:

   Node class must implement Comparable for PriorityQueue -> Option A

4. Quick Check:

   PriorityQueue needs Comparable nodes [OK]

Hint: Ensure Node implements Comparable for PriorityQueue [OK]

Common Mistakes:

• Ignoring Comparable interface requirement
• Thinking null character is invalid here
• Assuming PriorityQueue needs capacity argument

5. Given a string "abbcccdddd", how many bits will Huffman Encoding save compared to fixed-length 3-bit encoding per character?

hard

A. 7 bits saved

B. 10 bits saved

C. 11 bits saved

D. 15 bits saved

Solution

1. Step 1: Calculate fixed-length bits

   String length is 10, fixed-length 3 bits per char, total bits = 10*3 = 30 bits.

2. Step 2: Calculate Huffman bits

   Frequencies: a=1, b=2, c=3, d=4. Huffman codes: a:100 (3 bits), b:101 (3), c:11 (2), d:0 (1). Total bits = (1*3) + (2*3) + (3*2) + (4*1) = 3 + 6 + 6 + 4 = 19 bits.

3. Step 3: Calculate bits saved

   Bits saved = 30 - 19 = 11 bits.

4. Final Answer:

   11 bits saved -> Option C

5. Quick Check:

   Fixed 30 bits - Huffman 19 bits = 11 bits saved [OK]

Hint: Calculate fixed bits minus Huffman bits for savings [OK]

Common Mistakes:

• Not counting frequencies correctly
• Using wrong bit length for fixed encoding
• Miscomputing total Huffman bits