快捷導(dǎo)航

JS實現(xiàn)的哈夫曼編碼示例【原始版與修改版】

更新時間：2018年04月22日 12:25:03 作者：標子

這篇文章主要介紹了JS實現(xiàn)的哈夫曼編碼,結(jié)合實例形式分析了基于JavaScript定義、使用哈夫曼樹進行編碼、解碼等相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了JS實現(xiàn)的哈夫曼編碼。分享給大家供大家參考，具體如下：

原始版

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 = {};
  // 哈夫曼樹節(jié)點列表
  this.nodeList = null;
  // 哈夫曼樹根節(jié)點
  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();

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

您可能感興趣的文章: