赫夫曼码是 可变字长编码(VLC) 的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码.
在练习中需要注意以下几点：
- 赫夫曼树 根据排序方法不同，也可能不太一样，这样对应的 赫夫曼编码 也不完全一样，但是
WPL是一样的，都是最小的，最后生成的赫夫曼编码的长度是一样。 - 在初学时，不要秀技，把几行代码放在一行写完。保持一个清晰简明的逻辑结构是最重要的。
相对于前面所学，难度上升地有些大，部分内容涉及到二进制和集合。需要花点时间再回顾一下代码。
package Tree.huffmenCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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数组的长度
byte[] huffmanCodeBytes = huffmanzip(contentBytes);
/*
* List<Node> nodes = getNodes(contentBytes); System.out.println("nodes = " +
* nodes);
*
* // 测试创建的二叉树 System.out.println("赫夫曼树"); Node huffmanTreeRoot =
* createHuffmanTree(nodes); System.out.println("前序遍历");
* preOrder(huffmanTreeRoot);
*
* // 测试是否生成了赫夫曼编码： Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
* System.out.println("生成的赫夫曼编码表" + huffmanCodes);
*
* // 测试 byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
*/
System.out.println(
"huffmanCodeBytes =" + Arrays.toString(huffmanCodeBytes) + "length " + huffmanCodeBytes.length);
byte[] sourceBytes = decode(huffmanCodes, huffmanCodeBytes);
System.out.println("原来的字符串："+ new String(sourceBytes));
}
// 使用一个方法，将前面的方法封装起来，便于调用
/**
*
* @param bytes 原始的字符串对应的字节数组，即contentBytes
* @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;
}
/*
* 完成数据的解压 思路： 1.将huffmanCodeByte[] 重新转成赫夫曼编码对应的二进制字符串
* 2.将赫夫曼对应的二进制字符串对照赫夫曼编码重新转写成原始文件
*/
/**
* 将一个byte转换成一个二进制字符串
*
* @param flag
* @param b 标识是否需要补高位，如果是true，表示需要补高位，如果是false，表示不补，如果是最后一个字节，无需补高位
* @return 是该byte 对应的二进制字符串，是按补码返回的
*/
private static String byteToBitString(boolean flag, byte b) {
// 使用变量保存b
int tmp = b; // 将 b转成int
// 如果是正数，我们还需要补高位
if (flag) {
tmp |= 256; // 按位或256 1000 0000 按位或 0000 0001 => 1000 0001
}
String str = Integer.toBinaryString(tmp); // 返回的是temp对应的二进制的补码
if (flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
/**
*
* @param huffmanCodes 赫夫曼编码表
* @param huffmanBytes 赫夫曼编码得到的字节数组
* @return 原来的字符串对应的数组
*/
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
// 1.先得到huffmanBytes 对应的二进制字符串，形式如：10101001
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));
}
// 把字符串按照指定的赫夫曼编码进行解码
// 把赫夫曼编码表进行调换以便于进行反向查询
Map<String, Byte> map = new HashMap<String, Byte>();
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) {
// 递增的取出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;
}
/**
* 将字符串对应的byte[]数组，通过生成的赫夫曼编码表， 返回一个赫夫曼编码压缩后的byte[]
*
* @param bytes 原始的字符串对应的byte[]
* @param huffmanCodes huffmanCodes 生成的赫夫曼编码Map
* @return 返回赫夫曼编码后的byte[]
*
* 举例：传入 contentBytes 返回的是 "10101000101111……"对应的byte[]，即
* 8位对应一个byte，放入byte[]
*
* 10101000（补码） -> 10100111（反码[符号位不变]） -> 11011000（原码[符号位不变]）
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
// 先利用huffmanCode 将bytes转成赫夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
// 遍历byte[]组
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
// 将赫夫曼编码后的数据转成byte[]
// 下列语句也可以一句话完成：int len = (stringBuilder.length()+7) /8)
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
// 创建一个存储压缩后的byte[]
byte[] huffmanCodeBytes = new byte[len];
// 步长为8，每8位对应一个byte,所以步长+8
int index = 0;// 记录第几个byte
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);
}
// 将strByte转成一个byte，放入到by;
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
/*
* 生成赫夫曼树对应的赫夫曼编码表 思路：
*
* 1.将赫夫曼编码表存放在Map<Byte,String> 形式如：“ ”->01 97-> 100 100-> 11000 不一定完全如上
*/
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) {
// 将code加入到stringBuilder2
StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
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());
}
}
}
/**
* 先序遍历二叉树
*
* @param root 根节点
*/
private static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("赫夫曼树为空");
}
}
/**
* 接收一个字节数组，并返回List
*
* @param bytes 接收字节数组
* @return 返回的是List形式 [Node[data =97,weight =5],Node[data = 32,weight = 9],……]
*/
private static List<Node> getNodes(byte[] bytes) {
// 创建一个ArrayList
ArrayList<Node> nodes = new ArrayList<Node>();
// 遍历bytes,统计每一个byte 出现的次数
Map<Byte, Integer> counts = new HashMap<Byte, Integer>();
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;
}
/**
* 创建一个赫夫曼树
*
* @param nodes
* @return 返回赫夫曼树的根节点
*/
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();
}
}
}
