Huffman Encoding in DSA Javascript - Build from Scratch

Huffman Encoding

📖 Scenario: You work for a company that wants to compress text messages to save space and speed up transmission. Huffman encoding is a way to assign shorter codes to more frequent letters and longer codes to less frequent letters.In this project, you will build a simple Huffman encoding system step-by-step using JavaScript.

🎯 Goal: Build a Huffman encoding system that takes a string, counts the frequency of each character, builds a Huffman tree, and generates the binary codes for each character.

📋 What You'll Learn

Create a frequency dictionary for characters in a given string

Create a priority queue (array) of nodes sorted by frequency

Build the Huffman tree by combining the two lowest frequency nodes until one node remains

Generate the Huffman codes for each character by traversing the tree

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 involving data compression, storage optimization, and efficient data transmission in software engineering and data science.

1

Create frequency dictionary

Create a variable called text and set it to the string 'abbcccdddd'. Then create an empty object called freq. Use a for loop with variable char to iterate over text. Inside the loop, increase the count of char in freq by 1, or set it to 1 if it does not exist.

DSA Javascript

const text = 'abbcccdddd';
const freq = {};
// Your code here

Hint

Use a for...of loop to go through each character in text. For each character, update its count in freq.

2

Create priority queue of nodes

Create an array called nodes. Use a for loop with variables char and count to iterate over Object.entries(freq). For each pair, push an object {char: char, freq: count} into nodes. Then sort nodes in ascending order by freq.

DSA Javascript

const nodes = [];
// Your code here

Hint

Convert the frequency object into an array of objects with char and freq. Then sort by frequency.

3

Build Huffman tree

Create a while loop that runs while nodes.length > 1. Inside the loop, remove the first two nodes from nodes using shift(). Create a new node with char set to null, freq as the sum of the two nodes' frequencies, and left and right properties set to the two nodes. Push this new node back into nodes and sort nodes again by frequency. After the loop ends, the single node left in nodes is the root of the Huffman tree. Save it in a variable called tree.

DSA Javascript

// Your code here

Hint

Keep combining the two smallest nodes into a new node until only one node remains. This node is the Huffman tree root.

4

Generate and print Huffman codes

Create an empty object called codes. Write a recursive function called generateCodes that takes a node and a code string (default empty). If node.char is not null, set codes[node.char] to code. Otherwise, call generateCodes on node.left with code + '0' and on node.right with code + '1'. Call generateCodes with tree. Finally, print codes using console.log(codes).

DSA Javascript

const codes = {};
// Your code here

Hint

Use recursion to assign codes: go left adding '0', go right adding '1'. When you reach a leaf node (character), save the code.

Practice

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

easy

A. To encrypt data for security

B. To assign shorter codes to more frequent characters

C. To assign equal length codes to all characters

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by using shorter codes for frequent characters and longer codes for less frequent ones.

2. Step 2: Compare options with this purpose

   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 B

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 alphabetical sorting is the goal

2. Which of the following is the correct way to represent a node in a Huffman tree in JavaScript?

easy

A. const node = 'a:5';

B. const node = [ 'a', 5, null, null ];

C. const node = function(char, freq) { this.char = char; this.freq = freq; };

D. const node = { char: 'a', freq: 5, left: null, right: null };

Solution

1. Step 1: Identify proper node structure for Huffman tree

   A node should store character, frequency, and pointers to left and right children.

2. Step 2: Check each option

   const node = { char: 'a', freq: 5, left: null, right: null }; uses an object with char, freq, left, right properties which is clear and correct. const node = [ 'a', 5, null, null ]; uses an array without labels, making it unclear. const node = function(char, freq) { this.char = char; this.freq = freq; }; is a constructor but incomplete (no left/right). const node = 'a:5'; is a string, not a node.

3. Final Answer:

   const node = { char: 'a', freq: 5, left: null, right: null }; -> Option D

4. Quick Check:

   Node = object with char, freq, left, right [OK]

Hint: Use objects with named properties for tree nodes [OK]

Common Mistakes:

• Using arrays without labels for nodes
• Using strings instead of objects
• Missing left and right child pointers

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

medium

A. 00

B. 111

C. 110

D. 10

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5('a') and 9('b') -> node with freq 14. Then combine 12('c') and 13('d') -> node with freq 25. Finally combine 14 and 25 -> root 39.

2. Step 2: Assign codes by traversing tree

   Left edges get '0', right edges get '1'. 'a' is left child of first combined node, so code is '110'.

3. Final Answer:

   110 -> Option C

4. Quick Check:

   Lowest freq char 'a' gets code '110' [OK]

Hint: Combine lowest freq nodes first, assign 0 to left [OK]

Common Mistakes:

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

4. Consider this JavaScript snippet for building a Huffman tree:

function buildTree(freqMap) {
  let nodes = Object.entries(freqMap).map(([char, freq]) => ({char, freq}));
  while(nodes.length > 1) {
    nodes.sort((a,b) => a.freq - b.freq);
    let left = nodes.shift();
    let right = nodes.shift();
    let newNode = {char: null, freq: left.freq + right.freq, left, right};
    nodes.push(newNode);
  }
  return nodes[0];
}

What is the bug in this code?

medium

A. The function does not handle empty freqMap

B. The newNode should not have char property

C. The nodes array is not updated correctly after push

D. The nodes array is not sorted before each iteration

Solution

1. Step 1: Analyze function behavior with empty input

   If freqMap is empty, Object.entries(freqMap) is empty array, so nodes is empty. The while loop condition nodes.length > 1 is false, so function returns nodes[0], which is undefined.

2. Step 2: Identify missing edge case handling

   The function does not check for empty freqMap and returns undefined instead of a valid tree or null.

3. Final Answer:

   The function does not handle empty freqMap -> Option A

4. Quick Check:

   Empty input returns undefined, missing edge case [OK]

Hint: Check empty input cases in tree-building functions [OK]

Common Mistakes:

• Assuming nodes always have elements
• Ignoring empty input edge cases
• Thinking sorting is missing when it is present

5. You have the string "abbcccdddd". Using Huffman Encoding, what is the minimum total number of bits needed to encode this string? Frequencies: a=1, b=2, c=3, d=4.

hard

A. 19 bits

B. 17 bits

C. 15 bits

D. 21 bits

Solution

1. Step 1: Build Huffman tree and assign codes

   Frequencies: a=1, b=2, c=3, d=4. Combine a(1) and b(2) -> node(3). Combine node(3) and c(3) -> node(6). Combine node(6) and d(4) -> root(10). Assign codes: d=0 (1 bit), c=10 (2 bits), b=110 (3 bits), a=111 (3 bits).

2. Step 2: Calculate total bits

   Total bits = (a:1*3) + (b:2*3) + (c:3*2) + (d:4*1) = 3 + 6 + 6 + 4 = 19 bits.

3. Final Answer:

   19 bits -> Option A

4. Quick Check:

   Sum(freq * code length) = 19 bits [OK]

Hint: Multiply frequency by code length, then sum all [OK]

Common Mistakes:

• Adding frequencies instead of weighted bits
• Assigning wrong code lengths
• Ignoring frequency when calculating total bits