jpg与哈夫曼

发表于 | 分类于

哈夫曼

1.原理代码

c语言给定权值建立，编码，解码哈夫曼(默认6位ABCDEF)

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
#include<stdio.h>
#include<string.h>
typedef struct {
	int num;
	int p,l,r;
	
}h;
h hf[12]={0};
int s1,s2;
void select(int n)
{
	s1=0;
	s2=0;
	int i=1; 
	int ls=10000;
	for(i;i<=n;i++)
	{
		if(hf[i].p==0)
		{
			if(hf[i].num<ls)
			{
				s1=i;
				ls=hf[i].num;
			}
		}
	}
ls=10000;
	for(i=1;i<=n;i++)
	{
		if(hf[i].p==0&&i!=s1)
		{
			if(hf[i].num<ls)
			{
				s2=i;
				ls=hf[i].num;
			}
		}
	}
	
	
	
	
	
}
int main(void)
{
	int w[7];
	int i;
	for(i=1;i<=6;i++)
	{
		scanf("%d",&w[i]);
		hf[i].num=w[i];
	}
	for(i=7;i<12;i++)
	{
		select(i-1);
		hf[i].num=hf[s1].num+hf[s2].num;
		hf[i].l=s1;hf[i].r=s2;
		hf[s1].p=i;hf[s2].p=i;		
	}
	
	char bianma[7][13];
	char ls[13];
	ls[12]=0;
	int start;
	int n=12;
	int c;
	int p;
	for(i=1;i<=6;i++)
	{
		start=n;
		c=i;
		p=hf[i].p;
		while(p!=0)
		{
			start--;
			if(hf[p].l==c)
			{
				ls[start]='0';
			}
			else
			{
				ls[start]='1';
			}
			c=p;
			p=hf[p].p;
			
			
			
		}
		strcpy(bianma[i],&ls[start]);
		
	}
	
	for(i=1;i<=6;i++)
	{
		printf("%c:%s\n",'A'+i-1,bianma[i]);
	}
	
	
	char A[100];
	scanf("%s",A);
	for(i=0;i<strlen(A);i++)
	{
		printf("%s",bianma[A[i]-'A'+1]) ;
	}
	printf("\n");
	
	
	scanf("%s",A);
	i=0;
	
	int j=11;
	while(A[i]!=0)
	{
		 if(A[i]=='0')
		 {		 	
		
		 	j=hf[j].l;
		 	
		 }
		 else
		 {
	
		 	j=hf[j].r;
		 }
		if(hf[j].l==0&&hf[j].r==0)
		{
			printf("%c",'A'+j-1);
			j=11;
	
		}
		i++;
		
	}
	
	return 0;
 }

2.实用代码

题目：
已知某段通信报文内容，对该报文进行哈弗曼编码，并计算平均码长。
(1)统计报文中各字符出现的频度。(字符集范围为52个英文字母，空格，英文句号。报文长度<=200)
(2)构造一棵哈弗曼树，依次给出各字符编码结果。
(3)给字符串进行编码。
(4)给编码串进行译码。
(5)计算平均码长。
规定：
(1)结点统计：以ASCII码的顺序依次排列，例如：空格，英文句号，大写字母，小写字母。
(2)构建哈弗曼树时：左子树根结点权值小于等于右子树根结点权值。
(3)选择的根节点权值相同时，前者构建为双亲的左孩子，后者为右孩子。
(4)生成编码时：左分支标0，右分支标1。
输入
第一部分：报文内容，以’#’结束。
第二部分：待译码的编码串。
输出
依次输出报文编码串、译码串、平均码长，三者之间均以换行符间隔。
平均码长，保留小数点2位
AC代码：

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
#include<stdio.h>
#include<string.h>
typedef struct {
	int num;
	int p,l,r;
	
}h;
int charnum=54;
 //a-b A-Z ' ' .
