11.3赫夫曼编码
赫夫曼编码基本介绍：
1、 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
2、 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间
通信领域中信息的处理方式：
1、 定长编码
这种处理方法实质：每一个字符都对应一个Ascll编码，将对应字符转换成相应的Ascll编码，再把Ascll编码转换成对应的二进制，就可以进行传输，不过这种处理方法有一个很严重的缺陷，那就是编码长度太长了！
2、 变长编码
变长编码在定长编码的基础之上进行了优化：将每个字符按照出现的次数进行排序，出现次数越多编码越靠前，比如：上面空格出现的次数是9次，出现的次数最多，因此空格的编码是0，a出现的次数第二多，编码是1，i出现的次数第三多，编码是10（也就是十进制的2）。最后再将整个句子的字符替换成相应的编码进行传输
3、 赫夫曼编码
赫夫曼的编码的主要思路是：和变长编码类似，也是先统计每个字符出现的次数，然后进行排序，然后根据出现的次数来构建一棵赫夫曼树，这样就能合理的将权值大的放在离根节点近的地方（也就是出现次数多的字符放在前面，出现次数少的放在后面），然后将左边的路径设为0，右边的路径设为1，就完成了对字符的编码（这样说有点抽象，下面有张图可以结合理解一下）
构造赫夫曼树的步骤：
1、 从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
2、 取出根节点权值最小的两颗二叉树（在代码中是使用集合来进行排序的哦）
3、 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4、 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
5、 根据赫夫曼树，给各个字符,规定编码 (前缀编码)，向左的路径为 0 向右的路径为 1 ， 就可以获得对应字符的编码，如：空格：01、l：001、i：101等（注意：所有的字符都是在叶子节点上的）
6、 按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)：
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通过赫夫曼编码处理 长度为 133
7、 原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
8、 补充：此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性赫夫曼编码是无损处理方案，也就是说，比如编码的开头是101，它匹配的就是字符i，在编码的过程中，其他字符的编码不会以101开头，101是i字符的专属
9、 注意事项：这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是 wpl是一样的，都是最小的, 最后生成的赫夫曼编码的长度是一样，比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为（也就是说不同的排序可能会产生不同的树，但在本质上wpl是相等的）：
赫夫曼编码的应用实例（在代码中实现）：
1、 对数据的压缩；
2、 对数据的解压
3、 对文件的压缩
4、 对文件的解压
赫夫曼编码压缩文件的注意事项：
1、 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等
2、 赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件)
3、 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显
package com.atguigu10.huffmantree;
import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.*;
/**
* @author peng
* @date 2021/11/27 - 9:52
* <p>
* 代码实现赫夫曼编码
*/
public class HuffmanCode {
public static void main(String[] args) {
String content = "i like like like java do you like a java";
byte[] contentByte = content.getBytes();
System.out.println("初始数组的长度为：" + contentByte.length);
//进行赫夫曼压缩
byte[] huffmanZip = huffmanZip(contentByte);
System.out.println("进行赫夫曼压缩后的结果是：" + Arrays.toString(huffmanZip));
System.out.println("压缩后的长度是：" + huffmanZip.length);
byte[] decode = decode(huffmanCodes, huffmanZip);
System.out.println("原来的字符串是：" + new String(decode));
System.out.println("实现赫夫曼编码的压缩与解压：");
String srcFile = "E://001.png";
String descFile = "E://desc.png";
zipFile(srcFile, descFile);
//测试解压
System.out.println("实现文件的解压：");
String zipFile = "E://desc.png";
String destFile = "E://002.png";
unZipFile(zipFile, destFile);
System.out.println("解压成功！");
// List<HuffmanNode> huffmanNodeList = getNodes(contentByte);
// System.out.println(huffmanNodeList);
//
// System.out.println("创建好的赫夫曼树为：");
// HuffmanNode huffmanTreeRoot = createHuffmanTree(huffmanNodeList);
// huffmanTreeRoot.preOrder();
//
// System.out.println("生成对应的赫夫曼编码表：");
// getCodes(huffmanTreeRoot);
// System.out.println("生成的赫夫曼编码表：" + huffmanCodes);
//
// //经过这些操作，输入的字符串（44个字符）最终压缩成17个数字的形式，这就是赫夫曼编码！
// byte[] huffmanCodesBytes = zip(contentByte, huffmanCodes);
// System.out.println("经过赫夫曼编码之后的字符串转换成的结果：" + Arrays.toString(huffmanCodesBytes));
}
/**
* 编写一个方法，实现对文件的解压
*
* @param zipFile：准备解压的文件
* @param dstFile：文件解压的路径
*/
public static void unZipFile(String zipFile, String dstFile) {
FileInputStream fileInputStream = null;
ObjectInputStream objectInputStream = null;
FileOutputStream fileOutputStream = null;
try {
//定义文件输入流
fileInputStream = new FileInputStream(zipFile);
//定义对象输入流
objectInputStream = new ObjectInputStream(fileInputStream);
//读取byte数组
byte[] huffmanBytes = (byte[]) objectInputStream.readObject();
//读取赫夫曼编码表
Map<Byte, String> huffmanCodes = (Map<Byte, String>) objectInputStream.readObject();
//进行解码操作
byte[] bytes = decode(huffmanCodes, huffmanBytes);
//将解码后得到的字节数组，写入到目标文件之中
//定义文件输出流
fileOutputStream = new FileOutputStream(dstFile);
//写出数据到目标文件之中
fileOutputStream.write(bytes);
} catch (IOException e) {
e.printStackTrace();
} catch (ClassNotFoundException e) {
e.printStackTrace();
} finally {
try {
fileOutputStream.close();
} catch (IOException e) {
e.printStackTrace();
}
try {
objectInputStream.close();
} catch (IOException e) {
e.printStackTrace();
}
try {
fileInputStream.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
//实现对文件的压缩
/**
* @param srcFile：希望进行压缩的文件的文件路径
* @param descFile：压缩完成之后的文件的文件路径
*/
public static void zipFile(String srcFile, String descFile) {
FileInputStream fileInputStream = null;
FileOutputStream fileOutputStream = null;
ObjectOutputStream objectOutputStream = null;
try {
//创建文件输入流
fileInputStream = new FileInputStream(srcFile);
//创建一个和原文件一样大小的byte数组
byte[] bytes = new byte[fileInputStream.available()];
//读取文件
fileInputStream.read(bytes);
//对原文件进行压缩
byte[] huffmanBytes = huffmanZip(bytes);
//创建文件输出流，用于存放文件
fileOutputStream = new FileOutputStream(descFile);
//创建一个和文件输出流相关联的对象输出流
objectOutputStream = new ObjectOutputStream(fileOutputStream);
//把赫夫曼编码后的字节数组写到压缩文件中，这样做是为了方便之后的解压
objectOutputStream.writeObject(huffmanBytes);
//以对象流的方法写入赫夫曼编码，为了方便恢复文件
objectOutputStream.writeObject(huffmanCodes);
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
objectOutputStream.close();
} catch (IOException e) {
e.printStackTrace();
}
try {
fileOutputStream.close();
} catch (IOException e) {
e.printStackTrace();
}
try {
fileInputStream.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 暂时还不太理解这个方法
* <p>
* 定义一个方法实现：将经过赫夫曼编码压缩的文件进行解码
* 1、将生成的编码数字转换成对应的二进制编码
* 2、将二进制编码转换成对应的字符串
*
* @param flag:true表示需要补高位，false表示不需要补高位
* @param b:要进行编码的字符
* @return
*/
private static String byteToBitString(boolean flag, byte b) {
int temp = b;//将b转换成int类型
//如果是正数，则需要补高位
if (flag) {
temp |= 256;//按位与256
}
String str = Integer.toBinaryString(temp);
if (flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
//完成对压缩数据的解码
/**
* @param huffmanCodes：赫夫曼编码表
* @param huffmanBytes：赫夫曼编码表处理过之后的字节数组
* @return：返回的是原来的字符串
*/
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
//第一步：将huffmanBytes转换成对应分二进制字符串
StringBuilder stringBuilder = new StringBuilder();
//将byte数组转换成二进制字符串
for (int i = 0; i < huffmanBytes.length; i++) {
//判断是不是最后一个字节，因为最后一个字节不需要补高位
boolean flag = (i == huffmanBytes.length - 1);
//将转换成的二进制编码添加在字符串之后
stringBuilder.append(byteToBitString(!flag, huffmanBytes[i]));
}
//把字符串按照指定的赫夫曼编码进行解码
//把赫夫曼编码表key，value顺序进行调换，因为要进行反向查询
HashMap<String, Byte> stringByteHashMap = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
stringByteHashMap.put(entry.getValue(), entry.getKey());
}
//创建集合，存放byte
ArrayList<Byte> byteArrayList = new ArrayList<>();
//遍历二进制编码数组，将二进制编码转换成对应的字符串
for (int i = 0; i < stringBuilder.length(); ) {
int count = 1;//用于遍历二进制代码
boolean flag = true;//用于判断，是否已经找到了编码对应的字符串
Byte b = null;//暂时存放编码的结果
while (flag) {
String key = stringBuilder.substring(i, i + count);
b = stringByteHashMap.get(key);
if (b == null) {
//说明当前的二进制编码没有对应的字符
count++;
} else {
//说明当前的二进制代码已经匹配到了对应的字符
flag = false;//
}
}
byteArrayList.add(b);
i += count;//下次直接从count的位置开始
}
//当for循环结束之后，byteArrayList中就存放了所有的字符
//此时需要将byteArrayList中的所有数据放入到byte[]数组中，并返回
byte[] result = new byte[byteArrayList.size()];
for (int i = 0; i < result.length; i++) {
result[i] = byteArrayList.get(i);
}
return result;
}
/**
* 定义一个方法：对一下的方法进行封装
* 第一个byte是：编码完成之后要发送的分组
* 第二个byte是：传进来需要编码的分组
*
* @param bytes
* @return
*/
private static byte[] huffmanZip(byte[] bytes) {
//第一步：生成对应的ArrayList
List<HuffmanNode> huffmanNodeList = getNodes(bytes);
//第二步：创建赫夫曼树，并返回根节点
HuffmanNode huffmanTreeRoot = createHuffmanTree(huffmanNodeList);
//第三步：生成对应的赫夫曼编码表
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
//第四部：根据对应的赫夫曼编码表进行压缩
byte[] huffmanZip = zip(bytes, huffmanCodes);
return huffmanZip;
}
private static List<HuffmanNode> getNodes(byte[] bytes) {
//创建一个ArrayList，用于对节点进行排序，只有排好序之后才能创建赫夫曼树
ArrayList<HuffmanNode> huffmanNodes = new ArrayList<>();
//使用map存放节点的数据，也就是说在ArrayList中放map
HashMap<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
//遍历每一个字符，获得该字符出现的次数
Integer count = counts.get(b);//首先判断map中是否已经有这个字符，其实就是计算这个字符出现的次数
if (count == null) {
//如果次数为0， 说明map中还没有存放这个字符，该字符次数为0，直接将该字符放进map中即可，次数为1
counts.put(b, 1);
} else {
//如果map中已经有这个字符了，那么计数就要加一
counts.put(b, count + 1);
}
}
//遍历map，将每一个数据转换成HuffmanNode，并将其放进ArrayList中
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
huffmanNodes.add(new HuffmanNode(entry.getKey(), entry.getValue()));
}
return huffmanNodes;
}
//通过List，创建赫夫曼树
private static HuffmanNode createHuffmanTree(List<HuffmanNode> huffmanNodeList) {
while (huffmanNodeList.size() > 1) {
//先进行排序
Collections.sort(huffmanNodeList);
//取出第一棵树
HuffmanNode leftNode = huffmanNodeList.get(0);
//取出第二棵树
HuffmanNode rightNode = huffmanNodeList.get(1);
//创建两棵树的父节点
HuffmanNode parentNode = new HuffmanNode(null, leftNode.weight + rightNode.weight);
parentNode.left = leftNode;
parentNode.right = rightNode;
//将使用过的两棵二叉树移除掉
huffmanNodeList.remove(leftNode);
huffmanNodeList.remove(rightNode);
//将新的二叉树添加上去
huffmanNodeList.add(parentNode);
}
//最后返回赫夫曼树的根节点
return huffmanNodeList.get(0);
}
//生成赫夫曼树对应的赫夫曼编码
//因为要储存的形式是：字符 + 编码， 所以使用map来进行存储
static HashMap<Byte, String> huffmanCodes = new HashMap<Byte, String>();
//因为获得对应编码的时候要拼接路径，所以使用StringBuilder来拼接
static StringBuilder stringBuilder = new StringBuilder();
/**
* 这个方法实现的功能是将所有节点和对应的赫夫曼编码得到，并将它们放入到hashMap中
*
* @param node：表示对应的节点
* @param code：表示对应的编码，左边为0，右边为1
* @param stringBuilder：用于拼接路径
*/
private static void getCodes(HuffmanNode node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);//在这里要注意，要把原来的stringBuilder放进去
stringBuilder1.append(code);//拼接传进来的路径
if (node != null) {
//如果当前节点不为空
if (node.data == null) {
//如果当前节点是非叶子节点
//向左递归
getCodes(node.left, "0", stringBuilder1);
//左边递归完后向右递归
getCodes(node.right, "1", stringBuilder1);
} else {
//如果当前节点是一个叶子节点，说明已经遍历到最后了，直接将该节点和路径放进map中
//在这里需要注意一点：要将StringBuilder转换成String
huffmanCodes.put(node.data, stringBuilder1.toString());
}
}
}
/**
* 为了调用方便，对getCodes进行重载
*
* @param root
*/
private static Map<Byte, String> getCodes(HuffmanNode root) {
if (root == null) {
return null;
} else {
//向左递归
getCodes(root.left, "0", stringBuilder);
//向右递归
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
}
/**
* 编写一个方法实现：将字符串对应的byte数组，通过赫夫曼编码，返回一个压缩过后的byte数组
* 也就是将一个字符数组通过赫夫曼编码表生成对应的编码，100101形式，再将这些编码八个一位放到字节数组中去，返回该位字节对应的数字（有负数）
*
* @param bytes
* @param huffmanCodes
* @return
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
StringBuilder stringBuilder = new StringBuilder();
//遍历字节数组
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));//获取该字符对应的编码
}
//将获得的编码（字符串）转成一个byte数组
//统计字符数组的长度
int len;
int index = 0;//计数器
if (stringBuilder.length() % 8 == 0) {
//如果刚好能除尽
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
byte[] huffmanCodesBytes = new byte[len];//定义字节数组来存放分组后的编码，一个字节八个位
for (int i = 0; i < stringBuilder.length(); i += 8) {
String strByte;
if (i + 8 > stringBuilder.length()) {
//如果字符最后不足8位，就将剩余的看成一个整体
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i + 8);
}
//将StrByte转换成byte，并放在byte数组中
huffmanCodesBytes[index] = (byte) Integer.parseUnsignedInt(strByte, 2);//将字符串转换成二进制的形式
index++;
}
return huffmanCodesBytes;
}
//前序遍历赫夫曼树
private static void huffmanPreorder(HuffmanNode root) {
if (root == null) {
System.out.println("当前赫夫曼树为空，不能进行遍历！");
return;
} else {
root.preOrder();
}
}
}
/**
* 创建赫夫曼节点类，用于存放每一个字符的数据
*/
class HuffmanNode implements Comparable<HuffmanNode> {
Byte data;//用于存放结点的数据,例如如果要存放的字母是a，那么存放的就是97
int weight;//字符的权重，如果字符a出现了9次，那么weight就是9
com.atguigu10.huffmantree.HuffmanNode left;//左孩子结点
com.atguigu10.huffmantree.HuffmanNode right;//右孩子结点
public HuffmanNode(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "HuffmanNode{" +
"data=" + data +
", weight=" + weight +
'}';
}
@Override
public int compareTo(HuffmanNode o) {
//因为要实现对象的比较，所以要实现Comparable接口
return this.weight - o.weight;
}
/**
* 实现赫夫曼树的前序遍历
*/
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}