Huffman's compression algorithm implemented in JavaScript.
The other night I have implemented Huffman's compression algorithm in JavaScript.
Here is a wiki link describing what Huffman coding is:
http://en.wikipedia.org/wiki/Huffman_codingMy working example:
http://tom-ash.net/blogs/Programming/huffman_coding.htmlAnd its source code without the alerts:
<html>
<head>
<title>Huffman's compression algorithm implemented in JavaScript</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>