基于哈夫曼编码实现文件压缩与解压缩

发表于 | 分类于
字数统计: 1,146字 | 阅读时长 ≈ 5 分钟

基于哈夫曼编码实现文件压缩

是在学习数据结构（严蔚敏版）书中哈夫曼树及其应用后对书中伪代码的实现和完善，采用哈夫曼静态编码的方式，通过对数据进行两遍扫描，第一次统计出现的字符频次，进而构造哈夫曼树，第二遍扫描数据根据得到的哈夫曼树对数据进行编码。

对于其中的加密编码只是简单的将用户输入的密码用特殊的标识位拼接成字符串加入需要统计的数据，可以在拥有哈夫曼编码表以及加密后的文本情况下进行解密

哈夫曼树

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树的构造过程

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： (1)
将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2)
在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树

在构造哈夫曼树时首先选择权小的，这样保证权大的离根较近，这种生成算法是一种典型的贪心法。

哈夫曼编码思想

为了使压缩后的数据文件尽可能短，可采用不定长编码。而为了在对压缩文件进行解码时不产生二义性，确保正确解码应该采用前缀编码的形式(即要求一个字符的编码不能是另一个字符编码的前缀)。而哈夫曼编码是最优前缀编码。

例如：有一个数据序列ABACCDAA则编码为A(0),B(10),C(110),(D111)，压缩后为010011011011100。

部分实现代码

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
//哈夫曼树存储表示 
typedef struct {
	int  weight;  //节点的权值 
	int parent,lchild,rchild;  //节点的双亲，左孩子，右孩子的下标 
} HTNode,*HuffmanTree;
 
//存储数据扫瞄统计结果 
typedef struct {
	char* data;
	int* num;
	int length;
} TNode;
//存储文件读入哈夫曼编码结果 
typedef struct {
	char *data;
	char** HM;
} Code;

//存储哈夫曼编码结果
typedef char** HuffmanCode;
//选取节点构造哈夫曼树 
void Select(HuffmanTree &HT,int m,int& s1,int& s2) {
	int k,j,n,min=32767;
	for(k=1; k<=m; k++) {
		if(HT[k].parent==0)
			if(HT[k].weight<=min) {
				j=k;
				min=HT[k].weight;
			}
	}
	s1=j;
	HT[j].parent=1;
	min=32767;
	for(k=1; k<=m; k++) {
		if(HT[k].parent==0)
			if(HT[k].weight<=min) {
				n=k;
				min=HT[k].weight;
			}
	}
	s2=n;
}
//构造哈夫曼树 
void CreateHuffmanTree (HuffmanTree &HT,TNode T,int length) {
	int m,i,s1,s2;
	//初始化 
	if(length<=1)
		return;
	m=2*length-1;
	HT=new HTNode[m+1];
	for(i=1; i<=m; ++i) {
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(i=1; i<=length; ++i)
		HT[i].weight=T.num[i-1];
	//通过n-1次的选择，删除，合并来创建哈夫曼树 
	for(i=length+1; i<=m; i++) {
		Select(HT,i-1,s1,s2);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
}
//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中 
void CreatHuffmanCode (HuffmanTree HT,HuffmanCode &HC,int n) {
	int i,f,c,start;
	HC=new char*[n+1];
	char* cd=new char[n];
	cd[n-1]='\0';
	for(i=1; i<=n; i++) {
		start=n-1;
		c=i;
		f=HT[i].parent;
		while(f!=0) {
			--start;
			if(HT[f].lchild==c)
				cd[start]='0';
			else
				cd[start]='1';
			c=f;
			f=HT[f].parent;
		}
		HC[i]=new char[n-start];
		strcpy(HC[i],&cd[start]);
	}
	delete cd;
}

有兴趣可以下载源码查看https://pan.baidu.com/s/1skAP5lr

参考 数据结构：C语言版/严蔚敏，李冬梅，吴伟民编