13.6 赫夫曼编码解码
思路：
- 将
huffmanCodeBytes[] - 重新转成 赫夫曼编码对应的二进制对应的字符串‘1010100010111...’
- 将赫夫曼编码对应的二进制字符串‘1010100010111...’ 对照 赫夫曼编码 重新生成
i like like like java dot you like a java
package huffmancode;
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 = content.getBytes();
System.out.println(contentBytes.length);
byte[] huffmanCodeBytes = huffmanZip(contentBytes);
System.out.println("压缩后的编码为"+Arrays.toString(huffmanCodeBytes));
System.out.println("长度为："+huffmanCodeBytes.length);
byte[] sourceBytes = decode(huffmanCodes, huffmanCodeBytes);
System.out.println(new String(sourceBytes));
// 分布过程
/*
List<Node> nodes = getNode(contentBytes);
System.out.println(nodes);
Node huffmanTreeRoot = createHuffmanTree(nodes);
System.out.println("前序遍历");
huffmanTreeRoot.preOrder();
// 测试是否生成了对应的赫夫曼编码
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
System.out.println("~生成的赫夫曼编码表："+ huffmanCodes);
// 测试
huffmanCodeBytes = zip(contentBytes, huffmanCodes);
System.out.println("huffmanCodeBytes="+Arrays.toString(huffmanCodeBytes));
// 发送 HuffmanCodeBytes 数组
*/
}
// 完成数据的解压
//1. 将 `huffmanCodeBytes[] `
//2. 重新转成 赫夫曼编码对应的二进制对应的字符串‘1010100010111...’
//3. 将赫夫曼编码对应的二进制字符串‘1010100010111...’ 对照 赫夫曼编码 重新生成`i like like like java dot you like a java`
/**
* 将一个byte 转成一个二进制的字符串
* @param b 传入的 byte
* @param flag 标识是否需要补高位，如果为true，表示需要补高位，如果是flase 表示不需要补,如果是最后一个字节，我们不需要补高位
* @return 是该byte 对应的二进制的字符串，（注意是按照补码返回）
*/
private static String byteToBytes(boolean flag, byte b){
// 使用一个变量保存b
int temp = b; // 将 b 转成 int
// 如果是个正数我们还存在补高位
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;
}
}
// 编写一个方法，完成对压缩数据的解码
/**
*
* @param huffmanCodes 赫夫曼编码 map
* @param huffmanBytes 赫夫曼编码得到的字节数组 就是那个[-88,-65,-56,....]
* @return 原来的字符串对应的数组
*/
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
// 1. 得到huffmanBytes 对应的二进制的字符串 ‘1010100010111...’
StringBuilder stringBuilder = new StringBuilder();
// 将 byte[] 数组转成二进制的字符串
for (int i = 0; i < huffmanBytes.length; i++){
// 判断是不是最后一个字节
boolean flag = (i == huffmanBytes.length - 1);
byte b = huffmanBytes[i];
stringBuilder.append(byteToBytes(!flag, b));
}
// 把字符串按照指定的赫夫曼编码进行解码
// 把赫夫曼编码表进行一个调换，因为要反向查询, 从 100->a 到 a->100
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<>();
for (int i = 0; i < stringBuilder.length();){
// i 可以理解成一个索引，扫描stringBuilder
int count = 1; // 小的计数器
boolean flag = true;
Byte b = null;
while (flag){
// 递增的取出 key
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 = getNode(bytes);
// 根据 nodes 创建赫夫曼树
Node huffmanTreeRoot = createHuffmanTree(nodes);
// 根据赫夫曼树创建赫夫曼编码
Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
// 根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
byte[] huffmanCodeBytes = zip(bytes,huffmanCodes);
return huffmanCodeBytes;
}
// 编写一个方法，将一个字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码，压缩后的byte[]数组
/**
*
* @param bytes 这是原始的字符串对应的 byte[]
* @param 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.toString());
// 将 "101010001011111110..."转成 byte[]
// 统计返回的 byte[] huffmanCodeBytes 长度
int len;
// 下面代码一句话搞定就是 len = (stringBuilder.length() + 7) / 8
if (stringBuilder.length() % 8 == 0){
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
// 创建一个存储压缩后的 byte数组
byte[] huffmanCodeBytes = new byte[len];
int index = 0; // 记录是第几个byte
for (int i = 0; i < stringBuilder.length(); i += 8){
// 因为是每8为对应一个byte
String strByte;
if (i + 8 > stringBuilder.length()){
// 不够8位了，那么有多少取多少
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i + 8);
}
// 将strByte转成一个 byte 放入到 huffmanCodeBytes
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte,2);
index++;
}
return huffmanCodeBytes;
}
/**
*
* @param bytes 接受字节数组
* @return 返回是一个list形式
*/
private static List<Node> getNode(byte[] bytes){
// 创建一个ArrayList
ArrayList<Node> nodes = new ArrayList<>();
// 存储每个byte出现的次数 -> map
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对象并加入弄得集合
// 遍历map
for (Map.Entry<Byte,Integer> entry:counts.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 leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
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);
}
//前序遍历
private static void preOrder(Node root){
if (root != null){
root.preOrder();
}else{
System.out.println("赫夫曼树为空");
}
}
// 生成赫夫曼树对应的赫夫曼编码
//思路：
// 1. 将赫夫曼编码表存放在 Map<Byte,String>
static Map<Byte,String> huffmanCodes = new HashMap<Byte, String>();
// 2. 在生成赫夫曼编码表时，需要去拼接路径，定义一个 StringBuilder 存储某个叶子节点的路径
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结点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCodes
* @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());
}
}
}
}
// 创建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();
}
}
}