js神秘的电报密码 哈弗曼编码实现

这篇文章主要介绍了js神秘的电报密码哈弗曼编码,文中通过示例代码介绍的非常详细，对大

这篇文章主要介绍了js神秘的电报密码 哈弗曼编码,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

哈夫曼编码，根据每个单词在文本中出现的次数频率为权值，频率高的权值大。然后每次取两个频率最小的生成树，最后生成一颗大树。从根节点到该单词的路径，左边为0，右边为1,

function HFM(){
 var souce = []; 
 function createNode(node){
 var obj = {
 weight:0, 
 parent:-1,
 lchild:-1,
 rchild:-1,
 value:''
 }; 
 return Object.assign(obj,node);
 } 
 this.addNode = function(node){
 //添加单词和频率（权值）
 souce.push(createNode(node));
 } 
 this.createTree = function(){
 //哈夫曼树
 var HuffNode = JSON.parse(JSON.stringify(souce));
 var n = HuffNode.length; 
 var x1,x2; //两个权值最小的索引
 var m1,m2; //两个权值最小的值 
 for(var i = 0; i < n ; i++){
 m1 = m2 = Infinity; //初始化为最大值
 x1 = x2 = -1; 
 for(var j = 0; j < n+i; j++){ //寻找两个权值最小，且父节点为-1的
 var item = HuffNode[j];
 if(item.weight < m1 && item.parent == -1){
 m2 = m1;
 x2 = x1; 
 m1 = item.weight;
 x1 = j;
 
 }else if(item.weight < m2 && item.parent == -1){
 m2 = item.weight;;
 x2 = j;
 }
 } 
 if(x1 != -1 && x2 != -1){
 HuffNode[x1].parent = n + i; //更新父节点
 HuffNode[x2].parent = n + i;
 
 //创建一个新的节点
 HuffNode[n+i] = createNode({
 weight:m1+m2,
 lchild:x1,
 rchild:x2
 });
 } 
 } 
 return HuffNode;
 }; 
 this.getCode = function(){
 //哈夫曼编码
 var n = souce.length;
 var tree = this.createTree();
 var codes = {};
 for(var i = 0; i < n; i++){
 var p = tree[i].parent;
 var code = '';
 var c = i;
 while(p != -1){ //迭代前溯
 if(tree[p].lchild == c){
 code = 0 + code;
 }else{
 code = 1 + code;
 }
 c = p;
 p = tree[p].parent;
 } 
 codes[ tree[i].value ] = code;
 console.log(tree[i].value , code); 
 } 
 return codes;
 } 
} 
var hfm = new HFM();
hfm.addNode({
 weight:5,
 value:"a"
});
hfm.addNode({
 weight:32,
 value:"b"
});
hfm.addNode({
 weight:18,
 value:"c"
});
hfm.addNode({
 weight:7,
 value:"d"
});
hfm.addNode({
 weight:25,
 value:"e"
});
hfm.addNode({
 weight:13,
 value:"f"
});
console.log(hfm.getCode())

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。