简介
HuffmanTree：又称哈夫曼树、赫夫曼树、霍夫曼树。
哈夫曼树又称之为最优二叉树，是一种带权路径最短的二叉树。
概念
- 结点的权：给树的每个结点赋予一个具有某种具有实际意义的实数，称之为结点的权；
- 带权路径长度：从根结点到某一个结点的路径长度与该结点的权的乘积，叫做结点的带权路径长度；
- 树的带权路径长度（WPL：weighted path length）：树种所有叶子结点的带权路径长度之和；
- 最优二叉树：权值最大的结点离根结点越近的二叉树，所得的WPL值最小，称之为最优二叉树；
应用场景
数据压缩：在文件压缩和图像压缩中。例如， ZIP文件 和 JPEG图像 压缩都使用了哈夫曼编码。通过统计字符或像素的频率，构建哈夫曼树，高频字符或像素使用较短的编码，从而减少存储空间和传输时间
通信编码：哈夫曼树可以用于创建二进制前缀码，避免编码之间的歧义，并且高频字符使用短码，低频字符使用长码，这符合压缩的需求。因此，哈夫曼编码在需要无损压缩的场合（如文件传输、多媒体编码）中广泛应用
数据编码：在数据编码中，哈夫曼树可用于创建特定应用的编码表。例如，在网络通信中，可以使用哈夫曼树来创建二进制数据流的编码表，提高数据传输的效率
字符串匹配：哈夫曼树还可以用于实现高效的字符串匹配算法，如赫夫曼实现的哈希表，提高字符串处理的效率
访问控制：在访问控制中，哈夫曼树可以用于构建访问控制列表（ACL），以限制对系统资源的访问。通过构建哈夫曼树，可以实现对资源访问的精细化控制
代码案例
构造哈夫曼树
构建步骤
- 排序，从小到大排序，每一个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树；
- 取出根节点权值最小的两个二叉树，组成一颗新的二叉树；新的二叉树的根节点权值为前两个二叉树根节点权值的和；
- 重复：再将这棵新二叉树，以根节点的权值大小再次排序；
- 直到数列中所有数据都被处理，就得到一颗哈夫曼树
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* 哈夫曼树创建
*/
public class HuffmanTreeDemo {
public static void main(String[] args) {
int[] arr = {13,7,8,3,29,6,1};
HNode rootNode = createHuffmanTree(arr);
rootNode.preOrder();
}
/**
* 创建哈夫曼树
*/
public static HNode createHuffmanTree(int[] arr) {
//循环数组，方式一个List<HNode> 中然后进行从小到大排序
List<HNode> list = new ArrayList<HNode>();
for(int tmp : arr){
list.add(new HNode(tmp));
}
//list中只包含一个节点时，退出循环
while (list.size() > 1) {
//排序
Collections.sort(list);
System.out.println(list);
//取出最小的两个权值，创建一个新的二叉树
HNode leftNode = list.get(0);
HNode rightNode = list.get(1);
HNode tempNode = new HNode(leftNode.getValue()+rightNode.getValue());
tempNode.left = leftNode;
tempNode.right = rightNode;
//删除左右两个Node
list.remove(leftNode);
list.remove(rightNode);
//将tempNode 加入list
list.add(tempNode);
}
return list.get(0); //返回最后一个HNode，该HuffmanTree的root节点
}
}
/**
* 节点类 实现Comparable类，一遍完成快速排序
*/
class HNode implements Comparable<HNode>{
private int value; //权值
public HNode left; //左子节点
public HNode right;//右子节点
/**
* 前序遍历
*/
public void preOrder() {
System.out.println(this);
if(this.left != null) {
this.left.preOrder();
}
if(this.right != null) {
this.right.preOrder();
}
}
public HNode(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
@Override
public String toString() {
return "{" + "value=" + value + '}';
}
@Override
public int compareTo(HNode o) {
//表示从小到大排序
return this.value - o.value;
}
}
哈夫曼编码、解码
构建步骤
- 构建频率表：计算每个字符（含符号）出现的频率；
- 构建哈夫曼树：根据字符频率创建哈夫曼树；
- 生成哈夫曼编码表：为每个字符生成一个哈夫曼编码；
- 编码数据：使用哈夫曼编码对数据进行编码；
- 压缩数据：编码后的数据进行存储，通常以二进制进行存储；
- 解压数据：根据哈夫曼树，重构原始数据；
import java.util.*;
/**
* 哈夫曼编码、解码
*/
public class HuffmanTreeCodeDemo {
static Map<Byte, String> huffmanTreeMap = new HashMap<Byte, String>(); //哈夫曼编码表
public static void main(String[] args) {
String str = "i like like java, i very like java";
List<HNodeA> listNode = countCodes(str.getBytes());
System.out.println(listNode);
//创建哈夫曼树
HNodeA rootNode = createHuffmanTree(listNode);
//打印哈夫曼树
rootNode.preOrder();
//获取哈夫曼编码表
StringBuffer stringBuffer = new StringBuffer();
getHuffmanCode(rootNode,"", stringBuffer);
//打印哈夫曼编码
System.out.println(huffmanTreeMap);
//压缩哈夫曼编码
byte[] tmpByte = zip(str.getBytes(), huffmanTreeMap);
//打印哈夫曼压缩数据（字节数组）
System.out.println(Arrays.toString(tmpByte));
//哈夫曼解码
byte[] rstByte = unzip(tmpByte, huffmanTreeMap);
System.out.println(new String(rstByte));
}
/**
* 创建字符频率表，以字节形式处理
*/
public static List<HNodeA> countCodes(byte[] byteps) {
List<HNodeA> listNode = new ArrayList<HNodeA>(); //返回哈夫曼树所需要的结果集
Map<Byte,Integer> codesMap = new HashMap<>();//记录每个字符出现的次数
for (byte b : byteps) {
Integer count = codesMap.get(b);
if(count == null){
//不存在，则记录为1
codesMap.put(b, 1);
}else{
//存在，记录次数加1
codesMap.put(b, count+1);
}
}
System.out.println(codesMap);
//迭代codesMap 加入 listNode
for(Map.Entry<Byte, Integer> entry : codesMap.entrySet()){
listNode.add(new HNodeA(entry.getKey(), entry.getValue()));
}
return listNode;
}
/**
* 创建哈夫曼树
*/
public static HNodeA createHuffmanTree(List<HNodeA> list) {
//list中只包含一个节点时，退出循环
while (list.size() > 1) {
//排序
Collections.sort(list);
// System.out.println(list);
//取出最小的两个权值，创建一个新的二叉树
HNodeA leftNode = list.get(0);
HNodeA rightNode = list.get(1);
HNodeA tempNode = new HNodeA(null, leftNode.getValue()+rightNode.getValue());
tempNode.left = leftNode;
tempNode.right = rightNode;
//删除左右两个Node
list.remove(leftNode);
list.remove(rightNode);
//将tempNode 加入list
list.add(tempNode);
}
return list.get(0); //返回最后一个HNode，该HuffmanTree的root节点
}
/**
* 生成哈夫曼code
* @param node 传入的结点（递归）
* @param code 查找方向 左为0 ，右为1
* @param stringBuffer 拼接路径的字符串（最终编码）
*/
public static void getHuffmanCode(HNodeA node, String code, StringBuffer stringBuffer) {
StringBuffer tempBuffer = new StringBuffer(stringBuffer); //接受上层方法的路径字符串
tempBuffer.append(code); //拼接当前路径
//判断当前节点是否为叶子结点
if(node.getKey() == null){
//非叶子结点，进行递归调用
getHuffmanCode(node.left,"0", tempBuffer);
getHuffmanCode(node.right,"1", tempBuffer);
}else {
//叶子结点，记录哈夫曼编码
huffmanTreeMap.put(node.getKey(), tempBuffer.toString());
}
}
/**
* 压缩哈夫曼编码数据
* @param bytes 原字符串的byte[]
* @param huffmanTreeMap 哈夫曼编码表
*/
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanTreeMap) {
StringBuffer tempBuffer = new StringBuffer();
for (byte b : bytes) {
tempBuffer.append(huffmanTreeMap.get(b));
}
System.out.println("哈夫曼编码字符串："+tempBuffer.toString());
//将哈夫曼编码字符串转换为byte[]，进行压缩
int len = (tempBuffer.length()+7) / 8; //每8位一组取模计算长度
byte[] tempBytes = new byte[len]; //初始化byte[]
int index = 0; //记录tempBytes是第几个byte的index
for (int i = 0; i < tempBuffer.length(); i += 8) { //每8位一个步长，获取数据
String strByte; //初始化byte字符串形式
if(i+8 > tempBuffer.length()){ //不足八位直接放入原值
strByte = tempBuffer.substring(i);
}else{
strByte = tempBuffer.substring(i, i+8); //长度足够，截取8为存储
}
//将strByte 转换为byte[] 并记录
tempBytes[index] = (byte)Integer.parseInt(strByte,2);
index++;
}
//返回
return tempBytes;
}
/**
* 哈夫曼解码
* @param bytes 压缩后的哈夫曼编码
* @param huffmanTreeMap 哈夫曼编码表
* @return
*/
public static byte[] unzip(byte[] bytes, Map<Byte, String> huffmanTreeMap) {
//1.获取bytes对应的二进制字符串
StringBuffer tempBuffer = new StringBuffer();
for (int i = 0; i < bytes.length; i++) {
byte b = bytes[i];
// String tmpStr = String.format("%8s", Integer.toBinaryString(b & 0xFF)).replace(' ', '0'); //byte 对应的 二进制字符串
boolean flag = (i == bytes.length-1);
String tmpStr = byteToBitString(!flag,bytes[i]);
tempBuffer.append(tmpStr);
}
System.out.println("哈夫曼编码字符串："+tempBuffer.toString());
//调换哈夫曼编码，作为反向查询的字典
Map<String, Byte> reveresMap = new HashMap<>();
for (Map.Entry<Byte, String> entry : huffmanTreeMap.entrySet()) {
reveresMap.put(entry.getValue(), entry.getKey());
}
//创建集合存放byte
List<Byte> byteList = new ArrayList<>();
for(int i=0; i<tempBuffer.length();){
int count = 1; //计数器
boolean flag = true;
Byte b = null;
while (flag) {
String key = tempBuffer.substring(i, i+count); //i不变，移动count 知道匹配到一个字符
b = reveresMap.get(key);
if(b == null){
count++;
}else {
//匹配到字符
flag = false;
}
}
byteList.add(b);
i += count; //i用到count位置
}
//返回字符串的数组
byte[] rst = new byte[byteList.size()];
for (int i = 0; i < byteList.size(); i++) {
rst[i] = byteList.get(i);
}
return rst;
}
public static String byteToBitString(boolean flag, byte b) {
int tmp = b;
if(flag){
tmp |= 256;
}
String tmpStr = Integer.toBinaryString(tmp);
if(flag){
return tmpStr.substring(tmpStr.length()-8);
}else{
return tmpStr;
}
}
}
/**
* 节点类 实现Comparable类，一遍完成快速排序
*/
class HNodeA implements Comparable<HNodeA>{
private Byte key;
private int value; //权值
public HNodeA left; //左子节点
public HNodeA right;//右子节点
/**
* 前序遍历
*/
public void preOrder() {
System.out.println(this);
if(this.left != null) {
this.left.preOrder();
}
if(this.right != null) {
this.right.preOrder();
}
}
public HNodeA(Byte key, int value) {
this.key = key;
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Byte getKey() {
return key;
}
public void setKey(Byte key) {
this.key = key;
}
@Override
public String toString() {
return "{" + "key=" + key +", "+ "value=" + value + '}';
}
@Override
public int compareTo(HNodeA o) {
//表示从小到大排序
return this.value - o.value;
}
}
