一、浅谈赫夫曼编码

赫夫曼编码(Huffman Coding)，又称霍夫曼编码(哈夫曼编码），是一种编码方式，赫夫曼编码是可变字长编码(VLC)的一种。
赫夫曼编码满足前缀编码，即某个字符的编码都不能是其他字符编码的前缀编码，因此不会造成匹配的多义性。

二、获取赫夫曼编码

赫夫曼编码一般用于通信领域中当作信息的一种处理方式，处理的规则如下
我们将不同的字符当成不同的节点，每个字符出现的次数作为该节点的权值，将所有节点构造成一个赫夫曼树我的上一篇博客有提到赫夫曼树的创建（还请各位大佬斧正）link
形成赫夫曼树后，我们将二叉树的左路指定为0，右路指定为1，沿赫夫曼树根节点到每个节点的路径保存相应的编码。

下面我们以字符串“hungryandhumble”为例

1.获取字符出现的次数

通过分析各个字符出现的次数统计如下表1

表1 各个字符出现的次数
在这里插入图片描述

2.创建赫夫曼树

注意： 赫夫曼树根据排列的方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是赫夫曼树的带权路径长度WPL都是一样的，均为最小值。

例如在上面的例子中，有多个字符出现的次数一样，当我们在森林中取出两棵树形成新树的过程中，由于有多个字符权值相同，比如我们既可能取出字符r和字符y，也有可能取出字符a和字符b。同时，我们每次在森林中取出的两棵树摆放的位置也会影响赫夫曼树的生成，比如我们既可以将取出的字符r放在左边，将字符y放在右边，也可以反过来。

赫夫曼树（哈夫曼树）的创建（java实现）
视频演示赫夫曼树的生成过程

按照上述规则，创建的赫夫曼树如下

在这里插入图片描述

3.指定编码

我们将二叉树的左路指定为0，右路指定为1
效果图如下
在这里插入图片描述
沿赫夫曼树根节点到每个节点的路径保存相应的编码。
效果图如下

三、代码实现

1.指定编码代码

//获取赫夫曼编码 向左边路径为0  右边为1//思路//1.每个节点的赫夫曼编码保存到huffmanCodes中//2.生成赫夫曼编码的时候用到StringBuilder拼接路径static Map<Byte, String> huffmanCodes = new HashMap<>();static StringBuilder stringBuilder = new StringBuilder();/*** @param node 节点* @param code 代码编码的值 0 / 1* @param stringBuilder 用于拼接编码*/public static void getCodes(Node02 node, String code, StringBuilder stringBuilder) {StringBuilder temp = new StringBuilder(stringBuilder); //保存上次拼接的值temp.append(code); //拼接if (node != null) {if (node.getData() == null) { //node为非叶子节点getCodes(node.getLeft(), "0", temp); //向左递归遍历getCodes(node.getRight(), "1", temp); //向右递归遍历} else { //说明bide是叶子节点huffmanCodes.put(node.getData(), temp.toString()); //将相应的赫夫曼编码保存到Map中}}}

2.完整代码

package com.xx.huffmantree;import java.util.*;/*** @author 谢鑫* @version 1.0* @date 2021/12/10 10:41*/
public class HuffmanCode {public static void main(String[] args) {String str = "hungryandhumble";List<Node02> nodes = getNodes(str);System.out.println(nodes);Node02 root = createHuffmanTree(nodes);preOrder(root);//测试生成的赫夫曼编码getCodes(root, "", stringBuilder);System.out.println(huffmanCodes);}public static List<Node02> getNodes(String aString) {List<Node02> nodes = new ArrayList<>(); //用于存放节点byte[] contents = aString.getBytes();Map<Byte, Integer> map = new HashMap<>(); //Byte对象存放字符 Iterator对象存放字符出现的次数（权值）Integer count = null; //记录每个字符的权值for (byte element : contents) {count = map.get(element);if (count == null) { //如果map中不包含此元素map.put(element, 1); //则添加进map 并将权值设为1} else { //否则权值加1map.put(element, ++count);}}//将map中的数据新建节点添加到list中返回Set keySet = map.keySet(); //获取map的全部key值for (Object key_ : keySet) {Byte key = (Byte) key_;nodes.add(new Node02(key, map.get(key)));}return nodes;}//创建哈夫曼树public static Node02 createHuffmanTree(List<Node02> nodes) {while (nodes.size() > 1) {Collections.sort(nodes); //每次取节点前进行从小打到排序Node02 left = nodes.remove(0); //访问并移除第一元素Node02 right = nodes.remove(0); //访问并移除新的第一个元素Node02 parent = new Node02(null, left.getWeight() + right.getWeight());//创建小树parent.setLeft(left);parent.setRight(right);//将parent放入到nodes中nodes.add(parent);}return nodes.get(0); //最后nodes中的节点即为创建好的哈夫曼树}//获取赫夫曼编码 向左边路径为0  右边为1//思路//1.每个节点的赫夫曼编码保存到huffmanCodes中//2.生成赫夫曼编码的时候用到StringBuilder拼接路径static Map<Byte, String> huffmanCodes = new HashMap<>();static StringBuilder stringBuilder = new StringBuilder();/*** @param node 节点* @param code 代码编码的值 0 / 1* @param stringBuilder 用于拼接编码*/public static void getCodes(Node02 node, String code, StringBuilder stringBuilder) {StringBuilder temp = new StringBuilder(stringBuilder); //保存上次拼接的值temp.append(code); //拼接if (node != null) {if (node.getData() == null) { //node为非叶子节点getCodes(node.getLeft(), "0", temp); //向左递归遍历getCodes(node.getRight(), "1", temp); //向右递归遍历} else { //说明bide是叶子节点huffmanCodes.put(node.getData(), temp.toString()); //将相应的赫夫曼编码保存到Map中}}}//前序遍历public static void preOrder(Node02 root) {if (root != null) {root.preOrder();} else {System.out.println("树空，无法完成前序遍历！");}}}class Node02 implements Comparable<Node02> {private Byte data; //存放字符本身private int weight; //存放权值Node02 left;Node02 right;public Node02(Byte data, int weight) {this.data = data;this.weight = weight;}public Byte getData() {return data;}public void setData(Byte data) {this.data = data;}public int getWeight() {return weight;}public void setWeight(int weight) {this.weight = weight;}public Node02 getLeft() {return left;}public void setLeft(Node02 left) {this.left = left;}public Node02 getRight() {return right;}public void setRight(Node02 right) {this.right = right;}//前序遍历public void preOrder() {System.out.println(this);if (this.getLeft() != null) {this.getLeft().preOrder();}if (this.getRight() != null) {this.getRight().preOrder();}}@Overridepublic String toString() {return "Node02{" +"data=" + data +", weight=" + weight +'}';}@Overridepublic int compareTo(Node02 o) { //从小到大排序return this.getWeight() - o.getWeight();}
}

输出结果为
在这里插入图片描述

总结

hungryandhumble相应字符对应的十进制与二进制如下表

在这里插入图片描述
若按二进制压缩 hungryandhumble的压缩代码为
011010000111010101101110011001110111001001111001011000010110111001100100011010000111010101101101011000100110110001100101 （长度为 120）