哈夫曼树的js实现

更新日期: 2020-02-26阅读量: 929标签: 运算

前言

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

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

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


算法实现

树节点

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

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的题解,
希望对前端同行找工作面试、修炼算法内功有帮助。

原文:https://segmentfault.com/a/1190000021837224


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: https://www.fly63.com/article/detial/7790

斐波那契列数JS的三种实现

大家是怎么实现斐波那契列数的,再给两种解法,对比一下,还有一种更简单的用的是数组存储

在JavaScript中使用Spread运算符的8种方法

延展操作运算符将可迭代的对象扩展为其单独的元素,可迭代对象是可以使用 for 循环进行循环的任何对象。可迭代的示例:Array,String,Map,Set,DOM节点。

Js es6中扩展运算符(...)

拓展运算符,是es6一个很好的特性,它们可以通过减少赋值语句的使用,或者减少通过下标访问数组或对象的方式,使代码更加简洁优雅,可读性更佳。下面我将列出拓展运算符的主要应用场景,以及相关知识。

巧用JS位运算

位运算的方法在其它语言也是一样的,不局限于JS,所以本文提到的位运算也适用于其它语言。位运算是低级的运算操作,所以速度往往也是最快的

Js比较和逻辑运算符

比较和逻辑运算符用于测试 true 或 false。比较运算符在逻辑语句中使用,以判定变量或值是否相等。我们给定 x = 5,下表中解释了比较运算符:

javascript如何四舍五入?

javascript四舍五入的方法:方法一、使用toFixed()方法可把Number四舍五入为指定小数位数的数字。方法二、使用round()方法可把一个数字舍入为最接近的整数。

toFixed()与银行家舍入

一直在用toFixed()方法做浮点数的舍入取值,如果只是客户端展示数据是没有多大问题的,但是如果涉及到和后端互交,数据的精度可能会导致接口对接失败,当然了,涉及安全性的数值,比如金额之类的不应该放在前端计算

看了此文,你还敢说你懂了Javascript运算符吗

JavaScript的很多奇技淫巧,都来自于对运算符的灵活使用。JavaScript的JavaScript的很多奇技淫巧,都来自于对运算符的灵活使用。优先级: 优先级高的运算符最先被执行

关于js开发中保留小数位计算函数(以向上取整或向下取整的方式保留小数)

前端工作中经常遇到数字计算保留小数问题,由于不是四舍五入的方式不能使用toFixed函数,本文采用正则表达式匹配字符串的方式,解决对数字的向上或向下保留小数问题:

js中的相等==

今天学习 jest,看文档的时候发现 jest 用到了 Object.is(),以前没有见过,所以记录下来,供以后开发时参考,相信对其他人也有用。如果下列任何一项相同,则 Object.is(value1, value2) 返回 true:

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!