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

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