JS怎么实现的哈夫曼编码

这篇文章将为大家详细讲解有关JS怎么实现的哈夫曼编码，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

JS是什么

JS是JavaScript的简称，它是一种直译式的脚本语言，其解释器被称为JavaScript引擎，是浏览器的一部分，主要用于web的开发，可以给网站添加各种各样的动态效果，让网页更加美观。

本文实例讲述了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();

关于“JS怎么实现的哈夫曼编码”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。