songsong的垃圾堆

收废铜烂铁~

0%

哈弗曼编码与译码

发表于 更新于 阅读： Valine：
本文字数： 2.5k 阅读时长 ≈ 9 分钟

哈弗曼树

  • 定义：

    假设有m个权值{w1，w2，…wm}，可以构造一颗含n个叶子结点的二叉树，每个叶子结点的权重为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树或哈弗曼树。

  • 特点：

    权值越大的结点离根节点越近。根据这个特点可以构造哈弗曼树。

    哈弗曼树的构造算法

  1. 根据给定的n个权值{w1，w2，…wn}，构造n棵只有根结点的二叉树。构成森林F。

  2. 在森林F中选取两棵根结点权值最小的树作为左右子树构造一颗新的二叉树，置新二叉树根结点权值为其左右子树根节点权值之和。

  3. 从森林F中删除这两棵树，同时将新得到的二叉树加入森林F中。

  4. 重复（2）和（3），直到F只含一棵树为止，这棵树即是 哈弗曼树

    演示过程：
    在这里插入图片描述
    回到目录

    哈弗曼算法的实现

  • 哈弗曼的存储表示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    typedef struct {

    	char letter, *code;		//letter字符，code生成的哈弗曼编码

    	int weight;				//权重

    	int parent, lchild, rchild;

    }HTNode, *HuffmanTree;

  • 构造哈弗曼树

    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
    /*在HT[1...i]中选择parent为0且权值最小的结点  

        返回该结点的下标值  

        此函数被Select函数调用 
    */
    int Min(HuffmanTree &HT,int i) {   
        int j;  
        unsigned int k = UINT_iMAX;						//假设各结点的权值不会超过UINT_MAX  
        int flag;  

        for(j = 1; j <= i; ++j){  

            if(HT[j].weight < k && HT[j].parent == 0){	//用父结点是否为0来判断此结点是否已经被选过  

                k = HT[j].weight;  						 //找到最小值 
                flag = j;  
            }  
        }  

        HT[flag].parent = 1;							//作个标记，说明已经被选择了。

        return flag;  
    }  

      
    //在HT[1...i]中选择parent为0且权值最小的两个结点，其序号分别为s1,s2  
    //s1 <= s2 
    void Select(HuffmanTree &HT, int i, int &s1, int &s2) {  
        s1 = Min(HT,i);  
        s2 = Min(HT,i);  
    }  

    void CreateHuffmanTree(HuffmanTree &HT, char t[], int w[]){		//t[]为a[]形参，即字符，w[]为b[]形参，即权值 

    	int m=2*n-1; 				//总共需要2n－1个节点
    	int i, s1, s2;

    	if(n<=1)					//如果只有一个就不用创建
    		return ;

    	HT=new HTNode[m+1];			//开辟空间

    	for(i=1; i<=n; i++){		//将1-n号单元中的双亲、左孩子、右孩子的下标都初始化为0 		
    	
    		HT[i].parent=0;
    		
    		HT[i].lchild=0;
    	
    		HT[i].rchild=0;
    		
    		HT[i].code='\0';
    	
    		HT[i].letter=t[i-1];
    	
    		HT[i].weight=w[i-1]; 	
    	}

    	for(i=n+1; i<=m; i++)	{ 		//初始化	

    		HT[i].code='\0';

    		HT[i].parent=0;

    		HT[i].lchild=0;

    		HT[i].rchild=0;

    		HT[i].letter=' ';

    		HT[i].weight=0;

    	}

    	cout<<"-------------------------"<<endl;		//初始化结束，以下开始创建哈夫曼树 
    	
    	for(i=n+1; i<=m; i++){

    		Select(HT, i-1,s1, s2);						//在n个数中找出权值最小的两个
    		
    		HT[s1].parent=i;
    		HT[s2].parent=i;							//将他们两个的parent节点设置为i;	
    	
    		HT[i].lchild=s1;
    		HT[i].rchild=s2;							//把这两个分别当作左右节点
    		HT[i].weight=HT[s1].weight+HT[s2].weight;	//他们两个的双亲的权值为他们两个的和。 
    	
    	}
    }

    回到目录

哈弗曼不等长编码

在构造哈弗曼树之后，求哈弗曼编码的思想是：
依次以叶子为出发点，向上回溯至根结点为止。回溯时走左分支则生成代码0，走右分支则生成代码1。

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
void CreatHuffmanCode(HuffmanTree HT){

	int start, c, f;

	int i;

	char *cd=new char [n]; 		//临时存放编码 
	
	cd[n-1]='\0';

	cout<<"字符编码为："<<endl;

	for(i=1; i<=n; i++){

		start=n-1;	//开始时指向编码结束符位置 
	
		c=i;	
		f=HT[i].parent;	//f指向节点c的双亲节点 
	
		while(f!=0){	//从叶子节点开始向上回溯，直到根节点 

			--start;

			if(HT[f].lchild==c){	//如果是左孩子，则生成代码‘0 ’ 
				
				cd[start]='0';
			}

			else{			//如果是左孩子，则生成代码‘1 ’ 
				cd[start]='1';
			}

			c=f;

			f=HT[f].parent;	//继续向上回溯 

		}		
	
		HT[i].code=new char[n-start];
	
		strcpy(HT[i].code,&cd[start]);
	
		cout<<HT[i].letter<<":"<<HT[i].code<<endl;

	}
	
	delete cd;
	
}

