这篇文章你可以了解如下：
- 首先了解到在通信行业里面，传输数据的方式
- 了解赫夫曼编码的原理
- 用java代码实现一波
- 一定要对上一篇文章有一个了解：https://blog.csdn.net/weixin_46635575/article/details/121269506
- 赫夫曼编码也翻译哈夫曼编码（Huffman Conding），是一种编码方式，属于一种程序算法
- 赫夫曼编码是利用赫夫曼树在电讯通信中的经典应用之一
- 赫夫曼编码广泛地应用于数据文件压缩，其压缩通常在20%到90%之间
- 赫夫曼是可变字长编码的一种，是赫夫曼1952年提出的。
I like like like java do you like a java
（2）各个字符对应的个数d： 1
y： 1
u： 1
j：2
v：2
o：2
l：4
k：4
e：4
i：5
a：5
空格：9
按照上面的字符出现的次数构建一课赫夫曼树，次数作为权值。
（4）树样子
遍历出来会这样
Node{value=40}
Node{value=17}
Node{value=8}
Node{value=4}
Node{value=4}
Node{value=2}
Node{value=2}
Node{value=9}
Node{value=23}
Node{value=10}
Node{value=5}
Node{value=5}
Node{value=13}
Node{value=5}
Node{value=2}
Node{value=1}
Node{value=1}
Node{value=3}
Node{value=1}
Node{value=2}
Node{value=8}
Node{value=4}
Node{value=4}
（5）根据各个字符，规定编码
向左的路基为0，向右路径规1，编码如下
以e进分析，其他的自己推断
得到结果：（每一个编码都不是其他编码的前缀，这样就避免了传输过程中的误识别）
O：1000
u：10010
d：100110
y：100111
i：101
a：110
k：1110
e：111
j：0000
v：0001
I：001
空格：01
根据上面得到的赫夫曼编码，我们的I like like like java do you like a java得到字符串对应的编码为（这里我们使用的无损压缩）
（不过发送的时候还是以8个8个的发送）
之前的是359吧1001001 100000 1101100 1101001 1101011 1100101 100000 1101100 1101001 1101011 1100101 100000 1101100 1101001 1101011 1100101 100000 1101010 1100001 1110110 1100001 100000 1100100 1101111 100000 1111001 1101111 1110101 100000 1101100 1101001 1101011 1100101 100000 1100001 100000 1101010 1100001 1110110 1100001
（359 - 133） / 359 = 60几吧%
（8）要注意理解这个 4、代码练习之生成赫夫曼树 （1）问题引入I like like like java do you like a java 将这句话对应的进行压缩成133个数据
（2）处理问题（1）根据赫夫曼编码压缩数据的原理，需要创建I like like like java do you like a java 对应的赫夫曼树。
处理步骤
（1）节点类Node {data（存放数据）, weight（权值），left 和 right}
（2）得到I like like like java do you like a java 的byte[]数组
（3）编写一个方法，将准备构建赫夫曼树的Node节点放到List中，形式为{Node[date=97,weight = 5],Node[data = 32,weight = 9]、、、、、}目的要体现对应的字符出现的次数：d： 1 y： 1，u： 1，j：2，v：2，o：2，l：4，k：4，e：4，i：5，a：5，空格：9
（4）可以通过List创建对应的赫夫曼树。
代码阅读建议：必须执行，否则你可能看不懂
- 首先看我们的Node节点类，和之前的有一点编号
- 第二步去看我们的main方法里面的步骤1
- 第三步去看我们的main方法里面的步骤2，然后去Huffman 类里面去看getNodes方法
- 第四步去看我们的main方法里面的步骤3，然后去Huffman类里面去看createHuffman方法
public class helloTree {
public static void main(String[] args) throws UnsupportedEncodingException {
String str = "I like like like java do you like a java";
//步骤1、获得字节数组
byte[] bytes = str.getBytes();
Huffman huffman = new Huffman();
//步骤2、取得返回的数据
List nodeList = huffman.getNodes(bytes);
//步骤3、第三步制造我们的赫夫曼树
Node node = huffman.createHuffman(nodeList);
//测试一把
huffman.preOrder(node);
}
}
//第二就来看这个类
class Huffman {
public static List getNodes(byte[] bytes) {
//1、创建一个ArraysList
ArrayList nodes = new ArrayList();
//2、遍历bytes，统计存储每一个byte里面x数据出现的次数 --->map
Map counts = new HashMap<>();//Byte是数据，Integer是次数
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 entry: counts.entrySet()) {
//这个是Map.Entry entry的遍历方式，如果忘记了了，可以自己复习一下
nodes.add(new Node(entry.getKey(),entry.getValue()));
}
return nodes;
}
public static Node createHuffman(List nodes) {
while (nodes.size() > 1) {
//1、排序
Collections.sort(nodes);//必须实现Comparable接口
System.out.println("nodes = " + nodes);
//(1)取出权值最小的二叉树
Node leftNode = nodes.get(0);//一个元素也可以看成一个二叉树
//(2)取出权为第二的二叉树
Node rightNode = nodes.get(1);
//(3)将一二步制造为一课新的二叉树,它是没有data的，只有权值
Node parent = new Node(null,leftNode.weight + rightNode.weight);
//将一二三的挂起来
parent.left = leftNode;
parent.right = rightNode;
//(4)删除ArraysList里面处理过的数据
nodes.remove(leftNode);
nodes.remove(rightNode);
//(5)新构建的要加入里面
nodes.add(parent);
}
return nodes.get(0);
}
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼树为空，不能遍历");
}
}
}
class Node implements Comparable{
Byte data;//存放数据本身 比如'a'表示的是阿斯克码 97
int weight;//节点的权值
Node left;//指向左子节点
Node right;//指向右子节点
public Node(Byte data,int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
//表示从小到达排序
return this.weight - o.weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
public Byte getData() {
return data;
}
public void setData(Byte data) {
this.data = data;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
//为了方便进行后续测试，写一个前序遍历
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}
5、代码练习之生成赫夫曼编码表
代码阅读建议：其实一定要安装这个思路去看
- 首先节点类在前面一个中讲解到，不用管，这个没有变化，第二步是去看----------------------下面的内容，我标注了。
- 最后来看测试
- 因为前面编写的都是要用的，所以又不能删除，为了各位理解，一定要跟着我的思路来看的。
我们已经将对应带传输的数据进行赫夫曼树处理过了，我们要拿到赫夫曼编码，才能将其进行处理。
也就是这些表我们还没有得到：O：1000 u：10010 d：100110 y：100111 i：101 a：110 k：1110 e：111 j：0000 v：0001 I：001 空格：01然后才能进行处理，但是上面在这个过程中，生成的编码表不一定完全一样，因为采用不同的算法，后会有不同的编码。
我们目的是要将我们生成的赫夫曼树中的数据生成赫夫曼表，得到表。看下面代码编写理解。
1、首先我们肯定是放在Map中比较合适，所以选择Map
2、在生成这个赫夫曼编码表时，要去拼接路径，所以要去建一个StringBuilder对象来存储某个叶子节点的路径。
（3）代码处理
public class helloTree {
public static void main(String[] args) throws UnsupportedEncodingException {
String str = "I like like like java do you like a java";
//1、获得字节数组
byte[] bytes = str.getBytes();
Huffman huffman = new Huffman();
//2、取得返回的数据
List nodeList = huffman.getNodes(bytes);
//3、第三步制造我们的赫夫曼树
Node node = huffman.createHuffman(nodeList);
//测试一把
huffman.preOrder(node);
// -------------------------------------------------------------------------------------
// 上面是是生成赫夫曼树写的，下面的才是今天要写的
// -------------------------------------------------------------------------------------
//测试一把
//为什么code是空呢？因为我们跟节点是不存在左右前左右节点的
Huffman.getCodes(node,"",Huffman.huffmanBuilder);
System.out.println(Huffman.huffmanCodes);
}
}
//第二就来看这个类
class Huffman {
public static List getNodes(byte[] bytes) {
//1、创建一个ArraysList
ArrayList nodes = new ArrayList();
//2、遍历bytes，统计存储每一个byte里面x数据出现的次数 --->map
Map counts = new HashMap<>();//Byte是数据，Integer是次数
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 entry: counts.entrySet()) {
//这个是Map.Entry entry的遍历方式，如果忘记了了，可以自己复习一下
nodes.add(new Node(entry.getKey(),entry.getValue()));
}
return nodes;
}
public static Node createHuffman(List nodes) {
while (nodes.size() > 1) {
//1、排序
Collections.sort(nodes);//必须实现Comparable接口
System.out.println("nodes = " + nodes);
//(1)取出权值最小的二叉树
Node leftNode = nodes.get(0);//一个元素也可以看成一个二叉树
//(2)取出权为第二的二叉树
Node rightNode = nodes.get(1);
//(3)将一二步制造为一课新的二叉树,它是没有data的，只有权值
Node parent = new Node(null,leftNode.weight + rightNode.weight);
//将一二三的挂起来
parent.left = leftNode;
parent.right = rightNode;
//(4)删除ArraysList里面处理过的数据
nodes.remove(leftNode);
nodes.remove(rightNode);
//(5)新构建的要加入里面
nodes.add(parent);
}
return nodes.get(0);
}
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼树为空，不能遍历");
}
}
// -------------------------------------------------------------------------------------
// 上面是是生成赫夫曼树写的，下面的才是今天要写的
// -------------------------------------------------------------------------------------
//用来存储我们的赫夫曼编码表的数据
static Map huffmanCodes = new HashMap<>();
//用于拼接我们的数据
static StringBuilder huffmanBuilder = new StringBuilder();
public static void getCodes(Node node,String code,StringBuilder stringBuilder) {
//因为每一次来都要拼接，所有在内部自己创建一个
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
stringBuilder1.append(code);//进行拼接
if (node != null) {//如果不是空节点才处理
//先去判断是不是一个叶子节点还是非叶子节点
if (node.data == null) {//说明为非叶子节点
//继续递归向下查找叶子节点
//首先向左递归
getCodes(node.left,"0",stringBuilder1);
//向右递归
getCodes(node.right,"1",stringBuilder1);
} else {//说明是一个叶子节点，所有已经可以结束了
//表示找到了某个叶子节点了，说明我们得到了一个数据
huffmanCodes.put(node.data,stringBuilder1.toString());
}
}
}
}
class Node implements Comparable{
Byte data;//存放数据本身 比如'a'表示的是阿斯克码 97
int weight;//节点的权值
Node left;//指向左子节点
Node right;//指向右子节点
public Node(Byte data,int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
//表示从小到达排序
return this.weight - o.weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
public Byte getData() {
return data;
}
public void setData(Byte data) {
this.data = data;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
//为了方便进行后续测试，写一个前序遍历
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}
生成的结果：{32=01, 97=101, 100=10010, 101=1101, 73=10011, 105=1110, 106=0010, 107=1111, 108=000, 111=0011, 117=11000, 118=1000, 121=11001} 可能各自不相同，但是后续处理后，任然会相同。
6、代码练习之返回赫夫曼压缩处理代码阅读建议：其实一定要安装这个思路去看
- 首先节点类在前面一个中讲解到，不用管，这个没有变化，第二步是去看++++++++++++下面的内容，我标注了。
- 最后来看测试
我们要将我们的数据：I like like like java do you like a java 处理成一个byte数组，然后传递给我们接下来编写的方法处理，然后将它以对应的Huffman编码的字节数组。
（2）问题处理1、 利用我们上一步生成的HuffmanCodes编码，将我们的I like like like java do you like a java转化成为我们的一个用01组成的一个字符串
2、原始的字符长度为40，入以stringBuilder直接传输，那反而更大了，要将我们的二进制的字符转换为byte[]返回
3、创建一个byte数组来存储压缩后的数组
4、然后返回
import java.io.UnsupportedEncodingException;
import java.util.*;
public class helloTree {
public static void main(String[] args) throws UnsupportedEncodingException {
String str = "I like like like java do you like a java";
//1、获得字节数组
byte[] bytes = str.getBytes();
Huffman huffman = new Huffman();
//2、取得返回的数据
List nodeList = huffman.getNodes(bytes);
//3、第三步制造我们的赫夫曼树
Node node = huffman.createHuffman(nodeList);
//测试一把
huffman.preOrder(node);
// -------------------------------------------------------------------------------------
// 上面是是生成赫夫曼树写的，下面的才是今天要写的
// -------------------------------------------------------------------------------------
//测试一把
//为什么code是空呢？因为我们跟节点是不存在左右前左右节点的
Huffman.getCodes(node,"",Huffman.huffmanBuilder);
System.out.println(Huffman.huffmanCodes);
/
public static List getNodes(byte[] bytes) {
//1、创建一个ArraysList
ArrayList nodes = new ArrayList();
//2、遍历bytes，统计存储每一个byte里面x数据出现的次数 --->map
Map counts = new HashMap<>();//Byte是数据，Integer是次数
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 entry: counts.entrySet()) {
//这个是Map.Entry entry的遍历方式，如果忘记了了，可以自己复习一下
nodes.add(new Node(entry.getKey(),entry.getValue()));
}
return nodes;
}
public static Node createHuffman(List nodes) {
while (nodes.size() > 1) {
//1、排序
Collections.sort(nodes);//必须实现Comparable接口
System.out.println("nodes = " + nodes);
//(1)取出权值最小的二叉树
Node leftNode = nodes.get(0);//一个元素也可以看成一个二叉树
//(2)取出权为第二的二叉树
Node rightNode = nodes.get(1);
//(3)将一二步制造为一课新的二叉树,它是没有data的，只有权值
Node parent = new Node(null,leftNode.weight + rightNode.weight);
//将一二三的挂起来
parent.left = leftNode;
parent.right = rightNode;
//(4)删除ArraysList里面处理过的数据
nodes.remove(leftNode);
nodes.remove(rightNode);
//(5)新构建的要加入里面
nodes.add(parent);
}
return nodes.get(0);
}
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼树为空，不能遍历");
}
}
// -------------------------------------------------------------------------------------
// 上面是是生成赫夫曼树写的，下面的才是今天要写的
// -------------------------------------------------------------------------------------
//用来存储我们的赫夫曼编码表的数据
static Map huffmanCodes = new HashMap<>();
//用于拼接我们的数据
static StringBuilder huffmanBuilder = new StringBuilder();
public static void getCodes(Node node,String code,StringBuilder stringBuilder) {
//因为每一次来都要拼接，所有在内部自己创建一个
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
stringBuilder1.append(code);//进行拼接
if (node != null) {//如果不是空节点才处理
//先去判断是不是一个叶子节点还是非叶子节点
if (node.data == null) {//说明为非叶子节点
//继续递归向下查找叶子节点
//首先向左递归
getCodes(node.left,"0",stringBuilder1);
//向右递归
getCodes(node.right,"1",stringBuilder1);
} else {//说明是一个叶子节点，所有已经可以结束了
//表示找到了某个叶子节点了，说明我们得到了一个数据
huffmanCodes.put(node.data,stringBuilder1.toString());
}
}
}
/
public static byte[] zip(byte[] bytes,Map huffmanCodes) {
//步骤一
StringBuilder stringBuilder = new StringBuilder();
//遍历我们的bytes
for (byte b: bytes) {
stringBuilder.append(huffmanCodes.get(b));//找到我们bytes里面的字符对应的Huffman编码添加
}
//步骤二
//原始的字符长度为40，入以stringBuilder直接传输，那反而更大了，要将我们的二进制的字符转换为byte[]返回
int len;
if (stringBuilder.length() % 8 == 0) {//说明我们的数据刚刚好，能直接计算得到数组大小。
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
//步骤三 创建一个byte数组来存储压缩后的数组
byte[] huffmanCodeBytes = new byte[len];
//步长为8，每八位对应一个byte
int index = 0;//记录第几个byte
for (int i = 0; i < stringBuilder.length(); i+=8) {
String strByte;
if (i + 8 > stringBuilder.length()) {//说明最后剩下的还有不到八位的数据
strByte = stringBuilder.substring(i);
} else {//否则就是按着8位的形式走
strByte = stringBuilder.substring(i, i + 8);//每循环一次，就从stringBuilder截取8为
}
//将strByte转为一个byte数组，放入到HuffmanCodeBytes
huffmanCodeBytes[index] = ((byte) Integer.parseInt(strByte,2));
}
return huffmanCodeBytes;
}
}
class Node implements Comparable{
Byte data;//存放数据本身 比如'a'表示的是阿斯克码 97
int weight;//节点的权值
Node left;//指向左子节点
Node right;//指向右子节点
public Node(Byte data,int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
//表示从小到达排序
return this.weight - o.weight;
}
@Override
public java.lang.String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
public Byte getData() {
return data;
}
public void setData(Byte data) {
this.data = data;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
//为了方便进行后续测试，写一个前序遍历
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}
