哈夫曼树的js实现小白知识_运算使用攻略

哈夫曼树的js实现小白知识

前言

哈夫曼树是数据压缩编码算法的基础,本文使用JavaScript语言实现了该算法。算法流程:输入待编码的字符串,算法去构造哈夫曼树,从而实现对字符串的二进制压缩编码。

哈夫曼树的js实现小白知识_运算使用攻略

对于哈夫曼树理论的学习,可去参见其他文章。本文仅包含实现的代码以及注释。

注释比较丰富,相信不难理解。

算法实现

树节点

既然是树数据结构,就要有树节点,下面是树节点定义

class Node {  
    constructor(value, char, left, right) {  
        this.val = value; // 字符出现次数  
        this.char = char; // 待编码字符  
        this.left = left;  
        this.right = right;  
    }  
}

一般来说,节点只需要val,left,right即可,这里加了一个char字段,表示该节点代表待编码字符串里面的哪个字符,当前节点是叶子节点的时候,会赋值这个字段。

核心代码

构造函数
class huffmanTree{ 
    constructor(str){  
        // 第一步,统计字符出现频率  
        let hash = {};  
        for(let i = 0; i < str.length; i++){  
            hash[str[i]] = ~~hash[str[i]] + 1;  
        }  
        this.hash = hash;  
  
        // 第二步,构造哈夫曼树  
        this.huffmanTree = this.getHuffmanTree();  
  
        // 第三步,遍历哈夫曼树,得到编码表
        let map = this.getHuffmanCode(this.huffmanTree);  
        // 查看编码表,即每个字符的二进制编码是什么  
        console.log(map);  
  
        // 第四部,根据编码对照表,返回最终的二进制编码  
        this.binaryStr = this.getBinaryStr(map, str);  
    } 
}

下面我们逐一的看一下,(1)构造哈夫曼树的过程、(2)遍历哈弗曼树取得编码表的过程 以及 (3)返回最终二进制串的过程。

构造哈夫曼树
    // 构造哈夫曼树  
    getHuffmanTree(){  
        // 以各个字符出现次数为node.val, 构造森林  
        let forest = []  
        for(let char in this.hash){  
            let node = new Node(this.hash[char], char); 
            forest.push(node);  
        }  
  
        let allNodes = []; // 存放被合并的节点,因为不能真的删除森林中任何一个节点,否则.left .right就找不到节点了  
        // 等到森林只剩一个节点时,表示合并过程结束,树就生成了
        while(forest.length !== 1){  
            // 从森林中找到两个最小的树,合并之  
            forest.sort((a, b) => {  
                return a.val - b.val;  
            });  
  
            let node = new Node(forest[0].val + forest[1].val, '');  
            allNodes.push(forest[0]);  
            allNodes.push(forest[1]);  
            node.left = allNodes[allNodes.length - 2]; // 左子树放置词频低的  
            node.right = allNodes[allNodes.length - 1]; // 右子树放置词频高的  
  
            // 删除最小的两棵树  
            forest = forest.slice(2);  
            // 新增的树加入  
            forest.push(node);  
        }  
  
        // 生成的哈夫曼树,仅剩一个节点,即整棵树的根节点
        return forest[0];  
    } 
遍历哈夫曼树,返回编码表
    // 遍历哈夫曼树,返回一个 原始字符 和 二进制编码 的对照表  
    getHuffmanCode(tree){  
        let hash = {};  // 对照表
        let traversal = (node, curPath) => {  
            if (!node.length && !node.right) return;  
            if (node.left && !node.left.left && !node.left.right){  
                hash[node.left.char] = curPath + '0';  
            }  
            if (node.right && !node.right.left && !node.right.right){  
                hash[node.right.char] = curPath + '1';  
            }  
            // 往左遍历,路径加0  
            if(node.left){  
                traversal(node.left, curPath + '0');  
            }  
            // 往右遍历,路径加1  
            if(node.right){  
                traversal(node.right, curPath + '1');  
            }  
        };  
        traversal(tree, '');  
        return hash;  
    }  
返回编码串
    // 返回最终的压缩后的二进制串  
    getBinaryStr(map, originStr){  
        let result = '';  
        for(let i = 0; i < originStr.length; i++){  
            result += map[originStr[i]];  
        }  
        return result;  
    }  
代码汇总
// 哈弗曼编码是将一个 字符串序列 用 二进制表示 的压缩算法  
class huffmanTree{  
    constructor(str){  
        // 第一步,统计字符出现频率  
        let hash = {};  
        for(let i = 0; i < str.length; i++){  
            hash[str[i]] = ~~hash[str[i]] + 1;  
        }  
        this.hash = hash;  
  
        // 构造哈夫曼树  
        this.huffmanTree = this.getHuffmanTree();  
  
        let map = this.getHuffmanCode(this.huffmanTree);  
        // 查看对照表,即每个字符的二进制编码是什么  
        console.log(map);  
  
        // 最终的二进制编码  
        this.binaryStr = this.getBinaryStr(map, str);  
    }  
  
