11.树结构实际应用
package demo01;
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";
byte[] contentBytes = ();
(); //40
//编码
byte[] huffmanZipBytes = huffmanZip(contentBytes);
((huffmanZipBytes));
//如何将数据进行解压（解码）
byte[] sourceBytes = decode(huffmanCodes, huffmanZipBytes);
("原来的字符串=" + new String(sourceBytes));
*/
/*
//测试压缩文件
String srcFile="F:\\";
String dstFile="F:\\";
zipFile(srcFile,dstFile);
("压缩成功~~");
*/
//测试解压文件
String zipFile="F:\\";
String dstFile="F:\\";
unZipFile(zipFile,dstFile);
System.out.println("解压成功~~");
}
//编写一个方法,将一个文件进行压缩
public static void zipFile(String srcFile, String dstFile) {
//创建输出流
FileOutputStream os = null;
ObjectOutputStream oos = null;
//创建文件的输入流
FileInputStream is = null;
try {
is = new FileInputStream(srcFile);
//创建一个和源文件大小一样的byte[]
byte[] b = new byte[is.available()];
//读取文件
is.read(b);
//直接对源文件压缩
byte[] huffmanZipBytes = huffmanZip(b);
//创建文件的输出流，存放压缩文件
os = new FileOutputStream(dstFile);
//创建一个和文件输出流关联的ObjectOutputStream
oos = new ObjectOutputStream(os);
//把 赫夫曼编码后的字节数组写入压缩文件
oos.writeObject(huffmanZipBytes);
//这里我们以对象流的方式写入赫夫曼编码，是为了以后我们恢复源文件时使用
//注意：一定要把赫夫曼编码写入压缩文件
oos.writeObject(huffmanCodes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
oos.close();
os.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
//编写一个方法，对压缩文件解压
/**
* @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);
//读取byte数组到huffmanBytes
byte[] huffmanBytes=(byte[])ois.readObject();
//读取赫夫曼编码表
Map<Byte,String> huffmanCodes=(Map<Byte,String>)ois.readObject();
//解码
byte[] decode = decode(huffmanCodes, huffmanBytes);
//将bytes 数组写入到目标文件
os=new FileOutputStream(dstFile);
//写出数据到文件中
os.write(decode);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
//完成数据的解压
//思路
//1.将 [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
// 先转成赫夫曼编码对应的二进制字符串"101010011011110111101001101111011 ..."
//2.赫夫曼编码对应的二进制的字符串"1010100110111101111010 ... " => 对照 赫夫曼编码重新转成字符串 => "i like like like java do you like a java"
/**
* 将 一个byte 转成 一个二进制字符串
*
* @param b 传入的byte
* @return 返回的是该 b 对应的二进制的字符串，（注意是按补码返回）
* @Param flag 标志是否需要补高位，如果是true 表示需要补高位，如果是false 表示不补
*/
private static String byteToBitString(boolean flag, byte b) {
//使用变量保存 b
int temp = b;//将 b 转成 int类型
//如果是正数，我们还需要补高位
if (flag) {
temp = 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;
}
}
/**
* 编写一个方法，完成对压缩数据的解码
*
* @param huffmanCodes 赫夫曼编码表 map
* @param huffmanBytes 赫夫曼编码得到的字节数组
* @return 就是原来的字符串对应的数组
*/
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
//1.先得到 huffmanBytes 对应的二进制的字符串，如 1010100110111101111010 ...
StringBuilder stringBuilder = new StringBuilder();
//将byte数组转成二进制的字符串
for (int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
//判断是不是最后一个字节
boolean flag = (i == huffmanBytes.length - 1);
stringBuilder.append(byteToBitString(!flag, b));
}
System.out.println(stringBuilder.toString());
//把字符串按照指定的赫夫曼编码进行解码
//把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
Map<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
//创建一个集合，存放byte
List<Byte> list = new ArrayList<>();
//i 可以理解为索引,扫描 stringBuilder
for (int i = 0; i < stringBuilder.length(); ) {
int count = 1; //小的计数器
boolean flag = true;
Byte b = null;
while (flag) {
//1010100010111111110010001 ...
//递增取出一个 '1'或'0'
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中就存放了所有的字符
//把list中的数据放到byte[] 并返回
byte[] b = new byte[list.size()];
for (int i = 0; i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
//使用一个方法将前面的方法封装起来，便于调用
/**
* @param bytes 原始的字符串对应的字节数组
* @return 是经过 赫夫曼编码处理后的字节数组（压缩后的数组）
*/
private static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
//根据 nodes 创建赫夫曼树
Node huffmanTreeRoot = createHuffmanTree(nodes);
//根据赫夫曼树创建对应的 赫夫曼编码
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
//根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
return huffmanCodeBytes;
}
//编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
/**
* 例如：String content="i like like like java do you like a java"; =》 byte[] contentBytes=();
* 返回的是字符串 "1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110"
* => 对应的byte[] huffmanCodeBytes,即8位对应一个byte，放入到huffmanCodeBytes
* huffmanCodeBytes[0] = 10101001(补码) => byte [推导 10101001 =》 10101001 -1 =》10101000(反码) =》(符号位不变，其他为取反)11010111 = - 88] 第一位为符号位：0为正，1为负
* huffmanCodeBytes[1] =-88
*
* @param bytes 这是原始的字符串对应的byte[]
* @param huffmanCodes huffmanCodes 生成的赫夫曼编码 map
* @return 返回赫夫曼编码处理后的byte[]
*/
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));
}
System.out.println("测试 stringBuilder=" + stringBuilder.toString());
// 将 "1010100110111101111010011011110 ... "转成 byte[]
//统计返回 byte[] huffmanCodes
//一句话 int len = (() + 7)/8;
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
byte[] huffmanCodeBytes = new byte[len];
int index = 0;//记录是第几个 byte
for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是霉每8位对应一个byte，所以步长+8
String strByte;
if (i + 8 > stringBuilder.length()) {
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i + 8);
}
//将 strByte 转成一个byte放入到HuffmanCodeBytes
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
//生成赫夫曼树对应的赫夫曼编码
//思路
//1.将赫夫曼编码表存放在 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}
static Map<Byte, String> huffmanCodes = new HashMap<>();
//2.在生成赫夫曼编码表时，需要拼接路径，定义一个StringBuild 存储某个叶子节点的路径
static StringBuilder stringBuilder = new StringBuilder();
//为了调用方便，重载getCodes
private static Map<Byte, String> getCodes(Node root) {
if (root == null) {
return null;
}
//处理root的左子树
getCodes(root.left, "0", stringBuilder);
//处理root的右子树
getCodes(root.right, "1", stringBuilder);
return huffmanCodes;
}
/**
* 功能：将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入到HuffmanCode集合
*
* @param node 传入节点
* @param code 路径：左子节点是 0，右子节点是 1
* @param stringBuilder 用于拼接路径
*/
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
//将code加入到stringBuilder2
stringBuilder2.append(code);
if (node != null) {
//如果node等于null，不处理
//判断当前node，是叶子节点还是非叶子节点
if (node.data == null) {
//递归处理
//向左递归
getCodes(node.left, "0", stringBuilder2);
//向右递归
getCodes(node.right, "1", stringBuilder2);
} else {
//说明是一个叶子结点
//就表示找到某个叶子结点的最后
huffmanCodes.put(node.data, stringBuilder2.toString());
}
}
}
//前序遍历的方法
private static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼树为空");
}
}
/**
* @param bytes 接收字节数组
* @return 返回的是List [Node{data=32, weight=9}, Node{data=97, weight=5}, ....]
*/
private static List<Node> getNodes(byte[] bytes) {
//1.创建一个ArrayList
ArrayList<Node> nodes = new ArrayList<>();
//2.遍历bytes,统计每一个bytes出现的次数 -> map[key,value]
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) {//此时，Map中还没有这个字符数据，第一次存放该数据
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
//把每个键值对转成一个Node 对象，并加入到nodes集合中
//遍历map
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
//通过List 创建赫夫曼树
private 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.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//将已经处理的两颗二叉树从nodes 中删除
nodes.remove(leftNode);
nodes.remove(rightNode);
//将新的节点，加入到nodes 中
nodes.add(parent);
}
//nodes 最后的节点解释赫夫曼树的根节点
return nodes.get(0);
}
}
//创建Node，带数据和权值
class Node implements Comparable<Node> {
Byte data; //存放数据，比如'a' => 97, ' '=> 32
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();
}
}
}