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