哈夫曼编码 最佳实践-文件压缩
我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压， 具体要求：给你一个图片文件，要求对其进行无损压缩, 看看压缩效果如何。
思路：读取文件-> 得到赫夫曼编码表 -> 完成压缩
代码实现：
public class HuffmanCode {
public static void main(String[] args) {
//测试压缩文件 G:\360downloads\1001540.jpg
String srcFile = "G:\\360downloads\\1001540.jpg";
String destFile = "G:\\360downloads\\1001540Copy.zip";
//压缩操作
zipFile(srcFile, destFile);
//解压操作
String srcFileSrc = "G:\\360downloads\\1001540Copy.zip";
String destFileSrc = "G:\\360downloads\\1001540CopyToJPG.jpg";
unZipFile(srcFileSrc,destFileSrc);
}
/**
* 数据压缩
*
* @param srcPath 传入完整的路径
* @param destPath 输出;路径
*/
public static void zipFile(String srcPath, String destPath) {
//创建输出流
//创建输入流
FileInputStream is = null;
FileOutputStream fos = null;
ObjectOutputStream oos = null;
try {
is = new FileInputStream(srcPath);
byte[] bytes = new byte[is.available()];
//读取文件
is.read(bytes);
//直接对文件进行压缩
byte[] huffmanZipBytes = huffmanZip(bytes);
//输出
fos = new FileOutputStream(destPath);
//创建一个
oos = new ObjectOutputStream(fos);
//以对象流的方式写入 赫夫曼编码 为了回复数据流使用
oos.writeObject(huffmanZipBytes);
//把赫夫曼编码放进去
oos.writeObject(huffmanCodes);
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
is.close();
fos.close();
oos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
测试
压缩
哈夫曼编码 最佳实践-文件解压(文件恢复)
具体要求：将前面压缩的文件，重新恢复成原来的文件。
思路：读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)
代码实现：
代码实现：
public class HuffmanCode {
public static void main(String[] args) {
//测试压缩文件 G:\360downloads\1001540.jpg
String srcFile = "G:\\360downloads\\1001540.jpg";
String destFile = "G:\\360downloads\\1001540Copy.zip";
//压缩操作
zipFile(srcFile, destFile);
//解压操作
String srcFileSrc = "G:\\360downloads\\1001540Copy.zip";
String destFileSrc = "G:\\360downloads\\1001540CopyToJPG.jpg";
unZipFile(srcFileSrc,destFileSrc);
}
/**
* 数据解压
*
* @param zipFileSrc 传入完整的路径
* @param destPath 输出;路径
*/
public static void unZipFile(String zipFileSrc, String destPath) {
//定义文件输入流
InputStream is = null;
//定义一个对象输入了
ObjectInputStream ois = null;
//定义文件输出
OutputStream os = null;
try {
is = new FileInputStream(zipFileSrc);
ois = new ObjectInputStream(is);
//读取 数组
byte[] bytes = (byte[]) ois.readObject();
//读取编码表
Map<Byte, String> byteStringMap = (Map<Byte, String>) ois.readObject();
//节码
byte[] decode = decode(byteStringMap, bytes);
os = new FileOutputStream(destPath);
//写出数据到
os.write(decode);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
测试
测试
完整代码
package cn.icanci.datastructure.haffmantree.haffmancode;
import java.io.ObjectOutputStream;
import java.io.FileOutputStream;
import java.io.*;
import java.io.FileInputStream;
import java.util.*;
/**
* @Author: icanci
* @ProjectName: AlgorithmAndDataStructure
* @PackageName: cn.icanci.datastructure.haffmantree.haffmancode
* @Date: Created in 2020/3/15 21:04
* @ClassAction: 哈夫曼编码
*/
public class HuffmanCode {
public static void main(String[] args) {
//测试压缩文件 G:\360downloads\1001540.jpg
String srcFile = "G:\\360downloads\\1001540.jpg";
String destFile = "G:\\360downloads\\1001540Copy.zip";
//压缩操作
zipFile(srcFile, destFile);
//解压操作
String srcFileSrc = "G:\\360downloads\\1001540Copy.zip";
String destFileSrc = "G:\\360downloads\\1001540CopyToJPG.jpg";
unZipFile(srcFileSrc,destFileSrc);
}
/**
* 数据解压
*
* @param zipFileSrc 传入完整的路径
* @param destPath 输出;路径
*/
public static void unZipFile(String zipFileSrc, String destPath) {
//定义文件输入流
InputStream is = null;
//定义一个对象输入了
ObjectInputStream ois = null;
//定义文件输出
OutputStream os = null;
try {
is = new FileInputStream(zipFileSrc);
ois = new ObjectInputStream(is);
//读取 数组
byte[] bytes = (byte[]) ois.readObject();
//读取编码表
Map<Byte, String> byteStringMap = (Map<Byte, String>) ois.readObject();
//节码
byte[] decode = decode(byteStringMap, bytes);
os = new FileOutputStream(destPath);
//写出数据到
os.write(decode);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 数据压缩
*
* @param srcPath 传入完整的路径
* @param destPath 输出;路径
*/
public static void zipFile(String srcPath, String destPath) {
//创建输出流
//创建输入流
FileInputStream is = null;
FileOutputStream fos = null;
ObjectOutputStream oos = null;
try {
is = new FileInputStream(srcPath);
byte[] bytes = new byte[is.available()];
//读取文件
is.read(bytes);
//直接对文件进行压缩
byte[] huffmanZipBytes = huffmanZip(bytes);
//输出
fos = new FileOutputStream(destPath);
//创建一个
oos = new ObjectOutputStream(fos);
//以对象流的方式写入 赫夫曼编码 为了回复数据流使用
oos.writeObject(huffmanZipBytes);
//把赫夫曼编码放进去
oos.writeObject(huffmanCodes);
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
is.close();
fos.close();
oos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 数据解码
*
* @param huffmanCodes 编码表
* @param bytes 赫夫曼编码得到的字节数组
* @return
*/
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] bytes) {
//1.先得到 bytes 对应的二进制字符串
StringBuilder stringBuilder = new StringBuilder();
//2.将byte数组
for (int i = 0; i < bytes.length; i++) {
boolean flag = (i == bytes.length - 1);
stringBuilder.append(byteToString(!flag, bytes[i]));
}
//把字符串按照指定的赫夫曼编码进行节码
//把赫夫曼编码进行调换 反响查询
Map<String, Byte> map = new HashMap<String, Byte>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
//创建一个集合
ArrayList<Byte> list = new ArrayList<>();
for (int i = 0; i < stringBuilder.length(); ) {
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
//取出一个 1 0
String key = stringBuilder.substring(i, i + count);
b = map.get(key);
if (b == null) {
count++;
} else {
flag = false;
}
}
list.add(b);
i += count;
}
//把list数组放在 byte数组中
byte[] by = new byte[list.size()];
for (int i = 0; i < list.size(); i++) {
by[i] = list.get(i);
}
return by;
}
//数据的解压
//重新转成字符串 然后在转为 二进制字符串
private static String byteToString(boolean flag, byte b) {
int temp = b;
//如何是证数 需要补位
//按位与
if (flag) {
temp |= 256;
}
//返回的是temp 的对应的补码
String string = Integer.toBinaryString(temp);
if (flag) {
return string.substring(string.length() - 8);
} else {
return string;
}
}
/**
* @param bytes 需要压缩的
* @return 压缩之后的
*/
private static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
Node huffmanTree = createHuffmanTree(nodes);
preOrder(huffmanTree);
getCodes(huffmanTree);
byte[] zip = zip(bytes, huffmanCodes);
return zip;
}
/**
* 编写一个方法 将字符串对应的Byte数组 通过生成的哈夫曼编码表
*
* @param bytes
* @param huffmanCodes
* @return 对应的 byte数组
*/
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));
}
//将字符串转成 byte数组
//统计返回的 长度
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
//创建存储压缩后的数组
byte[] by = new byte[len];
int index = 0;
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);
}
by[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return by;
}
//生成赫夫曼树的对应的赫夫曼编码
//思路分析:
//1.将赫夫曼编码存放着在 Map<Byte,String>
//2.在生成哈夫曼编码表的时候 需要去拼接路径
static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
static StringBuilder sb = new StringBuilder();
private static void getCodes(Node root) {
if (root == null) {
System.out.println("空");
} else {
getCodes(root, "", sb);
}
}
/**
* 功能:将传入的node节点的所有叶子节点的赫夫曼编码得到 并放入huffmanCodes集合
*
* @param node 传入节点
* @param code 传入;路径 左 0 右1
* @param stringbuilder 拼接路径的
*/
private static void getCodes(Node node, String code, StringBuilder stringbuilder) {
StringBuilder stringBuilder = new StringBuilder(stringbuilder);
stringBuilder.append(code);
if (node != null) {
//判断当前Node是叶子节点还是非叶子节点
if (node.data == null) {
getCodes(node.left, "0", stringBuilder);
getCodes(node.right, "1", stringBuilder);
} else {
//是叶子节点 找到了叶子节点的最后
huffmanCodes.put(node.data, stringBuilder.toString());
}
}
}
//前序遍历
private static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("空");
}
}
/**
* 接收字节数组
*
* @param bytes 需要转换的字节数组
* @return 返回
*/
private static List<Node> getNodes(byte[] bytes) {
//创建一个ArrayList
List<Node> nodes = new ArrayList<>();
//编译bytes 统计
HashMap<Byte, Integer> hashMap = new HashMap<>();
for (byte b : bytes) {
Integer count = hashMap.get(b);
if (count == null) {
hashMap.put(b, 1);
} else {
hashMap.put(b, count + 1);
}
}
//把每个键值对 转成一个Node对象
for (Map.Entry<Byte, Integer> entry : hashMap.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
private static Node createHuffmanTree(List<Node> nodes) {
while (nodes.size() > 1) {
Collections.sort(nodes);
Node left = nodes.get(0);
Node right = nodes.get(1);
//创建一个新的二叉树 没有根节点 只有权值
Node parent = new Node(null, left.weight + right.weight);
parent.left = left;
parent.right = right;
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}
}
//创建Node
class Node implements Comparable<Node> {
//存放数据本身
Byte data;
//权值
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 void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
}
赫夫曼编码压缩文件注意事项
如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件 [举例压一个 .ppt]
赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml文件]
如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显.
