哈夫曼树
定义
- 定义：带权路径长度WPL最小的二叉树称作哈夫曼树，又叫最优二叉树
- 节点的带权路径长度为：从该节点到树根之间的路径长度与节点上的权的乘积
- 树的带权路径长度为：所有叶子节点的带权路径长度之和
构造方式
大话数据结构：
- 根据给定的n个权值{ w1,w2,w3,···,wn }构成n棵二叉树的集合F = { T1,T2,T3,···,Tn },其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均为空。(其实就是一个节点)
- 在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
- 在F中删除这两棵树，同时将新得到的二叉树加入F中。
- 重复步骤2和3，直到F只含一棵树为止，这棵树便是哈夫曼树。（这个节点便是哈夫曼树的根节点）
举个例子：
现在有五个字符ABCDE，权值分别为5, 15, 40, 30, 10
先取出权值最小的两个字符，分别为 A, E
将它们作为左右子树构造一棵新的二叉树：
再将A, E从集合F中删除，将新的得到的N1加入到F中：
N1的权值即为A, E的权值之和：5 + 10 = 15
重复上述步骤，将权值最小的N1和B作为左右子树构建一棵新的二叉树：
重复上述步骤，将N2加入到集合F中，将N1和B从集合F中删除，选取F中权值最小的两个节点分别为N2, D构建新的二叉树：
删除N2, D,添加N3，选取最小的两个节点，C和N3作为左右子树构建二叉树：
这样，就完成了哈夫曼树的构造，可以算得：
(WPL = 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220)
哈夫曼编码
将字符的频率作为权值来构建好的哈夫曼树，规定左分支为 0，右分支为 1，则从根节点到叶子节点所经过的路径分支组成的 01序列便为该节点对应字符的编码，这就是哈夫曼编码
将上述的哈夫曼树作为例子，设我们要传输的信息就只有ABCDE这五个字符。
设字符A的频率为5%，B为15%，C为40%，D为30%，E为10%。
假设我们不用哈夫曼编码，很自然的想到，我们用二进制来表示这5个字符：
现在有一段文本内容：CADECDDBACE
二进制表示：010000011100010011011001000010100
哈夫曼编码：01000111001000101100001001
很明显，用哈夫曼编码传送数据，节约了存储。
若编码为长短不等，那么必须任一字符的编码都不是另一个字符的编码的前缀，这种编码叫前缀编码。
仔细观察就会发现，哈夫曼编码不会出现混淆的情况，这是因为每个字符都是在树上的叶子节点上。
实验
实验简介
实验项目： 树形结构及其应用
实验题目： 哈夫曼编码与译码方法
实验内容：
哈夫曼编码是一种以哈夫曼树（最优二叉树，带权路径长度最小的二叉树）为基础变长编码方法。其基本思想是：将使用次数多的代码转换成长度较短的编码，而使用次数少的采用较长的编码，并且保持编码的唯一可解性。在计算机信息处理中，经常应用于数据压缩。是一种一致性编码法（又称”熵编码法”），用于数据的无损压缩。要求实现一个完整的哈夫曼编码与译码系统。
实验要求：
- 从文件中读入任意一篇英文文本文件，分别统计英文文本文件中各字符（包括标点符号和空格）的使用频率；
- 根据已统计的字符使用频率构造哈夫曼编码树，并给出每个字符的哈夫曼编码（字符集的哈夫曼编码表）；
- 将文本文件利用哈夫曼树进行编码，存储成压缩文件（哈夫曼编码文件）；
- 计算哈夫曼编码文件的压缩率；
- 将哈夫曼编码文件译码为文本文件， 并与原文件进行比较。
测试结果
test.txt 英文文本测试文件 test_Copy.txt 英文文本解码文件
code.txt 哈夫曼编码文件 huffman.txt 哈夫曼树的结构文件
test.hfm 哈夫曼压缩文件
关于压缩
就是将文本转换后的哈夫曼编码每一条首尾相连，然后每八位，也就是一个字节，转换为一个字符（但并不是字符，只是为了放到char型变量中），然后以二进制形式存储到文件中。
字符在文本文件中存储的是一字节，8位，对应的是ASCII码。这样压缩后，压缩率就可以得出一个理论计算公式: 压缩率 = 哈夫曼编码长度 / （8 * 文本字符数）。
但实际上，最后不足8位的，我们需要补上，凑一个8位然后存储。
哈夫曼树的结构
struct TreeNode{
int weight;//权值，这里存储字符出现次数
char ch;//存储的字符
TreeNode* left;//左儿子，右儿子，二叉树结构
TreeNode* right;
};
typedef TreeNode* Huff;
手写堆的结构
/*哈夫曼树的构建过程是每次取最小，然后再放入的过程，这就可以用堆来实现*/
struct HeapNode{
Huff* data;//直接用数组模拟的堆
int size;// 堆的大小
int cap; //容量
};
typedef HeapNode* Heap;
编码表
const int N = 128;
int cnt[N];//字符出现次数
map mp;//使用STL的映射存储
一开始，只需要test.txt，内容如下
Hello,I am Az1r!
I come from China.
Now I am a student,and I major in Computer Science.
编码，译码：
代码
点击查看代码
/*
Author: Az1r
Date: 2022/10/14
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <limits>
#include <queue>
#include <map>
#include <fstream>
#include <iomanip>
#define MAX_LENTH 100
using namespace std;
// 哈夫曼树
struct TreeNode{
int weight;
char ch;
TreeNode* left;
TreeNode* right;
};
typedef TreeNode* Huff;
// 小根堆
struct HeapNode{
Huff* data;
int size;// 堆的大小
int cap; //容量
};
typedef HeapNode* Heap;
Huff T = NULL;
//编码表
const int N = 128;
int cnt[N];
map<int, string> mp;
int codelenth; //编码长度
Huff CreateNode(char ch, int weight); //创建一个哈夫曼树的节点
Heap CreateHeap(); //创建一个小根堆
void InitHeap(Heap H); //初始化堆
void SetHeap(Heap H, int p); //向下调整堆
bool IsFull(Heap H); //判满
bool IsEmpty(Heap H); //判空
bool InsertHeap(Heap H,Huff tree); //向堆中插入插入
Huff Pop(Heap H); //弹出堆中根节点
void LoadTreeByInput(); //通过输入初始化哈夫曼树
Huff BuildHuffmanTree(Heap H); //建立哈夫曼树
void PrintTree(Huff tree); //打印哈夫曼树
void Menu(); //打印菜单
void CreateDict(Huff tree, string temp);//创建哈夫曼编码表
void PrintCode(); //打印编码表
void LoadTreeByFile(); //文件输入哈夫曼树
void CodeFile(); //编码文本文件
void Caulcute(); //计算压缩率
void DecodeFile(Huff tree); //解码文本文件
/*
test.txt 英文文本测试文件
test_Copy.txt 英文文本解码文件
code.txt 哈夫曼编码文件
huffman.txt 哈夫曼树的结构文件
test.hfm 哈夫曼压缩文件
*/
int main()
{
int select = -1;
while(select)
{
system("pause");
system("cls");
Menu();
printf("input your choose: ");
scanf("%d", &select);
switch(select)
{
case 1:
{
PrintTree(T);
break;
}
case 2:
{
DecodeFile(T);
break;
}
case 3:
{
CodeFile();
break;
}
case 4:
{
PrintCode();
}
case 5:
{
Caulcute();
break;
}
case 0:
{
break;
}
default:
{
break;
}
}
}
return 0;
}
void Menu()
{
printf("---- Menu ----"); printf("\n");
printf("---- 1.PrintTree ----"); printf("\n");
printf("---- 2.Decode ----"); printf("\n");
printf("---- 3.Code ----"); printf("\n");
printf("---- 4.PrintDictCode ----"); printf("\n");
printf("---- 5.Caulcute ----"); printf("\n");
printf("---- 0.Exit ----"); printf("\n");
}
void Caulcute()
{
int chTotal = 0;
int hfmTotal = 0;
for(int i = 0; i < N; i ++ )
{
chTotal += cnt[i];
hfmTotal += cnt[i] * mp[i].length();
}
if(hfmTotal % 8 == 0)
{
hfmTotal /= 8;
}else
{
hfmTotal = (hfmTotal + 8) / 8;
}
double rate = hfmTotal * 1.0 / chTotal * 100; //1个字符占8位
cout << "Code rate: " << rate << "%" << "\n";
}
void DecodeFile(Huff tree)
{
ifstream inbfile; //二进制读取
inbfile.open("test.hfm", ios::in | ios::binary);
ofstream outfile;
outfile.open("test_Copy.txt");
if(inbfile == NULL || outfile == NULL)
{
printf("File open error!\n");
return;
}
unsigned char temp;
Huff x = tree;
while(!inbfile.eof())
{
inbfile.read((char *)&temp, sizeof (unsigned char));
if(inbfile.fail())//防止读到最后
{
break;
}
for(int i = 0; i < 8; i++ )
{
int j = 7 - i;
if(codelenth == 0)
{
break;
}
codelenth --;
if( (temp >> j) & 1)
{
x = x->right;
}else
{
x = x->left;
}
if(x->left == NULL && x->right == NULL) // 左右儿子都无，那就是叶子节点，即保存字符的节点
{
outfile << x->ch;
x = tree;
}
}
}
inbfile.close();
outfile.close();
printf("Succeeful decode file!\n");
printf("Succeeful generate test_Copy.txt!\n");
}
void CodeFile()
{
for(int i = 0; i < N; i ++ )
{
cnt[i] = 0;
}
ifstream infile;
infile.open("test.txt");
if(infile == NULL)
{
printf("Open file error!\n");
return;
}
infile >> noskipws; // 控制符，可以读取空格回车
char ch;
while(!infile.eof())
{
infile >> ch;
if(infile.fail())//防止读到最后一个字符
{
break;
}
cnt[(int)ch] ++;
}
infile.close();
ofstream outfile;
outfile.open("huffman.txt");
if(outfile == NULL)
{
printf("Open file error!\n");
return;
}
for(int i = 0; i < N; i ++ )
{
if(cnt[i])
{
ch = i;
outfile << ch << cnt[i] << "\n"; //输出到哈夫曼树结构文件中
}
}
outfile.close();
LoadTreeByFile();
CreateDict(T, "");
infile.open("test.txt");
infile >> noskipws;
outfile.open("code.txt");
ofstream bfile;
bfile.open("test.hfm", ios::out | ios::binary);
if(outfile == NULL || infile == NULL || bfile == NULL)
{
printf("Open file error!\n");
return;
}
int bitflag = 0;
unsigned char res = 0;
while(!infile.eof())
{
infile >> ch;
if(infile.fail())//防止读到最后一个字符
{
break;
}
string temp = mp[(int)ch];
outfile << temp;
int templenth = temp.length();
for(int i = 0; i < templenth; i ++ )
{
codelenth ++;
bitflag ++;
res <<= 8 1; if(temp[i]="=" '1') { res |="1;" } if(bitflag="=" 8) bitflag="0;" bfile.write((char *)&res, sizeof (unsigned char)); if(bitflag) for(int i="0;" < - ;i ++) <<="1;" infile.close(); outfile.close(); bfile.close(); printf("succeeful code file!\n"); generate huffman.txt, code.txt, test.hfm !\n"); void printcode() int total="0;" n; ++ ) +="cnt[i];" 输出字符,频率,编码 if(cnt[i]) float f="cnt[i]" * 1.0 total; if(i="=" 10) cout setw(3) "---- " "\\n" ---- fixed setprecision(3) mp[i] "\n" ; }else if (i="=" 32) "<space>" << " ---- " << fixed << setprecision(3) << f << " " << mp[i] << "\n" ;
}else
{
cout << setw(3) << i << "---- " << (char)i << " ---- " << fixed << setprecision(3) << f << " " << mp[i] << "\n" ;
}
}
}
}
void CreateDict(Huff tree, string temp)
{
if(tree)
{
if(tree->left == NULL && tree->right == NULL)
{
int idx = tree->ch;
mp[idx] = temp;
}else
{
CreateDict(tree->left, temp + "0");//左 0
CreateDict(tree->right, temp + "1");//右 1
}
}
}
Huff CreateNode(char ch, int weight)
{
Huff Node = (Huff)malloc(sizeof (TreeNode));
Node->ch = ch;
Node->weight = weight;
Node->left = Node->right = NULL;
return Node;
}
// 堆的构建
Heap CreateHeap()
{
Heap Node = (Heap)malloc(sizeof (HeapNode));
Node->data = (Huff *)malloc((MAX_LENTH + 1) * sizeof (Huff));
Node->size = 0;
Node->cap = MAX_LENTH;
Node->data[0] = CreateNode('\0',INT_MIN);
return Node;
}
// 堆的向下调整
void SetHeap(Heap H, int p)
{
int parent, child;
int lenth = H->size;
Huff root = H->data[p];
for(parent = p; parent * 2 <= lenth; parent="child)" { 将child指向parent的左右子节点中最小者 child="parent" * 2; if((child < lenth) && h->data[child]->weight > H->data[child + 1]->weight){
child++;
}
// 如果child的权重不再小于parent,调整完毕,否则继续进行调整
if(root->weight <= h->data[child]->weight)
{
break;
}else
{
H->data[parent] = H->data[child];
}
}
H->data[parent] = root;
}
// 初始化最小堆
void InitHeap(Heap H)
{
// 从最后一个节点的父节点开始,一直到根节点1 (0是哨兵节点)
for(int i = H->size / 2; i > 0; i --)
{
SetHeap(H,i);
}
}
// 判空，判满
bool IsFull(Heap H)
{
return (H->size == H->cap);
}
bool IsEmpty(Heap H)
{
return (H->size == 0);
}
// 插入堆的操作
bool InsertHeap(Heap H,Huff tree)
{
if(IsFull(H))
{
printf("Full Heap!\n");
return false;
}
H->size ++;
int i= H->size;
// i为最后一个位置，然后一层一层向上过滤
for(; H->data[i / 2]->weight > tree->weight; i /= 2)
{
H->data[i] = H->data[i / 2];
}
H->data[i] = tree;
return true;
}
// 从堆中取出最小元素的实现
Huff Pop(Heap H)
{
if(IsEmpty(H))
{
printf("Empty Heap!\n");
return NULL;
}
int parent,child;
int lenth = H->size;
// 取出根节点
Huff rootTree = H->data[1];
// xTree为最后一个元素，同时size-1（因为取出了根节点）
Huff xTree = H->data[H->size --];
// 从根节点下面找出最小的替换上来
for(parent = 1;parent * 2 <= lenth; parent="child)" { child="parent" * 2; if((child < lenth) && (h->data[child]->weight > H->data[child+1]->weight))
{
child ++;
}
if(xTree->weight <= h->data[child]->weight)
{
break;
}else
{
H->data[parent] = H->data[child];
}
}
H->data[parent] = xTree;
return rootTree;
}
// 哈夫曼树的构造
Huff BuildHuffmanTree(Heap H)
{
// 假设已经无序的将节点保存在堆的data中,
// 首先要将堆调整为最小堆
Huff tree;
InitHeap(H);
int size = H->size;
for(int i = 1;i < size; i ++)
{
tree = (Huff)malloc(sizeof (TreeNode));
// 取出两个最小节点，作为这个节点的左右分支
tree->ch = '\0';
tree->left = Pop(H);
tree->right = Pop(H);
// 计算新的权值
tree->weight = tree->left->weight + tree->right->weight;
// 将这个节点再插入最小堆
InsertHeap(H,tree);
/* test
*/
}
// 取出哈夫曼树根节点(也就是堆顶节点)
tree = Pop(H);
return tree;
}
// 先序遍历哈夫曼树
void PrintTree(Huff tree)
{
if(tree)
{
if((tree->left == NULL) && (tree->right == NULL))
{
char ch = tree->ch;
if(ch == '\n')
{
cout << "Leaf " << setw(3) << tree->weight << " ---- " << "\\n" << "\n" ;
}else if(ch == ' ')
{
cout << "Leaf " << setw(3) << tree->weight << " ---- " << "<space>" << "\n" ;
}else
{
cout << "Leaf " << setw(3) << tree->weight << " ---- " << ch << "\n" ;
}
}else
{
cout << "Node " << setw(3) << tree->weight << "\n" ;
}
PrintTree(tree->left);
PrintTree(tree->right);
}
}
void LoadTreeByFile()
{
ifstream infile;
infile.open("huffman.txt");
if(infile == NULL)
{
printf("load file error!\n");
return;
}
int weight;
char ch;
char temp[20];
Heap heap = CreateHeap();
infile >> noskipws; // 控制符，可以读取空格回车
while(!infile.eof())
{
infile >> ch;
infile.getline(temp, 20);
weight = atoi(temp);
heap->data[++ heap->size] = CreateNode(ch, weight);
}
infile.close();
T = BuildHuffmanTree(heap);
}
// 哈夫曼树从用户输入
void LoadTreeByInput()
{
printf("please input your haffman:\n");
int weight,count;
char ch;
char temp[10];
Heap heap = CreateHeap();
printf("input data num :");
scanf("%d", &count);
cout << "( data+weight ):" <<endl; for(int i="1;i" <="count;" ++) { scanf("%s", temp); ch="temp[0];" weight="atoi(temp" + 1); cnt[(int)ch]="weight;" heap->data[i] = CreateNode(ch, weight);
heap->size ++;
}
T = BuildHuffmanTree(heap);
}
</endl;></space></=></=></=></=></=></int,></iomanip></fstream></map></queue></limits></cstdio></cstring></iostream>
一些相关的问题
- 代码中的堆，是手写的小根堆，也可以使用STL中优先队列priority_queue来实现。
- 上述 1-5 的编码和译码是基于字符的压缩，如何考虑基于单词的压缩，完成上述工作。
- 上述 1-5 的编码是二进制的编码，如何采用 K 叉的哈夫曼树完成上述工作，实现”K 进制”的编码和译码 。
参考资料
-
程杰. 大话数据结构：溢彩加强版[M]. 北京: 清华大学出版社, 2020.
Original: https://www.cnblogs.com/Az1r/p/16794068.html
Author: 江水为竭
Title: 哈夫曼编码解码（数据结构实验）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/685477/
转载文章受原作者版权保护。转载请注明原作者出处！