使用java实现Huffman树
我们为什么需要Huffman树
目前，我们常用的图像、音频、视频等多媒体信息，信息量大，以传统方式存储无疑会占用大量存储空间，因此，我们引入了Huffman编码来解决这个问题。
什么是Huffman编码
Huffman编码是一种变长的编码方案，数据的编码因其使用频率不同而长短不一，使用频率高的数据其编码较短，使用频率低的数据其编码较长，从而使得所有数据的编码总长度最短。
如何实现Huffman编码
考虑实现Huffman编码的结构，我们决定使用二叉树来实现。
这里涉及到一个概念，二叉树的带权外路径长度：树中所有叶子的带权路径长度之和。而Huffman树则是二叉树的带权外路径长度最小的二叉树，也称最优二叉树。
构造Huffman树并得到Huffman编码
这里，我们使用静态三叉链表存储Huffman树。
这是静态三叉链表结点类TriElement
/**
* @author cust
* 二叉树的静态三叉链表结点类
*/
public class TriElement{
int data; //数据域
int parent,left,right; //父母结点和左、右孩子结点下标
//不设置setter方法和getter方法,确保静态三叉链表结点只在具有权值时构造，且不可再被修改
//构造结点，各参数依次指定元素、父母结点下标、左/右孩子结点下标
public TriElement(int data, int parent, int left, int right)
{
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
public TriElement(int data) { //构造元素值为data、无父母的叶子结点
this(data, -1, -1, -1);
}
public String toString() { //返回结点的描述字符串
return "("+this.data+","+this.parent+","+this.left+","+this.right+")";
}
public boolean isLeaf() { //判断是否叶子结点
return this.left==-1 && this.right==-1;
}
public boolean equals(Object obj) { //比较是否相等 ，覆盖Object类的equals(obj)方法
//仅比较元素值
return obj==this || obj instanceof TriElement && this.data==((TriElement)obj).data;
}
}这是Huffman树类HuffmanTree
//哈夫曼树类
public class HuffmanTree{ //Huffman树类
private String charset; //字符集合
private TriElement[] huftree; //静态三叉链表结点数组
//用来存储数据
//不设置setter方法和getter方法,确保每一颗huffman树只在具有权值时构造，且不可再被修改
/**
* @param weights 权重数组
* 通过Huffman算法构建Huffman树
* 主要由三个步骤组成：
* 1.初始化
* 构造出wehights.length个结点的森林
* 2.合并二叉树
* 选择当前根结点权值最小的两颗二叉树合并，左孩子权值较小，合并后根结点的权值为其孩子结点的权值之和
* 3.重复2
* 只剩下最后一棵二叉树，这就是Huffman树
*/
//构造Huffman树，weights指定权值集合，数组长度为叶子结点数；默认字符集合从A开始
public HuffmanTree(int[] weights)
{
//准备部分
this.charset = "";
for (int i = 0; i < weights.length; i++) {
//将权值数组中的每一个数字转化为对应的字符
//默认字符集合是从'A'开始的weights.length个字符
// this.charset += (char)('A'+i);
if(i <= 25){
this.charset += (char)('A'+i);
}else if(i <= 51){
this.charset += (char)('a'+(i - 26));
}else if(i == 52){
this.charset += " ";
}
}
// System.out.println(charset);
// System.out.println(charset);
int n = weights.length; //叶子结点数
//叶子结点数与权值数组一一对应，每一个叶子都对应了一个字符的编码
//初始化
this.huftree = new TriElement[2*n-1]; //n个叶子的Huffman树共有2n-1个结点
//前n个存放叶子结点，后n-1个存放2度结点
for(int i=0; i<n; i++) //Huffman树初始化n个叶子结点
this.huftree[i] = new TriElement(weights[i]); //构造无父母的叶子结点
//合并二叉树
for(int i = n; i < 2*n-1; i++) { //构造n-1个2度结点
//当n-1个2度顶点构造完成时结束循环
int min1 = Integer.MAX_VALUE, min2 = min1; //最小和次小权值，初值为整数最大值
int x1=-1, x2=-1; //最小和次小权值结点下标
for (int j = 0; j < i; j++) { //寻找两个无父母的最小权值结点下标
//若该结点具有父母，说明该结点已经合并
if (this.huftree[j].parent == -1) //第j个结点无父母
//若能选出最小的，则用原本最小的记录，然后将原本记录最小的存储到次小的
if (this.huftree[j].data < min1) { //第j个结点权值最小
min2 = min1; //min2记得次小权值
x2 = x1; //x2记得次小权值结点下标
min1 = this.huftree[j].data; //min1记得最小权值
x1 = j; //x1记得最小权值结点下标
}else { //若能得到比次小小的，但比最小的大，则只需要更新次小的即可
if (this.huftree[j].data < min2) { //第j个结点权值次小
min2 = huftree[j].data; //记录次小权值
x2 = j; //记录次小的位置
}
}
}
this.huftree[x1].parent = i; //合并两棵权值最小的子树，左孩子最小
this.huftree[x2].parent = i;
this.huftree[i] = new TriElement(min1+min2, -1, x1, x2); //构造结点，指定值、父母、左右孩子
}
//Huffman树构造完毕
}
/**
* @param i 字符在charset中的位置
* @return 对应的描述字符串
* 通过访问Huffman树来实现
*/
private String getCode(int i) //返回charset第i个字符的Huffman编码字符串
{
int n = 59;
// int n = 8; //最多可以表示8个字符的huffman编码，这里可以修改为26
char hufcode[] = new char[n]; //声明字符数组暂存Huffman编码
int child = i, parent = this.huftree[child].parent; //获取这个元素的父节点
for (i = n-1; parent != -1; i--) //由叶结点向上直到根结点，反序存储编码
{
hufcode[i] = (huftree[parent].left==child) ? '0' : '1'; //左、右孩子编码为0、1
child = parent; //向上转移到根结点
parent = huftree[child].parent; //得到根结点
}
return new String(hufcode,i+1,n-1-i); //由hufcode数组从i+1开始的n-1-i个字符构造串
}
public String toString() //返回Huffman树的结点数组和所有字符的编码字符串
{
String str="Huffman树的结点数组:";
for (int i=0; i < this.huftree.length; i++)
str += this.huftree[i].toString()+",";
str = str.substring(0, str.length()-1);
str += "\nHuffman编码： ";
for (int i=0; i<this.charset.length(); i++) //输出所有叶子结点的Huffman编码
str+=this.charset.charAt(i)+":"+getCode(i)+",";
return str.substring(0, str.length()-1);
}
//数据压缩，将text各字符转换成Huffman编码存储，返回压缩字符串
public String encode(String text)
{
String compressed = ""; //被压缩的数据，以字符串显示
for (int i = 0; i < text.length(); i++) {
// compressed += getCode(text.charAt(i)-'A'); //默认字符集是从A开始的n个字符
if(text.charAt(i)-'A' >= 0 && text.charAt(i)-'A' <= 25){
compressed += getCode(text.charAt(i)-'A'); //默认字符集是从A开始的n个字符
}else if(text.charAt(i)-'a' >= 0 && text.charAt(i)-'a' <= 25){
compressed += getCode(text.charAt(i)-'a'+26); //默认字符集是从A开始的n个字符
}else{
compressed += getCode(52); //默认字符集是从A开始的n个字符
}
}
return compressed; //返回对应字符串
}
//数据解压缩，将压缩compressed中的0/1序列进行Huffman译码，返回译码字符串
public String decode(String compressed)
{
String text = ""; //结果字符串
int node = this.huftree.length-1; //node搜索一条从根到达叶子的路径
//huftree的最后一个元素是根结点
for (int i = 0; i < compressed.length(); i++) //将每一段数字转化成对应的英文字符
{
if (compressed.charAt(i) == '0') //根据0、1分别向左或右孩子走
node = huftree[node].left;
else
node = huftree[node].right;
if (huftree[node].isLeaf()) //到达叶子结点
{
text += this.charset.charAt(node); //获得一个字符
node = this.huftree.length-1; //node再从根结点开始
}
}
return text;
}
}这是与Huffman树对应的字符映射类AsciiCodeMap，在Huffman树中指定的默认字符集则是来自于这里，此处我只设置了大小写英文字母和空格，实际上也可以继续添加，最好设置为ASCII的所有字符。
import java.util.HashMap;
import java.util.Map;
//英文符号对应的映射
public class AsciiCodeMap {
public Map<Character, Integer> asciiCodeMap = new HashMap<Character, Integer>();
public AsciiCodeMap(){
for(int i = 0; i <= 25; i++){
asciiCodeMap.put((char)('A'+(i-26)), i);
}
for(int i = 26; i <= 51; i++){
asciiCodeMap.put((char)('a'+(i-26)), i);
}
asciiCodeMap.put(' ', 52);
}
}这里是测试类
import java.util.Scanner;
//采用Huffman算法对字符串进行数据压缩和解压缩。
public class HuffmanTree_ex {
public static void main(String[] args)
{
// String text="AAAACFHHHFFFCEEEHEHCGBGAFFEHHHHHHHECCAEECDCEEEADC"
// + "CDAACCCCABHHAAGADDAAAFAHHHHAA"; //【例6.4】 数据
// int[] weight6_34={19, 2, 13, 5, 11, 7, 3, 17}; //6-34
// HuffmanTree huffman = new HuffmanTree(weight6_34); //构造Huffman树
// System.out.println(huffman.toString()); //输出Huffman树的结点数组和所有字符编码
// String compressed = huffman.encode(text);
// System.out.println("将"+text+"压缩为"+compressed+"，"+compressed.length()+"位");
// System.out.println("将"+compressed+"解码为"+huffman.decode(compressed));
//手动编码，测试
Scanner input = new Scanner(System.in);
String text2 = input.nextLine();
AsciiCodeMap a = new AsciiCodeMap();
// String text2="Hello world";
int[] weight = new int[59]; //6-34
for(int i = 0; i<weight.length; i++){
weight[i] = 0;
}
for(int i = 0; i<text2.length(); i++){
int m = a.asciiCodeMap.get(text2.charAt(i)); //找到对应的索引位置
weight[m]++;
// System.out.println(text2.charAt(i)+" "+ m);
}
HuffmanTree huffman2 = new HuffmanTree(weight); //构造Huffman树
System.out.println(huffman2.toString()); //输出Huffman树的结点数组和所有字符编码
String compressed2 = huffman2.encode(text2);
System.out.println("将"+text2+"压缩为"+compressed2+"，"+compressed2.length()+"位");
System.out.println("将"+compressed2+"解码为"+huffman2.decode(compressed2));
input.close();
}
}总结
构建Huffman树，需要了解Huffman编码的基本原理：也就是出现次数多的字符的编码尽可能地短，这样就可以实现了我们所说的数据压缩。
使用java实现Huffman树
https://blog.fulequn.online/2020/08/Article202008203/