怎样使用JS实现哈夫曼编码

来源：榕意旅游网

这次给大家带来怎样使用JS实现哈夫曼编码，使用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();

相信看了本文案例你已经掌握了方法，更多精彩请关注Gxl网其它相关文章！