20、数据结构与算法 - 实战：赫夫曼树树（图文很详细）、赫夫曼编码、应用实践（数据压缩、数据解压）、这一章自我感觉看懂就好。。。
前言
一、赫夫曼树
1.1 基本介绍
1、 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为**最优二叉树，也称为哈夫曼树**(HuffmanTree),还有的书翻译为霍夫曼树；
2、 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近；
1.2 赫夫曼树的概念
1、 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径通路中分支的数目称为路径长度若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1；
2、 结点的权及结点带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权``结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积；
3、 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为**WPL(weightedpathlength)**,权值越大的结点离根结点越近的二叉树才是最优二叉树；
4、 WPL最小的就是赫夫曼树；
5、 举例说明，中间的wpl最小为59，所以中间的才是最优二叉树，也是赫夫曼树；
1.3 思路图解分析
1.3.1 案例
给定一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树
1.3.2 步骤分析
图中文字：
构成赫夫曼树的步骤：
1、 从小到大进行排序,将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树；
2、 取出根节点权值最小的两颗二叉树；
3、 组成一颗新的二叉树,该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和；
4、 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中，；
5)所有的数据都被处理，就得到一颗赫夫曼树
1.3.3 图文分析
1、 第一步排序，将初始数组array={13,7,8,3,29,6,1}排序为array={1,3,6,7,8,13,29}；
2、 第二步取出两个最小的子树；
3、 第三步组成新的二叉树；
4、 第四步再将这颗新的二叉树，以根节点的权值大小再次排序，如下图所示：![ ][nbsp3]；
5、 重复第二步（取两个最小子树）、第三步（组成新树）、第四步（排序），再将这颗新的二叉树，以根节点的权值大小再次排序，如下图所示；
这次取出 结点 4 和结点 6,结合成结点 10 ，在进行排序。
6、 然后重复第二步（取两个最小子树）、第三步（组成新树）、第四步（排序），再将这颗新的二叉树，以根节点的权值大小再次排序，如下图所示；
这次取出 结点 7 和结点8,结合成结点 15 ，在进行排序。
7、 然后重复第二步（取两个最小子树）、第三步（组成新树）、第四步（排序），再将这颗新的二叉树，以根节点的权值大小再次排序，如下图所示；
这次取出 结点 10 和结点13,结合成结点 23 ，在进行排序。
8、 然后重复第二步（取两个最小子树）、第三步（组成新树）、第四步（排序），再将这颗新的二叉树，以根节点的权值大小再次排序，如下图所示；
这次取出 结点 15 和结点23,结合成结点 38 ，在进行排序。最后在于 29 进行排序，组成新的子树，到了这里就成了一个二叉树了，也就是最优二叉树、也是赫夫曼树。
1.4 代码实现
1.4.1 Node 节点类
package com.feng.ch13_huffmantree;
/*
* 创建节点类
* // 为了让 Node 对象 持续排序 Collection 集合排序
* 让 Node 实现 Comparable 接口，重写 compareTo() 方法
* */
public class Node implements Comparable<Node> {
private int value;// 结点权值
private Node left; // 指向左子结点
private Node right; // 指向右子结点
public Node(int value) {
this.value = value;
}
// 前序遍历
public void preOrder(){
System.out.println(this);
if (this.left != null){
this.left.preOrder();
}
if (this.right != null){
this.right.preOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public int compareTo(Node o) {
// 表示从小到大进行排序 -(this.value - o.value):从大到小排列
return this.value - o.value;
}
}
1.4.2 HuffmanTree赫夫曼树类
package com.feng.ch13_huffmantree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/*
* 哈弗曼树
* 构成赫夫曼树的步骤：
* 1、从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
* 2、取出根节点权值最小的两颗二叉树
* 3、组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
* 4、再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
*
* 注意点：这里使用 ArrayList 集合 储存 数组的元素，表示每个元素为一个二叉树，这里仅保存根节点
* */
public class HuffmanTree {
public static void main(String[] args) {
int array[] = {
13, 7, 8, 3, 29, 6, 1};
Node root = createHuffmanTree(array);
// 测试一把
preOrder(root);
}
// 前序遍历
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("是空树，不能遍历~~~");
}
}
/*
* 创建 哈弗曼树的方法
* @param array 需要创建成哈弗曼树的数组
* @return 创建好的哈弗曼树root 结点
* */
public static Node createHuffmanTree(int[] array) {
/*
* 第一步，为了操作方便
* 1、遍历 array 数组
* 2、将 array 的每个元素构成 一个 Node
* 3、将 Node 放入到 ArrayList 中
* */
List<Node> nodes = new ArrayList<>();
for (int value : array) {
nodes.add(new Node(value));
}
/*
* 第二步：
* 处理过程 是循环过程
* 1、从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
* 2、取出根节点权值最小的两颗二叉树
* 3、组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
* 4、再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
* 最后，循环完后，list集合中，只有一个数据，也就是哈弗曼树的根节点。
* */
while (nodes.size() > 1) {
// 排序 从小到大
Collections.sort(nodes);
// System.out.println("nodes=" + nodes); //nodes=[Node{value=1}, Node{value=3}, Node{value=6}, Node{value=7}, Node{value=8}, Node{value=13}, Node{value=29}]
// 取出根节点权值最小的两颗二叉树
// 1、取出权值最小的结点（二叉树）
Node leftNode = nodes.get(0);
// 2、取出权值第二小的结点（二叉树）
Node rightNode = nodes.get(1);
// 3、构建一颗新的二叉树
Node parent = new Node(leftNode.getValue() + rightNode.getValue());
parent.setLeft(leftNode);
parent.setRight(rightNode);
// 4、从 ArrayList 中删除 处理过的二叉树
nodes.remove(leftNode);
nodes.remove(rightNode);
// 5、将parent 加入到 nodes
nodes.add(parent);
// System.out.println("第一次处理后：" + nodes);
}
// 返回 哈弗曼树的 root 结点
return nodes.get(0);
}
}
二、赫夫曼编码
2.1 基本介绍
1、 赫夫曼编码也翻译为哈夫曼编码(HuffmanCoding)，又称霍夫曼编码，是一种编码方式,属于一种程序算法；
2、 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一；
3、 赫夫曼编码**广泛地用于数据文件压缩其压缩率通常在20%～90%之间；
4、 赫夫曼码是可变字长编码(VLC)的一种**Huffman于1952年提出一种编码方法，称之为最佳编码；
2.2 原理剖析
2.2.1 通信领域中信息的处理方式1-定长编码
- i like like like java do you like a java // 共40个字符(包括空格)
- 105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码
- 01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制
- 按照二进制来传递信息，总的长度是 359 (包括空格)
- 在线转码 工具 ：https://www.mokuge.com/tool/asciito16/
2.2.2 通信领域中信息的处理方式1-变长编码
- i like like like java do you like a java // 共40个字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
- 0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d 说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如 空格出现了9 次， 编码为0 ,其它依次类推.
- 按照上面给各个字符规定的编码，则我们在传输 “i like like like java do you like a java” 数据时，编码就是 10010110100…
- 字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做 前缀编码， 即不能匹配到重复的编码(这个在赫夫曼编码中，我们还要进行举例说明, 不捉急)
2.2.3 通信领域中信息的处理方式1-赫夫曼编码
- i like like like java do you like a java // 共40个字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
- 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值.(图后)
注意, 这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl 是一样的，都是最小的, 比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:
三、最佳实践-数据压缩
3.1 案例说明
将给出的一段文本，比如 “i like like like java do you like a java” ， 根据前面的讲的赫夫曼编码原理，对其进行数据压缩处理 ，形式如 “1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110”
3.2 步骤一 创建赫夫曼树
步骤1：根据赫夫曼编码压缩数据的原理，需要创建 “i like like like java do you like a java” 对应的赫夫曼树.
3.3 代码实现
3.3.1 Node类
package com.feng.ch14_huffmancode;
/*
* 创建 Node，带数据和权值
* */
public class Node implements Comparable<Node> {
private Byte data; // 存放数据（字符）本身，比如 'a'=>97 ' '=> 32
private int weight; // 权值，表示字符出现的次数
private Node left;
private Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
// 前序遍历
public void preOrder(){
System.out.println(this);
if (this.left != null){
this.left.preOrder();
}
if (this.right != null){
this.right.preOrder();
}
}
@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 Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public int compareTo(Node o) {
// 从小到大排序
return this.weight - o.weight;
}
}
3.3.2 HuffmanCode 类 赫夫曼编码类
package com.feng.ch14_huffmancode;
import java.io.*;
import java.util.*;
public class HuffmanCode {
public static void main(String[] args) {
String content = "i like like like java do you like a java";
//###################################################### 哈夫曼数据压缩 测试#################################
/*
* 一、字符串 转成 字节数组
* 字节数组 储存的是 ASCII 表对应的 数字
* */
byte[] contentBytes = content.getBytes();
System.out.println("字符串转成的字节数组：" + Arrays.toString(contentBytes));// [105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97]
System.out.println("字符串转成的字节数组大小：" + contentBytes.length); // 40
/*
* 将下面的 4 步，封装成一个方法 huffmanZip()
*
* */
byte[] huffmanCodesBytes = huffmanZip(contentBytes);
System.out.println("压缩后的结果大小是：" + huffmanCodesBytes.length); // 40
System.out.println("压缩后的结果是：" + Arrays.toString(huffmanCodesBytes)); // [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
/*
* 二、字节数组 转成 list集合
* 1、对字节数组进行遍历，统计每一个 byte 出现的次数，封装在 Map 集合
* 2、然后对map 集合进行遍历，对每个 key-value 生成一个 Node 结点，以 Node 结点形式 封装在 List 集合 中
* */
// List<Node> nodes = getNodes(contentBytes);
// System.out.println("nodes=" + nodes); // nodes=[Node{data=32, weight=9}, Node{data=97, weight=5}, Node{data=100, weight=1}, Node{data=101, weight=4}, Node{data=117, weight=1}, Node{data=118, weight=2}, Node{data=105, weight=5}, Node{data=121, weight=1}, Node{data=106, weight=2}, Node{data=107, weight=4}, Node{data=108, weight=4}, Node{data=111, weight=2}]
/*
* 三、list集合 转成 哈弗曼树，
* 1、使用 Collections 集合 对 List 集合进行从小到大排序，
* 2、取出根节点权值最小的两颗二叉树
* 3、组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
* 4、再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
* 最后，循环完后，list集合中，只有一个数据，也就是哈弗曼树的根节点。
*
* 前序遍历中， data 为空的为 父结点， 不为空的为叶子结点。
* */
// System.out.println("哈弗曼树");
// Node huffmanTreeRoot = createHuffmanTree(nodes);
// System.out.println("测试一把 ，创建的二叉树，前序遍历哈弗曼树 前序遍历：");
// preOrder(huffmanTreeRoot);
// System.out.println();
/*
* 四、哈夫曼树 转成 哈夫曼编码
* 哈夫曼编码使用Map<Byte, String> 来储存
* 哈夫曼编码：前面的每个元素对应的 ASCII 和 次数 构成一个 叶子结点，形成的哈弗曼树，左边为0，右边为1。元素=路径，叶子节点的路径称为 哈夫曼编码
* */
// Map<Byte, String> huffmanCodes = getCodes(root);// 对 getCodes(root, "", stringBuilder); 进行了重载
// System.out.println("生成的 哈夫曼编码表 huffmanCodes：" + huffmanCodes); //{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
// System.out.println("~生成的 哈夫曼编码表 codes：" + codes); //{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
// System.out.println();
/*
* 五、对哈夫曼编码进行压缩，得到压缩后的 哈夫曼编码字节数组
* 传入的 字符串 转成 的字节数组 和 哈夫曼编码表
* 测试
* */
// byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
// System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes)); // 17个 huffmanCodeBytes=[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
//###################################################### 哈夫曼数据解压#################################
System.out.println();
System.out.println();
System.out.println("哈夫曼数据解压:");
// byteToBitString((byte) 1);
byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
System.out.println("原来的字符串大小=" + new String(sourceBytes).length()); // i like like like java do you like a java
System.out.println("原来的字符串=" + new String(sourceBytes)); // i like like like java do you like a java
//###################################################### 哈夫曼编码应用实例：压缩和解压文件#################################
System.out.println();
System.out.println();
System.out.println("哈夫曼编码应用实例：压缩和解压文件");
// String srcFile = "D:\\HuffmanCode.java";
// String dstFile = "D:\\HuffmanCode.zip";
//
// zipFile(srcFile, dstFile);
// System.out.println("压缩文件成功~~");
String zipFile = "D:\\HuffmanCode.zip";
String dstFile2 = "D:\\HuffmanCode2.java";
unZipFile(zipFile, dstFile2);
System.out.println("解压文件成功~~~");
}
//###################################################### 哈夫曼数据压缩#################################
/**
* 使用一个方法，将前面的方法封装起来，便于我们的调用
*
* @param contentBytes 原始字符串对应的字节数组
* @return 是经过哈夫曼编码处理后的字节数组（压缩后的数组）
*/
private static byte[] huffmanZip(byte[] contentBytes) {
//二、字节数组 转成 list集合
List<Node> nodes = getNodes(contentBytes);
//三、list集合 转成 哈弗曼树，
Node huffmanTreeRoot = createHuffmanTree(nodes);
//四、哈夫曼树 转成 哈夫曼编码
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
//五、对哈夫曼编码进行压缩，得到压缩后的 哈夫曼编码字节数组
byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
return huffmanCodeBytes;
}
/*
* 二、字节数组 转成 list集合
* @param bytes 接收一个 字节数组
* @return 返回的就是一个 List 集合，如形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
* */
private static List<Node> getNodes(byte[] bytes) {
// 1、先创建一个 ArrayList
ArrayList<Node> nodes = new ArrayList<>();
// 遍历 bytes 字节数组,统计每一个 byte 出现的次数 -》 map[key, value]
Map<Byte, Integer> map = new HashMap(); // Byte 为数据，Integer 为次数
for (byte b : bytes) {
Integer count = map.get(b);
if (count == null) {
// Map 还没有这个字符数据，第一次
map.put(b, 1);
} else {
map.put(b, count + 1);
}
}
// 把每一个键值对 转成 一个 Node 对象，并加入到 nodes 集合中
// 遍历map
for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
/*
* 三、list集合 转成 哈弗曼树，
* 通过一个 list 创建对应的哈弗曼树
* */
public static Node createHuffmanTree(List<Node> nodes) {
while (nodes.size() > 1) {
// 排序 从小到大
Collections.sort(nodes);
// 取出第一颗最小的二叉树
Node leftNode = nodes.get(0);
// 取出第二颗最小的二叉树
Node rightNode = nodes.get(1);
// 创建一颗新的二叉树，他的根节点 没有data，只有权值
Node parent = new Node(null, leftNode.getWeight() + rightNode.getWeight());
parent.setLeft(leftNode);
parent.setRight(rightNode);
// 将已经处理的两颗二叉树从nodes 删除
nodes.remove(leftNode);
nodes.remove(rightNode);
// 将新的二叉树 添加到 nodes
nodes.add(parent);
}
// 循环后，此集合 也就只有一个节点了，返回的为 nodes 第一个节点，此结点为根节点
return nodes.get(0);
}
// 前序遍历
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("哈弗曼树为空~~");
}
}
/*
* huffmanCodes ： 存放所有叶子节点的哈弗曼编码
* stringBuilder ：拼接路径
* */
static Map<Byte, String> huffmanCodes = new HashMap<>();
static StringBuilder stringBuilder = new StringBuilder();
/*
* 四、哈夫曼树 转成 哈夫曼编码
* 重载 getCodes
* */
public static Map<Byte, String> getCodes(Node root) {
if (root == null) {
return null;
}
// 处理root 的左子树
getCodes(root.getLeft(), "0", stringBuilder);
// 处理 root 的右子树
getCodes(root.getRight(), "1", stringBuilder);
return huffmanCodes;
}
/*
* 四、哈夫曼树 转成 哈夫曼编码
* 功能：将传入的 node结点 的所有叶子结点的哈夫曼编码，并放入到 huffmanCodes 集合
*
* 生成 哈弗曼树 对应 的哈夫曼编码
* 思路：
* 1、将哈夫曼编码表 存放在 Map<Byte,String> 形式为：32=>01 97=>100 100=>11000 等等
* 2、在生成 哈夫曼编码表 时，需要去拼接这个路径，所以定义一个StringBuilder 存储 某个叶子结点的路径
*
* @param node 传入结点
* @param code 路径：左子结点是 0， 右子结点是 1
* @param stringBuilder 是用于拼接路径
* */
public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
// 将 code 加入到 stringBuilder2
stringBuilder2.append(code);
if (node != null) {
// 判断当前 node，是叶子结点 还是非叶子结点
if (node.getData() == null) {
// 非叶子结点
// 递归处理
// 向左递归
getCodes(node.getLeft(), "0", stringBuilder2);
// 向右递归
getCodes(node.getRight(), "1", stringBuilder2);
} else {
// 叶子结点
huffmanCodes.put(node.getData(), stringBuilder2.toString());
}
}
}
/*
* 五、对哈夫曼编码进行压缩，得到压缩后的 哈夫曼编码字节数组
* 编写一个方法，将字符串对应的byte[] 数组，通过生成的 哈夫曼编码表，返回一个哈夫曼编写 压缩后 的 byte[]
*
* @param bytes 这时原始的字符串对应的 byte[]
* @param huffmanCodes 生成的哈夫曼编码 map
* @return 返回的哈夫曼编码处理后的 byte[]
* 举例 String content = "i like like like java do you like a java"; => byte[] contentBytes = content.getBytes()
* 返回的字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
* => 对应的 byte[] huffmanCodeBytes , 即 8 位对应一个 byte，放入到 huffmanCodeBytes
* huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000 => 10101000-1 => 10100111(反码)=> 11011000= -88 ]
* huffmanCodeBytes[0] = -88
* */
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
// 1、利用 HuffmanCodes 将 bytes 转成 哈夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
// 遍历 bytes 数组
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b)); // 以 bytes 数组 的每个元素为 key ，取出 value值，value 值为其 路径，也就是哈夫曼编码map集合中的 value值
}
System.out.println("测试 stringBuilder=" + stringBuilder.toString()); //测试 stringBuilder= 11011011000110111111111101011000110111111111101011000110111111111101011001011001110111100101111000100111011110101001111100110110001101111111111010111001011001011001110111100
// 将 “110110110001101111111111010110。。。” 转成 byte[]
// 统计返回 byte[] huffmanCodeBytes 长度
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
// 创建存储压缩后的 byte 数组
byte[] huffmanCodeBytes = new byte[len];
int index = 0; // 记录第几个byte
for (int i = 0; i < stringBuilder.length(); i += 8) {
String strByte;
if (i + 8 > stringBuilder.length()) {
// 不够 8位
strByte = stringBuilder.substring(i); // 从i位 到最后
} else {
strByte = stringBuilder.substring(i, i + 8);
}
// 将 strByte 装成一个byte ，放入到 huffmanCodeBytes
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//###################################################### 哈夫曼数据解压#################################
//
//
// 1、将huffmanCodeBytes[]
//
/*
* 完成数据的解压
* 思路
* 1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
* 重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..."
* 2. 赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码 =》 "i like like like java do you like a java"
* */
/*
*
* 功能：将一个byte 转成一个二进制的字符串
* @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
* @param b 传入的 byte，需要将其转化为 二进制字符串，
* @return
*
* 如果仅使用 String str = Integer.toBinaryString(temp); 进行返回，
* 测试：输入 (byte)-1 ，输出 str=11111111111111111111111111111111
* 输入 (byte)1 , 输出 java.lang.StringIndexOutOfBoundsException: String index out of range: -7 报错。
* 说明 要对String str = Integer.toBinaryString(temp); 返回的数据进行处理，
* 1、先进行截取后8位。
* 2、对于正数 还要补高位。 |= 按位与 256 10000 0000 | 0000 0001 =》 10000 0001
* */
private static String byteToBitString(boolean flag, byte b) {
// 使用变量 保存 b
int temp = b;
// 如果是正数我们还存在补高位
if (flag) {
temp |= 256; // |= 按位与 256 10000 0000 | 0000 0001 =》 10000 0001
}
String str = Integer.toBinaryString(temp);
if (flag) {
// System.out.println("str=" + str); // -1 str=11111111111111111111111111111111 , 1 java.lang.StringIndexOutOfBoundsException: String index out of range: -7 报错。
return str.substring(str.length() - 8);
} else {
return str;
}
}
/*
* 编写 一个方法，完成对压缩数据的解码
* */
/**
* @param huffmanCodes 哈夫曼编码表 map
* @param huffmanBytes 哈夫曼编码得到的字节数组
* @return 就是原来的字符串对应的数组
*/
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
// 1、先得到 HuffmanBytes 对应的二进制的字符串，形式 1010100010111...
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]));
}
System.out.println("哈夫曼字节数组 对应的 二进制字符串=" + stringBuilder.toString()); // 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
// 2、把字符串按照指定的哈夫曼编码进行解码
// 把哈夫曼编码进行调换，因为反向查询 a->100 100->a
Map<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
System.out.println("map=" + map); // map={000=108, 01=32, 100=97, 101=105, 11010=121, 0011=111, 1111=107, 11001=117, 1110=101, 11000=100, 11011=118, 0010=106}
// 创建一个集合， 存放 byte
List<Byte> list = new ArrayList<>();
// i 可以理解为 索引，扫描 stringBuilder 10101000101111111100100010111111110010001....
for (int i = 0; i < stringBuilder.length(); ) {
// 这里不再进行调整 i， 因为下面有 i += count ，已经调整了
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
// 10101000101111111100100010111111110010001....
// 递增的取出 key 1
String key = stringBuilder.substring(i, i + count); // i不动，让count 移动，指定匹配到一个字符
b = map.get(key);
if (b == null) {
// 说明没有匹配到
count++;
} else {
// 匹配到
flag = false;
}
}
list.add(b);
i += count; // i 直接移动到 count
}
// 当 for 循环结束后， 我们list 中 就存放了所有的字符 “i like like like java do you like a java”
byte b[] = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/*
* 编写方法，将一个文件进行压缩
* */
/**
*
* @param srcFile 传入的压缩的文件全路径
* @param dstFile 压缩后将压缩文件存放目录
*/
public static void zipFile(String srcFile, String dstFile){
FileInputStream fis = null;
FileOutputStream fos = null;
ObjectOutputStream oos = null;
try {
// 创建文件的输入流、输出流
fis = new FileInputStream(srcFile);
// 创建一个和源文件大小一样的 byte 数组
byte[] b = new byte[fis.available()];
//读取文件
fis.read(b);
// 直接 对源文件 进行压缩
byte[] huffmanBytes = huffmanZip(b);
// 创建文件的输出流， 存放压缩文件
fos = new FileOutputStream(dstFile);
// 创建一个和文件输出流关联的 ObjectOutputStream
oos = new ObjectOutputStream(fos);
// 以对象流的方式写入 哈夫曼编码，是为了以后 我们 恢复源文件时 使用
oos.writeObject(huffmanBytes);
/*
* 这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
* 注意一定要把赫夫曼编码 写入压缩文件
* */
oos.writeObject(huffmanCodes);
}catch (Exception e){
System.out.println(e.getMessage());
} finally {
try {
fis.close();
fos.close();
oos.close();
} catch (IOException e) {
System.out.println(e.getLocalizedMessage());
}
}
}
//编写一个方法，完成对压缩文件的解压
/**
*
* @param zipFile 准备解压的文件
* @param dstFile 将文件解压到哪个路径
*/
public static void unZipFile(String zipFile, String dstFile) {
//定义 文件输入流
InputStream is = null;
//定义一个 对象输入流
ObjectInputStream ois = null;
//定义文件的输出流
OutputStream os = null;
try {
//创建文件输入流
is = new FileInputStream(zipFile);
//创建一个和 is关联的对象输入流
ois = new ObjectInputStream(is);
//读取 哈夫曼字节数组 huffmanBytes
byte[] huffmanBytes = (byte[])ois.readObject();
//读取 赫夫曼编码表
Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
//解码
byte[] bytes = decode(huffmanCodes, huffmanBytes);
//将bytes 数组写入到目标文件
os = new FileOutputStream(dstFile);
//写数据到 dstFile 文件
os.write(bytes);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e2) {
System.out.println(e2.getMessage());
}
}
}
}