16、数据结构与算法 - 实战：哈夫曼树和哈夫曼编码
1、先掌握几个概念
先听一遍哈夫曼树的概念：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也成为哈夫曼树（Huffman Tree）。好的，知道你懵逼了，下面还是先学习几个概念。
1.1 什么是路径？
在一棵树中，从一个结点到另一个结点所经过的所有结点，成为两个结点之间的路径。
比如上图这颗二叉树，从根结点A到结点H的路径，就是A、B、D、H。
1.2 什么是路径长度？
在一棵树中，从一个结点到另一个结点所经过的“边”的数量，成为两个结点之间的路径长度。
比如从根结点A到叶子结点H，共经历了3个边，因此路径长度为3。
1.3 什么是结点的带权路径长度？
树的每一个结点，都可以拥有自己的权重（Weight），权重在不同算法中起到不同的作用。结点的带权路径长度指的是该结点的路径和权重的乘积。
比如，结点G的带权路径长度为：2×8=16。
1.4 什么是树的带权路径长度？
在一棵树中，所有叶子结点（强调：是叶子节点）的带权路径长度之和，称为树的带权路径长度，英文缩写为WPL。
比如上面这棵树的带权路径长度WPL=3×3+3×6+2×1+2×4+2×8=53。
2、哈夫曼树
2.1 概念
现在再听一遍哈夫曼树的概念：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，称这样的二叉树为最优二叉树，也成为哈夫曼树（Huffman Tree）。这下懵逼程度已经减少了50%。下面用通俗的话来解释什么是哈夫曼树：
假设存在6个结点，这6个结点的权重从小到大排列分别为{1，3，4，6，8}。以这6个结点作为叶子结点的二叉树有无数个，比如下面随便凑两个：
树A和树B的叶子结点都是这6个结点的组合。那这跟哈夫曼树有什么关系呢？别急，我们先计算一下树A和树B的带权路径长度，计算可得树A的WPL为46，树B的WPL为53。数学验证这6个数字组成的二叉树最小WPL就是46，因此，树A就是哈夫曼树。
现在我们再来听一遍哈夫曼树的概念：给定n个权值作为n个叶子结点（例子里面的6个数字作为6个叶子结点），构造一棵二叉树，若该树的带权路径长度（WPL）达到最小（例子里的树A），称这样的二叉树为最优二叉树，也成为哈夫曼树（Huffman Tree）。这下懵逼程度已经减少到0了。
强调：一组结点构成的哈夫曼树可不止一棵，比如例子里的这6个结点，我改成一下三种树：
这三棵树都是这6个结点对应的哈夫曼树，因为WPL值相同且都是最小，但明显不是同一棵树。
2.2 图解构造哈夫曼树
构造哈夫曼树的过程很简单，小学生都看得懂。
比如有一个结点数组arr = {2，7，18，3，9，25}，把每一个数字看成结点的权重。
第一步，根据权重大小从小到大排序{2，3，7，9，18，25}
第二步：，构建森林，把每一个叶子结点都当成一棵只有根结点的树，于是形成一个森林：
上图左边是辅助队列，按照权重大小存储，右边是叶子节点的森林。
第三步：借助辅助队列，找出最小权重的两个结点，明显就是辅助队列的前面两个，生成父结点，父节点的权重是这两个结点权重之和：
第四步：删除上一步选择的两个最小结点，把新的父结点加入到辅助队列中，并对辅助排列再次进行排列，以保证辅助队列是从小到大的：
循环操作第三步、第四步，直到辅助队列只剩下一个结点。
此时，辅助队列只有一个结点，说明整个森林已经合并成一棵树，而这棵树就是这以{2，7，18，3，9，25}为权重的6个结点所对应的哈夫曼树。对于这些中间生成的结点，是没有什么作用的，我们做这么多计算，只是为了获得路径：
反思：其实整个过程是计算{2，7，18，3，9，25}的最小WPL，本质就是计算每个数字的乘积因子。
2.3 代码实现
结点类：
package cn.klb.datastructures.tree;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 二叉树结点类
* @Date: Create in 2023/4/10 16:06
* @Modified By:
*/
public class Node implements Comparable<Node> {
public int id;
public String data;
public Node left;
public Node right;
public Node(int id){
this.id = id;
}
public Node(int id, String data) {
this.id = id;
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"id=" + id +
", data='" + data + '\'' +
'}';
}
@Override
public int compareTo(Node o) {
return this.id - o.id;
}
}
哈夫曼树类：
package cn.klb.datastructures.tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 哈夫曼树
* @Date: Create in 2023/4/15 15:36
* @Modified By:
*/
public class HuffmanTree {
private List<Node> nodes;
public HuffmanTree(List<Node> nodes){
this.nodes = nodes;
}
/**
* 生成哈夫曼树
*
*/
public void generate() {
// 当nodes剩下一个结点时，说明生成完毕
while (nodes.size() > 1) {
// 对结点列表进行升序排列
Collections.sort(nodes);
// 取出id最小的前两个结点（把结点看成没有子结点的二叉树）
Node left = nodes.get(0);
Node right = nodes.get(1);
// 把取出的两个结点生成新的二叉树
Node parent = new Node(left.id + right.id);
parent.left = left;
parent.right = right;
// 删除这处理完的这两个结点
nodes.remove(left);
nodes.remove(right);
// 把新的二叉树添加回去
nodes.add(parent);
}
}
3、哈夫曼编码
3.1 背景
上面讲了一堆概念来介绍哈夫曼树，那么，哈夫曼树有什么作用呢？一个牛逼的作用就是哈夫曼编码。
比如有一句字符串：“i like like like java do you like a java”，总共40个字符（包括空格），那么，转成ASCII编码就是：[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]，统计这个字节数组，其实总共有12种字节，用json来表示就是{32：9，97：5，100：1，101：4，117：1，118：2，105：5，121：1，106：2，107：4，108：4，111：2}。冒号前面表示某一种字节，冒号后面表示重复次数。如：32：9表示字节32出现了9次（ASCII的32表示空格，数一下字符串果然有9个空格）。
统计这个有什么用呢？仔细观察，如果我把32看成结点，把9看成这个结点的权。是不是就可以构造一个哈夫曼树了？然而这又有什么用呢？回顾刚才那句字符串，总共40个字节，如果传输的话，就传输40个字节。而计算机低层传输的就是0和1，那么总共传输40×8=320个二进制。
哈夫曼编码就是一种缩减每一个字符所占用的二进制位数，把重复频率高的字符用最少的二进制位表示。听到这里，是不是跟哈夫曼树联系上了？哈夫曼编码就是一种无损压缩编码。
3.2 原理
就用字符串"i like like like java do you like a java"来举例，如果不压缩，总共320个二进制位。那如何进行压缩呢？
首先统计每个字符出现的频率{32：9，97：5，100：1，101：4，117：1，118：2，105：5，121：1，106：2，107：4，108：4，111：2}，这里总共12种字符，对应12种字节。我们把它看成12个结点，重复次数看成结点的权。然后对这12个结点构造出哈夫曼树，左路为0，右路为1，最后统计每一个叶子结点的路径，得到编码。
假设有一个哈夫曼树如下：
那么，A的编码为“1”，B的编码为“01”，C的编码为“00”。
根据这个原理，这12个结点生成的编码就为：{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
原来的字符串对应的二进制总共320位，经过哈夫曼编码后，变成1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100，共133个二进制位，压缩率为（320-133）/320=58%。
解码的时候只需要根据编码表进行解码，即可恢复原样，无损解压。
3.1 代码实现
3.1.1 构造结点类
package cn.klb.datastructures.huffman;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 二叉树结点类
* @Date: Create in 2023/4/10 16:06
* @Modified By:
*/
public class Node implements Comparable<Node> {
public int count;
public Byte data;
public Node left;
public Node right;
public Node(int count){
this.count = count;
}
public Node(Byte data,int count) {
this.count = count;
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"count=" + count +
", data='" + data + '\'' +
'}';
}
@Override
public int compareTo(Node o) {
return this.count - o.count;
}
}
3.1.2 实现哈夫曼编码/解码的类
package cn.klb.datastructures.huffman;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 实现哈夫曼编码
* @Date: Create in 2023/4/16 16:35
* @Modified By:
*/
import java.util.*;
public class Huffman {
// 哈夫曼编码表
// 在 generateCodingSchedule 方法中实例化
private Map<Byte, String> encodeSchedule = new HashMap<Byte, String>();
public Map<Byte, String> getEncodeSchedule() {
return encodeSchedule;
}
/**
* 对哈夫曼编码后的数组进行解码，返回解码后的字节数组
*
* @param target
* @return
*/
public byte[] unzip(byte[] target) {
StringBuilder targetStringBuilder = new StringBuilder();
// 遍历解压前的字节数组，把每个字节对应的二进制字符串拼接到 targetStringBuilder 中
for (int i = 0; i < target.length; i++) {
boolean isLast = (i == target.length - 1);// 是不是最后一个字节
// 如果是最后一个字节，那么就不需要把最后一个字节高位的0补充完整
targetStringBuilder.append(byteToBitString(!isLast, target[i]));
}
// 获取解码表
Map<String, Byte> decodeSchedule = getDecodeSchedule();
// 存放targetStringBuilder截取后的字节
List<Byte> bytesList = new ArrayList<Byte>();
int count; // 遍历targetStringBuilder的所有字符的计数器
Byte b = null; // 临时存放匹配到的字节
boolean notMached = true; // 是否从targetStringBuilder中扫描到了可以匹配的二进制字符串
// 遍历targetStringBuilder所有可能长度的子字符串
for (int i = 0; i < targetStringBuilder.length(); i += count) {
count = 1;
notMached = true;
b = null;
while (notMached) {
// key 会从1开始递增来扫描
String key = targetStringBuilder.substring(i, i + count);
b = decodeSchedule.get(key); // 看这个 key 可不可以解码
if (b == null) {
// 解码表没有对应可解码
count++; // 加长截取长度，然后再看一次能不能解码
} else {
notMached = false; // 匹配到了，可以解码了
}
}
bytesList.add(b);
}
// 把list转成byte
byte[] source = new byte[bytesList.size()];
for (int i = 0; i < source.length; i++) {
source[i] = bytesList.get(i);
}
return source;
}
/**
* 获取解码表
*
* @return
*/
public Map<String, Byte> getDecodeSchedule() {
Map<String, Byte> decodeSchedule = new HashMap<String, Byte>();
for (Map.Entry<Byte, String> entry : encodeSchedule.entrySet()) {
decodeSchedule.put(entry.getValue(), entry.getKey());
}
return decodeSchedule;
}
/**
* 对传进来的源字节数组进行哈夫曼编码，返回编码后的字节数组
*
* @param source
* @return
*/
public byte[] zip(byte[] source) {
// 1.根据源字节数组生成 nodes
List<Node> nodes = createNodes(source);
// 2.nodes生成哈夫曼树
generate(nodes);
// 3.生成哈夫曼树对应的编码表
generateEncodeSchedule(nodes);
// 4.对源字节数组进行编码
byte[] target = encoding(source, encodeSchedule);
return target;
}
/**
* 根据字节数组生成结点序列 nodes，其中 其中每一个node的data表示字节，count表示字节重复的次数
* 比如字符串为：“I love my country”
* 则，其中一个 node为：Node{count=2,data=121} 121的 ascii 对应 y
*
* @param bytes
* @return nodes
*/
private List<Node> createNodes(byte[] bytes) {
List<Node> nodes = new ArrayList<Node>();
// 用于临时统计
// Byte表示字节
// Integer 表示这个字节重复的次数
Map<Byte, Integer> map = new HashMap<Byte, Integer>();
// 遍历字节数组
for (byte b : bytes) {
Integer count = map.get(b); // 获取字节b对应的重复次数
if (count == null) {
// 如果字节b第一次出现，则现在新加入字节b
map.put(b, 1);
} else {
// 字节 b不是第一次出现，说明又重复了一次
map.put(b, count + 1);
}
}
// 根据统计好的 map 生成 nodes
for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
/**
* 调整nodes为哈夫曼树
*
* @param nodes
* @return
*/
private void generate(List<Node> nodes) {
// 当nodes剩下一个结点时，说明生成完毕
while (nodes.size() > 1) {
// 先对结点列表进行升序排列
Collections.sort(nodes);
// 取出id最小的前两个结点（把结点看成没有子结点的二叉树）
Node left = nodes.get(0);
Node right = nodes.get(1);
// 把取出的两个结点生成新的二叉树
Node parent = new Node(left.count + right.count);
parent.left = left;
parent.right = right;
// 删除这处理完的这两个结点
nodes.remove(left);
nodes.remove(right);
// 把新的二叉树添加回去
nodes.add(parent);
}
}
/**
* 获取哈夫曼树对应的编码表
*/
private void generateEncodeSchedule(List<Node> nodes) {
if (nodes.size() == 1) {
// size == 1 才有可能是哈夫曼树
if (encodeSchedule.size() == 0) {
// 如果编码表键值对数量为0，说明没有编码过，执行编码
// 临时存放叶子节点的路径
StringBuilder accumulativeTag = new StringBuilder();
// 处理根结点的左子树
coding(nodes.get(0).left, '0', accumulativeTag, encodeSchedule);
// 处理根结点的右子树
coding(nodes.get(0).right, '1', accumulativeTag, encodeSchedule);
}
}
}
/**
* 生成编码表
*
* @param node 准备处理的结点
* @param tag 如果这个结点是其父节点的左结点，则为0，反之为1
* @param accumulativeTag 走到这个结点所经历 tag 的累积拼接
*/
private void coding(Node node, char tag, StringBuilder accumulativeTag, Map<Byte, String> codingSchedule) {
StringBuilder path = new StringBuilder(accumulativeTag);
path.append(tag);
if (node != null) {
// node不为空才处理
if (node.data == null) {
// data == null 说明该结点不是叶子结点
// 向左递归
coding(node.left, '0', path, codingSchedule);
// 向右递归
coding(node.right, '1', path, codingSchedule);
} else {
// data != null，说明这个node是叶子结点，可以收尾了
codingSchedule.put(node.data, path.toString());
}
}
}
/**
* 根据编码表对字节数组进行编码，返回编码后的字节数组
*
* @param source
* @param codingSchedule
* @return
*/
private byte[] encoding(byte[] source, Map<Byte, String> codingSchedule) {
StringBuilder targetStringBuilder = new StringBuilder();
// 对待编码字节数组进行编码，编码后的二进制拼接成字符串
for (byte b : source) {
targetStringBuilder.append(codingSchedule.get(b)); // 对编码后的0101这些二进制转成字符串形式，方便后面截取
}
// 后面要把targetStringBuilder对应的字符串形式进行截取，每8个二进制装进一个byte中
// 如果targetStringBuilder长度为12，那么len就为 （12+7）/8=2
int len = (targetStringBuilder.length() + 7) / 8;
byte[] targetBytes = new byte[len];
int index = 0;
// 把拼接好的字符串以8位为单位进行截取，把截取到的8位看成是一个字节
String targetString;
for (int i = 0; i < targetStringBuilder.length(); i += 8) {
if (targetStringBuilder.length() < i + 8) {
// 不够8位
targetString = targetStringBuilder.substring(i); // 截取剩余的所有
} else {
targetString = targetStringBuilder.substring(i, i + 8); // 截取8个
}
// 把strByte转成一个byte，放到encodedBytes中
// 如果targetStringBuilder不是8的倍数，最后剩下如 0101四位，调用parseInt会把它当成 0000 0101
// parseInt("1100110", 2) returns 102，而102的补码为 01100110，前面多了一个0，所以最后一个字节在解码的时候要特别小心
targetBytes[index++] = (byte) Integer.parseInt(targetString, 2);
}
return targetBytes;
}
/**
* 0xff默认为整形，二进制位最低8位是1111 1111，前面24位都是0；所以和0xff进行&运算后会变为int
* toBinaryString方法有个毛病，就是二进制如果最高位为0，转为字符串时会被省略
* 比如：00000000 00000000 00000000 10011101，调用toBinaryString方法后获得的字符串为 10011101
* <p>
* 如果 b = -88，根据计算机组成原理，-88 的原码为 1101 1000，反码为 1010 0111，补码为 1010 1000
* 计算机保存数字保存的都是补码，所以 -88 计算机保存的其实是它的补码，为 1010 1000
* 如果要杠，说你看到的就是原码，那你看到的其实是正数的补码，正数的原码反码和补码都是一样的
* <p>
* b & 0xFF 使得字节类型转为int类型，加 0x100 是为了兼容正数（负数加了也没影响，因为会截取掉）
* 比如：b = 88，那么补码就是 0101 1000（正数的原码、反码、补码都一样）
* 执行 b & 0xFF 后变成了 00000000 00000000 00000000 01011000
* 上面说了 toBinaryString 会把前面的0全给省略了，所以执行 toBinaryString(b & 0xFF)会得到字符串 “1011000”
* 但我们要的是 01011000，所以 b & 0xFF 加上 0x100后，会变成 00000000 00000000 00000001 01011000
* 执行toBinaryString方法后就得到 “101011000”，然后再截取第一位后面的所有，得到 “01011000”
*
* @param flag 是否要一个完整的 8位二进制字节
* @param b
* @return
*/
private String byteToBitString(boolean flag, byte b) {
if (flag) {
return Integer.toBinaryString((b & 0xFF) + 0x100).substring(1);
} else {
return Integer.toBinaryString((b & 0xFF));
}
}
}
3.1.3 测试类
@Test
public void testEncode() {
String content = "i like like like java do you like a java";
byte[] source = content.getBytes();
Huffman huffman = new Huffman();
byte[] target = huffman.zip(source);
System.out.println("编码前：" + Arrays.toString(source));
System.out.println("编码后：" + Arrays.toString(target));
System.out.println("编码表:"+huffman.getEncodeSchedule());
System.out.println("解码表:"+huffman.getDecodeSchedule());
byte[] source1 = huffman.unzip(target);
System.out.println("解码后："+Arrays.toString(source1));
}
注意：代码中private byte[] encoding(byte[] source, Map<Byte, String> codingSchedule)方法存在一个bug，当最后剩下的二进制位的从左到右第一个是0时，就会出问题。因时间关系，加上和哈夫曼编码知识点无关，有空再回来处理。