实验1：霍夫曼信源编码综合设计
【实验目的】
通过本专题设计，掌握霍夫曼编码的原理和实现方法，并熟悉利用C语言进行程序设计，对典型的文本数据和图像数据进行霍夫曼编解码。
【预备知识】
1、熵的概念，霍夫曼编码原则
2、数据结构和算法设计
3、C(或C++)编程语言
【实验环境】
1、 设备：计算机一台
2、 软件：C程序编译器
【设计要求】
根据霍夫曼编码原则，利用C语言设计并实现霍夫曼编码和解码程序，要求能够对给出的典型文本数据和图像数据进行霍夫曼编解码，并计算相应的熵和压缩比。
【实验原理】
Huffman编码属于熵编码的方法之一，是根据信源符号出现概率的分布特性而进行的压缩编码。
Huffman编码的主要思想是：出现概率大的符号用长的码字表示；反之，出现概率小的符号用短的码字表示。
Huffman编码过程描述：
1. 初始化:
将信源符号按出现频率进行递增顺序排列，输入集合L;
2. 重复如下操作直至L中只有1个节点:
(a) 从L中取得两个具有最低频率的节点，为它们创建一个父节点；
(b) 将它们的频率和赋给父结点，并将其插入L;
3. 进行编码 ：
从根节点开始，左子节点赋予1，右节点赋予0，直到叶子节点。
【基本定义】
1. 熵和平均编码符号长度
熵是信息量的度量方法，它表示某一事件出现的概率越小，则该事件包含的信息就越多。根据Shannon理论，信源S的熵定义为,其中是符号在S中出现的概率；表示包含在中的信息量，也就是编码所需要的位数
假设符号编码后长度为li (i=1,…,n)，则平均编码符号长度L为：
2. 压缩比
设原始字符串的总长度为Lorig位,编码后的总长度为Lcoded位，则压缩比R为
R = (Lorig - Lcoded)/ Lorig
【例子】
有一幅40个象素组成的灰度图像，灰度共有5级，分别用符号A、B、C、D和E表示，40个象素中出现灰度A的象素数有15个，出现灰度B的象素数有7个，出现灰度C的象素数有7个等等，如表1所示。如果用3个位表示5个等级的灰度值，也就是每个象素用3位表示，编码这幅图像总共需要120位。
表1 符号在图像中出现的数目
符 号
A
B
C
D
E
出现的次数
15
7
7
6
5
根据Shannon理论，这幅图像的熵为
H(S) = (15/40)´(40/15)+(7/40)´(40/7)++(5/40)´(40/5)=2.196
平均编码符号长度L为(15/40)*1+(7/40)*3+(7/40)*3+(6/40)*3+(5/40)*3 ＝ 2.25
根据霍夫曼编码原则可以得到如下的霍夫曼编码表。
表2 霍夫曼编码举例
符号
出现的次数
log2(1/pi)
分配的代码
所需 位数
A
15(0.375)
1.4150
1
15
B
7(0.175)
2.5145
011
21
C
7(0.175)
2.5145
010
21
D
6(0.150)
2.7369
001
18
E
5(0.125)
3.0000
000
15
因而，这副图采用霍夫曼编码的压缩比R为1.3333:1(120:90)。
霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。例如，码串中的第1位为0，那末肯定是符号A，因为表示其他符号的代码没有一个是以0开始的，因此下一位就表示下一个符号代码的第1位。同样，如果出现“110”，那么它就代表符号D。如果事先编写出一本解释各种代码意义的“词典”，即码簿，那么就可以根据码簿一个码一个码地依次进行译码。
【实验步骤】(16学时)
根据提供的示例Huffman编译码器源程序，利用VC++6.0进行编译生成可执行文件，阅读并运行程序。
1、 用Microsoft Office Vision分别画出Huffman编码和译码程序流程图，写出用到的主要数据结构并加以说明。
2、 在Huffman编码器合适位置加入4个函数：calcProbability，calcEntropy，calcAvgSymbolLength，calcCompressionRatio，分别计算信源各符号出现的概率、信源的熵、平均编码符号长度以及压缩比。(自定义函数的参数)
3、 分析霍夫曼编译码码的计算复杂度，定量说明Huffman编码和译码哪种操作更耗时？
4、 设计中遇到的问题，怎样解决问题的。在设计过程中的心得体会。
思考题：
1、 霍夫曼编码是否具有唯一性？
2、 个人对霍夫曼编码方式的不足之处的思考以及怎么样在进行压缩时避免这些问题。
3、 分析霍夫曼编码对文本数据以及图象数据的编码效率，观察与对应信源概率分布的关系。
4、 参考静止图像压缩编码国际标准JPEG，为了提高对图像编码的效率，通常要在霍夫曼编码之前进行什么操作？
5、 。
【实验结果】
一． 译码与编码流程图如下所示：
1.译码流程图
图像显示指令？
接收到有效指令？
主程序
程序初始化
否
返回主程序
调用字符库数据
显示字符
字符显示指令？
是
调用图像库数据
是
图像像素数据？
否
是
否
否
显示图像
JPEG格式图像解码
是
2.编码流程图
图像显示指令？
接收到有效指令？
主程序
程序初始化
否
返回主程序
调用字符库数据
显示字符编码
字符显示指令？
是
调用图像库数据
是
图像像素数据？
否
是
否
否
显示图像编码
JPEG格式图像编码
是
二．四个部分的程序
1.计算每个个符号出现的概率
void calcProbability(int total, SymbolFrequencies *pSF)
{
int i;
float prob[MAX_SYMBOLS];
memset(prob, 0, sizeof(prob));
for(i = 0; i < MAX_SYMBOLS; ++i)
{
if((*pSF)[i])
{
prob[i] = (float)(*pSF)[i]->count / total;
printf("%c, %f\n", (*pSF)[i]->symbol, prob[i]);
}
}
}
2.计算熵
void calcEntrop(SymbolFrequencies *pSF)
{
int i;
float prob[MAX_SYMBOLS];
double entropy;
double difference;
double difference1;
double difference2;
entropy = 0;
for(i = 0; i < MAX_SYMBOLS; ++i)
{
difference1 = log(prob[i]);
difference2 = log(2);
difference = difference1/difference2;
entropy = entropy - prob[i]*difference;
}
printf(" %f\n", entropy);
}
3.计算平均长度
void calcAvgSymbolLength(SymbolFrequencies *pSF, *bits[MAX_SYMBOLS])
{
int i;
double AvgSymbolLength;
AvgSymbolLength = 0;
for(i = 0; i < MAX_SYMBOLS; ++i)
{
AvgSymbolLength = AvgSymbolLength + prob[i]*numbytes[i];
}
printf(" %f\n", AvgSymbolLength);
}
4.计算压缩比
void calcCompressionRatio(int total, AvgSymbolLength)
{
doubule Ratio;
doubule CompressionRatio;
Ratio = total – AvgSymbolLength* MAX_SYMBOLS;
CompressionRatio = Ratio/total;
}
三． 分析耗时
从Huffman编码和译码的代码相比较，可以看出译码的操作更加耗时。
四．遇到的问题
在这次实验中，由于以前并没有学过C++，所以在编程期间遇到很多基础性的问题，对于语言的运用不熟悉，所以导致在写出代码之后编译很久都不成功，但是在老师的辅导下，还是可以做出来一些成果，对于C++的运用有了一定的了解和运用。虽然在这次实验中，并没有将老师所布置的任务全部完成，但是在经过了将近三个星期的反复调试，将最基础最简单的任务完成了。其中或许有些错误，但是已经是尽了全力去完成的。
五． 思考题
1.霍夫曼编码是否具有唯一性？
答：霍夫曼信源不具有唯一性，可将1与0交换。
2.参考静止图像压缩编码国际标准JPEG，为了提高对图像编码的效率，通常要在霍夫曼编码之前进行什么操作？
答：参考静止图像压缩编码国际标准JPEG，为了提高对图像编码的效率，通常要在霍夫曼编码之前进行数据压缩。
3.通过本综合设计，谈谈对“算法+数据结构=程序”的认识
答：程序是计算机指令的某种组合，控制计算机的工作流程，完成一定的逻辑功能，以实现某种任务；算法是程序的逻辑抽象，是解决某类客观问题的数学过程；在这里，数据结构具有两个层面上的涵义--逻辑结构和物理结构：客观事物自身所具有的结构特点，我们将其称之为逻辑结构。算法的确定依赖于数据结构的选择，数据结构的选择制约于算法设计的复杂程度--算法 + 数据结构 = 程序。
7
展开阅读全文
