基于游程编码数据压缩算法设计与实现.docx

本科毕业设计论文基于游程编码数据压缩算法的设计与实现2023年6月本科毕业设计论文）基于游程编码数据压缩算法的设计与实现燕山大学毕业设计论文任务书学学生姓名专业班皴题题目名称基于游程编码数据压缩算法的设计与实现题目性质1.理工类：工程设计（）;工程技术实验研究型（）；理论研究型（）：计算机软件型（）：综合型（）;3.外语类（）；4.艺术类（）题目类型1.毕业设计）2.论文）题目来源科研课题（）生产实际（）自选题目（）主要内容是基于游程编码数据压缩算法的设计与实现用C语言完成游程编码，完成哈夫曼编码；并画出流程图和结果图，得出相应结论。周次第14周第58周第913周第1415周第1617周应完成的内容熟悉课题，查阅、搜集相关资料，并完成开题报告学习游程编码、哈夫曼编码方法，以及进一步学习C语言编码编写C语言程序实现对数据的游程压缩进一步完善程序,并开始撰写毕业论文总结毕设，完成论文，准备辩论指导教师：职称：教授2023年2月4日系级教学单位审批：年月日学院：里仁学院系级教学单位:摘要本次毕业设计主要是针对于游程编码数据压缩算法的设计与实现，游程编码非常简单，编码、解码速度快，应用广泛。游程编码是针对于二元序列的一种编码方法，对于二值图像而言是一种编码方法，对连续的黑、白像素数（游程）以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法，其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之，其缺点是对于不重复的资料反而加大容量。游程编码即需大量的缓冲和优质信道，所以对数据游程编码后在进一步的进行哈夫曼编码己到达更完善的数据压缩。哈夫曼编码使用变长编码表对源符号进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的那么使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而到达无损压缩数据的目的。本文主要介绍了信源编码的分类、获得最正确编码的方法、哈夫曼树的构建方法以及游程编码的原理和实现技术,对游程长度编码技术做了较为全面地研究。包括游程数据压缩、解压缩过程，并给出了流程图；哈夫曼数据压缩、解压缩过程，并给出流程图和结果图。关键词游程编码哈夫曼编码压缩AbstractThisgraduationdesignismainlybasedonrun-lengthcodingdatacompressionalgorithmdesignandimplementationofrun-lengthcodingisverysimple,encodinganddecodingspeed,wideapplication.Run-lengthcodingisacodingmethodforbinarysequence,isakindofcodingmethodforbinaryimage,theblackandwhitepixelsofcontinuous(run)indifferentcodecodeword.Run-lengthcodingisakindofsimplenondestructivedatacompressionmethod,theadvantageisthatofcompressionanddecompressionareveryfast.Itsmethodistocalculateacontinuouslengthofdatacompression,thedownsideistonotrepeatdatainsteadofincreasingcapacity.Run-lengthcodingisneedalotofbufferandchannel,sothedataaftertherun-lengthcodinginfurtherHuffmanencodinghasreachedmore.Sourcecodingismainlyintroducedinthispapertheclassification,theoptimalmethodofcoding,Huffmantree,constructionmethods,andtherun-lengthcodingprincipleandimplementationtechnology,thelengthoftherun-lengthencodingtechnologyisdonemorecomprehensiveresearch.Includingtherun-lengthdatacompressionanddecompressionprocess,andgivestheflowchart;Huffmandatacompressionanddecompressionprocess,chartandflowchartisgivenandtheresults.KeywordsRun-IengthcodingHuffmanencodingThecompression目录摘要AbstractI第1章绪论O1. 1课题背景O选题目的、意义1错误!未定义书签。第2章信源编码分类11.1 信源编码11.1.1 信源编码简介1错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。第3章游程编码以及哈夫曼编错误!未定义书签。游程编码14错误!未定义书签。错误!未定义书签。错误!未定义书签。绮论18参考文献18致谢20附录121附录224附录326附录429第1章绪论1.1课题背景信息时代人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大差距2。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为Imin,图像尺寸为640X480PiXete,每秒播放30帧的非压缩彩色24位真彩色视频的信息量为：640×480×3×30×60;165888OOOOBytes,约为L6GB侏含音频信息的容量)，如果用650MB的CD-R来存放，需要3张。由此可见,在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的。数据压缩技术主要采用两种方法：-种是"保真率"较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是很高，但复原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(HUfman)编码、算术编码(AC)和游程长度编码(RLC)Do其中，游程长度编码是一种十分简单的压缩方法，编码/解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMP,.TIF及.AVI等，都采用了这种压缩方法，尤其适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以到达减少数据文件所占的存储空间的目的飞速开展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据平安性要求比拟苛刻的领域，现在比拟流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如HUffman、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比拟差或者算法实现比拟困难，因此十分有必要对无损压缩算法进行研究通过对游程编码(RUnLengIhEnCoding,RLE)进行研究,结合哈夫曼编码。最后找到一种实现相对简单、压缩效果比拟好的方法，即对游程编码后的数据在进一步的进行哈夫曼编码，采用该方法可以收到比拟理想的效果。选题目的、意义飞速开展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据平安性要求比拟苛刻的领域，现在比拟流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如HUffman、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比拟差或者算法实现比拟困难，而游程编码却是一种是一种非常简单，且编码、解码速度很快编码方法。所以通过对于游程编码的研究能够比拟快捷语简单的实现对于数据的无损压缩。本文主要介绍了信源编码中的几种最正确变长编码方法：香农(Shannon)费诺(Fano)、哈夫曼(Huffman)编码，以及这几种编码的编码过程。然后主要描述了哈夫曼编码方法以及如何构造哈夫曼树。然后详细的介绍了游程编码的编码算法以及游程编码的特点。画出游程编码哈夫曼编码的流程图，以及得出的结果图，最后做出总结。第2章信源编码分类2.1 信源编码2.1.1 信源编码简介编码实质上就是对信源的原始符号按一定规那么进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的根本途径有两个：使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性印。信源编码就是从信源符号到码符号的一种映射f,它把信源输出的符号Ui变换成码元序列wi。信源编码定义如图2-1：图2-1信源编码定义图信源编码理论是信息论的一个重要分支,其理论根底是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的根底；限失真信源编码定理：是连续信源/模拟信号编码的根底。信源编码的分类：离散信源编码：独立信源编码,可做到无失真编码:连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。编码的作用：信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。2. 1.4信源编码的历史最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：HUffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。另外，在数字电视领域，信源编码包括通用的MPEG-2编码和H.264(MPEG-PartlOAVC)编码等相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力上但凡能载荷一定的信息量，且码字的平均长度最短，可别离的变长码的码字称为最正确变长码。为此必须将概率大的信