Example code of Huffman Compression.

huffman.js

// ==============================================
// ハフマン圧縮アルゴリズムの実装
// ==============================================

// ツリーの生成
function create_tree(str) {
  // 登場回数を算出
  var count = {};
  str.split('').forEach(function(word){
    if (!(word in count)) {
      count[word] = 0;
    }
    count[word]++;
  });

  // 配列に変換
  var tree = [];
  for(var word in count) {
    tree.push({
      weight: count[word],
      word:   word
    });
  }

  // 比較関数
  var comparator = function(a, b){
    if (a.weight < b.weight) return 1;
    if (a.weight > b.weight) return -1;
    return 0;
  };

  // 2分木を生成
  while (tree.length >= 2) {
    tree = tree.sort(comparator);

    var node1 = tree.pop();
    var node2 = tree.pop();

    tree.push({
      weight: node1.weight + node2.weight,
      tree:   [node1, node2]
    });
  }

  return tree[0];
}

// 変換テーブルの出力
function create_table(root, table, code) {
  code = code || '';

  if ('tree' in root) {
    create_table(root.tree[0], table, code+'0');
    create_table(root.tree[1], table, code+'1');
  } else {
    table[root.word] = code;
  }
}

// エンコード
function encode(str, tree) {
  var encoded_str = '';
  var table = {};

  // テーブルを生成
  create_table(tree, table);
  // テーブルを元にエンコード
  str.split('').forEach(function(char){
    encoded_str += table[char];
  });

  return encoded_str;
}

// デコード
function decode(encoded_str, tree) {
  var str = '';
  var index = 0;

  encoded_str = encoded_str.split('');

  while (index < encoded_str.length) {
    var word = null;
    var current = tree;

    while (word === null) {
      var bit = parseInt(encoded_str[index], 10);
      index++;

      current = current.tree[bit];
      if ('word' in current) {
        word = current.word;
      }
    }

    str += word;
  }

  return str;
}

var str = 'aabbccccddddeeeeeeeeffff';
var tree = create_tree(str);
var encoded_str = encode(str, tree);
var decoded_str = decode(encoded_str, tree);

console.log('Original:', str);
console.log('Compressed:', encoded_str);
console.log('Decompressed:', decoded_str);