哈夫曼编码
本文最后更新于：2022年12月13日 晚上
哈夫曼编码
基本介绍
（1）哈夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，属于一种程序算法。
（2）哈夫曼编码是哈夫曼树在电讯通信中的经典的应用之一。
（3）哈夫曼编码广泛地用于数据文件压缩，其压缩率通常在20%~90%之间。
（4）哈夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码。
实现思路
（1）统计字符串各个字符出现的次数。
（2）按照上面字符出现的次数构建一棵哈夫曼树，次数作为权值。
（3）根据哈夫曼树，给各个字符规定编码（前缀编码），向左的路径为0，向右的路径为1。这样，每个字符都有独一无二的编码，而且出现次数越多的字符，编码越短。
特点总结
（1）此编码满足前缀编码，即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性。
（2）生成的哈夫曼树根据排序方法不同，也可能不太一样，这样对应的哈夫曼编码也不完全一样，但是wpl是一样的，都是最小的。
最佳实践
数据压缩及解压
（1）构建结点类
class Node implements Comparable<Node> {
Byte data; // 存放字符本身的 ASCII 码
int weight; // 存放权值（字符出现的次数）
Node left;
Node right;
public Node(Byte data， int weight) {
this.data = data;
this.weight = weight;
}
// 前序遍历
public void perOrder() {
System.out.println(this);
if (this.left != null) {
this.left.perOrder();
}
if (this.right != null) {
this.right.perOrder();
}
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
@Override
public String toString() {
return "Node{" + "data=" + this.data + "， weight=" + this.weight + "}";
}
}（2）构建HuffmanCode类，里面有个主方法
public class HuffmanCode {
public static void main(String[] args) {
//主方法
}
}（3）在主方法中将字符串转为byte数组
String content = "yorick yur bei yu Android java Hello World yorick你好";
byte[] contentBytes = content.getBytes();（4）将byte数组的每个元素转化为二叉树结点，可以统计字符串各个字符出现的次数，作为权重。
构建将byte数组的每个元素转化为二叉树结点的方法
private static List<Node> str2Node(byte[] bytes) { // 存储结点的数据和权值 Map<Byte， Integer> count = new HashMap<>(); for (Byte b : bytes) { // 当 key 存在时。value+1，key不存在时新建key，并另value=1 count.merge(b， 1， Integer::sum); } List<Node> nodes = new ArrayList<>(); for (Map.Entry<Byte， Integer> entry : count.entrySet()) { nodes.add(new Node(entry.getKey()， entry.getValue())); } return nodes; }主方法调用
List<Node> nodes = str2Node(contentBytes);（5）生成哈夫曼树
根据结点生成哈夫曼树的方法
private static Node buildHuffmanTree(List<Node> nodes) { while (nodes.size() > 1) { Collections.sort(nodes); Node left = nodes.get(0); Node right = nodes.get(1); nodes.remove(0); nodes.remove(0); Node pare = new Node(null， left.weight + right.weight); pare.left = left; pare.right = right; nodes.add(pare); } return nodes.get(0); }主方法调用
Node root = buildHuffmanTree(nodes);（6）根据哈夫曼树生成哈夫曼编码表
在主方法中声明两个静态属性
// 供递归入口使用，存储过程值 static StringBuilder stringBuilder = new StringBuilder(); // 存储递归结果 static Map<Byte， String> huffmanCode = new HashMap<>();通过递归获取哈夫曼树中非叶子结点对应的路径字符串
/** 递归获得哈夫曼编码 * @param node 结点 * @param str 三种情况：”“、”0“、”1“ * @param stringBuilder 可变字符串，记录路径 */ private static void getCodes(Node node， String str， StringBuilder stringBuilder) { if (node == null) return; StringBuilder sb = new StringBuilder(stringBuilder); sb.append(str); // 判断node是否为叶子结点 if (node.data == null) { // 向左递归 getCodes(node.left， "0"， sb); // 向右递归 getCodes(node.right， "1"， sb); } else { huffmanCode.put(node.data， String.valueOf(sb)); } }为了主方法调用方便，重载方法
private static Map<Byte， String> tree2code(Node root) { getCodes(root， ""， stringBuilder); return huffmanCode; }在主方法中调用
Map<Byte， String> huffmanCode = tree2code(root);
// 哈夫曼编码表：32->01 97->100 100->11000 117->11001 101->1110 118->11011 105->101 121->11010 106->0010 107->1111 108->000 111->0011 （7）根据编码表对字符进行压缩
- 压缩方法
private static byte[] zip(byte[] bytes， Map<Byte， String> huffmanCode) { StringBuilder codes = new StringBuilder(); for (Byte b : bytes) { codes.append(huffmanCode.get(b)); } int length; if (codes.length() % 8 == 0) { length = codes.length() / 8; } else { length = codes.length() / 8 + 1; } byte[] huffmanCodeBytes = new byte[length]; int index = 0; for (int i = 0; i < codes.length(); i += 8) { String huffmanCodeStr; if (i + 8 < codes.length()) { huffmanCodeStr = codes.substring(i， i + 8); } else { huffmanCodeStr = codes.substring(i); } huffmanCodeBytes[index] = (byte) Integer.parseInt(huffmanCodeStr， 2); index++; } return huffmanCodeBytes; } - 为了便于调用，将压缩方法封装
public static byte[] huffmanZip(byte[] contentBytes) {
// 将字符串的每个字符转化为二叉树结点
List<Node> nodes = str2Node(contentBytes);
// 生成哈夫曼树
Node root = buildHuffmanTree(nodes);
//perOder(buildHuffmanTree(nodes));
// 根据哈夫曼树生成哈夫曼编码表
Map<Byte， String> huffmanCode = tree2code(root);
System.out.print("哈夫曼编码表：");
for (Map.Entry<Byte， String> entry : huffmanCode.entrySet()) {
System.out.print(entry.getKey() + "->" + entry.getValue() + " ");
}
System.out.println();
return zip(contentBytes， huffmanCode);
}- 在主方法中调用
byte[] huffmanCodeBytes = huffmanZip(contentBytes);输出压缩后内容
System.out.println("压缩后内容：" + Arrays.toString(huffmanCodeBytes)); // 压缩后内容：[-88， -65， -56， -65， -56， -65， -55， 77， -57， 6， -24， -14， -117， -4， -60， -90， 28]（8）解压内容
将单个byte转二进制字符串
/** 单个byte转二进制字符串 * @param b 单个byte * @param flag 是否需要补高位 * @return 对应的二进制补码的字符串 */ private static String byte2BitString(byte b， boolean flag) { int temp = b; if (flag) { // 两个位都为0时，结果才为0 256 -> 10000000 temp |= 256; } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8); } else { return str; } }解压
public static byte[] decode(Map<Byte， String> huffmanCode， byte[] huffmanCodeBytes) {
StringBuilder bitString = new StringBuilder();
for (int i = 0; i < huffmanCodeBytes.length; i++) {
// 判断是否位最后一个字节
boolean flag = i == (huffmanCodeBytes.length - 1);
bitString.append(byte2BitString(huffmanCodeBytes[i]， !flag));
}
//System.out.println(bitString);
Map<String， Byte> map = new HashMap<>();
// 反转map
for (Map.Entry<Byte， String> entry : huffmanCode.entrySet()) {
map.put(entry.getValue()， entry.getKey());
}
List<Byte> list = new ArrayList<>();
for (int i = 0; i < bitString.length(); ) {
Byte b = null;
int count = 1;
boolean flag = true;
while (flag) {
b = map.get(bitString.substring(i， i + count));
if (b == null) {
count++;
} else {
flag = false;
}
}
list.add(b);
i += count;
}
byte[] bytes = new byte[list.size()];
for (int j = 0; j < list.size(); j++) {
bytes[j] = list.get(j);
}
return bytes;
}- 在主方法中调用
byte[] resBytes = decode(huffmanCode， huffmanCodeBytes); - 输出解压后内容
System.out.println("解压后内容：" + new String(resBytes));文件的压缩与解压
- 文件压缩方法
// 文件压缩 public static void zipFile(String src， String dst) throws IOException { // 输入 FileInputStream is = new FileInputStream(src); byte[] b = new byte[is.available()]; is.read(b); byte[] huffmanBytes = huffmanZip(b); // 输出 OutputStream os = new FileOutputStream(dst); ObjectOutputStream oos = new ObjectOutputStream(os); oos.writeObject(huffmanBytes); oos.writeObject(huffmanCodes); // 关闭IO is.close(); oos.close(); os.close(); } - 文件解压方法
// 文件解压
public static void unZipFile(String src， String dst) throws IOException， ClassNotFoundException {
// 输入
FileInputStream is = new FileInputStream(src);
ObjectInputStream ois = new ObjectInputStream(is);
byte[] huffmanBytes = (byte[]) ois.readObject();
Map<Byte， String> huffmanCodes = (Map<Byte， String>) ois.readObject();
byte[] bytes = decode(huffmanCodes， huffmanBytes);
// 输出
OutputStream os = new FileOutputStream(dst);
os.write(bytes);
os.close();
ois.close();
is.close();
}- 主方法要添加异常签名
public static void main(String[] args) throws IOException， ClassNotFoundException { zipFile("E://yy.bmp"， "E://yy.bmp.huf"); System.out.println("压缩完成"); unZipFile("E://yy.bmp.huf"，"E://yy_1.bmp"); System.out.println("解压完成"); }
哈夫曼编码压缩文件注意事项
（1）如果文件本身就是经过压缩处理的，那么使用哈夫曼编码再压缩效率不会有明显变化，比如视频，ppt等等文件
（2）哈夫曼编码是按字节来处理的，因此可以处理所有的文件（二进制文件、文本文件）
（3）如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显。