    // 构造哈夫曼树  
    getHuffmanTree(){  
        // 以各个字符出现次数为node.val, 构造森林  
        let forest = []  
        for(let char in this.hash){  
            let node = new Node(this.hash[char], char); 
            forest.push(node);  
        }  
  
        // 等到森林只剩一个节点时,表示合并过程结束,树就生成了  
        let allNodes = []; // 存放被合并的节点,因为不能真的删除森林中任何一个节点,否则.left .right就找不到节点了  
        while(forest.length !== 1){  
            // 从森林中找到两个最小的树,合并之  
            forest.sort((a, b) => {  
                return a.val - b.val;  
            });  
  
            let node = new Node(forest[0].val + forest[1].val, '');  
            allNodes.push(forest[0]);  
            allNodes.push(forest[1]);  
            node.left = allNodes[allNodes.length - 2]; // 左子树放置词频低的  
            node.right = allNodes[allNodes.length - 1]; // 右子树放置词频高的  
  
            // 删除最小的两棵树  
            forest = forest.slice(2);  
            // 新增的树加入  
            forest.push(node);  
        }  
  
        // 生成的哈夫曼树  
        return forest[0];  
    }  
  
    // 遍历哈夫曼树,返回一个 原始字符 和 二进制编码 的对照表  
    getHuffmanCode(tree){  
        let hash = {};  // 对照表
        let traversal = (node, curPath) => {  
            if (!node.length && !node.right) return;  
            if (node.left && !node.left.left && !node.left.right){  
                hash[node.left.char] = curPath + '0';  
            }  
            if (node.right && !node.right.left && !node.right.right){  
                hash[node.right.char] = curPath + '1';  
            }  
            // 往左遍历,路径加0  
            if(node.left){  
                traversal(node.left, curPath + '0');  
            }  
            // 往右遍历,路径加1  
            if(node.right){  
                traversal(node.right, curPath + '1');  
            }  
        };  
        traversal(tree, '');  
        return hash;  
    }  
  
    // 返回最终的压缩后的二进制串  
    getBinaryStr(map, originStr){  
        let result = '';  
        for(let i = 0; i < originStr.length; i++){  
            result += map[originStr[i]];  
        }  
        return result;  
    }  
}

测试代码

let tree = new huffmanTree('ABBCCCDDDDEEEEE')  
console.log(tree)

编码对照表:{ C: ’00’, A: ‘010’, B: ‘011’, D: ’10’, E: ’11’ }
最终编码结果:010011011000000101010101111111111

结语

前端算法库:https://github.com/cunzaizhuyi
这里记录了我刷过的近500道LeetCode的题解,
希望对前端同行找工作面试、修炼算法内功有帮助。

海计划公众号
(0)
上一篇 2020/03/19 07:13
下一篇 2020/03/19 07:13

