1.定义节点类
class Node1 implements Comparable<Node1> {
Byte data;
int weight;
Node1 left;
Node1 right;
public Node1(Byte data, int weight) {
this.weight = weight;
this.data = data;
}
@Override
public int compareTo(Node1 o) {
return this.weight - o.weight;
}
@Override
public String toString() {
return "Node1{" +
"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();
}
}
}
2.定义Map，StringBuilder类型 全局变量
-
将赫夫曼编码表存放在 Map<Byte,String> 形式
生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011} - 在生成赫夫曼编码表示，需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
static Map<Byte, String> huffmanCodes = new HashMap<>();
static StringBuilder stringBuilder = new StringBuilder();
3.压缩
//统计
private static List<Node1> getNodes(byte[] bytes) {
ArrayList<Node1> nodes = new ArrayList<>();
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) {
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new Node1(entry.getKey(), entry.getValue()));
}
return nodes;
//List 形式 [Node1[date=97 ,weight = 5], Node1[]date=32,weight = 9]......]
}
//可以通过List 创建对应的赫夫曼树
private static Node1 createHuffmanTree(List<Node1> nodes) {
while (nodes.size() > 1) {
Collections.sort(nodes);
Node1 leftNode = nodes.get(0);
Node1 rightNode = nodes.get(1);
Node1 parent = new Node1(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
return nodes.get(0);
}
//前序遍历的方法
private static void preOrder(Node1 root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("HuffmanTree is null");
}
}
//将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
private static void getCodes(Node1 node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
stringBuilder2.append(code);
if (node != null) {
if (node.data == null) {
getCodes(node.left, "0", stringBuilder2);
getCodes(node.right, "1", stringBuilder2);
} else {
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//为了调用方便，我们重载 getCodes
private static Map<Byte, String> getCodes(Node1 root) {
if (root == null) {
return null;
}
getCodes(root.left, "0", stringBuilder);
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
//将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的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[1] = -88
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
int len = (stringBuilder.length() + 7) / 8;
byte[] huffmanCodeBytes = 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);
}
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//将前面的方法封装起来
private static byte[] huffmanZip(byte[] bytes){
List<Node1> nodes = getNodes(bytes);
Node1 huffmanTreeRoot = createHuffmanTree(nodes);
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
return huffmanCodeBytes;
}
public static void zipFile(String srcFile,String dstFile){
FileInputStream fis = null;
FileOutputStream fos = null;
ObjectOutputStream oos = null;
try {
fis = new FileInputStream(srcFile);
byte[] b = new byte[fis.available()];
fis.read(b);//读进b数组中
byte[] huffmanBytes = huffmanZip(b);
oos = new ObjectOutputStream(new FileOutputStream(dstFile));
oos.writeObject(huffmanBytes);
oos.writeObject(huffmanCodes);
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
fis.close();
fos.close();
oos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
4.解压
完成数据的解压思路:
-
将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
重写先转成 赫夫曼编码对应的二进制的字符串 “1010100010111…” - 赫夫曼编码对应的二进制的字符串 “1010100010111…” ==> 对照 赫夫曼编码
//将一个byte 转成一个二进制的字符串,可以参考二进制的原码，反码，补码
private static String byteToBitString(boolean flag,byte b){
int temp = b;
if(flag){//如果是正数补高位
temp |= 256; //按位与256 1 0000 0000 | 0000 0001 => 1 0000 0001
}
String str = Integer.toBinaryString(temp);//返回temp对应的二进制的补码
if(flag){
return str.substring(str.length() - 8);
}else{
return str;
}
}
//完成对压缩数据的解码
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
boolean flag = (i == huffmanBytes.length - 1);
stringBuilder.append(byteToBitString(!flag, b));
}
Map<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
List<Byte> list = new ArrayList<>();
for (int j = 0; j < stringBuilder.length(); ) {
int count = 1;
boolean flag1 = true;
Byte b =null;
while(flag1){
String key = stringBuilder.substring(j, j + count);
b = map.get(key);
if(b == null){
count++;
}else{
flag1 = false;
}
}
list.add(b);
j += count;
}
byte[] b = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
public static void unZipFile(String zipFile, String dstFile) {
FileInputStream fis = null;
ObjectInputStream ois = null;
OutputStream os = null;
try {
fis = new FileInputStream(zipFile);
ois = new ObjectInputStream(fis);
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 (IOException e) {
e.printStackTrace();
} catch (ClassNotFoundException e) {
e.printStackTrace();
} finally {
try {
fis.close();
ois.close();
os.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
5.测试方法
public static void main(String[] args) {
//测试压缩文件
String srcFile = "d://Uninstall.xml";
String dstFile = "d://Uninstall.zip";
zipFile(srcFile, dstFile);
System.out.println("压缩成功");
//测试解压文件
// String zipFile = "d://Uninstall.zip";
// String dstFile = "d://Uninstall2.xml";
// unZipFile(zipFile, dstFile);
// System.out.println("解压成功");
}
版权声明：本文为luo1454925298原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。