1、写在前面
文件的压缩原理与字符串压缩原理相同，都是用哈夫曼编码；文件的压缩与解压涉及到输入输出流操作；注意：
如果文件本身经过压缩处理，再使用哈夫曼编码压缩，效率不会有明显变化，如ppt，视频等文件；哈夫曼编码压缩按照字节处理，所以可以处理所有文件；哈夫曼编码的压缩率与文件中内容的重复率有关，重复的内容越多，压缩率越高。
2、Java代码 -- 文件的解压和压缩
package DataStructures.Tree;
import java.io.*;
import java.util.*;
/**
* @author yhx
* @date 2020/10/17
*/
public class HuffmanCode {
/**
* 生成哈夫曼树对应的哈夫曼编码
* 1、将哈夫曼编码存放在 Map<Byte,String> 中
* 2、生成哈夫曼编码时，需要拼接路径，定义一个StringBuilder存储某个叶子节点的路径
*/
static Map<Byte, String> huffmanCodes = new HashMap<>();
static StringBuilder stringBuilder = new StringBuilder();
public static void main(String[] args) {
String srcFile = "C://Users//bigyang//Desktop//==//JavaWorkspace//测试文件.txt";
String dstFile = "C://Users//bigyang//Desktop//==//JavaWorkspace//压缩后的文件.zip";
zipFile(srcFile, dstFile);
System.out.println("文件压缩完成");
String zipFile = "C://Users//bigyang//Desktop//==//JavaWorkspace//压缩后的文件.zip";
String dstFile2 = "C://Users//bigyang//Desktop//==//JavaWorkspace//解压后的文件.txt";
unZipFile(zipFile,dstFile2);
System.out.println("文件解压完成");
}
/**
* 接收字符串数组，转换为哈夫曼节点集合，节点统计了每个字符出现的次数
*
* @param bytes 字符串数组
* @return 返回哈夫曼节点集合
*/
private static List<HuffmanNode> getNodes(byte[] bytes) {
// 1、创建一个ArrayList
List<HuffmanNode> nodes = new ArrayList<>();
/*
2、统计每一个字符出现的次数
键Key：字符，byte整型
值Value：次数，Integer整型
*/
HashMap<Byte, Integer> counts = new HashMap<>();
for (byte ch : bytes) {
// 获取每个字符在哈希表中值（次数）
Integer count = counts.get(ch);
// 如果值为空，说明该字符第一次被统计到，将该字符ch（Key）的次数count（Value）改为1
if (count == null) {
counts.put(ch, 1);
}
// 值不为空，说明该字符不是第一次出现，只需将出现次数加1
else {
counts.put(ch, count + 1);
}
}
// 3、遍历哈希表，将每个“键值对”转成一个HuffmanNode对象，加入到Nodes集合中
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new HuffmanNode(entry.getKey(), entry.getValue()));
}
return nodes;
}
/**
* 创建哈夫曼树
*
* @param nodes 节点集合
* @return 返回树根节点
*/
private static HuffmanNode createHuffmanTree(List<HuffmanNode> nodes) {
while (nodes.size() > 1) {
// 排序
Collections.sort(nodes);
// 取出最小的二叉树
HuffmanNode leftNode = nodes.get(0);
// 取出第二小的二叉树
HuffmanNode rightNode = nodes.get(1);
// 创建一棵新的二叉树，没有data，只有权值
HuffmanNode parent = new HuffmanNode(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
// 移除两棵处理过的二叉树
nodes.remove(leftNode);
nodes.remove(rightNode);
// 将新的二叉树加入到nodes集合
nodes.add(parent);
}
// 最后的节点就是哈夫曼树的根节点
return nodes.get(0);
}
/**
* 得到 node节点的所有叶子节点的哈夫曼编码，并存放到容器huffmanCodes中
*
* @param node 传入的节点（根节点）
* @param code 叶子节点的路径。左子节点是0，右子节点是1
* @param stringBuilder 拼接路径
*/
private static void getCodes(HuffmanNode node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
// 将code拼接到stringBuilder2后
stringBuilder2.append(code);
if (node != null) {
// 判断当前node节点是否是叶子节点
if (node.data == null) {
// 左右递归处理
getCodes(node.left, "0", stringBuilder2);
getCodes(node.right, "1", stringBuilder2);
}
// 叶子节点
else {
// 说明找到了某个叶子节点，将对应的路径（哈夫曼编码）存入到容器huffmanCodes中
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
/**
* 为了调用方便，重载getCodes方法
*
* @param root 根节点
* @return 返回哈夫曼编码表
*/
private static Map<Byte, String> getCodes(HuffmanNode root) {
if (root == null) {
return null;
}
// 处理根节点的左右子树
getCodes(root.left, "0", stringBuilder);
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
/**
* 输入一个字符串数组，返回哈夫曼编码压缩后的 byte[]
*
* @param bytes 待压缩字符串数组
* @param huffmanCodes 生成的哈夫曼编码表
* @return 返回压缩结果
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
// 先利用huffmanCodes将字符数组bytes转为哈夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
// 按顺序得到每个字符对应的哈夫曼编码，并将其拼接到一起
stringBuilder.append(huffmanCodes.get(b));
}
//System.out.println("5、根据哈夫曼编码表，将字符串转为二进制编码字符串：\n" + stringBuilder.toString() + "\n");
// 统计返回byte[]的长度
// 以下6行代码等价于：int len = (stringBuilder.length() + 7) / 8;
int len;
// 因为每8位对应一个byte，所以步长为8
int stride = 8;
if (stringBuilder.length() % stride == 0) {
len = stringBuilder.length() / stride;
} else {
len = stringBuilder.length() / stride + 1;
}
// 存储压缩后的byte数组
byte[] huffmanCodeBytes = new byte[len];
// 记录是第几个byte
int index = 0;
for (int i = 0; i < stringBuilder.length(); i += stride) {
String strByte;
// 不足8位
if (i + stride > stringBuilder.length()) {
strByte = stringBuilder.substring(i);
}
// 位数足够
else {
strByte = stringBuilder.substring(i, i + stride);
}
// 将strByte转成一个byte，放入到huffmanCodeBytes数组中
// parseInt(String s, int radix)函数：表示将s字符串（radix表示其进制）转为10进制整型
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
/**
* 将以上方法封装，传入待压缩字符串，返回压缩后的哈夫曼编码字节数组
*
* @param contentBytes 待压缩字符串
* @return 哈夫曼编码
*/
private static byte[] huffmanZip(byte[] contentBytes) {
// 将每个字符转为node节点
List<HuffmanNode> nodes = getNodes(contentBytes);
// 创建哈夫曼树
HuffmanNode huffmanTreeRoot = createHuffmanTree(nodes);
//System.out.println("3、哈夫曼树前序遍历的结果：");
//huffmanTreeRoot.preOrder();
//System.out.println();
// 根据哈夫曼树创建哈夫曼编码表
//System.out.println("4、生成哈夫曼编码表：");
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
//System.out.println(huffmanCodes);
System.out.println();
// 根据哈夫曼编码表将字符串压缩为哈夫曼编码字节数组
byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
//System.out.println("6、字符串转为哈夫曼编码字节数组：\n" + Arrays.toString(huffmanCodeBytes) + "\n");
// 返回
return huffmanCodeBytes;
}
/**
* 将一个byte转成一个二进制字符串，如 8 --> 0000 1000
*
* @param b 字节
* @param flag 标识是否需要补高位，true表示需要。
* 如果是最后一个字节，不需要补高位。
* 因为最后一个字节在压缩时不一定有8位，解码时如果强行补位就改变其值了。
* @return 二进制字符串，按照补码返回
*/
private static String byteToBitString(boolean flag, byte b) {
int temp = b;
if (flag) {
/*
按位或，用于将正数补高位
256 二进制 => 1 0000 0000
*/
temp = temp | 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) {
// 先得到哈夫曼编码字节数组对应的二进制字符串
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < huffmanBytes.length; i++) {
// 判断是否是最后一个字节
boolean flag = (i == huffmanBytes.length - 1);
stringBuilder.append(byteToBitString(!flag, huffmanBytes[i]));
}
//System.out.println("7、（哈夫曼字节数组 -> 二进制编码字符串）解码后：\n" + stringBuilder.toString() + "\n");
// 解码
Map<String, Byte> map = new HashMap<>();
// 将哈夫曼编码表的键K值V反转
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
//System.out.println("8、哈夫曼编码表的键K值V反转后为：\n" + map + "\n");
// 将二进制编码字符串转换为字符数组
List<Byte> list = new ArrayList<>();
for (int i = 0; i < stringBuilder.length(); ) {
// 递增计数器
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
// 递增取字符串中的0或1
String key = stringBuilder.substring(i, i + count);
// 从编码表中找，是否有字符串对应的数值（ASCII）
b = map.get(key);
// 没有匹配到
if (b == null) {
count++;
} else {
flag = false;
}
}
// 将匹配到的数值（ASCII）添加到集合
list.add(b);
i += count;
}
// 将集合中的数据放入数组，返回结果
byte[] bs = new byte[list.size()];
for (int i = 0; i < bs.length; i++) {
bs[i] = list.get(i);
}
return bs;
}
/**
* 文件压缩
*
* @param srcFile 传入待压缩文件的全路径
* @param dstFile 压缩后的存放位置
*/
private static void zipFile(String srcFile, String dstFile) {
// 创建文件输入流和输出流
FileInputStream is = null;
OutputStream os = null;
ObjectOutputStream oos = null;
try {
is = new FileInputStream(srcFile);
os = new FileOutputStream(dstFile);
oos = new ObjectOutputStream(os);
// 创建一个和源文件大小一致的byte[]
byte[] b = new byte[is.available()];
// 读取文件
is.read(b);
// 获取文件对应的哈夫曼编码表
byte[] huffmanBytes = huffmanZip(b);
// 将哈夫曼编码表以对象流的形式输出出去，恢复源文件时会用到
oos.writeObject(huffmanBytes);
// 将哈夫曼编码表写入压缩文件
oos.writeObject(huffmanCodes);
} catch (Exception e) {
System.out.println(e.getMessage());
}
// 关闭文件
finally {
try {
is.close();
os.close();
oos.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
/**
* 文件解压
*
* @param zipFile 准备解压的文件
* @param dstFile 将文件解压的路径
*/
private 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);
byte[] huffmanBytes = (byte[]) ois.readObject();
// 读取哈夫曼编码表
Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
// 解码
byte[] bytes = decode(huffmanCodes, huffmanBytes);
// 写入到目标文件
os = new FileOutputStream(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());
}
}
}
/**
* 前序遍历的方法
*
* @param root 根节点
*/
private static void preOrder(HuffmanNode root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("哈夫曼树为空");
}
}
}
/**
* 创建节点Node，带数据和权值
*/
class HuffmanNode implements Comparable<HuffmanNode> {
Byte data;
int weight;
HuffmanNode left;
HuffmanNode right;
/**
* 构造器
*
* @param data 以ASCII码存放数据，如'a' = 97
* @param weight 权值，表示字符出现的次数
*/
public HuffmanNode(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 int compareTo(HuffmanNode o) {
// 升序排序
return this.weight - o.weight;
}
/**
* 重写方法：打印节点信息
*
* @return 打印形式
*/
@Override
public String toString() {
return "Huffman Node [ data = " + data + " weight = " + weight + " ]";
}
}
3、运行结果
测试文件是一个txt文件，内容如下，其中含有大量1，对于哈夫曼编码压缩，文件中重复的内容越多，压缩率越高；
程序运行后，将 “测试文件.txt” 压缩为 “压缩后的文件.zip” ，之后又将 “压缩后的文件.zip” 解压为 “解压后的文件.txt”；
