文档介绍：计算机软件基础课程设计
题目: Huffman编码
学院: 信息与通信工程学院

专业: 通信工程专业
任务书一
题目1
Huffman编码(难度系数10)
主要
内容
完成Huffman编码中各个子函数的全部功能。
学会编写DLL函数。
掌握C++编程环境的基本调试方法,熟练使用可视化C++编程工具。
4、理解信源编码的软件实现过程,掌握数据压缩的基本原理。
设计
要求
1、上交课程设计的书面材料,要求打印。包括课程设计任务书、主要内容,Huffman编码源程序,指定函数的流程图,回答问题的详尽解答等,对程序的功能进行客观评价,明确指出自己编写了哪些具体函数。
2、上交Huffman编码电子版源程序。
3、写出build_tree函数的流程图。
4、回答下面问题。
(1) 给定已压缩文件(见电子版),请用同伴的解码程序还原成*.doc格式,还原后,word文件的内容是什么?
(2) 对于给定的待压缩文件,Huffman编码是否唯一?为什么?
(3) Huffman编码是否能进行无限次数压缩,为什么?,,;,进行第2次压缩,;,进行第3次压缩,......。请画出原始文件和每次压缩后的ASCII码字符概率分布图。
(4) 自己编写一个求素数函数,把它书写成一个动态链接库形式,并在主函数中调用它。尝试把自己编写的Huffman编码程序写成动态链接库和静态链接库形式(无需上交),并比较以下三种EXE文件的大小。
A:调用静态链接库生成的EXE执行文件。
B:调用动态链接库生成的EXE执行文件。
C:直接调用函数生成的EXE执行文件。
5:假设简单马尔可夫信源A={a, b, c},某符号输出与它之前的1个字母相关,信源输出序列为:
a, b, b, c, c, b, a, a, b, b, b, c, c, c, c, a, b, a, b, a, b, c, a, b, a, b
总计26个字符,因为总计只有3个字母,所以未压缩时,每个字母由2bit组成,回答下列问题:
未压缩时,求序列总计的编码长度。
采用通常的Huffman编码(也叫0次序Huffman编码)压缩后,求序列总计的编码长度。
若考虑某符号输出与它之前的1个字母相关,这在日常中是经常见到的,例如英语字母q之后出现字母u的概率接近于1,而其它字母出现的概率近似于0。若采用这种Huffman编码(也叫1次序Huffman编码)压缩后,求序列总计的编码长度。(提示:此时是否只有一棵Huffman树?)
以上3种编码长度是否相同,为什么?
主要
仪器
设备
计算机一台,安装Windows XP 操作系统、Microsoft Visual C++ 、MSDN Library。
主要
参考
文献
[1] 侯俊杰. 深入浅出MFC(第二版)[M]. 武汉:华中科技大学出版社, 2001.
[2] 谭浩强. C程序设计(第二版)[M]. 北京:清华大学出版社, 1999..
[3] 孟彩霞. 计算机软件基础[M]. 陕西:西安电子科技大学出版社, 2003.
[4] 严蔚敏, 吴伟民. 数据结构[M]. 北京:清华大学出版社, 2005.
课程设计进度计划(起止时间、工作内容)
选做Huffman数据压缩题目的同学,2人1组,1人做编码,1人做解码,整个课程设计共20学时,具体进度如下:
4 学时了解课题背景,选题,学习DLL,学习文件读写。
4 学时读文件、初始化Huffman树,计算权重。
4 学时构建Huffman树。
4 学时根据Huffman树,生成代码。
4 学时调试程序,答辩。
课程设计开始日期
2012-9-17
课程设计完成日期
2012-10-15
课程设计实验室名称
计算中心机房
地点
健翔桥校区
摘要
Huffman编码
霍夫曼编码是可变字长编码的一种。它是由Huffman于1952年提出的一种编码方法,该方法完全依据字符出现概率来构造异字头平均长度最短的码字,称之为最佳编码。
在数据通信中,需要将传送的文字转换成二进制的字符,用0、1码的不同排列来表示字符。如果采用等长编码,编码的长度取决于报文中不同字符的个数。如果报文中可能出现26个不同字符,则固定编码长度为5。然而,传送报文时总是希望总长度尽可能短。在实际应用中,各个字符的出现频度或使用次数是不同的,如果让使用平频率高的用短码,使用频率低的用长码,就可以优化整个报文编码