哈夫曼编码原理及实现

一.哈夫曼编码原理

哈夫曼编码（Huffman Coding）是一种用于数据压缩的编码方法，它通过给出不同的数据符号分配不同长度的编码，使得出现频率高的符号具有较短的编码，而出现频率低的符号具有较长的编码，从而达到压缩数据的目的。

哈夫曼编码的原理可以通过以下步骤来解释：

统计频率：首先，需要统计待编码数据中每个符号的出现频率。符号可以是字符、字节或其他数据单元。统计频率可以通过遍历整个数据集来完成，并记录每个符号出现的次数。

构建编码树：根据符号的频率构建一个特殊的二叉树，称为哈夫曼树（Huffman Tree）或编码树。构建编码树的方法是将频率最低的两个符号合并为一个新节点，该节点的频率为两个节点频率之和。将新节点插入到已有节点的集合中，重复这个步骤，直到只剩下一个节点，即根节点为止。在构建过程中，可以使用优先队列或最小堆来维护频率最低的节点。

分配编码：从根节点开始，沿着左子树走为0，沿着右子树走为1，将0和1分别分配给左右子节点。重复这个过程，直到遍历到每个叶子节点为止。每个叶子节点的路径上的0和1的序列就是对应符号的哈夫曼编码。

生成编码表：将每个符号及其对应的哈夫曼编码存储在一个编码表中，以备后续的编码和解码使用。

进行编码：将原始数据中的每个符号替换为其对应的哈夫曼编码，生成压缩后的编码数据。由于频率高的符号具有较短的编码，而频率低的符号具有较长的编码，所以整个编码后的数据长度会相对减小。

哈夫曼编码的优点是没有冗余和歧义性，即每个编码都不是其他编码的前缀，这种性质被称为前缀码。这使得编码和解码过程都是非常高效的。然而，对于哈夫曼编码的最佳性能，符号的频率应该是根据数据集的统计特征进行调整的。

哈夫曼编码举例： 假设要对“we will we will r u”进行压缩
压缩前,使用 ASCII 码保存

共需： 19 个字节 - 152 个位保存

下面我们先来统计这句话中每个字符出现的频率。如下表，按频率高低已排序：

接下来，我们按照字符出现的频率，制定如下的编码表：

这样，“we will we will r u”就可以按如下的位来保存：
01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100

哈夫曼二叉树构建

1.按出现频率高低将其放入一个数组中，从左到右依次为频率逐渐增加


2. 从左到右进行合并，依次构建二叉树。第一步取前两个字符 u 和 r 来构造初始二叉树，第一个字符作为左节点，第二个元素作为右节点，然后两个元素相加作为新的空元素，并且两者权重相加作为新元素的权重。

3.新节点加入后，依据权重重新排序，按照权重从小到大排列，上图已有序。
4.红色区域的新增元素可以继续和 i 合并,如下图所示：

5. 合并节点后, 按照权重从小到大排列，如下图所示。

6. 排序后，继续合并最左边两个节点，构建二叉树，并且重新计算新节点的权重

7. 重新排序

8. 重复上面步骤 6 和 7,直到所有字符都变成二叉树的叶子节点

二.具体代码实现

Huff.h

