这次给大家带来怎样使用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();
相信看了本文案例你已经掌握了方法，更多精彩请关注其它相关文章！
推荐阅读：
使用vue做出分页器（附代码）
如何做出vue移动端实现下拉刷新功能
如何使用vue.js中router传参
以上就是怎样使用js实现哈夫曼编码的详细内容。