Monday, October 3, 2011

Huffman's compression algorithm implemented in JavaScript

Originally published 2009-06-02, on tom-ash.net

The other night I have implemented Huffman's compression algorithm in JavaScript. Here is a wiki link describing what Huffman coding is:
Huffman coding
Here is my JavaScript implementation:
<html>
<head>
<title>Huffman's compression algorithm implemented in JavaScript 
by Tomasz Andraszek</title>
<script type="text/javascript">
   
function compress() {
 var input = document.getElementById("input").value;
 document.getElementById("inputlength").innerHTML =input.length*8;
 var probabilities = getProbabilities(input);
 var codes = getCodes(probabilities);
 var output = compressHuffman(input, codes);
 
 var temp = "";
 for (var elem in probabilities) {
   temp += elem + " = " + probabilities[elem] + "<br/>";
 }
 document.getElementById("probabilities").innerHTML = temp;
 
 temp = "";
 for (var elem in codes) {
   temp += elem + " = " + codes[elem] + "<br/>";
 }
 document.getElementById("codes").innerHTML = temp;
 document.getElementById("output").innerHTML = output;
 document.getElementById("outputlength").innerHTML =output.length;
}

function sortNumberAsc(a, b) {
 return a[1] - b[1];
}

function getCodes(prob) {
 var tree = new Array();
 var secondTree = new Array();
 
 this.getNext = function() {
 if (tree.length > 0 && secondTree.length > 0 
               && tree[0].prob < secondTree[0].prob)
   return tree.shift();
 
 if (tree.length > 0 && secondTree.length > 0 
                && tree[0].prob > secondTree[0].prob)
   return secondTree.shift();
 
 if (tree.length > 0)
   return tree.shift();
 
 return secondTree.shift();
 }
 var sortedProb = new Array();
 var codes = new Array();
 
 var x = 0;
 for (var elem in prob) {
   sortedProb[x] = new Array(elem, prob[elem]);
   x = x + 1;
 }
 
 sortedProb = sortedProb.sort(sortNumberAsc);
 x = 0;
 
 for (var elem in sortedProb) {
   tree[x] = new node();
   tree[x].prob = sortedProb[elem][1];
   tree[x].value = sortedProb[elem][0];
   x = x + 1;
 }
 while (tree.length + secondTree.length > 1) {
  var left = getNext();
  var right = getNext();
  var newnode = new node();
  newnode.left = left;
  newnode.right = right;
  newnode.prob = left.prob + right.prob;
  newnode.left.parent = newnode;
  newnode.right.parent = newnode;
  secondTree.push(newnode);
 }

 var currentnode = secondTree[0];
 var code = "";
 while (currentnode) {
  if (currentnode.value) {
   codes[currentnode.value] = code;
   code = code.substr(0, code.length - 1);
   currentnode.visited = true;
   currentnode = currentnode.parent;
  }
  else if (!currentnode.left.visited) {
   currentnode = currentnode.left;
   code += "0";
  }
  else if (!currentnode.right.visited) {
   currentnode = currentnode.right;
   code += "1";
  }
  else {
   currentnode.visited = true;
   currentnode = currentnode.parent;
   code = code.substr(0, code.length - 1);
  }
 }
 return codes;
}

function node() {
  this.left = null;
  this.right = null;
  this.prob = null;
  this.value = null;
  this.code = "";
  this.parent = null;
  this.visited = false;
}

function compressHuffman(input, codes) {
  var output = input.split("");
  for (var elem in output) {
   output[elem] = codes[output[elem]];
  }
  return output.join("");
}

function getProbabilities(input) {
  var prob = new Array();
  var x = 0;
  var len = input.length;
  while (x < len) {
   var chr = input.charAt(x);
   if (prob[chr]) {
    prob[chr] = prob[chr] + 1;
   }
   else {
    prob[chr] = 1;
   }
   x++;
  }

  for (var elem in prob) {
   prob[elem] = prob[elem] / len;
  }
  return prob;
}
</script>

</head>
<body>
Type in the text to compress here:<br />
<textarea id="input" rows="5" cols="80">aaabcc</textarea><br/>
<input type="button" onclick="compress()" value="Compress" /><br/>
Text's length (8 bits per character): <span id="inputlength"></span><br/>
Probabilities of all distinct characters in the text:<br />
<span id="probabilities"></span><br/>
Binary codes assigned to characters: <br /><span id="codes"></span><br/>
Binary output: <span id="output"></span><br/>
Output's length in bits: <span id="outputlength"></span><br/>
</body>
</html>

1 comment:

  1. i find a free online service to compress js and minify css, so it will reduce the size of web page.

    ReplyDelete