回到目录

哈弗曼译码

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
void HuffmanTreeYima(HuffmanTree HT,char cod[],int b) {          //译码 

	char code[100]; 

    char temp[50]; 

    int t=0; 

	int s=0; 

 	int xx=0;									//记录从第几位起不能译码 

    for(int i=0; i<b; i++){ 
	
		temp[t++]=cod[i];    		 			//读取字符，直到找到编码 

	    temp[t] = '\0';       		 			//有效字符串
	
	    for(int j=1;j<=n;j++){       			//依次与所有字符编码开始匹配
		
	  	 	if (!strcmp(HT[j].code,temp)){      //匹配成功   
	
	    			code[s]=HT[j].letter;   	//将字符保存到code中
	
	                s++; 
	
	  				xx+=t;
	
	                strcpy(temp,"");            //将TEMP置空 
	
	                t=0;         				//t置空
	
	                break;
	
	 	  	}	
	  	} 	
	} 

	if(t==0){     //t如果被置空了，表示都匹配出来了，打印译码

	 	code[s]='\0';

	    cout<<"译码为:"<<endl; 

	    cout<<code<<endl;
	}
	else{                //t如果没有被置空 ， 源码无法被完全匹配
	  	cout<<"二进制源码有错！从第"<<xx+1<<"位开始"<<endl;
	}

}

回到目录

总的代码：

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
#include<iostream>
#include<string.h>
#define  UINT_iMAX 10000 
using namespace std;

typedef struct {

	char letter, *code;		//letter字符，code生成的哈弗曼编码
	
	int weight;				//权重

	int parent, lchild, rchild;

}HTNode, *HuffmanTree;
 

int n;	//全局变量会被默认赋值0 
char coding[100];


/*在HT[1...i]中选择parent为0且权值最小的结点  

    返回该结点的下标值  

    此函数被Select函数调用 
*/
int Min(HuffmanTree &HT,int i) {   

    int j;  

    unsigned int k = UINT_iMAX;	//假设各结点的权值不会超过UINT_MAX  

    int flag;  

    for(j = 1; j <= i; ++j){  

        if(HT[j].weight < k && HT[j].parent == 0){	//用父结点是否为0来判断此结点是否已经被选过  

            k = HT[j].weight;  //找到最小值 
            flag = j;  
        }  
    }  

    HT[flag].parent = 1;	//作个标记，说明已经被选择了。

    return flag;  

}  

  
//在HT[1...i]中选择parent为0且权值最小的两个结点，其序号分别为s1,s2  
//s1 <= s2 
void Select(HuffmanTree &HT, int i, int &s1, int &s2) { 
 
    s1 = Min(HT,i);  
    s2 = Min(HT,i);  
}  

void CreateHuffmanTree(HuffmanTree &HT, char t[], int w[]){		//t[]为a[]形参，即字符，w[]为b[]形参，即权值 

	int m=2*n-1; 	//总共需要2n－1个节点
	int i, s1, s2;

	if(n<=1)	//如果只有一个就不用创建
		return ;

	HT=new HTNode[m+1];	//开辟空间

	for(i=1; i<=n; i++){		//将1-n号单元中的双亲、左孩子、右孩子的下标都初始化为0 		
	
		HT[i].parent=0;
		
		HT[i].lchild=0;
	
		HT[i].rchild=0;
		
		HT[i].code='\0';
	
		HT[i].letter=t[i-1];
	
		HT[i].weight=w[i-1]; 	
	}

	for(i=n+1; i<=m; i++)	{ 		//初始化	

		HT[i].code='\0';

		HT[i].parent=0;

		HT[i].lchild=0;

		HT[i].rchild=0;

		HT[i].letter=' ';

		HT[i].weight=0;

	}

	cout<<"-------------------------"<<endl;		//初始化结束，以下开始创建哈夫曼树 
	
	for(i=n+1; i<=m; i++){

		Select(HT, i-1,s1, s2);//在n个数中找出权值最小的两个
		
		HT[s1].parent=i;
		HT[s2].parent=i;//将他们两个的parent节点设置为i;	
	
		HT[i].lchild=s1;
		HT[i].rchild=s2;//把这两个分别当作左右节点
		HT[i].weight=HT[s1].weight+HT[s2].weight;//他们两个的双亲为他们两个的和。 
	
	}
}

