Lossless Text Compression with Huffman Coding in JavaScript
Lossless data compression relies on eliminating statistical redundancy from raw information streams without discarding a single bit of source data. In conventional character representations such as standard ASCII or fixed UTF-8 byte sequences, each symbol occupies a uniform 8-bit width regardless of whether it appears once or ten thousand times throughout a document. Developed by David A. Huffman in 1952, Huffman Coding circumvents this structural inefficiency by generating variable-length binary codes calibrated directly against observed symbol frequencies, serving as a core algorithmic engine within industry-standard compression formats including DEFLATE, GZIP, and JPEG.
The algorithm relies on a greedy tree-building process that repeatedly combines the least frequent symbols into composite parent nodes. High-frequency characters are situated near the root of the resulting binary tree and receive succinct bit sequences, whereas rare characters gravitate toward deeper branches and receive longer bit sequences. Because every encoded symbol corresponds strictly to a terminal leaf node, the generated codes satisfy the prefix property: no code is a prefix of any other code. This mathematical guarantee allows a continuous binary bitstream to be parsed and decoded sequentially without delimiters, ambiguity, or lookahead backtracking.
Example
// Conceptual overview of Huffman frequency tree and prefix codes
const input = "abracadabra";
// Character frequencies: { a: 5, b: 2, r: 2, c: 1, d: 1 }
// 'a' appears most frequently, so it receives the shortest prefix code ('0')
// 'b' and 'r' receive medium-length codes ('10', '110')
// 'c' and 'd' receive the longest codes ('1110', '1111')
// Encoded bitstream replaces 88 bits (11 chars * 8 bits) with 23 bits:
// 'a' -> 0, 'b' -> 10, 'r' -> 110, 'a' -> 0, 'c' -> 1110, ...
const encodedBits = "01011001110011110101100";
const decodedText = decodeHuffman(encodedBits, huffmanTree);
console.log(decodedText); // "abracadabra"Implementation
/**
* Binary Tree Node representing a character or an internal composite node.
*/
class HuffmanNode {
constructor(char, freq, left = null, right = null) {
this.char = char; // null for internal nodes
this.freq = freq; // total occurrence frequency
this.left = left; // left child branch (0)
this.right = right; // right child branch (1)
}
isLeaf() {
return this.left === null && this.right === null;
}
}
/**
* Builds a frequency mapping of each unique character in the source text.
* @param {string} text - Raw input string
* @returns {Map<string, number>} Character frequencies
*/
function buildFrequencyTable(text) {
const frequencies = new Map();
for (const char of text) {
frequencies.set(char, (frequencies.get(char) || 0) + 1);
}
return frequencies;
}
/**
* Builds the optimal Huffman binary tree using a priority queue.
* @param {Map<string, number>} frequencies
* @returns {HuffmanNode|null} Root of the Huffman Tree
*/
function buildHuffmanTree(frequencies) {
if (frequencies.size === 0) return null;
// Single-character edge case: wrap in an internal node with a single child
if (frequencies.size === 1) {
const [char, freq] = frequencies.entries().next().value;
const leaf = new HuffmanNode(char, freq);
return new HuffmanNode(null, freq, leaf, null);
}
// Priority collection sorted in ascending order of frequency
const queue = [];
for (const [char, freq] of frequencies.entries()) {
queue.push(new HuffmanNode(char, freq));
}
queue.sort((a, b) => a.freq - b.freq);
// Greedily combine the two lowest-frequency nodes until one root remains
while (queue.length > 1) {
const left = queue.shift();
const right = queue.shift();
const merged = new HuffmanNode(
null,
left.freq + right.freq,
left,
right
);
// Insert merged node back into the sorted queue
let inserted = false;
for (let i = 0; i < queue.length; i++) {
if (merged.freq < queue[i].freq) {
queue.splice(i, 0, merged);
inserted = true;
break;
}
}
if (!inserted) {
queue.push(merged);
}
}
return queue[0];
}
/**
* Recursively traverses the Huffman Tree to derive the prefix code dictionary.
* @param {HuffmanNode} node - Current node in the tree traversal
* @param {string} prefix - Accumulated bit string ('0' for left, '1' for right)
* @param {Map<string, string>} codes - Output dictionary
*/
function generatePrefixCodes(node, prefix = "", codes = new Map()) {
if (!node) return codes;
if (node.isLeaf()) {
codes.set(node.char, prefix.length > 0 ? prefix : "0");
return codes;
}
generatePrefixCodes(node.left, prefix + "0", codes);
generatePrefixCodes(node.right, prefix + "1", codes);
return codes;
}
/**
* Compresses an input string into a binary bitstring using Huffman Coding.
* @param {string} text - Plaintext to compress
* @returns {object} Encoded bitstring, tree root, and compression statistics
*/
function encode(text) {
if (!text || text.length === 0) {
return {
encoded: "",
tree: null,
codeTable: {},
originalBits: 0,
compressedBits: 0,
savingsPercent: "0.0%"
};
}
const frequencies = buildFrequencyTable(text);
const tree = buildHuffmanTree(frequencies);
const codes = generatePrefixCodes(tree);
let encoded = "";
for (const char of text) {
encoded += codes.get(char);
}
const originalBits = text.length * 8;
const compressedBits = encoded.length;
const savings = ((1 - compressedBits / originalBits) * 100).toFixed(1);
return {
encoded,
tree,
codeTable: Object.fromEntries(codes),
originalBits,
compressedBits,
savingsPercent: `${savings}%`
};
}
/**
* Decompresses a Huffman-encoded bitstring back to the original string.
* @param {string} encoded - Binary bitstring
* @param {HuffmanNode} tree - Root of the Huffman Tree used during encoding
* @returns {string} Reconstructed plaintext
*/
function decode(encoded, tree) {
if (!encoded || !tree) return "";
// Handle single-character tree special case
if (tree.left && tree.left.isLeaf() && !tree.right) {
return tree.left.char.repeat(encoded.length);
}
let decoded = "";
let currentNode = tree;
for (let i = 0; i < encoded.length; i++) {
const bit = encoded[i];
// Branch left on '0', right on '1'
currentNode = bit === "0" ? currentNode.left : currentNode.right;
if (!currentNode) {
throw new Error(`Corrupted bitstream encountered at offset ${i}`);
}
// Reached a leaf node: emit character and reset to tree root
if (currentNode.isLeaf()) {
decoded += currentNode.char;
currentNode = tree;
}
}
return decoded;
}
// ==========================================================================
// Verification and Demonstration
// ==========================================================================
const sampleText = "lossless compression algorithms eliminate statistical redundancy";
console.log(`Original Text: "${sampleText}"`);
const result = encode(sampleText);
console.log("\nGenerated Prefix Code Table:");
console.table(result.codeTable);
console.log(`\nOriginal Size: ${result.originalBits} bits (${sampleText.length} bytes)`);
console.log(`Compressed Size: ${result.compressedBits} bits (~${Math.ceil(result.compressedBits / 8)} bytes)`);
console.log(`Storage Savings: ${result.savingsPercent}`);
const recoveredText = decode(result.encoded, result.tree);
console.log(`\nDecoded Match: ${recoveredText === sampleText}`);Main Point: Huffman coding achieves optimal lossless text compression by constructing a frequency-weighted binary tree that maps common symbols to short, prefix-free binary bitstrings.