Exploring the Huffman Compression Algorithm in JavaScript

The JavaScript program below displays a simple message, encodes that message using a Huffman tree, displays the tree and the message encoded as bits, then decodes those bits using the same tree and displays the result, to verify that it matches.  It’s not very optimized–it’s mostly just intended to show how the algorithm works.

The output of the file looks like this:

messageToEncode is Your attention please, Mister Huffman has left the building!
huffmanTree is 
{symbol='fsetinmHdbpYM,ro!gh alu' frequency='60' }
    {symbol='fsetin' frequency='26' }
        {symbol='fse' frequency='12' }
            {symbol='fs' frequency='6' }
                {symbol='f' frequency='3' }
                {symbol='s' frequency='3' }
            {symbol='e' frequency='6' }
        {symbol='tin' frequency='14' }
            {symbol='t' frequency='6' }
            {symbol='in' frequency='8' }
                {symbol='i' frequency='4' }
                {symbol='n' frequency='4' }
    {symbol='mHdbpYM,ro!gh alu' frequency='34' }
        {symbol='mHdbpYM,ro!gh' frequency='16' }
            {symbol='mHdbpYM,' frequency='8' }
                {symbol='mHdb' frequency='4' }
                    {symbol='mH' frequency='2' }
                        {symbol='m' frequency='1' }
                        {symbol='H' frequency='1' }
                    {symbol='db' frequency='2' }
                        {symbol='d' frequency='1' }
                        {symbol='b' frequency='1' }
                {symbol='pYM,' frequency='4' }
                    {symbol='pY' frequency='2' }
                        {symbol='p' frequency='1' }
                        {symbol='Y' frequency='1' }
                    {symbol='M,' frequency='2' }
                        {symbol='M' frequency='1' }
                        {symbol=',' frequency='1' }
            {symbol='ro!gh' frequency='8' }
                {symbol='ro' frequency='4' }
                    {symbol='r' frequency='2' }
                    {symbol='o' frequency='2' }
                {symbol='!gh' frequency='4' }
                    {symbol='!g' frequency='2' }
                        {symbol='!' frequency='1' }
                        {symbol='g' frequency='1' }
                    {symbol='h' frequency='2' }
        {symbol=' alu' frequency='18' }
            {symbol=' ' frequency='8' }
            {symbol='alu' frequency='10' }
                {symbol='a' frequency='4' }
                {symbol='lu' frequency='6' }
                    {symbol='l' frequency='3' }
                    {symbol='u' frequency='3' }

messageEncoded is 100101101011111110100110111001001000101110100110101010111110100100111100011110000100110011111010011001100001010001101001101000011111100000000100000111001111101011111100001110111100010000010110010101110011101000111111101101111010001001100111101101101100
messageDecoded is Your attention please, Mister Huffman has left the building!

And here’s the code that produces that result:

<html>
<body>
<script type='text/javascript'>

// main

function main()
{
	var newline = "<br />";
	var messageToEncode = "Your attention please, Mister Huffman has left the building!"
	document.write("messageToEncode is " + messageToEncode + newline);
	var huffmanEncoding = new HuffmanEncoding();
	huffmanEncoding.encodeMessageIntoBits(messageToEncode);
	document.write("huffmanTree is " + newline + huffmanEncoding.treeRoot.toString("") + newline);
	document.write("messageEncoded is " + huffmanEncoding.bitsEncoded.join("") + newline);
	var messageDecoded = huffmanEncoding.decodeMessageFromBits(huffmanEncoding.bitsEncoded);
	document.write("messageDecoded is " + messageDecoded + newline);
}

// classes

