JS实现的哈夫曼编码示例【原始版与修改版】
本文实例讲述了JS实现的哈夫曼编码。分享给大家供大家参考，具体如下：
原始版
functioncal(str){
if(typeofstr!=='string'||str.length<1){
return;
}
varmap={};
vari=0;
while(str[i]){
map[str[i]]?map[str[i]]++:(map[str[i]]=1);
i++;
}
returnmap;
}
functionsort(map){
map=map||{};
varresult=[];
for(keyinmap){
if(map.hasOwnProperty(key)){
varobj={
key:key,
val:map[key]
};
result.push(newNode(null,null,obj));
}
}
returnresult.sort(function(x,y){returnx.data.val>y.data.val});
}
functionNode(left,right,data){
this.left=left;
this.right=right;
this.data=data;
}
functionmakeTree(table){
vari=0;
varlen=table.length;
varnode1;
varnode2;
varparentNode;
while(table.length>1){
parentNode=newNode(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){returnx.data.val>y.data.val});
}
returntable;
}
functionencode(str,ret){
if(typeofstr!=='string'||str.length<1){
return;
}
vari=0;
varresult='';
while(str[i]){
result+=ret[str[i++]];
}
returnresult
}
functionreverseRet(ret){
varresult={};
for(keyinret){
if(ret.hasOwnProperty(key)){
result[ret[key]]=key;
}
}
returnresult;
}
functiondecode(str,ret){
vari=0;
varresult='';
vardata='';
varmap=reverseRet(ret);
while(str){
result+=str[i++];
if(resultinmap){
data+=map[result];
str=str.replace(newRegExp("^"+result),'');
result='';
i=0;
}
}
console.log(data)
}
functiontraversal(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;
}
}
varret={};
varstr='ewqewqdef24gfewrgetElementsByTagName';
traversal(makeTree(sort(cal(str)))[0],'',ret)
decode(encode(str,ret),ret)
btoa(encode(str,ret))
修改版
functionHuffman(str){
//需要编码的字符串
this.str=str;
//键和频率映射表
this.keyCountMap=null;
//编码和键的映射表
this.codeKeyMap={};
//键和编码的映射表
this.keyCodeMap={};
//哈夫曼树节点列表
this.nodeList=null;
//哈夫曼树根节点
this.root=null;
//哈夫曼编码后的01序列
this.code=null;
}
Huffman.prototype.cal=functioncal(){
str=this.str;
varmap={};
vari=0;
while(str[i]){
map[str[i]]?map[str[i]]++:(map[str[i]]=1);
i++;
}
this.keyCountMap=map;
}
Huffman.prototype.sort=functionsort(){
map=this.keyCountMap;
varresult=[];
for(keyinmap){
if(map.hasOwnProperty(key)){
varobj={
key:key,
val:map[key]
};
result.push(newNode(null,null,obj));
}
}
this.nodeList=result.sort(function(x,y){returnx.data.val>y.data.val});
}
functionNode(left,right,data){
this.left=left;
this.right=right;
this.data=data;
}
Huffman.prototype.makeTree=functionmakeTree(){
vari=0;
varlen=this.nodeList.length;
varnode1;
varnode2;
varparentNode;
vartable=this.nodeList;
while(table.length>1){
parentNode=newNode(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){returnx.data.val>y.data.val});
}
this.root=table[0]||newNode();
returnthis.root;
}
Huffman.prototype.traversal=functiontraversal(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=functionencode(){
this.cal();
this.sort();
varroot=this.makeTree();
this.traversal(root,'');
varret=this.keyCodeMap;
vari=0;
varresult='';
varstr=this.str;
while(str[i]){
result+=ret[str[i++]];
}
this.code=result;
console.log('encode:'+result);
returnresult
}
Huffman.prototype.reverseMap=functionreverseMap(){
varret=this.keyCodeMap;
varresult={};
for(keyinret){
if(ret.hasOwnProperty(key)){
result[ret[key]]=key;
}
}
this.codeKeyMap=result;
returnresult;
}
Huffman.prototype.decode=functiondecode(){
vari=0;
varresult='';
vardata='';
varmap=this.reverseMap();
varstr=this.code;
while(str){
result+=str[i++];
if(resultinmap){
data+=map[result];
str=str.replace(newRegExp("^"+result),'');
result='';
i=0;
}
}
console.log("decode:"+data)
}
Huffman.prototype.encodeBase64=function(){
try{
varbase64=btoa(this.code);
returnbase64;
}catch(e){
return'';
}
}
varstr='ewqewqdef24gfewrgetElementsByTagName';
varhuffman=newHuffman(str)
huffman.encode(str)
huffman.decode();
huffman.encodeBase64();
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。