package com.haiyang.datastructure.huffmancode;
import com.sun.org.apache.bcel.internal.generic.NEW;
import java.io.*;
import java.util.*;
public class HuffmanCode {
//标记最后一个数的位数
static int lastCode = 8;
//用于存储哈夫曼编码
static Map huffmanCodes = new HashMap();
//用于拼接哈夫曼编码
static StringBuilder stringBuilder = new StringBuilder();
public static void main(String[] args) {
zipFile("C:\Users\haiyang\Pictures\草纸\3.jpg", "C:\Users\haiyang\Pictures\草纸\3.zip");
unZipFile("C:\Users\haiyang\Pictures\草纸\3.zip", "C:\Users\haiyang\Pictures\草纸\6.jpg");
}
public static void unZipFile(String zipFile, String dstFile) {
InputStream is = null;
OutputStream os = null;
ObjectInputStream ois = null;
try {
is = new FileInputStream(zipFile);//通过输入流读取压缩后文件
ois = new ObjectInputStream(is);//通过对象流读取压缩后文件和哈夫曼编码两部分
byte[] huffmanBytes = (byte[]) ois.readObject();
Map huffmanCodes = (Map) ois.readObject();
byte[] decode = decode(huffmanCodes, huffmanBytes);//进行解压
os = new FileOutputStream(dstFile);//通过输出流保存解压后文件
os.write(decode);//写入解压后文件
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
System.out.println(e.getMessage());
}
}
}
public static void zipFile(String srcFile, String dstFile) {
FileInputStream is = null;
FileOutputStream os = null;
ObjectOutputStream oos = null;
try {
is = new FileInputStream(srcFile);//通过输入流读取文件
byte[] b = new byte[is.available()];//用于读取文件
is.read(b);//读取文件到byte[] 中
byte[] huffmanZip = huffmanZip(b);//进行压缩
os = new FileOutputStream(dstFile);//输出流保存压缩后文件
oos = new ObjectOutputStream(os);//因为需保存压缩后文件和哈夫曼编码两部分，使用对象流方便操作
oos.writeObject(huffmanZip);//写入压缩后文件
oos.writeObject(huffmanCodes);//写入哈夫曼编码
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
os.close();
oos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
public static byte[] decode(Map huffmanCodes, byte[] bytes) {
//
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < bytes.length; i++) {
byte b = bytes[i];
boolean flag = (i == bytes.length - 1);
stringBuilder.append(byteToBitString(!flag, b));
}
System.out.println(stringBuilder.length());
//将huffmanCodes 翻转便于比较
HashMap map = new HashMap<>();
for (Map.Entry entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
//存储比较完成的字符串
ArrayList list = new ArrayList<>();
for (int i = 0; i < stringBuilder.length(); ) {
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
String s = stringBuilder.substring(i, i + count);
b = map.get(s);
if (b == null) {
count++;
} else {
flag = false;
}
}
list.add(b);
i += count;
}
byte[] bytes1 = new byte[list.size()];
for (int i = 0; i < list.size(); i++) {
bytes1[i] = list.get(i);
}
return bytes1;
}
public static String byteToBitString(boolean flag, byte b) {
int temp = b;//将字节转化为整数类型
temp |= 256;//整数需要补位 按位与256运算 1 0000 0000 | 0000 0001 => 1 0000 0001
String str = Integer.toBinaryString(temp);//将整数转化为二进制补码
if (flag) {
return str.substring(str.length() - 8);//每个整数占4个字节，32位需取后八位
} else {
return str.substring(str.length() - lastCode);//如果字节数组的最后一位位整数，解析时不需要补位
}
}
public static byte[] huffmanZip(byte[] bytes) {
//调用getCodes方法将字节数组转化为结点类型
List nodes = getNodes(bytes);
//创建哈夫曼树
Node huffmanTree = createHuffmanTree(nodes);
//获取哈夫曼编码
Map codes = getCodes(huffmanTree);
byte[] zip = zip(bytes, codes);
return zip;
}
public static byte[] zip(byte[] bytes, Map huffmanCodes) {
//将所有字节的哈夫曼编码拼接
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
//遍历字节数组，进行哈夫曼编码拼接
stringBuilder.append(huffmanCodes.get(b));
}
// System.out.println(stringBuilder.toString());
int len;
//每8位代表一个字节
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
lastCode = stringBuilder.length() % 8;
len = stringBuilder.length() / 8 + 1;
}
byte[] bys = new byte[len];
int index = 0;
for (int i = 0; i < stringBuilder.length(); i += 8) {
String strByte;
if (i + 8 > stringBuilder.length()) {
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i + 8);
}
bys[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return bys;
}
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 {
//如果是叶子结点，代表该字符的编码已拼接完成，加入到Map中
huffmanCodes.put(node.data, stringBuilder1.toString());
}
}
}
public static Map getCodes(Node root) {
if (root == null) {
return null;
}
getCodes(root.left, "0", stringBuilder);
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("树为空，无法遍历");
}
}
//将字节数组转化为结点类型
public static List getNodes(byte[] bytes) {
ArrayList nodes = new ArrayList<>();//储存结点
HashMap map = new HashMap<>();//储存每种字节出现的次数
for (byte b : bytes) {
//遍历数组记录每种字节出现的次数
Integer count = map.get(b);
if (count == null) {
map.put(b, 1);
} else {
map.put(b, count + 1);
}
}
for (Map.Entry entry : map.entrySet()) {
//遍历Map将每种字节及其出现的次数转化为结点
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
public static Node createHuffmanTree(List nodes) {
while (nodes.size() > 1) {
//按weight升序排序
Collections.sort(nodes);
//从结点列表nodes中选取两个最小的结点
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
//通过选取的结点构建一棵树,其根节点的weight为两个最小结点的和
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//将结点列表中的已选取两个最小的结点移除，并将新构建的树的根节点加入到结点列表中
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
return nodes.get(0);
}
}
class Node implements Comparable {
//在给定的序列中，每种字符是一个data，weight代表每种字符出现堆得次数
Byte data;
int weight;
Node left;
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
//自定义比较器，通过weight进行升序排序
@Override
public int compareTo(Node o) {
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();
}
}
}
