Huffman Coding

Huffman coding is a lossless compression technique that assigns shorter binary codes to frequently used characters and longer codes to less frequent ones, reducing overall storage size.

Let’s walk through a simple example with the word “BANANA” and visualize how the Huffman tree is built.

📊 Step 1 — Character Frequencies

We first count how often each character appears in the word BANANA:

• B → 1
• A → 3
• N → 2

🌳 Step 2 — Build the Huffman Tree

• Start with the least frequent characters (B:1 and N:2) → combine into a node with frequency 3.
• Now we have nodes: A:3 and BN:3.
• Combine them into the root node with frequency 6.

The tree looks like this:

        (6)
       /   \
    (3)     A(3)
   /   \
 B(1)   N(2)

🔢 Step 3 — Assign Binary Codes

• Left edges = 0, right edges = 1.
• B → 00
• N → 01
• A → 1

📦 Step 4 — Encode the Word

Original word: BANANA Encoded sequence:

• B → 00
• A → 1
• N → 01
• A → 1
• N → 01
• A → 1

Result: 00 1 01 1 01 1 → compressed binary string: 001011011

🎯 Why It Works

• Efficiency: Frequent letters like “A” get short codes (just 1), while rare ones like “B” get longer codes (00).
• Compression: Instead of storing each character with 8 bits (UTF-8), Huffman coding reduces the total bit count significantly.

🎨 The Final

BANANA → 00 1 01 1 01 1 → 001011011

Get Emad Mohamed’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So instead of storing 6 characters × 8 bits = 48 bits, we only need 9 bits — a huge compression gain!

ASCII encoding, Fixed-Size Codes encoding, and Huffman encoding:

Here’s a clear comparison between ASCII encoding, Fixed-Size Codes encoding, and Huffman encoding, showing how each method represents data differently.

🧠 Concept Overview

Example Comparison

Let’s encode the word “BANANA”:

🎯 Summary

• ASCII → simple, universal, but large.
• Fixed‑Size Codes → uniform, easy to decode, but inefficient.
• Huffman → smart, adaptive, and space‑saving.

JS Code for Huffman for encoding and decoding text :

//* write huffman coding in js :

//1. Define the Node StructureEach node stores the character, its frequency, 
// and references to its left and right children.
class Node {
    constructor(char, freq) {
        this.char = char;   
        this.freq = freq;
        this.left = null;
        this.right = null;
    }
}

function buildHuffmanTree(text) {

    // Step 1: Count how many times each character appears
    const freqMap = new Map();  
    for (const char of text) {
        freqMap.set(char, (freqMap.get(char) || 0) + 1);
    } 
    
    // Step 2: Build the Huffman Tree using a priority queue (min-heap) to always 
    // combine the two least frequent nodes
    const nodes = [];
    for (const [char, freq] of freqMap.entries()) {
        nodes.push(new Node(char, freq));
    }   
    while (nodes.length > 1) {
        nodes.sort((a, b) => a.freq - b.freq);  
        const left = nodes.shift();  
        const right = nodes.shift(); 
        const newNode = new Node(null, left.freq + right.freq); 
        newNode.left = left; 
        newNode.right = right; 
        nodes.push(newNode); 
    }
    return nodes[0]; 
}   

// Step 3: Traverse the tree to generate binary codes (0 for left, 1 for right)
function generateCodes(node, prefix = '', codeMap = {}) {
    if (node.char !== null) { 
        codeMap[node.char] = prefix; 
    } else {
        generateCodes(node.left, prefix + '0', codeMap); 
        generateCodes(node.right, prefix + '1', codeMap); 
    }   
    return codeMap;
}

function huffmanCoding(text) {
    const root = buildHuffmanTree(text); 
    const codeMap = generateCodes(root); 
    let encodedText = '';   
    for (const char of text) {
        encodedText += codeMap[char]; 
    }           
    return { encodedText, codeMap };
}

// Example usage:
const text = "hello huffman";
const { encodedText, codeMap } = huffmanCoding(text);
console.log("Encoded Text:", encodedText);
console.log("Code Map:", codeMap);


//decoding function
function huffmanDecoding(encodedText, codeMap) {
    const reverseCodeMap = {};  
    for (const char in codeMap) {
        reverseCodeMap[codeMap[char]] = char; 
    }   
    let currentCode = '';
    let decodedText = '';
    for (const bit of encodedText) {
        currentCode += bit;
        if (reverseCodeMap[currentCode]) {
            decodedText += reverseCodeMap[currentCode];
            currentCode = ''; 
        }
    }
    return decodedText;
}

// Example usage of decoding:
const decodedText = huffmanDecoding(encodedText, codeMap);
console.log("Decoded Text:", decodedText);

output :

Encoded Text: 0111100100100110111100111111101101000001010

Code Map: {
  m: '000',
  a: '001',
  n: '010',
  h: '011',
  l: '100',
  f: '101',
  e: '1100',
  o: '1101',
  ' ': '1110',
  u: '1111'
}

Decoded Text: hello huffman