您可能感兴趣的内容

  • 酷方网基础入门_面向圈子的招聘网站

    酷方网基础入门 官方网址:https://www.koofun.com/ 简介描述:面向圈子的招聘网站 酷方网是面向圈子的招聘网站,依靠圈子的力量帮求职者找工作,帮企业招聘找人才,…

    2020/03/06
  • Js实现数组删除重复项小白基础_数组入门百科

    题目: 删除排序数组中的重复项给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 示例 1:给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你

    2020/03/21
  • Koa使用koa-multer上传文件(上传限制、错误处理)使用帮助_koa入门基础教程

    前言上传文件在开发中是很常见的操作,今天我选择使用koa-multer中间件来实现这一功能,除了上传文件外,我还会对文件上传进行限制,以及发生上传错误时的处理。由于原来的 koa-multer 已经停止维护,我们要使用最新的 @koa/multer 。这个模块是 koa-multer 的一个分支,它被分叉到官方的Koa组织中,并以@koa/multer包名提

    2020/03/26
  • 了解css3样式表写法和优先级小白帮助_优先级菜鸟知识

    了解css3样式表写法和优先级小白帮助 css3和css有什么区别?首先css3是css(层叠样式表)技术的升级版本,而css是一种用来表现HTML(标准通用标记语言的一个应用)或…

    2020/03/20
  • JS判断网页广告是否被浏览器拦截过滤的代码零基础入门_联盟菜鸟指南

    本来现在投广告赚钱也不像前几年好做,现在还大部分浏览器都拦截了广告,很多浏览器还是默认拦截广告,做站长不是一般辛苦啊!目前中小站长大部分收入还是靠广告,广告被拦截,收入自然会大大减少。目前大部分浏览器的广告拦截规则都是广告黑名单+一些广告字眼匹配,比如百度联盟、搜狗联盟、Google联盟这些就算在广告黑名单里的,一般广告过滤都会过滤掉这些广告联盟代码。剩下的

    2020/04/03
  • 【译】React团队的技术准则使用说明_技术入门教程

    本文翻译自React团队核心成员Dan Abramov的技术博客。地址:https://overreacted.io/本文首发于公众号:符合预期的CoyPan我React团队工作的这段时间,很幸运能够看见 Jordan、Sebastian、Sophie 和其他团队成员是如何解决问题的。在本文中,我会把从他们身上学到的,浓缩为一篇较高层次的技术准则。这些准则未

    2020/03/20
  • css的repaint和reflow入门基础教程_重绘基础知识入门

    简单理解:repaint主要是针对某一个DOM元素进行的重绘,reflow则是回流,针对整个页面的重排。字面意思来说:repaint就是重绘,reflow就是回流。repaint和reflow的目的是:展示一个新的页面样貌。性能消耗:在性能优先的前提下,性能消耗 reflow大于repaint。体现:repaint是某个DOM元素进行重绘;reflow是整个

    2020/03/22
  • 什么是web前端?前端工程师前景如何使用说明_web菜鸟教程下载

    什么是web前端?Web为你在浏览器、APP、应用程序等设备上提供直观界面,这些界面展现以及用户交互就是前端。从2016年到2018年,web前端岗位从之前的爆发式增长变为平稳的发展。同时,企业不再满足只会HTML,CSS这些简单的页面搭建,而是希望前端成为更健壮,更体系化的东西。所以,Angular与Vue这类JS框架开始火了起来,且发展速度极快,在一年的

    2020/04/03
  • Razzle菜鸟指南_无需配置,创建服务器呈现的通用Js应用

    Razzle菜鸟指南 GitHub:https://github.com/jaredpalmer/razzle 简介描述:无需配置,创建服务器呈现的通用Js应用 Razzle可用于…

    2020/03/07
  • nprogress基础入门教程_前端轻量级web进度条插件

    nprogress基础入门 官方网址:http://ricostacruz.com/nprogress/ GitHub:https://github.com/rstacruz/np…

    2020/03/05
  • ES6中的Set数据结构以及使用使用场景小白攻略_数据指南攻略

    Set 是ES6提供的一种新的数据结构,它允许你存储任何类型的唯一值,而且Set中的元素是唯一的。我们用new操作符来生成一个Set对象基本用法let arr = [1,2,3,1,2,2,1,2,1,1];
    let set = new Set(arr);
    set.size // 3
    […set] // [1,2,3] 元素是唯一的 可以用来数组去重属性

    2020/03/31
  • httpwatch小白帮助强大的网页数据分析工具

    httpwatch基础入门 官方网址:https://www.httpwatch.com/ 简介描述:强大的网页数据分析工具

    2020/03/05
  • 程序员上班时的各种内心戏…小白指南_段子使用教程

    01读大神写的代码的时候:这是什么………… 我X,太牛X了。读刚来的程序员写的代码的时候:这是什么………… 我X,太傻X了。02读大神写的代码的时候当读其他程序员写的代码的时候03当别人写的bug,让自己发现的时候:我操这个大撒比写出这么个烂代码幸亏有哥这样神一样的存在才发现哥真是救世主没有哥这个公司分分钟要倒闭。当自己写的bug,被自己发现的时候:卧槽,隐

    2020/04/06
  • 微软WPF开源了使用帮助_开源使用帮助

    在去年的 Microsoft Connect(); 开发者大会上,微软宣布开源三种主要的 Windows UX 技术,其中就包括了 Windows Presentation Foundation (WPF),除此之外还有 Windows Forms 和 Windows UI XAML 库 (WinUI)。近日,微软正式将 WPF 框架的源码托管至 GitHu

    2020/03/30
  • 学习web前端培训就业前景怎么样?小白攻略_就业菜鸟教程

    随着移动端的快速发展,web前端人员的需求量也是越来越大。与此同时web前端中的HTML5技术更是日趋成熟,HTML5是移动互联网前端的主流开发语言,目前还没有任何一种前端开发技术能够取代HTML5。因此,无论是PC端还是APP端的应用,前端样式都离不开HTML5. 通过手机与电脑上网的使用率来看,从事html5或者web相关的开发工作,就业前景还是比较可观

    2020/03/30
  • 如何正确选型,React Native 还是 Native?小白攻略_native入门知识

    随着 H5 标准的发布以及推广,使得移动应用的开发也受到了很大影响,出于效率、成本等原因,移动应用的开发不再完全依赖于 “原生”。近日越发火热的混合应用(Hybrid App)介于 Web 应用和原生应用之间,兼具了 “原生应用良好用户交互体验” 和 “Web 应用跨平台开发”的两大优势。而 Facebook 开源的 React Native 跨平台移动应用

    2020/03/29