JS实现的哈夫曼编码示例【原始版与修改版】

function cal(str) {  if (typeof str !== 'string' || str.length < 1) {    return;  }  var map = {};  var i = 0;  while(str[i]) {    map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);    i++;  }  return map;}function sort(map) {  map = map || {};  var result = [];  for (key in map) {    if(map.hasOwnProperty(key)) {      var obj = {        key: key,        val: map[key]      };      result.push(new Node(null, null, obj));    }  }  return result.sort(function(x,y){return x.data.val > y.data.val});}function Node(left, right, data) {  this.left = left;  this.right = right;  this.data = data;}function makeTree(table) {  var i = 0;  var len = table.length;  var node1;  var node2;  var parentNode;  while(table.length > 1) {    parentNode = new Node(table[i], table[i+1], {key: null, val: table[i]['data'].val + table[i+1]['data'].val});    table.splice(i,2);    table.unshift(parentNode);    table.sort(function(x,y){return x.data.val > y.data.val});  }  return table;}function encode(str, ret) {  if (typeof str !== 'string' || str.length < 1) {    return;  }  var i = 0;  var result = '';  while(str[i]) {    result += ret[str[i++]];  }  return result}function reverseRet(ret) {  var result = {};  for (key in ret) {    if(ret.hasOwnProperty(key)) {      result[ret[key]] = key;    }  }  return result;}function decode(str, ret) {  var i = 0;  var result = '';  var data = '';  var map = reverseRet(ret);  while(str) {    result += str[i++];    if (result in map) {      data += map[result];      str = str.replace(new RegExp("^"+result),'');      result = '';      i = 0;    }  }  console.log(data)}function traversal(tree, code, ret) {  if (tree.left !== null) {    traversal(tree.left, code + '0', ret);  } else {    ret[tree.data.key] = code;  }  if (tree.right !== null) {    traversal(tree.right,code + '1', ret);  } else {    ret[tree.data.key] = code;  }}var ret = {};var str = 'ew qew qd ef 24 gf ewr getElementsByTagName';traversal(makeTree(sort(cal(str)))[0],'', ret)decode(encode(str, ret), ret)btoa(encode(str,ret))

function Huffman(str) {  // 需要编码的字符串  this.str = str;  // 键和频率映射表  this.keyCountMap = null;  // 编码和键的映射表  this.codeKeyMap = {};  // 键和编码的映射表  this.keyCodeMap = {};  // 哈夫曼树节点列表  this.nodeList = null;  // 哈夫曼树根节点  this.root = null;  // 哈夫曼编码后的01序列  this.code = null;}Huffman.prototype.cal = function cal() {  str = this.str;  var map = {};  var i = 0;  while(str[i]) {    map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1);    i++;  }  this.keyCountMap = map;}Huffman.prototype.sort = function sort() {  map = this.keyCountMap;  var result = [];  for (key in map) {    if(map.hasOwnProperty(key)) {      var obj = {        key: key,        val: map[key]      };      result.push(new Node(null, null, obj));    }  }  this.nodeList = result.sort(function(x,y){return x.data.val > y.data.val});}function Node(left, right, data) {  this.left = left;  this.right = right;  this.data = data;}Huffman.prototype.makeTree = function makeTree() {  var i = 0;  var len = this.nodeList.length;  var node1;  var node2;  var parentNode;  var table = this.nodeList;  while(table.length > 1) {    parentNode = new Node(table[i], table[i+1], {key: null, val: table[i]['data'].val + table[i+1]['data'].val});    table.splice(i,2);    table.unshift(parentNode);    table.sort(function(x,y){return x.data.val > y.data.val});  }  this.root = table[0] || new Node();  return this.root;}Huffman.prototype.traversal = function traversal(tree, code) {  if (tree.left !== null) {    traversal.call(this,tree.left, code + '0');  } else {    this.keyCodeMap[tree.data.key] = code;  }  if (tree.right !== null) {    traversal.call(this, tree.right,code + '1');  } else {    this.keyCodeMap[tree.data.key] = code;  }}Huffman.prototype.encode = function encode() {  this.cal();  this.sort();  var root = this.makeTree();  this.traversal(root, '');  var ret = this.keyCodeMap;  var i = 0;  var result = '';  var str = this.str;  while(str[i]) {    result += ret[str[i++]];  }  this.code = result;  console.log('encode:' + result);  return result}Huffman.prototype.reverseMap = function reverseMap() {  var ret = this.keyCodeMap;  var result = {};  for (key in ret) {    if(ret.hasOwnProperty(key)) {      result[ret[key]] = key;    }  }  this.codeKeyMap = result;  return result;}Huffman.prototype.decode = function decode() {  var i = 0;  var result = '';  var data = '';  var map = this.reverseMap();  var str = this.code;  while(str) {    result += str[i++];    if (result in map) {      data += map[result];      str = str.replace(new RegExp("^"+result),'');      result = '';      i = 0;    }  }  console.log("decode:" + data)}Huffman.prototype.encodeBase64 = function() {  try {    var base64 = btoa(this.code);    return base64;  } catch(e) {    return '';  }}var str = 'ew qew qd ef 24 gf ewr getElementsByTagName';var huffman = new Huffman(str)huffman.encode(str)huffman.decode();huffman.encodeBase64();