JS实现的哈夫曼编码示例【原始版与修改版】
程序员文章站
2022-03-31 14:09:32
本文实例讲述了js实现的哈夫曼编码。分享给大家供大家参考,具体如下:
原始版
function cal(str) {
if (typeof str !==...
本文实例讲述了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();
更多关于javascript相关内容感兴趣的读者可查看本站专题:《javascript数据结构与算法技巧总结》、《javascript数学运算用法总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。
上一篇: office2007密钥2007office密钥最新提供参考
下一篇: ajax实现数据分页查询