文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

js如何实现哈弗曼编码

2024-04-02 19:55

关注

小编给大家分享一下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())

以上是“js如何实现哈弗曼编码”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网行业资讯频道!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