哈夫曼编码（上）

2024-05-12 12:20
文章标签 编码 哈夫曼

本文主要是介绍哈夫曼编码（上），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

    • 问题引入
    • 哈夫曼编码的编写
      • 总述
      • 步骤一
      • 步骤二
      • 步骤三
      • 步骤四
    • 实现代码如下

在这里插入图片描述

问题引入

哈夫曼编码通常用于通信领域，是对较长信息进行压缩，然后发送到指定的位置，是为了节省发送信息占用的空间。
通常来说，如果信息中字符的重复次数越多，那么哈夫曼编码后所占的空间就越小，这也是我们为什么使用哈夫曼编码的原因，同时，哈夫曼编码还是天然的前缀编码，这让它与其他编码方式(定长编码，变长编码)相比，具有天然的优势。

哈夫曼编码的编写

总述

1.将字符串对应的字节数组变为list集合
2.创建list集合对应的哈夫曼树
3.得到对应的哈夫曼编码
4.根据哈夫曼编码得到最后压缩的byte[]

步骤一

首先我们需要一个字符串，此字符串将会用哈夫曼编码压缩为最后的byte数组。
比如为"i like like like java do you like a java"。
我们需要一个Node节点用来存储数据和对应的权值，这个节点为二叉树的节点。
我们将此字符串变为字节数组，然后统计各个字符出现的次数，将该字符作为Node节点的存储数据，
出现的次数作为Node节点对应的权值，统计之后将所有的节点放入List集合中保存。