function HuffmanEncoding()
{}
{
	HuffmanEncoding.prototype.decodeMessageFromBits = function(bitsToDecode)
	{
		var messageDecoded = "";

		var treeNodeCurrent = this.treeRoot;

		for (var b = 0; b < bitsToDecode.length; b++)
		{
			var bitCurrent = bitsToDecode[b];
			treeNodeCurrent = treeNodeCurrent.children[bitCurrent];

			if (treeNodeCurrent.children.length == 0)
			{
				messageDecoded += treeNodeCurrent.symbol;
				treeNodeCurrent = this.treeRoot;
			}
		}

		return messageDecoded;
	}

	HuffmanEncoding.prototype.encodeMessageIntoBits = function(messageToEncode)
	{
		var numberOfUniqueSymbols = 0;
		var symbolToFrequencyLookup = [];

		for (var i = 0; i < messageToEncode.length; i++)
		{
			var symbol = messageToEncode[i];
			var frequencyOfSymbol = symbolToFrequencyLookup[symbol];
			if (frequencyOfSymbol == null)
			{
				numberOfUniqueSymbols++;
				frequencyOfSymbol = 0;
			}
			frequencyOfSymbol++;
			symbolToFrequencyLookup[symbol] = frequencyOfSymbol;
		}

		var treeNodesForSymbols = [];
		var symbolToTreeNodeLookup = [];

		for (var symbol in symbolToFrequencyLookup)
		{
			var frequencyOfSymbol = symbolToFrequencyLookup[symbol];
			var treeNodeForSymbol = new HuffmanTreeNode
			(
				symbol,
				frequencyOfSymbol,
				[] // children
			);

			symbolToTreeNodeLookup[symbol] = treeNodeForSymbol;

			var i;
			for (i = 0; i < treeNodesForSymbols.length; i++)
			{
				var treeNodeExisting = treeNodesForSymbols[i];
				if (frequencyOfSymbol <= treeNodeExisting.frequency)
				{					
					break;
				}
			}

			treeNodesForSymbols.splice(i, 0, treeNodeForSymbol);
		}

		var treeNodeParent;

		while (treeNodesForSymbols.length > 1)
		{
			var treeNodesWithFrequenciesLeast = 
			[
				treeNodesForSymbols[0],
				treeNodesForSymbols[1]
			];

			treeNodesForSymbols.splice(0, 1);
			treeNodesForSymbols.splice(0, 1);

			var symbolsCombined = 
				treeNodesWithFrequenciesLeast[0].symbol
				+ treeNodesWithFrequenciesLeast[1].symbol;

			var sumOfFrequencies = 
				treeNodesWithFrequenciesLeast[0].frequency
				+ treeNodesWithFrequenciesLeast[1].frequency;

			treeNodeParent = new HuffmanTreeNode
			(
				symbolsCombined, // symbol
				sumOfFrequencies, // frequency
				treeNodesWithFrequenciesLeast // children
			)

			var i;
			for (i = 0; i < treeNodesForSymbols.length; i++)
			{
				var treeNodeExisting = treeNodesForSymbols[i];
				if (sumOfFrequencies <= treeNodeExisting.frequency)
				{
					break;
				}
			}	
			treeNodesForSymbols.splice(i, 0, treeNodeParent);	
		}

		this.treeRoot = treeNodeParent;

		var bitsEncoded = [];
		var bitsForSymbol = [];

		for (var i = 0; i < messageToEncode.length; i++)
		{
			var symbol = messageToEncode[i];
			var treeNodeCurrent = symbolToTreeNodeLookup[symbol];

			bitsForSymbol.length = 0;			
			while (treeNodeCurrent.parent != null)
			{
				var parent = treeNodeCurrent.parent;
				var indexWithinParent = parent.children.indexOf
				(
					treeNodeCurrent
				);
				bitsForSymbol.splice(0, 0, indexWithinParent);
				treeNodeCurrent = treeNodeCurrent.parent;
			}	

			for (var b = 0; b < bitsForSymbol.length; b++)
			{
				var bitCurrent = bitsForSymbol[b];
				bitsEncoded.push(bitCurrent);
			}
		}

		this.bitsEncoded = bitsEncoded;

		return this.bitsEncoded;
	}

	HuffmanEncoding.prototype.toString = function()
	{
		var treeAsString = this.treeRoot.toString("");

		var bitsAsString = "";
		for (var b = 0; b < this.bitsEncoded.length; b++)
		{
			var bitCurrent = this.bitsEncoded[b];
			bitsAsString += bitCurrent;
		}

		var returnValue = treeAsString;
		returnValue += bitsAsString;

		return returnValue;
	}
}

function HuffmanTreeNode(symbol, frequency, children)
{
	this.symbol = symbol;
	this.frequency = frequency;
	this.children = children;

	for (var i = 0; i < this.children.length; i++)
	{
		var child = this.children[i];
		child.parent = this;
	}
}
{
	HuffmanTreeNode.prototype.toString = function(indentSoFar)
	{
		var returnValue = 
			indentSoFar
			+ "{"
			+ "symbol='" + this.symbol + "' "
			+ "frequency='" + this.frequency + "' "
			+ "}"
			+ "<br />";

		for (var i = 0; i < this.children.length; i++)
		{
			var child = this.children[i];
			returnValue += child.toString(indentSoFar + "&nbsp;&nbsp;&nbsp;&nbsp;");
		}

		return returnValue;
	}
}

// run

main();

</script>
</body>
</html>
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s