#pragma once
#pragma once
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define MaxSize 1024 //队列的最大容量
typedef struct _Bnode
{
	char value;
	int weight;
	struct _Bnode* parent;
	struct _Bnode* lchild;
	struct _Bnode* rchild;
} Btree, Bnode; /* 结点结构体 */
typedef Bnode* DataType; //任务队列中元素类型
typedef struct _QNode { //结点结构
	int priority; //每个节点的优先级,数值越大，优先级越高，优先级相同，取第一个节点
	DataType data;
	struct _QNode* next;
}QNode;
typedef QNode* QueuePtr;
typedef struct Queue
{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;

//队列初始化，将队列初始化为空队列897943840118979438401111
void InitQueue(LinkQueue* LQ)
{
	if (!LQ) return;
	LQ->length = 0;
	LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置 0
}
//判断队列为空
int IsEmpty(LinkQueue* LQ)
{
	if (!LQ) return 0;
	if (LQ->front == NULL)
	{
		return 1;
	}
	return 0;
}
//判断队列是否为满
int IsFull(LinkQueue* LQ)
{
	if (!LQ) return 0;
	if (LQ->length == MaxSize)
	{
		return 1;
	}
	return 0;
}
//入队,将元素 data 插入到队列 LQ 中
int EnterQueue(LinkQueue* LQ, DataType data, int priority) {
	if (!LQ) return 0;
	if (IsFull(LQ)) {
		cout << "无法插入元素 " << data << ", 队列已满!" << endl;
		return 0;
	}
	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->priority = priority;
	qNode->next = NULL;
	if (IsEmpty(LQ)) {//空队列
		LQ->front = LQ->rear = qNode;
	}
	else {
		qNode->next = LQ->front;
		LQ->front = qNode;
		//LQ->rear->next =qNode;//在队尾插入节点 qNode
		//LQ->rear = qNode; //队尾指向新插入的节点
	}
	LQ->length++;
	return 1;
}
//出队，遍历队列，找到队列中优先级最高的元素 data 出队
int PopQueue(LinkQueue* LQ, DataType* data) {
	QNode** prev = NULL, * prev_node = NULL;//保存当前已选举的最高优先级节点上一个节点的指针地址。
	QNode* last = NULL, * tmp = NULL;
	if (!LQ || IsEmpty(LQ)) {
		cout << "队列为空！" << endl;
		return 0;
	}
	if (!data) return 0;
	//prev 指向队头 front 指针的地址
	prev = &(LQ->front);
	//printf("第一个节点的优先级: %d\n", (*prev)->priority);
	last = LQ->front;
	tmp = last->next;
	while (tmp) {
		if (tmp->priority < (*prev)->priority) {
			//printf("抓到个更小优先级的节点[priority: %d]\n",tmp->priority);
			prev = &(last->next);
			prev_node = last;
		}
		last = tmp;
		tmp = tmp->next;
	}
	*data = (*prev)->data;
	tmp = *prev;
	*prev = (*prev)->next;
	delete tmp;
	LQ->length--;
	//接下来存在 2 种情况需要分别对待
	//1.删除的是首节点,而且队列长度为零
	if (LQ->length == 0) {
		LQ->rear = NULL;
	}
	//2.删除的是尾部节点
	if (prev_node && prev_node->next == NULL) {
		LQ->rear = prev_node;
	}
	return 1;
}
//打印队列中的各元素
void PrintQueue(LinkQueue* LQ)
{
	QueuePtr tmp;
	if (!LQ) return;
	if (LQ->front == NULL) {
		cout << "队列为空！";
		return;
	}
	tmp = LQ->front;
	while (tmp)
	{
		cout << setw(4) << tmp->data->value << "[" << tmp->priority << "]";
		tmp = tmp->next;
	}
	cout << endl;
}
//获取队首元素，不出队
int GetHead(LinkQueue* LQ, DataType* data)
{
	if (!LQ || IsEmpty(LQ))
	{
		cout << "队列为空!" << endl;
		return 0;
	}
	if (!data) return 0;
	*data = LQ->front->data;
	return 1;
}
//清空队列
void ClearQueue(LinkQueue* LQ)
{
	if (!LQ) return;
	while (LQ->front) {
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}
	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}
//获取队列中元素的个数
int getLength(LinkQueue* LQ) {
	if (!LQ) return 0;
	return LQ->length;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

main.cpp

#include "Huff.h"

using namespace std;
void PreOrderRec(Btree* root);
/* 构造哈夫曼编码树 */
void HuffmanTree(Btree*& huff, int n)
{
	LinkQueue* LQ = new LinkQueue;
	int i = 0;
	//初始化队列
	InitQueue(LQ);
	/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
	for (i = 0; i < n; i++)
	{
		Bnode* node = new Bnode;
		cout << "请输入第" << i + 1 << "个字符和出现频率: " << endl;
		cin >> node->value; //输入字符
		cin >> node->weight;//输入权值
		node->parent = NULL;
		node->lchild = NULL;
		node->rchild = NULL;
		EnterQueue(LQ, node, node->weight);
	}
	PrintQueue(LQ);
	//system("pause");
	//exit(0);
	do {
		Bnode* node1 = NULL;
		Bnode* node2 = NULL;
		if (!IsEmpty(LQ)) {
			PopQueue(LQ, &node1);
			printf("第一个出队列的数：%c, 优先级: %d\n", node1->value,
				node1->weight);
		}
		else {
			break;
		}
		if (!IsEmpty(LQ)) {
			Bnode* node3 = new Bnode;
			PopQueue(LQ, &node2);
			printf("第二个出队列的数：%c, 优先级: %d\n", node2->value,
				node2->weight);
			node3->lchild = node1;
			node1->parent = node3;
			node3->rchild = node2;
			node2->parent = node3;
			node3->value = ' ';
			node3->weight = node1->weight + node2->weight;
			printf("合并进队列的数：%c, 优先级: %d\n", node3->value,
				node3->weight);
			EnterQueue(LQ, node3, node3->weight);
		}
		else {
			huff = node1;
			break;
		}
	} while (1);
}
/************************
* 采用递归方式实现前序遍历
*************************/
void PreOrderRec(Btree* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("- %c -", root->value);
	PreOrderRec(root->lchild);
	PreOrderRec(root->rchild);
}
int main(void) {
	Btree* tree = NULL;
	HuffmanTree(tree, 7);
	PreOrderRec(tree);
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78