//将对应字符串对应的byte数组转为list集合
private static List<Node2> getNodes(byte[] bytes){//创建一个ListList<Node2> nodes = new ArrayList<Node2>();//存储每一个byte出现的次数Map<Byte,Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if(count == null){counts.put(b,1);}else {counts.put(b,count + 1);}}//把每一个键值对转成一个Node对象，并加入nodes集合for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node2(entry.getKey(),entry.getValue()));}return nodes;}
//创建Node，存数据和权值
class Node2 implements Comparable<Node2>{Byte data; //存放数据本身，比如'a' = 97int weight; //权值，表示字符出现的次数Node2 left;Node2 right;public Node2(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node2 o) {return this.weight - o.weight;}@Overridepublic String toString() {return "Node2{" + "data=" + data + ", weight=" + weight + '}';}//前序遍历public void preOrder(){System.out.println(this);if(this.left != null){this.left.preOrder();}if(this.right != null){this.right.preOrder();}}
}

步骤二

接下来我们就需要用我们刚刚得到的list集合来创建哈夫曼树了。
将list集合排序，把list集合的前两个节点拿出来，作为新树的两个子节点，然后将该新树放回list集合中，将原本拿出的两个子节点从list集合中移除，然后再次排序，重复上面步骤，就能得到一颗哈夫曼树。
当哈夫曼树构建完成，list集合就剩下一个节点，此节点就是哈夫曼树的根节点。
假设list集合中放的node节点的权值为1 2 4 5 6.
简述过程如下：

在这里插入图片描述

//通过list创建赫夫曼树private static Node2 createHuffmanTree(List<Node2> nodes){while (nodes.size() > 1){//排序Collections.sort(nodes);//取出前两个最小的二叉树Node2 left = nodes.get(0);Node2 right = nodes.get(1);//创建一课新的二叉树，它的根节点没有data，只有权值Node2 parent = new Node2(null, left.weight + right.weight);parent.left = left;parent.right = right;nodes.add(parent);//将已经处理的两个二叉树从nodes删除nodes.remove(left);nodes.remove(right);}return nodes.get(0);}

步骤三

哈夫曼树我们已经构建完毕了，接下来我们需要得到对应的哈夫曼编码。
我们规定，哈夫曼树中的节点，从该节点到左子节点路径的值为0，到右子节点的值为1。
接下来就是递归的创建赫夫曼编码表了，此表我们用Map<Byte,String> buffmanCodes来表示，map的key表示对应的字符，map的value表示赫夫曼编码，还需要一个StringBuilder stringBuilder，用来存放某个叶子节点的路径。
从根节点开始，当我们遇到非叶子节点就递归处理，向左递归，将0加入stringBuilder，然后向右递归，将1加入stringBuilder。当我们遇到叶子节点时，stringBuilder已经将该路径的0或1收集完毕，将该节点的data作为key，stringBuilder里存储的字符串作为value存入buffmanCodes。
简述过程如下：
在这里插入图片描述

//1.将赫夫曼编码表存放Map<Byte,String>形式
static Map<Byte,String> buffmanCodes = new HashMap<Byte,String>();
//2.在生成赫夫曼编码表时，需要去拼接路径，定义一个StringBuilder 存储某个叶子节点的路径
static StringBuilder stringBuilder = new StringBuilder();
private static void getCodes(Node2 node,String code,StringBuilder stringBuilder){StringBuilder builder = new StringBuilder(stringBuilder);//将code加入builderbuilder.append(code);if(node != null){//判断当前节点是叶子节点还是非叶子节点if(node.data == null){ //非叶子节点//递归处理//向左递归getCodes(node.left,"0",builder);//向右递归getCodes(node.right,"1",builder);}else{//找到叶子节点buffmanCodes.put(node.data,builder.toString());}}}

步骤四

根据赫夫曼编码将数据压缩得到最后的byte[]。
首先利用buffmanCodes 将 bytes转成 赫夫曼编码对应的字符串，用StringBuilder stringBuilder来接收。
接下来我们统计我们要压缩byte的长度int len，如果stringBuilder的长度恰好为8的倍数，则len = stringBuilder.length / 8,否则就是len = stringBuilder.length / 8 + 1，如果基础好的话很容易想到
int len = (stringBuilder.length() + 7) / 8。
最后我们创建压缩后的byte数组byte[] huffmanCodeBytes = new byte[len]。
读取stringBuilder的值，每八位作为一个字节，将该字节放入huffmanCodeBytes，当len的长度为8的倍数时，我们就按上述处理方法即可，但是当len的长度不为8的倍数，则最后几位的取法应有所不同。
简述过程如下：
在这里插入图片描述

 private static byte[] zip(byte[] contentBytes,Map<Byte,String> huffmanCodes){//1.利用huffmanCodes 将 bytes转成 赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();for (byte b : contentBytes) {stringBuilder.append(huffmanCodes.get(b));}int len;if(stringBuilder.length() % 8 == 0){len = stringBuilder.length() / 8;}else {len = stringBuilder.length() / 8 + 1;}//创建存储压缩后的bute数组byte[] huffmanCodeBytes = new byte[len];int index = 0; //记录是第几个byte//因为每8位对应一个byte，所以步长 + 8for (int i = 0; i < stringBuilder.length(); i+=8) {String strByte;if(i + 8 > stringBuilder.length()){strByte = stringBuilder.substring(i);}else {strByte = stringBuilder.substring(i,i + 8);}//将strByte转为一个byte，放入huffmanCodeByteshuffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte,2);}return huffmanCodeBytes;}

实现代码如下

public class HuffmanCode {public static void main(String[] args) {String str = "i like like like java do you like a java";byte[] bytes = str.getBytes(StandardCharsets.UTF_8);byte[] huffmanCodeBytes = huffmanZip(bytes);System.out.println("压缩后的结果为 : " + Arrays.toString(huffmanCodeBytes));}private static byte[] huffmanZip(byte[] contentBytes){List<Node2> nodes = getNodes(contentBytes);//根据nodes创建的赫夫曼树Node2 root = createHuffmanTree(nodes);//得到对应的赫夫曼编码Map<Byte, String> huffmanCodes = getCodes(root);//根据赫夫曼编码huffmanCodes得到最后压缩的byte[]byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);return huffmanCodeBytes;} private static byte[] zip(byte[] contentBytes,Map<Byte,String> huffmanCodes){//1.利用huffmanCodes 将 bytes转成 赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();for (byte b : contentBytes) {stringBuilder.append(huffmanCodes.get(b));}int len;if(stringBuilder.length() % 8 == 0){len = stringBuilder.length() / 8;}else {len = stringBuilder.length() / 8 + 1;}//创建存储压缩后的bute数组byte[] huffmanCodeBytes = new byte[len];int index = 0; //记录是第几个byte//因为每8位对应一个byte，所以步长 + 8for (int i = 0; i < stringBuilder.length(); i+=8) {String strByte;if(i + 8 > stringBuilder.length()){strByte = stringBuilder.substring(i);}else {strByte = stringBuilder.substring(i,i + 8);}//将strByte转为一个byte，放入huffmanCodeByteshuffmanCodeBytes[index++] = (byte) Integer.parseInt(strByte,2);}return huffmanCodeBytes;}//为了调用方便，我们重载getCodesprivate static Map<Byte,String> getCodes(Node2 root){if(root == null){return null;}else {getCodes(root.left,"0",stringBuilder);getCodes(root.right,"1",stringBuilder);return buffmanCodes;}}static Map<Byte,String> buffmanCodes = new HashMap<Byte,String>();static StringBuilder stringBuilder = new StringBuilder(); private static void getCodes(Node2 node,String code,StringBuilder stringBuilder){StringBuilder builder = new StringBuilder(stringBuilder);//将code加入builderbuilder.append(code);if(node != null){//判断当前节点是叶子节点还是非叶子节点if(node.data == null){ //非叶子节点//递归处理//向左递归getCodes(node.left,"0",builder);//向右递归getCodes(node.right,"1",builder);}else{//找到叶子节点buffmanCodes.put(node.data,builder.toString());}}}private static List<Node2> getNodes(byte[] bytes){//创建一个ListList<Node2> nodes = new ArrayList<Node2>();//存储每一个byte出现的次数Map<Byte,Integer> counts = new HashMap<>();for (byte b : bytes) {Integer count = counts.get(b);if(count == null){counts.put(b,1);}else {counts.put(b,count + 1);}}//把每一个键值对转成一个Node对象，并加入nodes集合for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {nodes.add(new Node2(entry.getKey(),entry.getValue()));}return nodes;}private static Node2 createHuffmanTree(List<Node2> nodes){while (nodes.size() > 1){//排序Collections.sort(nodes);//取出前两个最小的二叉树Node2 left = nodes.get(0);Node2 right = nodes.get(1);//创建一课新的二叉树，它的根节点没有data，只有权值Node2 parent = new Node2(null, left.weight + right.weight);parent.left = left;parent.right = right;nodes.add(parent);//将已经处理的两个二叉树从nodes删除nodes.remove(left);nodes.remove(right);}return nodes.get(0);}
}//创建Node，存数据和权值
class Node2 implements Comparable<Node2>{Byte data; //存放数据本身，比如'a' = 97int weight; //权值，表示字符出现的次数Node2 left;Node2 right;public Node2(Byte data, int weight) {this.data = data;this.weight = weight;}@Overridepublic int compareTo(Node2 o) {return this.weight - o.weight;}@Overridepublic String toString() {return "Node2{" + "data=" + data + ", weight=" + weight + '}';}//前序遍历public void preOrder(){System.out.println(this);if(this.left != null){this.left.preOrder();}if(this.right != null){this.right.preOrder();}}
}

这篇关于哈夫曼编码（上）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/982617。

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
form表单提交编码的问题

form表单提交编码的问题

浏览器在form提交后，会生成一个HTTP的头部信息"content-type"，标准规定其形式为Content-type: application/x-www-form-urlencoded; charset=UTF-8        那么我们如果需要修改编码，不使用默认的，那么可以如下这样操作修改编码，来满足需求： hmtl代码：   <meta http-equiv="Conte
阅读更多...
4-4.Andorid Camera 之简化编码模板（获取摄像头 ID、选择最优预览尺寸）

4-4.Andorid Camera 之简化编码模板（获取摄像头 ID、选择最优预览尺寸）

一、Camera 简化思路 在 Camera 的开发中，其实我们通常只关注打开相机、图像预览和关闭相机，其他的步骤我们不应该花费太多的精力 为此，应该提供一个工具类，它有处理相机的一些基本工具方法，包括获取摄像头 ID、选择最优预览尺寸以及打印相机参数信息 二、Camera 工具类 CameraIdResult.java public class CameraIdResult {
阅读更多...
Python字符编码及应用

Python字符编码及应用

字符集概念 字符集就是一套文字符号及其编码的描述。从第一个计算机字符集ASCII开始，为了处理不同的文字，发明过几百种字符集，例如ASCII、USC、GBK、BIG5等，这些不同的字符集从收录到编码都各不相同。在编程中出现比较严重的问题是字符乱码。 几个概念 位：计算机的最小单位二进制中的一位，用二进制的0，1表示。 字节：八位组成一个字节。（位与字节有对应关系） 字符：我们肉眼可见的文字与符号。
阅读更多...
在Eclipse环境下修改Tomcat编码的问题

在Eclipse环境下修改Tomcat编码的问题

问题： 由于BMS需要设置UTF-8编码，要不就会出现中文乱码问题； 一、项目保持UTF-8格式； 二、由于可能会多次移除项目、加载项目，不想每次都要修改tmp0\conf 原因： 如果在eclipse中配置了tomcat后，其实，tomcat所用的所有tomcat配置文件，都不是catalina_home/config下面的xml文件，而是在eclipse所创建的Serve
阅读更多...
在Unity环境中使用UTF-8编码

在Unity环境中使用UTF-8编码

为什么要讨论这个问题         为了避免乱码和更好的跨平台         我刚开始开发时是使用VS开发,Unity自身默认使用UTF-8 without BOM格式,但是在Unity中创建一个脚本,使用VS打开,VS自身默认使用GB2312(它应该是对应了你电脑的window版本默认选取了国标编码,或者是因为一些其他的原因)读取脚本,默认是看不到在VS中的编码格式,下面我介绍一种简单快
阅读更多...
霍夫曼编码/译码器

霍夫曼编码/译码器

赫夫曼树的应用 1、哈夫曼编码 　　在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用
阅读更多...
Base64编码 及 在HTML中用Base编码直接显示图片或嵌入其他文件类型

Base64编码 及 在HTML中用Base编码直接显示图片或嵌入其他文件类型

1.为什么要用到BASE64编码的图片信息      Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一。Base64 主要不是加密，它主要的用途是把一些二进制数转成普通字符用于网络传输。由于一些二进制字符在传输协议中属于控制字符，不能直接传送需要转换一下。最常见的用途是作为电子邮件或WebService附件的传输编码.  2.base64编码定义  　　目前的internet
阅读更多...
批量文件编码转换用python实现的utf8转gb2312,vscode设置特殊文件的默认打开编码

批量文件编码转换用python实现的utf8转gb2312,vscode设置特殊文件的默认打开编码

批量文件编码转换用python实现的utf8转gb2312, 任意编码之间的相互转换都是可以的.改一下下面的参数即可 convert.py文件内容如下 import osimport globimport chardet#检测文件编码类型def detect_file_encoding(file_path):with open(file_path, 'rb') as f:data = f
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2