Huffman Encoding in DSA Typescript - 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 shorter codes to frequent letters and longer codes to rare letters.We will build a simple Huffman encoder step-by-step to understand how it works.

🎯 Goal: Create a Huffman encoding for a given string. You will build the frequency map, create nodes, combine them into a tree, and generate codes for each character.

📋 What You'll Learn

Create a frequency map of characters from a given string

Create nodes for each character with frequency

Combine nodes to build a Huffman tree

Generate Huffman codes for each character

Print the Huffman codes as the final output

💡 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 involving data compression, storage optimization, and efficient data transmission.

1

Create frequency map of characters

Create a variable called text and set it to the string "huffman". Then create an empty object called freqMap to store character frequencies.

DSA Typescript

const text = "huffman";
const freqMap: { [key: string]: number } = {};
// Your code here

Hint

Use a for...of loop to count each character in text and store counts in freqMap.

2

Create nodes array from frequency map

Create an array called nodes that contains objects with char and freq properties for each entry in freqMap.

DSA Typescript

const text = "huffman";
const freqMap: { [key: string]: number } = {};
for (const char of text) {
    freqMap[char] = (freqMap[char] || 0) + 1;
}
const nodes = [];
// Your code here

Hint

Use a for...in loop to go through freqMap keys and push objects into nodes.

3

Build Huffman tree by combining nodes

Write a loop that repeatedly sorts nodes by freq, removes the two smallest nodes, combines them into a new node with summed frequency and children, and pushes the new node back into nodes. Stop when nodes has only one node left.

DSA Typescript

const text = "huffman";
const freqMap: { [key: string]: number } = {};
for (const char of text) {
    freqMap[char] = (freqMap[char] || 0) + 1;
}
const nodes = [];
for (const char in freqMap) {
    nodes.push({ char, freq: freqMap[char] });
}
// Your code here

Hint

Keep combining the two smallest nodes until only one node remains. Use shift() to remove nodes and sort() to order by frequency.

4

Generate and print Huffman codes

Create a function called generateCodes that takes a node and a prefix string. It should recursively assign codes to characters by traversing left with prefix + '0' and right with prefix + '1'. Store codes in an object called codes. Then call generateCodes on the root node in nodes[0] with empty string and print codes.

DSA Typescript

const text = "huffman";
const freqMap: { [key: string]: number } = {};
for (const char of text) {
    freqMap[char] = (freqMap[char] || 0) + 1;
}
const nodes = [];
for (const char in freqMap) {
    nodes.push({ char, freq: freqMap[char] });
}
while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq);
    const left = nodes.shift()!;
    const right = nodes.shift()!;
    const newNode = {
        char: null,
        freq: left.freq + right.freq,
        left,
        right
    };
    nodes.push(newNode);
}
const codes: { [key: string]: string } = {};
function generateCodes(node: any, prefix: string) {
    // Your code here
}
generateCodes(nodes[0], "");
console.log(codes);

Hint

Use recursion to assign codes. If the node has a character, assign the current prefix. Otherwise, go left with '0' and right with '1'.

Practice

1. What is the main purpose 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 goal

   Huffman Encoding aims to reduce the total bits used by giving shorter codes to frequent characters.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal. Others describe different or incorrect purposes.

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

Common Mistakes:

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

2. Which TypeScript data structure is best suited to build the priority queue for Huffman Encoding?

easy

A. Array with manual sorting

B. Min-Heap

C. Set

D. Map

Solution

1. Step 1: Identify priority queue needs

   Huffman Encoding requires repeatedly extracting the smallest frequency node efficiently.

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

   Min-Heap allows quick access and removal of the smallest element, ideal for this use.

3. Final Answer:

   Min-Heap -> Option B

4. Quick Check:

   Priority queue = Min-Heap for Huffman [OK]

Hint: Use Min-Heap for efficient smallest element extraction [OK]

Common Mistakes:

• Using Set which has no order
• Using Map which is key-value, not priority queue
• Using Array without sorting is inefficient

3. What is the output Huffman code for characters {a:5, b:9, c:12, d:13, e:16, f:45} after building the Huffman tree?

medium

A. { 'f': '1', 'c': '00', 'd': '01', 'a': '100', 'b': '101', 'e': '110' }

B. { 'a': '0', 'b': '10', 'c': '110', 'd': '1110', 'e': '1111', 'f': '101' }

C. { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' }

D. { 'a': '111', 'b': '110', 'c': '10', 'd': '0', 'e': '101', 'f': '100' }

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (a=5,b=9)->14, (c=12,d=13)->25, then combine 14 and 16 (e) and so on, finally f=45 is highest frequency with shortest code.

2. Step 2: Assign codes from tree paths

   Left edges as '0', right edges as '1' produce codes: f='0', c='100', d='101', a='1100', b='1101', e='111'.

3. Final Answer:

   { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' } -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Assigning codes without building tree
• Mixing left/right edge bits
• Ignoring frequency order

4. Given this TypeScript snippet for Huffman tree node insertion, what is the bug?

class Node {
  constructor(public char: string | null, public freq: number, public left: Node | null = null, public right: Node | null = null) {}
}

function insertNode(queue: Node[], node: Node) {
  queue.push(node);
  queue.sort((a, b) => a.freq - b.freq);
}

// Usage
const queue: Node[] = [];
insertNode(queue, new Node('a', 5));
insertNode(queue, new Node('b', 9));
insertNode(queue, new Node(null, 14));

medium

A. Sorting after push is inefficient; use a Min-Heap instead

B. Node constructor missing type annotations

C. Function insertNode should remove duplicates

D. queue.sort comparator should be reversed

Solution

1. Step 1: Analyze insertNode function

   It pushes a node then sorts the entire queue array by frequency each time.

2. Step 2: Identify inefficiency

   Sorting the whole array on every insertion is inefficient for large data; a Min-Heap is better for priority queue operations.

3. Final Answer:

   Sorting after push is inefficient; use a Min-Heap instead -> Option A

4. Quick Check:

   Priority queue needs efficient insert and extract [OK]

Hint: Use Min-Heap, not array sort, for priority queue [OK]

Common Mistakes:

• Thinking sorting order is wrong
• Missing inefficiency of sorting whole array
• Confusing type annotations as bug

5. You have a string "aaabbc" and want to encode it using Huffman Encoding. Which of the following is the correct Huffman code assignment and encoded bit string?

hard

A. Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011'

B. Codes: {a:'10', b:'0', c:'11'}, Encoded: '101010011'

C. Codes: {a:'0', b:'11', c:'10'}, Encoded: '00011110'

D. Codes: {a:'1', b:'0', c:'10'}, Encoded: '1110010'

Solution

1. Step 1: Calculate frequencies

   String "aaabbc" has frequencies: a=3, b=2, c=1.

2. Step 2: Build Huffman tree and assign codes

   Lowest freq c=1 and b=2 combine first, then with a=3. Assign codes: a='0', b='10', c='11'.

3. Step 3: Encode string using codes

   Encoding "aaabbc" = a(3 times) '0 0 0', b(2 times) '10 10', c(1 time) '11' -> '000101011'.

4. Final Answer:

   Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011' -> Option A

5. Quick Check:

   Freq order a>b>c matches codes and encoding [OK]

Hint: Encode by replacing chars with shortest codes from tree [OK]

Common Mistakes:

• Mixing code assignments
• Encoding with wrong code bits
• Ignoring frequency order in code assignment