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'.