So verwenden Sie JS zur Implementierung der Huffman-Codierung

Dieses Mal zeige ich Ihnen, wie Sie JS zur Implementierung der Huffman-Codierung verwenden und welche Vorsichtsmaßnahmen für die Verwendung von JS zur Implementierung der Huffman-Codierung gelten. Hier ist ein praktischer Fall, schauen wir uns das an.

Originalversion

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

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

Glauben Sie es oder nicht Nachdem Sie den Fall in diesem Artikel gelesen haben, beherrschen Sie die Methode. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Mit Vue einen Paginator erstellen (mit Code)

So erstellen Sie eine mobile Vue-Implementierung Pulldown-Aktualisierungsfunktion

So verwenden Sie den Router in Vue.js zum Übergeben von Parametern

Das obige ist der detaillierte Inhalt vonSo verwenden Sie JS zur Implementierung der Huffman-Codierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!