赫夫曼编码
1. 基本介绍
- 赫夫曼编码也即哈夫曼编码（Huffman Coding），是一种编码方式，属于一种程序算法；
- 赫夫曼编码是赫夫曼树在电讯通信中的经典应用之一；
- 赫夫曼编码广泛地应用于数据文件压缩，其压缩率通常在20%~90%之间。重复次数越多，压缩率越高。
- 赫夫曼编码是可变字长编码（VLC）的一种。
2. 通信领域中信息的处理方式
-
定长编码
- i like like like java do you like a java// 共40个字符(包括空格)
- 105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码
- 01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制
- 按照二进制来传递信息，总的长度是359
-
变长编码
- i like like like java do you like a java// 共40个字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 //其中各个字符（包括空格）对应的重复次数
- 0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d //说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如空格出现了9次， 编码为0，其它依次类推
- 按照上面给各个字符规定的编码规则，则在传输 "i like like like java do you like a java" 数据时，特殊编码就是：
- 上图中不同颜色分别代表不同的字符，但可以看出上述的编码方式可能会匹配到重复的编码，也即可能导致编码的二义性。通常情况下，要求字符的编码都不能是其他任意字符编码的前缀（符合此要求的编码称为前缀编码）。因此引入了哈夫曼编码，哈夫曼编码是一种前缀编码，不会产生二义性。
-
赫夫曼编码
- i like like like java do you like a java// 共40个字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 //其中各个字符（包括空格）对应的重复次数
- 按照上面的字符出现的次数，构建一棵Huffman Tree，将次数作为节点的权值（即arr = {1,1,1,2,2,2,4,4,4,5,5,9}）
- 根据赫夫曼树给各个字符规定编码（前缀编码）。向左的路径为0，向右的路径为1，则编码如下：
- o: 1000，u: 10010，d: 100110，y: 100111，i: 101，a : 110，k: 1110，e: 1111，j: 0000，v: 0001，l: 001， : 01（空格）
- 按照上面的赫夫曼编码，"i like like like java do you like a java" 字符串对应的编码为：
- 1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
- 长度为133，原来的长度为359，压缩了 (359-133) / 359 = 62.9%
- 注意：
- 此编码满足前缀编码，不会导致编码的二义性；
- 除此之外，赫夫曼编码是一种无损压缩编码；
- 根据排序方式的不同，构造的赫夫曼树也可能不太一样（ie.List中新加入的具有相同权值的节点排序后所放置的位置不同），这就导致对应的赫夫曼编码也不完全一样。但是WPL一定是一样的且是最小的，因此最后生成整体字符串对应的赫夫曼编码的长度是一样的。
3. 代码实现：赫夫曼编码实现数据压缩与解压缩
package com.algorithm;
import java.util.*;
/**
* @author SnkrGao
* @create 2023-05-16 11:16
*/
public class HuffmanCode {
public static void main(String[] args) {
String content = "I like java, do you like java ? We can study it together and make progress.";
// 字符串content对应的byte[]数组
byte[] contentBytes = content.getBytes();
System.out.println("压缩前长度为：" + contentBytes.length); // 75
List<HuffmanCodeNode> nodes = getNodes(contentBytes);
System.out.println(nodes);
HuffmanCodeNode root = createHuffmanTree(nodes);
// 生成对应的哈夫曼编码表
Map<Byte, String> huffmanCodes = getCodes(root);
System.out.println("生成的哈夫曼编码表：" + huffmanCodes);
// 获取哈夫曼编码压缩的byte[]数组
byte[] huffmanCodeBytes = huffmanZip(contentBytes, huffmanCodes);
System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));
System.out.println("压缩后长度位：" + huffmanCodeBytes.length); // 40
// 解压
byte[] decodeBytes = decode(huffmanCodes, huffmanCodeBytes);
// Arrays.toString仍是以数组的形式输出，只是将数组转换成String类型
// 要将这个byte[]数组以原String的形式输出，可以直接new一个String
System.out.println("解压后的content字符串为：" + new String(decodeBytes));
}
/**
* 将用于构建哈夫曼树的节点放入List中
* @param bytes 接收contentBytes数组
* @return 返回List
*/
public static List<HuffmanCodeNode> getNodes(byte[] bytes) {
List<HuffmanCodeNode> nodes = new ArrayList<>();
// 遍历bytes，统计每个字符出现的次数，存到map[key, value]中
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
if (!counts.containsKey(b)) {
counts.put(b, 1);
} else {
counts.put(b, counts.get(b) + 1);
}
}
// 遍历该map，将每一个键值对转化成Node(Byte value, int weight)，并放入List中
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new HuffmanCodeNode(entry.getKey(), entry.getValue()));
}
return nodes;
}
public static HuffmanCodeNode createHuffmanTree(List<HuffmanCodeNode> nodes) {
while (nodes.size() > 1) {
// 从小到大排序
Collections.sort(nodes);
HuffmanCodeNode leftNode = nodes.get(0);
HuffmanCodeNode rightNode = nodes.get(1);
// 创建新的二叉树，根节点只有weight，没有value
HuffmanCodeNode parent = new HuffmanCodeNode(null, leftNode.getWeight() + rightNode.getWeight());
// 构建二叉树节点之间的关系
parent.setLeft(leftNode);
parent.setRight(rightNode);
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
return nodes.get(0);
}
/**
* 根据构建的哈夫曼树生成对应的哈夫曼编码表
* 1. 将哈夫曼编码表存放在Map<Byte, String>中
* 2. 生成哈夫曼编码表示需要拼接路径，需要定义一个StringBuilder存储某个叶子节点的路径
*/
static Map<Byte, String> huffmanCodes = new HashMap<>();
/**
* 为了方便调用，重载getCodes方法
*/
public static Map<Byte, String> getCodes(HuffmanCodeNode root) {
StringBuilder stringBuilder = new StringBuilder();
if (root == null) {
return null;
}
getCodes(root.getLeft(), "0", stringBuilder);
getCodes(root.getRight(), "1", stringBuilder);
return huffmanCodes;
}
/**
* 得到传入的node节点到所有叶子节点的路径（哈夫曼编码），放入到huffmanCodes中
* @param node 传入的节点
* @param code 路径：左子节点为0，右子节点为1
* @param stringBuilder 用于拼接路径
*/
public static void getCodes(HuffmanCodeNode node, String code, StringBuilder stringBuilder) {
StringBuilder curStringBuilder = new StringBuilder(stringBuilder);
curStringBuilder.append(code);
if (node != null) { // node为空不处理
if (node.getValue() == null) { // 判断当前节点是否为叶子节点
getCodes(node.getLeft(), "0", curStringBuilder);
getCodes(node.getRight(), "1", curStringBuilder);
} else {
// 表示找到某个叶子节点，将哈夫曼编码（路径）放入map中
huffmanCodes.put(node.getValue(), curStringBuilder.toString());
}
}
}
/**
* 通过哈夫曼编码，将contentBytes数组压缩为相应的byte[]数组
* @param bytes 原始的contenBytes数组
* @param huffmanCodes 生成的哈夫曼编码表Map
* @return 返回哈夫曼编码处理压缩后的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]
*/
// 方便解码时，判断解码的正确性，即最后一项是否需要补零
static StringBuilder huffmanCodeStr = new StringBuilder();
public static byte[] huffmanZip(byte[] bytes, Map<Byte, String> huffmanCodes) {
// 利用huffmanCodes将contentBytes转为对应的字符串，StringBuilder用于拼接字符串
// 遍历contentBytes数组
for (byte b : bytes) {
huffmanCodeStr.append(huffmanCodes.get(b));
}
// 将字符串转成byte[]数组
int len;
// if (huffmanCodeStr.length() % 8 == 0) {
// len = huffmanCodeStr.length() / 8;
// } else {
// len = huffmanCodeStr.length() / 8 + 1;
// }
// 统计byte[]数组的长度
len = (huffmanCodeStr.length() + 7) / 8;
byte[] huffmanCodeBytes = new byte[len];
int index = 0; // 记录是第几个byte
for (int i = 0; i < huffmanCodeStr.length(); i += 8) { // 每8位一个byte
String str;
if (i + 8 > huffmanCodeStr.length()) {
// 如果不够8位
str = huffmanCodeStr.substring(i);
} else {
str = huffmanCodeStr.substring(i, i + 8);
}
// 将str转化为一个byte放入huffmanCodeBytes数组中
huffmanCodeBytes[index] = (byte) Integer.parseInt(str, 2);
index++;
}
return huffmanCodeBytes;
}
/**
* 将一个byte转化为二进制字符串（数据在计算机中以补码形式存储，带符号位）
* @param flag 用于标识传入的是否是byte[]数组的最后一项，最后一项单独进行处理不需要补高位“0”
* @param b 传入的byte
* @return 按补码形式返回的二进制字符串
*/
public static String byteToBitString(boolean flag, byte b) {
// Integer中有直接转化成二进制字符串的方法toBinaryString
int temp = b;
// 非最后一项的正数转化需要补0，因此需要与256进行按位或运算，补齐8位
// 而负数是不受影响的，直接拿后8位即可
if (flag) {
temp |= 256; // 按位或256 1 0000 0000 | 0000 0001 => 1 0000 0001
}
String str = Integer.toBinaryString(temp);
if (flag || temp < 0) {
// flag == true还没到最后一项，若是正数已经做了补0处理
// 若是负数，负数转化完是int类型32位的二进制补码--所以需要取出后8位
return str.substring(str.length() - 8);
} else {
// flag == false到最后一项，正数，不论是否为8位都直接返回
return str;
}
}
/**
* 完成数据的解压
* @param huffmanCodes 哈夫曼编码表
* @param huffmanCodeBytes 根据哈夫曼编码得到的字节数组
* @return 返回解压后的原字符串content对应的byte数组
*/
public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanCodeBytes) {
// 先得到huffmanCodeBytes对应的二进制字符串，形式如10101000101111
StringBuilder stringBuilder = new StringBuilder();
// 解压时先处理非最后一项，将最后一项单独拿出来进行判断和处理
boolean flag = true;
for (int i = 0; i < huffmanCodeBytes.length - 1; i++) {
stringBuilder.append(byteToBitString(flag, huffmanCodeBytes[i]));
}
/**
* 单独处理最后一个字节，这是因为最后一个字节转成二进制时，位数不确定可能导致解压后字符串错误
* eg. 最后一个byte存储1，原先经编码后可能为001，使用Integer中的toBinaryString解析该byte时
* 正数只会返回1，因此最后一位可能需要补“0”处理
* 但也可能最后一个byte存储的是27，即11011，以“1”开头并没有丢失“0”，这种情况不需要补位
* 方法：因此，将最后一位转成二进制字符串后，需要与原先编码获得的字符串比较长度，
* 若相等，则直接将最后一个二进制字符串拼接上去即可
* 若不相等，则现在前面已经拼接好的末端补0，并不断比较，直至长度一致，再拼接最后一项的二进制字符串
*/
byte lastByte = huffmanCodeBytes[huffmanCodeBytes.length - 1];
String lastByteStr = byteToBitString(!flag, lastByte);
if (stringBuilder.length() + lastByteStr.length() == huffmanCodeStr.length()) {
stringBuilder.append(lastByteStr);
} else {
while (stringBuilder.length() + lastByteStr.length() < huffmanCodeStr.length()) {
stringBuilder.append(0);
}
stringBuilder.append(lastByteStr);
}
// 把字符串按照指定的哈夫曼编码表进行解码，需要将哈夫曼编码表进行逆转
Map<String, Byte> decodesMap = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
decodesMap.put(entry.getValue(), entry.getKey());
}
// 创建一个集合List，扫描上面得到的二进制字符串，存放对应的byte
List<Byte> list = new ArrayList<>();
for (int i = 0; i < stringBuilder.length(); ) {
// 一个小的计数器，i仅用于移动，count用于扫描寻找
int count = 1;
// 遍历扫描的结束标志符
boolean flag2 = true;
String subStr = null;
while (flag2) {
// 截取子串，并在decodesMap中进行查找
subStr = stringBuilder.substring(i, i + count);
if (decodesMap.containsKey(subStr)) {
flag2 = false;
} else {
// 若不存在，则继续向后遍历
count++;
}
}
// 将找到的这个byte放入List中
list.add(decodesMap.get(subStr));
// 查找到一个后，后移到下一个i起始处.此处后移了i那么for中就不要再后移了
i += count;
}
// 扫描完全部字符串，将List中的数据转化成byte[]数组
byte[] decodeBytes = new byte[list.size()];
for (int i = 0; i < decodeBytes.length; i++) {
decodeBytes[i] = list.get(i);
}
return decodeBytes;
}
}
class HuffmanCodeNode implements Comparable<HuffmanCodeNode> {
private Byte value; // 存放数据（字符），eg.'a'=>97
private int weight; // 权值，表示字符出现的次数
private HuffmanCodeNode left;
private HuffmanCodeNode right;
public HuffmanCodeNode(Byte value, int weight) {
this.value = value;
this.weight = weight;
}
@Override
public int compareTo(HuffmanCodeNode o) {
// 按出现次数从小到大排序
return this.weight - o.weight;
}
@Override
public String toString() {
return "HuffmanCodeNode{" +
"value=" + value +
", weight=" + weight +
'}';
}
public Byte getValue() {
return value;
}
public void setValue(Byte value) {
this.value = value;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public HuffmanCodeNode getLeft() {
return left;
}
public void setLeft(HuffmanCodeNode left) {
this.left = left;
}
public HuffmanCodeNode getRight() {
return right;
}
public void setRight(HuffmanCodeNode right) {
this.right = right;
}
}
运行结果展示：
4. 赫夫曼编码压缩文件注意事项
- 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再进行压缩，效率不会有明显的变化。eg.视频、ppt等文件
- 赫夫曼编码是按字节来处理的，因此可以处理所有的文件（二进制文件、文本文件）
- 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显