h hf[108]={0};
char bianma[55][108+1];
int s1,s2;
void select(int n)
{
	s1=0;
	s2=0;
	int i=1; 
	int ls=100000;
	for(i;i<=n;i++)
	{
		if(hf[i].p==0&&hf[i].num!=0)
		{
			if(hf[i].num<ls)
			{
				s1=i;
				ls=hf[i].num;
			}
		}
	}
ls=100000;
	for(i=1;i<=n;i++)
	{
		if(hf[i].p==0&&i!=s1&&hf[i].num!=0)
		{
			if(hf[i].num<ls)
			{
				s2=i;
				ls=hf[i].num;
			}
		}
	}
	
	
	
	
	
}
int main(void)
{
	int i;
	
	char wenzhang[1000];
	gets(wenzhang);
	int weizi;
	for(i=0;i<1000;i++)
	{
		if(wenzhang[i]=='#')
		break;
		if(wenzhang[i]>='a'&&wenzhang[i]<='z')
		{
			weizi=wenzhang[i]-'a'+1+2+26;
			hf[weizi].num++;
		}
		else if(wenzhang[i]>='A'&&wenzhang[i]<='Z')
		{
			weizi=wenzhang[i]-'A'+1+2;
			hf[weizi].num++;
		}
		else if(wenzhang[i]==' ')
		{
			hf[1].num++;
		}
		else if(wenzhang[i]=='.')
		{
			hf[2].num++;
		}
		
	}
	int synum=0;
	float sum=0;
	int maxsum=0;
	for(i=1;i<=charnum;i++)
	{
		if(hf[i].num!=0)
		{
			synum++;
			maxsum+=hf[i].num;
		}
	}
	
	for(i=charnum+1;i<synum+charnum;i++)
	{
		select(i-1);
		hf[i].num=hf[s1].num+hf[s2].num;
		hf[i].l=s1;hf[i].r=s2;
		hf[s1].p=i;hf[s2].p=i;		
	}
	char ls[charnum*2+1];
	ls[charnum*2]=0;
	int start;
	int n=charnum*2;
	int c;
	int p;
	for(i=1;i<=charnum;i++)
	{
		if(hf[i].num==0)
		{
			continue;
		}
		start=n;
		c=i;
		p=hf[i].p;
		while(p!=0)
		{
			start--;
			if(hf[p].l==c)
			{
				ls[start]='0';
			}
			else
			{
				ls[start]='1';
			}
			c=p;
			p=hf[p].p;
			
			
			
		}
		strcpy(bianma[i],&ls[start]);
		
	}
	
	for(i=1;i<=charnum;i++)
	{
		if(hf[i].num!=0)
		{
			sum=sum+((float)strlen(bianma[i]))*(hf[i].num/(float)maxsum);
			
		}
	}
	
	
	char A[10000];
	for(i=0;i<201;i++)
	{
		if(wenzhang[i]=='#')
		break;
		if(wenzhang[i]>='a'&&wenzhang[i]<='z')
		{
			weizi=wenzhang[i]-'a'+1+2+26;
			printf("%s",bianma[weizi]);
		}
		else if(wenzhang[i]>='A'&&wenzhang[i]<='Z')
		{
			weizi=wenzhang[i]-'A'+1+2;
			printf("%s",bianma[weizi]);
		}
		else if(wenzhang[i]==' ')
		{
			printf("%s",bianma[1]);
		}
		else if(wenzhang[i]=='.')
		{
			printf("%s",bianma[2]);
		}	
	}
	printf("\n");
//		for(i=1;i<55;i++)
//	{
//		if(i==1)
//		printf(" :%s",bianma[i]);
//		if(i==2)
//		printf(".:%s",bianma[i]);
//		if(i>2&&i<=28)
//		printf("%c:%s",i-3+'A',bianma[i]);
//		if(i>28&&i<=55)
//		printf("%c:%s",i-29+'a',bianma[i]);
//		printf("\n");
//
//	}
	gets(A);
	i=0;
	
	int j=synum+charnum-1;
	while(A[i]!=0)
	{
		 if(A[i]=='0')
		 {		 	
		
		 	j=hf[j].l;
		 	
		 }
		 else
		 {
	
		 	j=hf[j].r;
		 }
		if(hf[j].l==0&&hf[j].r==0)
		{			
        	if(j==1)
		printf(" ");
		if(j==2)
		printf(".");
		if(j>2&&j<=28)
		printf("%c",j-3+'A');
		if(j>28&&j<=55)
		printf("%c",j-29+'a');
			
			
			
			j=synum+charnum-1;
	
		}
		i++;
		
	}
	
	printf("\n");
	printf("%.2f",sum);
	
	return 0;
 }

踩到的坑：

1.虽然预留了全部符号的树，但是报文中使用了的字符要现统计，这点与上题大不相同，所造成的bug也很多：hu树的建立问题尤为突出
2.编码时仍按全部字符对号入座，文中没有的编码空字符串。这样便于查找。
3.平均码长为：编码长度乘以出现频率之和，在本题中为：编码长度乘以（该字符在文中的出现次数/文章总长度）

jpg

JPEG（Joint Photographic Experts Group）是联合图像专家小组的英文缩写。它由国际电话与电报咨询委员会CCITT（The International Telegraph and Telephone Consultative Committee）与国际标准化组织ISO于1986年联合成立的一个小组，负责制定静态数字图像的编码标准。
小组一直致力于标准化工作，开发研制出连续色调、多级灰度、静止图像的数字图像压缩编码方法，即JPEG算法。JPEG算法被确定为国际通用标准，其适用范围广泛，除用于静态图像编码外，还推广到电视图像序列的帧内图像压缩。而用JPEG算法压缩出来的静态图片文件称为JPEG文件，扩展名通常为.jpg、.jpe*.jpeg。
JPEG专家组开发了两种基本的压缩算法、两种数据编码方法、四种编码模式。具体如下：
压缩算法：
l 有损的离散余弦变换（Discrete Cosine Transform，DCT）；
l 无损的预测技术压缩。
数据编码方法：
l 哈夫曼编码；
l 算术编码；
编码模式：
l 基于DCT顺序模式：编/解码通过一次扫描完成；
l 基于DCT递进模式：编/解码需要多次扫描完成，扫描效果从粗糙到精细，逐级递进；
l 无损模式：基于DPCM，保证解码后完全精确恢复到原图像采样值；
l 层次模式：图像在多个空间多种分辨率进行编码，可以根据需要只对低分辨率数据作解码，放弃高分辨率信息。
在实际应用中，JPEG图像使用的是离散余弦变换、哈夫曼编码、顺序模式。

jpg解码时的步骤

读出文档信息：

  1. 大体结构：
    JFIF格式的JPEG文件(*.jpg)的一般顺序为：
    SOI(0xFFD8)
    APP0(0xFFE0)
    [APPn(0xFFEn)]可选
    DQT(0xFFDB)
    SOF0(0xFFC0)
    DHT(0xFFC4)
    SOS(0xFFDA)
    压缩数据
    EOI(0xFFD9)
  2. 字的高低问题
    JPEG文件格式中，一个字（16位）的存储使用的是 Motorola 格式,也就是低地址存高字节(人类习惯)
  3. 读出哈夫曼数据表
    DHT内提供哈夫曼表数据：ID与类型，不同位数的码字数量，编码内容
    开始为最小长度全为0，之后相同长度的在其上末位加一，下一个的位数大于前面时当前末位加一再补0到规定位数。

未完待续……