Skip to content

Instantly share code, notes, and snippets.

@siddMahen
Created December 28, 2014 16:10
Show Gist options
  • Save siddMahen/8fc9fe1813fa931a90ce to your computer and use it in GitHub Desktop.
Save siddMahen/8fc9fe1813fa931a90ce to your computer and use it in GitHub Desktop.
var alg = require("algorithms"),
sort = alg.mergeSort;
/*
* Huffman coding.
*
* @api public
*/
var huffman = function(alphabet){
if(!(this instanceof huffman))
return new huffman(alphabet);
var syms = [],
symtbl = {};
for(var sym in alphabet){
symtbl[sym] = null;
syms.push({ obj: [sym], key: alphabet[sym] });
}
var cmp = function(a, b){ return a.key >= b.key },
h = sort(syms, cmp);
while(h.length !== 2){
var fmin = h.pop(),
smin = h.pop();
var meta = smin.obj.concat(fmin.obj),
key = fmin.key + smin.key;
h.push({ obj: meta, key: key });
h = sort(h, cmp);
}
var rsyms = h[0]["obj"],
lsyms = h[1]["obj"],
isone = false,
split = function(array, base){
if(array.length === 1){
if(isone) symtbl[array[0]] = base + "0";
else symtbl[array[0]] = base + "1";
}else if(array.length === 2){
var sym = array.shift();
symtbl[sym] = base + "0";
var sym = array.shift();
symtbl[sym] = base + "1";
}else{
var sym = array.shift();
symtbl[sym] = base + "0";
split(array, base + "1");
}
isone = !isone;
return;
};
if(lsyms.length === 1){
symtbl[lsyms[0]] = "0";
split(rsyms, "1");
}else{
split(lsyms, "0");
split(rsyms, "1");
}
var luptbl = {};
for(var i in symtbl){
luptbl[symtbl[i]] = i;
}
this.symtbl = symtbl;
this.luptbl = luptbl;
}
/*
* Encode a string.
*
* @returns {String} encoded string
*
* @api public
*/
huffman.prototype.encode = function(str){
var enc = [];
for(var i = 0; i < str.length; i++){
var code = this.symtbl[str[i]];
if(code !== undefined){
enc = enc.concat(code);
}
}
return enc.join("");
}
/*
* Decode a buffer.
*
* @returns {String} decoded string
*
* @api public
*/
huffman.prototype.decode = function(str){
var holder = "",
out = ""
luptbl = this.luptbl;
for(var i = 0; i < str.length; i++){
var letter = str[i];
holder += letter;
var decode = luptbl[holder];
if(decode){
out += decode;
holder = "";
}
}
return out;
}
// Exports
module.exports = huffman;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment