Detailed explanation of the steps to implement Huffman coding in Yuansheng js

This time I will bring you a detailed explanation of the steps to implement Huffman encoding in Yuansheng js. What are the precautions for Yuansheng js to implement Huffman encoding. The following is a practical case, let’s take a look.

Original version

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 = &#39;&#39;;
  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 = &#39;&#39;;
  var data = &#39;&#39;;
  var map = reverseRet(ret);
  while(str) {
    result += str[i++];
    if (result in map) {
      data += map[result];
      str = str.replace(new RegExp("^"+result),&#39;&#39;);
      result = &#39;&#39;;
      i = 0;
    }
  }
  console.log(data)
}
function traversal(tree, code, ret) {
  if (tree.left !== null) {
    traversal(tree.left, code + &#39;0&#39;, ret);
  } else {
    ret[tree.data.key] = code;
  }
  if (tree.right !== null) {
    traversal(tree.right,code + &#39;1&#39;, ret);
  } else {
    ret[tree.data.key] = code;
  }
}
var ret = {};
var str = &#39;ew qew qd ef 24 gf ewr getElementsByTagName&#39;;
traversal(makeTree(sort(cal(str)))[0],&#39;&#39;, ret)
decode(encode(str, ret), ret)
btoa(encode(str,ret))

Modified version

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();

Believe it or not After reading the case in this article, you have mastered the method. For more exciting information, please pay attention to other related articles on the PHP Chinese website!

Recommended reading:

Detailed explanation of the steps to read and remove duplicate excel using nodejs

Detailed explanation of the use of classes in js and typescript

The above is the detailed content of Detailed explanation of the steps to implement Huffman coding in Yuansheng js. For more information, please follow other related articles on the PHP Chinese website!