基于游程编码数据压缩算法设计与实现.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)编码等相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力上但凡能载荷一定的信息量，且码字的平均长度最短，可别离的变长码的码字称为最正确变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最正确编码的方法主要有：香农(Shannon)费诺(Fano)、哈夫曼(Huffman)编码等。香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长到达极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度Ki满足下式I(xi)K<I(i)+1,Yi(2-1)就可以得到这种码。这种编码方法就是香农编码。香农编码法冗余度稍大，实用性不大，但有重要的理论意义。编码步骤如下：1)将信源消息符号按其出现的概率大小依次排列P(X1)p(X2)-pCXn)(2-2)2)确定满足以下不等式整数码长Ki：-Iogzp(Xi)Ki<-log2p(xi)+l(2-3)3)为了编成唯一可译码，计算第i个消息的累加概率Pi=£P(Xk)(2-4)+l4)将累加概率Pi变成二进制数。5)取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。设信源共7个符号消息，其概率和累加概率如表2-1,那么其香农编码过程如表2-1。所以信源符号的平均码长为：(2-5)平均信息传输率即编码效率为：R=)=跑=0.83Ibit码元K3,14(2-6)表2-1香农编码过程信源消息符号Ai符号概率P(Ai)累加概率Pi-Iogp(Ai)码字长度Ki码字AlA2A3A4A56A703333347000OOlOll1001011110Illl110费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高，但它属于概率匹配编码它不是最正确的编码方法。费诺编码步骤：(1)将信源消息符号按其出现的概率大小依次排列：月P2'Pn(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0"和“1"。(3)将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0"和“1"。(4)如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。对表2-1中信源消息进行费诺编码，那么编码过程如表2-2。那么该费诺编码的平均码长：(2-7)信息传输速率(2-8)表2-2费诺编码过程消息符号Ai消息概率PW第一次分组第二次分组第三次分组第四次分组二元码字码长KiAl0002A20100103A31Oll3A410IO2A5101103610HlO4A71Hll4显然费诺码要比上述香农码的平均码长小，消息传输速率大，说明编码效率高。哈夫曼编码是一种常见的压缩方法。它的根本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。哈夫曼编码步骤：(1)首先把信源中的消息出现的频率从小到大排列。(2)每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比拟，新的根节点参与比拟。(3)重复(2),直到最后得到和为1的根节点。(4)将形成的二叉树的左节点标0,右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。对表2T中的信源数据进行哈夫曼编码，编码过程如表2-3。A40.1800.1910013A500.1710103A6OllO4A71Olll4该哈夫曼码的平均码长为E=£p(aiK=2.72码元/符号信息传输速率",R=)=21=096bit/码元(2-10)K2.72由此可见，哈夫曼编码的平均码长最小，消息传输速率最大，编码效率最高0哈夫曼编码是用概率匹配方法进行信源编码。他有两个明显的特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同,从而保证哈夫曼编码是即时码。哈弗曼编码几乎是所有压缩算法的根底，其实这个算法并不复杂，简单的理解就是，如何用更短的bit来编码数据。我们知道普通的编码都是定长的，比方常用的ASCII编码,每个字符都是8个bit:字符编码A00101001B00101010C00101011这样，计算机就能很方便的把由O和1组成的数据流解析成原始信息，但我们知道，在很多情况下，数据文件中的字符出现的概率是不均匀的，比方在一篇英语文章中，字母"E"出现的频率最高，"Z"最低，如果我们使用不定长的bit编码，频率高的字母用比拟短的编码表示，频率低的字母用长的编码表示，岂不是可以大大缩小文件的空间吗？但这就要求编码要符合“前缀编码"的要求，即较短的编码不能是任何较长的编码的前缀，这样解析的时候才不会混淆，比方下面的编码方法就符合前缀原那么：根据这个码表，下面一段数据就可以唯一解析成原始信息了:要生成这种编码，最方便的就是用二叉树，考察一下下面这个树图2-2二叉树图把要编码的字符放在二叉树的叶子上，所有的左节点是0,右节点是1,从根浏览到叶子上，因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合前缀原那么编码就可以得到字符编码A00B010COllD10E11现在我们可以开始考虑压缩的问题，如果有一篇只包含这五个字符的文章,而这几个字符的出现的次数如下：A: 6次B:15次C: 2次D:9次E: 1次用过用定长的编码，每个字符3bit,这篇文章总长度为：3*6+3*15+3*2+3*9+3*1=99(2-11)而用上面用二叉树生成的编码，总长度为：2*6+3*15+2*2+2*9+2*1=80(2-12)显然，这颗树还可以进一步优化，使得编码更短，比方下面的编码生成的数据长度为：3*6+1*15+4*2+舞陵计4*1可以看出，构造更优的二叉树,，该越近，而我们的终级目标是生万下面两个条件:所有上层节点都大于等于卜层他某节点，设其较大的子节点为m,较小的子节点为n,m下的任一层的所有节点都应大于等于n下的该层的所有节点。上面这个例子是比拟简单的，实际的文件中，一个字节有256种可能的取值，所以二叉树的叶子节点多达256个，最终的树形可能非常复杂，但有一种非常精巧的算法可以快速地建起一棵最优二叉树，这种算法由D.Huffman（戴?哈夫曼）提出，下面我们先来介绍哈弗曼算法的步骤，然后再来证明通过这么简单的步骤得出Ilg形确实是一棵最优二叉树。们建-个父节点，值为这两个之叱从节点序列中去除这两个节点,参加它们的父节点到序列中。重两、膏黑直到节点序列中只剩下唯一一个节点。这时一棵最优二叉木艰1经夕，它的根就是剩下的这个节比方上面的例子，K羲%建g用艮德R:d列出原始的节点数据：2）招最小的两个节点C和E结合世来：罐，、图2-5C和字3）再将新的节点和A组合起来图2-6新节点结合图4）再招D节点参加5）如此循环，最终得到一个最优二誉图2-8最优二星树图生成的数据文件长度为：3*6+1*15+4*2+2*9+4*1=63下面我们用逆推法来证明对于各种不同的节点序列，用哈弗曼算法建立起来的树总是一棵最优二叉树：当这个过程中的节点序列只有两个节点时(比方前例中的15和18),肯定是一棵最优二叉树，一个编码为0,另一个编码为1,无法再进一步优化。然后往前步进，节点序列中不断地减少个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为：按照哈弗曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于(或等于)这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。这样一步步逆推下去，在这个过程中哈弗曼树每一步都始终保持着是一棵最优二叉树。游程长度RL(RUn-Length),简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度以及串的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。游程编码的根本原理是：用一个符号值或串长代替具有相同值的连续符号(连续符号构成了一段连续的“游程"，游程编码因此而得名)，使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。在二元序列中,只有两种符号，即“0"和"1"，这些符号可连续出现，连“0"这一段称为“0"游程，连“1"这一段称为“1"游程。它们的长度分别称为游程长度L(O)和L(I)J'0"游程和"1"游程总是交替出现的。如果规定二元序列是以"0"开始，第一个游程是"0"游程，第二个必为"1"游程，第三个又是“0"游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2,3,，直到无限。将任何（二元）序列变换成一一对应的游程长度序列，再按哈夫曼编码或其他方法处理以到达压缩码率的目的。游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。此外，编程长度可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改良。一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为到达概率匹配或较长，损失不会太大,也就是对平均码字长度影响较小。再按哈夫曼编码或其他方法处理以到达压缩码率的目的。D共前缀码共前缀码编码时也是按照一定规律用尽量短的码字来表示游程形式的初始测试数据，但该编码压缩方案进一步考虑了相邻游程之间存在的联系。如果相邻游程的长度在同一组，那么它们对应码字的前缀是相同的即共前缀，可以用一个标志位来表示这些相邻游程除第一个游程以外的其他游程的前缀，这样数据压缩率得以进-步提高。同组共前缀码的前缀和后缀的位数相同，前缀和后缀相加对应的十进制数比对应的游程长度多2,也就是说跟FDR码相比，相同的码字所表示的游程长度少2,使压缩效果受到一些影响,因此对初始测试数据进行无关位（don，tcaresbit）填充时，要尽量时这种影响降到最低。所谓无关位是指无论它们的取值是0还是1都不会影响测试结果。不过由此也可看出待测试数据的游程长度加上2所对应的FDR码就是相应的共前缀码，假设这两个相差为2的游程长度在同一组内，那么码字长度并没有增加，不会影响压缩效果。共前缀码的前缀都是以1开始，以0结束的数字串，所以当相邻游程长度在同一组时，可以用数字0来表示后面游程的码字前缀，后缀那么不变，这样码字的长度进一步缩短。下面给出一个共前缀编码的实例：编码前的初始测试数据：OOOOOOOOl10000001000000000000010000000000000001（47位）；编码后的码字：IlOlOO10001100101110000100011（29位）。可见数据串OOOOOOOOOOOOOl和OoOOOoOOOoOOOoOl的游程长度分别为13和15,都在第三组，前缀都为1110,所以后一游程的码字前缀用标志位0表示，其码字为00011。2）共游程码前面介绍的共前缀码是利用游程长度同组的前缀相同，用标志位0加码字后缀来表示后面的游程，从而进一步压缩初始测试数据。共游程码（SharingRunLengthCode,SRLC）与共前缀码的编码方案类似，该方案注意到初始测试数据中有的相邻游程是相同的，于是就用一个标志位来表示后面的相同游程，所以该方案被称为共游程码。显然该编码方案的数据压缩率比共前缀码高一些，不考虑相邻游程的长度相同的前提下，编码方法与共前缀码相同。对共游程码编码方案，如果有假设干相邻游程相同，那么后面的一个或多个相同游程都可以用唯一的标志位来代替，从而大大减少了编码码字的长度，即进一步提高了测试数据压缩率。共游程码的前缀都是以"1"开头以"0"结尾的数字串，没有以"0"开头的前缀，所以可以用数字0来作为相邻相同游程的标志位，即后面相邻相同游程的码字只有1位。显然相邻相同游程的长度越长，测试数据压缩率就越高。由于初始测试数据中存在着大量的无关位，可以有意识的对它们进行赋值填充，以增加长度相同的相邻游程的数量，从而降低码字的长度。例如数据串OOOOOOOOOOOXOOOOOOOOOO01,其中的X是无关位，如果把它填充为0那么该数据串是一个长度为23的0游程，由编码码表可知其对应的码字为IIlolol1（8位）:如果把无关位赋值为1,那么数据串变成了两个长度都为11的相邻0游程，其对应的码字为IlOIIl0（7位），使码字的长度减少了1位，提高了数据压缩效果。3）共前缀连续长度码共前缀连续长度码（Co-PrefixalRunLengthcodes,CPRL）也考虑了相邻游程的相关性。如果相邻游程的长度在同一组内，那么同组的后面的相邻游程的前缀可以省略，那么编码后码字的前缀越长，那么压缩效果越明显。由于初始测试数据集中存在大量的无关位，可以适当的对这些无关位进行赋值填充，增加0游程的长度，这些游程长度在同组的概率很高。该编码方案为了增加0游程的长度，对填充后的测试数据采取了差分处理，即把测试数据等长划分并进行异或逻辑运算。通过对ISCAS-89基准电路硬故障测试集的分析对不同的电路各组共前缀次数的分布不均匀，因此CPRL码引入了一个参变量M,M表示确定的组号，M取值不同，编码结果就不同。但对于具体的编码，M是事先确定好的常数，显然M的取值范围在1和最大组号之间。CPRL码的具体编码方法如下：假设待编码的O游程长度所在的组号WM,那么直接用FDR码字表示CPRL码字，原因是组号小的码字前缀位数也短；假设待编码的O游程长度所在的组号NM,且相邻游程长度在同一组内，那么后面的游程CPRL码字由该游程长度对应的FDR码字省略前缀，并在剩下的码字后缀后面加上一个标志位O组成，同组相邻的第一个游程的CPRL码字由对应的FDR码字加上标志位1组成:假设待编码的O游程长度所在的组号2M,且相邻游程长度不在同一组内，那么各游程的CPRL码字由对应的FDR码字加一位标志位组成。下面给出一个CPRL码的编码实例：(参变量M=I)编码前的初始测试数据:00000010000001000011100101111010010；对应的差分测试数据：OOoOOOI0000000000011000100001000101(35位差分后的测试数据对应的FDR码：110000IlOlOl0010011010100101(28位)；对应的CPRL码字：11000011010001001110101001(26位)。本章主要介绍了信源编码中的几种最正确信源变长编码:香农(Shannon)费诺(Fano)-,哈夫曼(Huffman)编码，以及这几种编码的编码过程,然后主要介绍了哈夫曼树的构成步骤，以及游程编码的算法和编码特点。第3章游程编码以及哈夫曼编游程编码游程编码是针对于二元序列的压缩编码方法，在二元序列中，只有两种符号，即“0"游程和“1"游程，"0"游程和“1"游程总是交替出现的。如果规定二元序列是以"0"开始，第一个游程是“0"游程，第二个必为"1"游程，第三个又是"0"游程等等。而对二元序列游程编码主要是针对于每个游程长度以及总共有多少个游程。我在C语言编码过程中主要针对这两方面进行编码，即通过对"0"、"1"的变换次数来确定二元序列中总共有多少个游程；然后在确定每一个游程中游程的长度。两者综合即实现对于二元序列的游程编码。用游程编码压缩数据时，首先要计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来。这种压缩数据的方法，连续相同的字符及出现连续相同的次数越多，压缩比就越大，反之，压缩比就越小。数据压缩算法流程如下：1）翻开源数据文件和压缩后的数据文件:2）从源数据文件中读取字符，并把它放入一个存放器中，然后再循环读取后面的字符，并与存放器中的字符相比拟。如果相等，那么计数器加1,否那么，把存放器中的字符和计数器中数写入压缩数据文件中，然后再把存放器中字符不相等的字符放入存放器中，并把计数器置1。游程编码数据压缩算法流程图如图3-1：数据解码算法流程如下：1）翻开压缩数据文件和恢复文件；2）从压缩文件中循环读出字符和该字符连续的个数，在恢复文件中连续写入从压缩文件中读出的字符，写的次数等于该字符连续的个数：。游程编码数据解压缩算法流程图3-2图3T游程编码数据压缩算法游程图图3-2游程编码数据解码流程图哈夫曼编码是一种常见的压缩方法。它的根本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。要完成哈夫曼的编码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码。建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，那么2*NT就为最终根节点）为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。对于哈夫曼编码树来说，由于哈夫曼编码是前缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。建立哈夫曼树的流程图如图3-3：图3-3构建哈夫曼树流程图构建完哈夫曼树后，根据建立哈夫曼树建立哈夫曼码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子那么对其编码'0',如果当前节点为右子那么对其编码'1'。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。构建哈夫曼编码表的算法流程图如图3-4：有了码表就可以进行编码了。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件翻开，将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐-读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比拟，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。编码流程图如图3.4：在解码时先翻开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是'0'的时候，那么索引走向左子节点；当是'1'的时候，那么走向右子节点。以此类推，一直走到叶子节点为止，那么当前叶子节点所代表的字符即为前一段密文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕，并将解神任里左入fit解码守住也由信息传输速率：(3-2)压缩前二元序 夫曼编码后序列长 所以进行两次编码 这次的仿真只是对 不能过很好的表达 好的表达出游程编 出这种方法的压缩游程编码是一 损压缩，一般情况从树的当前0 点向左子走:曼树并且是否构建了编 所以此步省略了，因为 中先进行判定。在解码之前，i 码表。不过由于本 编码表是唯一的。 解码图： 进行完编码后的平从树的当前节 点向左子走将叶子节点字符 存入译文文件否结束(3-1)列长度为36,再进行哈 而游程压缩效率为80%o 编码的压缩效率高很多。 存程长度也很短，所以还 二值图像序列的就能够很 士编码就能够很好的表达)效的对二元序列进行无而且随着长度的增大逐渐趋向零。对于小概率的码字，其长度未到达概率匹配或较长，损失不会太大，也就对平均码字长度影响较小，这样就可以对长游程不严格按哈夫曼码步骤进行。哈夫曼码是用概率匹配方法进行信源编码。它有两明显的个特点:一是哈夫曼编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码:一是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码。哈夫曼变长码的效率是相当高的，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也简单的多。但应当注意要到达很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。结论游程编码是图像压缩的根本算法，因此对于二元相关信源数据编码研究变得尤为重要。为此，本人对游程编码压缩原理做了深入的学习，并结合哈夫曼编码把其应用到二元相关信源数据的压缩。经过这段时间的学习与实践，我对二元相关信源游程编码与信号编码的开展及现状有了更深刻的认识，意识到数据压缩与解压对于信息时代的巨大影响及其潜在的经济效益，并对MiCroCSoftVisualC+软件有了进一步的了解。经过这一段的学习，我想我对于知识的猎取是有限的，关键是我学会了如何用认真、严谨的学习态度去面对工作，如何用自学的方法来处理问题，如何把书籍和网上查找到的信息运用到实践中去。二元相关游程编码一般不直接应用与多灰度图像，但比拟适于二值图像的编码，例如图像的编码等。为了到达较好的压缩效果，二值图像游程编码需和其它一些编码混合使用。本文中我才用游程编码和哈夫曼编码混合使用。游程压缩作为数据压缩技术的一个分支，理论浅显，走过半个多世纪的离散余弦变换理论在数据压缩领域至今不衰；近来，小波变换理论更使数据压缩技术登峰造极，图像压缩的JPEG2000标准是小波理论傲视群雄。可以预见，新的数学理论将不断为数据压缩技术输入新鲜血液，因此数学理论决不可偏废。最后，给出一点使用无损压缩算法的建议。由于每种无损压缩都有自己的适用范围，压缩比受不失真要求的限制，真正意义上高压缩比的通用无损压缩算法目前哈有待继续研究。因此在选用算