《压缩软件课程设计报告-并行与串行数据结构与算法》由会员分享，可在线阅读，更多相关《压缩软件课程设计报告-并行与串行数据结构与算法（20页珍藏版）》请在金锄头文库上搜索。
1、华 中 科 技 大 学 计 算 机 科 学 与 技 术 学 院课 程 设 计 报 告课程设计报告题目：简单压缩软件课程名称：并行与串行数据结构与算法专业班级：ACM1301学号：姓名：指导教师：报告日期：2015年9月27日计算机科学与技术学院I任务书p 设计内容本实验要求实现一个简单的压缩软件。压缩软件由两部分编码器和译码器组成。编码器位于发送端，可以将文件进行压缩，体积减小；译码器位于接收端，可以将文件进行解压，恢复原文件。p 设计要求（1） 压缩解压过程保证无损（2） 实现两种压缩策略，第一种压缩文件后缀名记为.CS，要求在保证一定的压缩率的情况下体现压缩速率；第二种压缩文件后缀名记为.
2、SCS，强调压缩率，但时间也需要比较合理（3） 压缩文件中保存了需要解压的全部信息（4） 具有图形化进度条显示压缩过程和解压过程的进度和显示估计剩余时间的功能（5） 具有图形化选项选择将编码信息输出到指定磁盘目录的功能（6） 实验所使用的算法不限，实验报告中需要详细描述使用的算法策略。（7） 软件的衡量标准对比标准的压缩软件，实验检查时需要准备一定的统计对比信息加以佐证，实验报告中也需要对压缩软件的优劣进行详细的建模分析。p 参考文献1LZW for GIF 算法原理实现，http:/ 几种压缩算法，http:/ 而解决这一问题的最常用的就是数据压缩技术。计算机为什么需要数据压缩技术呢? 一是
3、因为容量的限制, 促使各程序员开始开发各种压缩软件对软件进行压缩。二是信息通讯量的限制, 人们希望在网上下载的软件越小越好。随着数码技术的发展,压缩技术也在不断发展, 因为硬盘和光盘的空间毕竟是有限的, 而游戏、音频、视频、图片在计算机中应用中越来越普遍, 但它们又非常占据空间, 所以压缩技术前景非常广阔并且不断在发展。与压缩相关的有两个步骤: 第一个步骤是压缩, 第二个步骤则是解压缩。在计算机中所有信息都是以二进制代码形式存在的, 这些信息具体形式可以是声音、图像、软件, 因此我们把只用二进制编码的像片、音频等可以称为数码像片或数码音频。以数码图片为例, 压缩就是要把的图像的二进制代码中冗长
4、的、重复的代码遵循一定的算法用简短的代码来代替。如果把软件中的冗长的、重复的代码如果都按一定的算法用简短的代码来替换的话, 最后重新生成的软件一定会小得多。这个过程, 就叫做压缩。一般而言, 被压缩的文件是不能直接运行的, 那是因为它的代码都被简化了。被压缩了的文件只是变小了空间而已, 是不能直接使用的。要想再使用这些压缩过的文件, 就必须解压缩。解压缩文件要用到对应的压缩软件。解压缩的过程正好和压缩的过程相反, 即通过算法将简短的压缩代码还原为程序的真正代码。在多媒体应用中，数字化信息的数据量相当庞大，对存储器的存储器的存储容量、网络带宽以及计算机的处理速度都有较高的要求，完全通过增加硬件设
5、施来满足现实需求是不可能的，必须采用有效的压缩技术。多媒体数据之所以能够进行压缩时因为原始数据存在以下三种形式的冗余：（1）编码冗余。如频率相差很大的像素用相同长度的代码进行编码；（2）像素间冗余。如相邻像素间具有时域或空域相关性；（3）视觉信息冗余。即人的视觉图像边缘急剧变化不敏感，对色彩的分辨能力弱，只对图像的亮度敏感，对经压缩和解压缩后的图像失真难以察觉或影响甚微。这些数据本身的冗余和人的感官特性构成了多媒体数据压缩的基础，同时也确定了数据压缩的研究方向。1.1.1数据压缩标准从20世纪80年代开始，世界上已有几十家公司纷纷投入到多媒体计算机系统的研制和开发工作。20世纪90年代已有不少
6、精彩的多媒体产品问世，诸如荷兰菲利浦和日本索尼联合推出的CD-I，苹果公司Macintosh为基础的多媒体功能的计算机系统，Intel和IBM公司联合推出的DVI。此外，还有Microsoft公司的MPC及苹果的Quick Time等，这些多媒体计算机系统各具特色，丰富多彩，竞争异常激烈。具有人机交互特色的多媒体技术，使计算机进入普通家庭，进入人们的生活、学习、娱乐及人们的精神生活领域。人们像使用家用电器一样地使用计算机。计算机能听懂人的话语；计算机成为能讲话的实用型产品进入市场，也为时不远了。Internet技术的迅猛发展与普及，推动了世界范围的信息传输和信息交流。在色彩缤纷、变幻无穷的多媒
7、体世界中，用户如何选择产品，如何自由地组合、装配来自不同厂家的产品部件，构成自己满意的系统，这就涉及一个不同厂家产品的兼容性问题，因此需要一个全球性的统一的国际技术标准。国际标准化协会（International Standardization Organization，ISO）、国际电子学委员会（International Electronics Committee，IEC）、国际电信协会（International Telecommunication Union，ITU）等国际组织及CCITT，于20世纪90年代领导制定了多个重要的多媒体国际标准。如H.261、H.263、JPEG和MPE
8、G等标准。H.261是被可视电话、电视会议中采用的视频、图像压缩编码标准，由CCITT制定，1990年12月正式批准通过；JPEG是由ISO与CCITT成立的“联合图片专家组（Joint Photographic Experts Group，JPEG）”制定的，用于灰度图、彩色图的连续变化的静止图像编码标准，于1992年正式通过；MPEG是以H.261标准为基础发展而来的。它是由IEC和ISO成立的“运动图像专家组（Moving Picture Experts Group，MPEG）”制定的，于1992年通过了MPEG-1，并在后来的几年中，陆续推出了MPEG-2、MPEG-4、MPEG-7等
9、标准。1.1.2数据压缩评价（1）压缩比,即压缩前后的数据量之比,一般来说,压缩比要在一定的质量主观满意度基础上尽可能的大。（2）算法的复杂性和运算速度,实现压缩的算法要简单,以便在有限的硬件资源上加快压缩解压缩的速度,尽可能地实时压缩解压缩。（3）失真度,即解压后数据的恢复质量要好,尽可能地完全再现原始数据。1.2国内外研究现状从国际数据压缩技术的发展尤其是MPEG的发展可以看出，基于内容的图像压缩编码方法是未来编码的发展趋势。它不仅能满足进一步获得更大的图像数据压缩比的要求，而且能够实现人机对话的功能。另外，任意形状物体的模型建立的关键问题还没有解决，这严重影响其应用的广泛性。因此，视频编
10、码将朝着多模式和跨模式的方向发展。通过元数据进行编码也是今后编码的发展方向。元数据是指详细的描述音/视频信息的基本元素，利用元数据来描述音视频对象的同时也就完成了编码，因为此时编码的对象是图像的一种描述而不再是图像本身。从另一个角度来说，进一步提高压缩比，提高码流的附属功能（码流内容的可访问性、抗误码能力、可伸缩性等）也将是未来的编码的两个发展方向。当前，压缩域处理技术作为新兴的技术还远未成熟，许多问题有待解决，其中缺乏统一的理论支持是主要问题。未来的研究工作主要集中在四个方面：设计新的压缩算法，支持对压缩域数据直接操作；研究用小波、矢量量化、分形等压缩算法的多媒体数据的压缩处理算法；设计专用
11、的压缩域数据处理芯片；如何将用于多媒体内容的传输和使用的各种标准结合起来，形成一个用于多媒体的统一的体系结构。未来多媒体数据压缩技术的发展趋势将是基于内容的压缩。另外，图像压缩技术、视频技术与网络技术相结合的应用前景十分可观，如远程图像传输系统、动态视频传输（可视电话）、电视会议系统等已经开始商品化，MPEG标准与视频技术相结合的产物家用数字视盘机、VideoCD系统等已进入市场。可以预计，这些技术和产品的发展将对21世纪的社会进步产生中大影响。1.3课程设计的主要研究工作本次课程设计主要研究如何在无损的前提下实现数据的压缩，并用不同的压缩策略分别对数据进行压缩时间优先和压缩率优先两种压缩。具
12、体实现中，我使用了LZW算法和Huffman编码算法对数据进行压缩，对于较小的文件，LZW算法压缩时间短，Huffman编码算法压缩率低，而对于较大的文件，前者压缩率低，后者压缩时间短。-2系统需求分析与总体设计2.1系统需求分析本课程设计编写的压缩软件要求压缩解压过程保证无损，并实现两种压缩策略，第一种压缩文件后缀名记为.CS，要求在保证一定的压缩率的情况下体现压缩速率；第二种压缩文件后缀名记为.SCS，强调压缩率，但时间也需要比较合理。同时压缩文件中保存了需要解压的全部信息。另外，软件要具有图形化进度条显示压缩过程和解压过程的进度和显示估计剩余时间的功能，还要具有图形化选项选择将编码信息输
13、出到指定磁盘目录的功能2.2系统总体设计本软件使用Huffman编算法和LZW算法，基于Qt图形用户界面，总体结构如下流程图所示：3系统详细设计3.1有关数据结构的定义1. Huffman树节点：huffman_node_tag，huffman_node结构成员数据类型成员定义isLeafunsigned char标记该节点是否为叶子节点countunsigned long记录哈夫曼树节点总个数parenthuffman_node_tag*记录该节点的父节点zerounionhuffman_node_tag*记录该节点的左孩子onehuffman_node_tag*记录该节点的右孩子symbolunsigned char该节点对应的字符2. Huffman编码：new_code_tag，new_code结构成员数据类型成员定义numbitsunsigned long编码位数bitsunsigned char *编码3. 栈节点：node结构成员数据类型成员定义cchar栈节点储存的字符nextnode*指向下一结点4. 栈：stack结构成员数据类型成员定义lengthint栈内数据个数SPnode *指向栈顶3.2主要算法设计（1）Huffman编码算法：（2）LZW算法：4系统实现与测试4.1系统实现本次课程设计压缩软件的编写基于Qt环境，采用C+语言。具
