huffman_coding.js

// The following code implements Huffman Coding: 
// https://en.wikipedia.org/wiki/Huffman_coding 
function start() {
    var text = readLine("enter text:\n");
    
    var counterMap = new Map();
    for (var i = 0; i < text.length; i++) {
        var char = text.charAt(i);
        if(!counterMap.has(char)) {
            counterMap.set(char, 0);
        }
        
        counterMap.set(char, counterMap.get(char) + 1);
    }
    
    println();
    println("Letter frequency, in descending order:");
    new Map([...counterMap.entries()].sort((a, b) => b[1] - a[1]))
        .forEach((v,k) => {println(k + ": " + v);});
    println();
    
    var [encodingMap, root] = generaterEncoding(counterMap);
    println("Encoding mapping, in ascending order of length:");
    new Map([...encodingMap.entries()].sort((a, b) => a[1].length - b[1].length))
        .forEach((v,k) => {println(k + ": " + v);});
    println();
    
    var encoded = "";
    for (var i = 0; i < text.length; i++) {
        encoded += encodingMap.get(text.charAt(i));
    }
    
    println("Encoded text:");
    println(encoded);
    println();
    println("Encoded text is " + encoded.length + " bit long");
    println("Original text is " + text.length * 8 + " bit long");
    println("Compression ratio: " + (text.length * 8.0 / encoded.length));
    println();
    
    var deocded = decode(encoded, root);
    println("Decoded text:");
    println(deocded);
    println();
}

function decode(encoded, root) {
    var decoded = "";
    var curr = root;
    for(var i = 0; i < encoded.length; i++) {
        var char = encoded.charAt(i);
    
        if(char == '0') {  
            curr = curr.left;
        } else {
            curr = curr.right;
        }
           
        if(curr.c != null) {
            decoded += curr.c;
            curr = root;
        }
    }
    
    return decoded;
}


function generaterEncoding(counterMap) {
	let q = [];
	
	counterMap.forEach((freq, char) => {
		q.push(new HuffmanNode(freq, char, null, null)); 
    });
	
	let root = null; 
	q.sort(function(a,b){return a.data-b.data;}); 
		
	while (q.length > 1) { 
	    var [x, y] = q.splice(0, 2);
		let f = new HuffmanNode(x.data + y.data, null, x, y); 
		root = f; 
		q.push(f); 
		q.sort(function(a,b){return a.data-b.data;}); 
	} 
	
	var encodingMap = new Map;
	traverseCode(root, "", encodingMap); 
	return [encodingMap, root];
}

function traverseCode(node, s, encodingMap) { 
	if (isLeaf(node)) {
		encodingMap.set(node.c, s); 
	} else {
	    // if we go to left then add "0" to the code. 
	    // if we go to the right add"1" to the code. 
	    traverseCode(node.left, s + "0", encodingMap); 
	    traverseCode(node.right, s + "1", encodingMap);
	}
} 

function isLeaf(node) {
    return node.left == null
		&& node.right == null
		&& node.c != null;
}

class HuffmanNode { 
	constructor(data, c, left, right) { 
		this.data = data; 
		this.c = c; 
		this.left = left;
		this.right = right; 
	} 
}