void CreatHuffmanCode(HuffmanTree HT){

	int start, c, f;

	int i;

	char *cd=new char [n]; 		//临时存放编码 
	
	cd[n-1]='\0';

	cout<<"字符编码为："<<endl;

	for(i=1; i<=n; i++){

		start=n-1;	//开始时指向编码结束符位置 
	
		c=i;	
		f=HT[i].parent;	//f指向节点c的双亲节点 
	
		while(f!=0){	//从叶子节点开始向上回溯，直到根节点 

			--start;

			if(HT[f].lchild==c){	//如果是左孩子，则生成代码‘0 ’ 
				
				cd[start]='0';
			}

			else{			//如果是左孩子，则生成代码‘1 ’ 
				cd[start]='1';
			}

			c=f;

			f=HT[f].parent;	//继续向上回溯 

		}		
	
		HT[i].code=new char[n-start];
	
		strcpy(HT[i].code,&cd[start]);
	
		cout<<HT[i].letter<<":"<<HT[i].code<<endl;

	}
	
	delete cd;
	
}
 
void HuffmanTreeYima(HuffmanTree HT,char cod[],int b) {          //译码 

	char code[100]; 

    char temp[50]; 

    int t=0; 

	int s=0; 

 	int xx=0;									//记录从第几位起不能译码 

    for(int i=0; i<b; i++){ 
	
		temp[t++]=cod[i];    		 			//读取字符，直到找到编码 

	    temp[t] = '\0';       		 			//有效字符串
	
	    for(int j=1;j<=n;j++){       			//依次与所有字符编码开始匹配
		
	  	 	if (!strcmp(HT[j].code,temp)){      //匹配成功   
	
	    			code[s]=HT[j].letter;   	//将字符保存到code中
	
	                s++; 
	
	  				xx+=t;
	
	                strcpy(temp,"");            //将TEMP置空 
	
	                t=0;         				//t置空
	
	                break;
	
	 	  	}	
	  	} 	
	} 

	if(t==0){     //t如果被置空了，表示都匹配出来了，打印译码

	 	code[s]='\0';

	    cout<<"译码为:"<<endl; 

	    cout<<code<<endl;
	}
	else{                //t如果没有被置空 ， 源码无法被完全匹配
	  	cout<<"二进制源码有错！从第"<<xx+1<<"位开始"<<endl;
	}

} 

int main(){  

    HuffmanTree HT;   

    char a[20], buff[20], p;	//a存放字符 buff为输入的字符串 p为输入译码时的字符 

    int b[20];//存放权值信息 

    int  i, j;

	int symbol=1, x, k; //译码时做判断用的变量  

    cout<<"请输入一段字符:";

    cin.getline(buff,10);		//接收10个字符到m中，其中最后一个为'\0'.

    int len=strlen(buff); 

 	for (i=0;i<len;i++) {
 		
		for(j=0; j<n;  j++) {

		   if (a[j]==buff[i]) {
		
		   	 	b[j]=b[j]+1;		
		    	break;		
		   }
		
		}

		if (j>=n){

			a[n]=buff[i];

			b[n]=1;

			n++;

		}

 	}

	cout<<"字符和权值信息如下"<<endl;

	for (i=0;i<n;i++){

	  cout<<"字符："<<a[i]<<"  权值："<<b[i]<<endl;

	}

    CreateHuffmanTree(HT, a, b);

    CreatHuffmanCode(HT);

    

	cout<<"译码："<<endl;
	
 	while(1){ 

  		cout<<"请输入要译码的二进制字符串,输入'#'结束：";

   		x=1;		//判断是否有非法字符只能是0 1 

   		k=0;		//作为循环变量来使coding[k]=输入的字符 

   		symbol=1;	//判断是否输入结束 

 		while(symbol){ 

   			cin>>p; 

   			if(p!='1'&&p!='0'&&p!='#'){ //若存在其它字符，x设为0，表示输入的不是二进制
   			 	x=0;
   			}

  			coding[k]=p;

   			if(p=='#')  	symbol=0;  //#号结束标志

  			k++;

  		}

 		if(x==1){
  			HuffmanTreeYima(HT,coding,k-1);        //进行译码
  		}
  		else{
  			 cout<<"有非法字符！"<<endl;
  		}

		cout<<"是否继续?(Y/N):";
		cin>>p;
		
		if(p=='y'||p=='Y')	 continue;		
		else 	break;

 	}
    return 0;  
}

回到目录

运行结果：

在这里插入图片描述
上面运行结果存储变化：
HT的初态：
在这里插入图片描述
HT的终态：
在这里插入图片描述
回到目录

------------- Thank you for reading -------------
Title - Artist
0:00