本科毕业设计（论文）-基于游程编码数据压缩算法设计与实现

本科毕业设计（论文）基于游程编码数据压缩算法的设计与实现2013年6月摘要本次毕业设计主要是针对于游程编码数据压缩算法的设计与实现，游程编码非常简单，编码、解码速度快，应用广泛。游程编码是针对于二元序列的一种编码方法，对于二值图像而言是一种编码方法，对连续的黑、白像素数游程以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法，其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之，其缺点是对于不重复的资料反而加大容量。游程编码即需大量的缓冲和优质信道，所以对数据游程编码后在进一步的进行哈夫曼编码已达到更完善的数据压缩。哈夫曼编码使用变长编码表对源符号进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。本文主要介绍了信源编码的分类、获得最佳编码的方法、哈夫曼树的构建方法以及游程编码的原理和实现技术，对游程长度编码技术做了较为全面地研究。包括游程数据压缩、解压缩过程，并给出了流程图；哈夫曼数据压缩、解压缩过程，并给出流程图和结果图。关键词游程编码哈夫曼编码压缩ABSTRACTTHISGRADUATIONDESIGNISMAINLYBASEDONRUNLENGTHCODINGDATACOMPRESSIONALGORITHMDESIGNANDIMPLEMENTATIONOFRUNLENGTHCODINGISVERYSIMPLE,ENCODINGANDDECODINGSPEED,WIDEAPPLICATIONRUNLENGTHCODINGISACODINGMETHODFORBINARYSEQUENCE,ISAKINDOFCODINGMETHODFORBINARYIMAGE,THEBLACKANDWHITEPIXELSOFCONTINUOUSRUNINDIFFERENTCODECODEWORDRUNLENGTHCODINGISAKINDOFSIMPLENONDESTRUCTIVEDATACOMPRESSIONMETHOD,THEADVANTAGEISTHATOFCOMPRESSIONANDDECOMPRESSIONAREVERYFASTITSMETHODISTOCALCULATEACONTINUOUSLENGTHOFDATACOMPRESSION,THEDOWNSIDEISTONOTREPEATDATAINSTEADOFINCREASINGCAPACITYRUNLENGTHCODINGISNEEDALOTOFBUFFERANDCHANNEL,SOTHEDATAAFTERTHERUNLENGTHCODINGINFURTHERHUFFMANENCODINGHASREACHEDMORESOURCECODINGISMAINLYINTRODUCEDINTHISPAPERTHECLASSIFICATION,THEOPTIMALMETHODOFCODING,HUFFMANTREE,CONSTRUCTIONMETHODS,ANDTHERUNLENGTHCODINGPRINCIPLEANDIMPLEMENTATIONTECHNOLOGY,THELENGTHOFTHERUNLENGTHENCODINGTECHNOLOGYISDONEMORECOMPREHENSIVERESEARCHINCLUDINGTHERUNLENGTHDATACOMPRESSIONANDDECOMPRESSIONPROCESS,ANDGIVESTHEFLOWCHARTHUFFMANDATACOMPRESSIONANDDECOMPRESSIONPROCESS,CHARTANDFLOWCHARTISGIVENANDTHERESULTSKEYWORDSRUNLENGTHCODINGHUFFMANENCODINGTHECOMPRESSION目录摘要IABSTRACTII第1章绪论111课题背景112选题目的、意义213主要内容2第2章信源编码分类321信源编码3211信源编码简介3212信源编码的理论基础3213信源编码的分类及作用422最佳变长编码4221香农编码方法5222费诺编码方法6223哈夫曼编码方法723游程编码15231游程长度15232游程编码算法15233游程编码特点16234几种基于游程相关性的数据压缩方案1624本章小结19第3章游程编码以及哈夫曼编2031游程编码2032哈夫曼编码过程2333运行结果2834本章小结30结论31参考文献33致谢35附录136附录241附录345附录450第1章绪论11课题背景信息时代人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大差距1。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为1MIN，图像尺寸为640480PIXETE，每秒播放30帧的非压缩彩色24位真彩色视频的信息量为640480330601658880000BYTES，约为16GB未含音频信息的容量，如果用650MB的CDR来存放，需要3张。由此可见，在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的2。数据压缩技术主要采用两种方法一种是“保真率”较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是很高，但还原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼HUFMAN编码、算术编码AC和游程长度编码RLC2。其中，游程长度编码是一种十分简单的压缩方法，编码解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMP，TIF及AVI等，都采用了这种压缩方法，尤其适用于文本文件数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以达到减少数据文件所占的存储空间的目的6。飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如HUFFMAN、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，因此十分有必要对无损压缩算法进行研究4。通过对游程编码RUNLENGTHENCODING,RLE进行研究,结合哈夫曼编码。最后找到一种实现相对简单、压缩效果比较好的方法，即对游程编码后的数据在进一步的进行哈夫曼编码，采用该方法可以收到比较理想的效果。12选题目的、意义飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如HUFFMAN、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，而游程编码却是一种是一种非常简单，且编码、解码速度很快编码方法。所以通过对于游程编码的研究能够比较快捷语简单的实现对于数据的无损压缩。13主要内容本文主要介绍了信源编码中的几种最佳变长编码方法香农（SHANNON）、费诺（FANO）、哈夫曼（HUFFMAN）编码，以及这几种编码的编码过程。然后主要描述了哈夫曼编码方法以及如何构造哈夫曼树。然后详细的介绍了游程编码的编码算法以及游程编码的特点。画出游程编码哈夫曼编码的流程图，以及得出的结果图，最后做出总结。第2章信源编码分类21信源编码211信源编码简介编码实质上就是对信源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性3。212信源编码的理论基础信源编码就是从信源符号到码符号的一种映射F，它把信源输出的符号UI变换成码元序列WI。信源编码定义如图21信源编码器UU1，U2ULWW1,W2WKXX1，X2XR图21信源编码定义图信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。无失真信源编码定理是离散信源/数字信号编码的基础；限失真信源编码定理是连续信源/模拟信号编码的基础。213信源编码的分类及作用信源编码的分类离散信源编码独立信源编码,可做到无失真编码；连续信源编码独立信源编码,只能做到限失真信源编码；相关信源编码非独立信源编码。编码的作用信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。214信源编码的历史最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有HUFFMAN编码、算术编码、LZ编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。另外，在数字电视领域，信源编码包括通用的MPEG2编码和H264（MPEGPART10AVC）编码等相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力4。22最佳变长编码凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳编码的方法主要有香农（SHANNON）、费诺（FANO）、哈夫曼（HUFFMAN）编码等。221香农编码方法香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码香农第一定理指出，选择每个码字的长度KI满足下式IXIKIXI1,（2I1）就可以得到这种码。这种编码方法就是香农编码。香农编码法冗余度稍大，实用性不大，但有重要的理论意义。编码步骤如下1）将信源消息符号按其出现的概率大小依次排列P（X1）P（X2）P（XN）（22）2）确定满足下列不等式整数码长KILOG2PXIKILOG2PXI1（23）3为了编成唯一可译码，计算第I个消息的累加概率PIPXK（21K4）4将累加概率PI变成二进制数。5取PI二进制数的小数点后KI位即为该消息符号的二进制码字。设信源共7个符号消息，其概率和累加概率如表21，则其香农编码过程如表21。所以信源符号的平均码长为（25）符号码元/143IPK71IA平均信息传输率即编码效率为码元BIT8310462KXHR（26）表21香农编码过程信源消息符号AI符号概率PAI）累加概率PILOGPAI码字长度KI码字A1A2A3A4A5A6A7020019018017015010001002039057074089099234241248256274334666333334700000101110010111101111110222费诺编码方法费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高，但它属于概率匹配编码它不是最佳的编码方法。费诺编码步骤（1）将信源消息符号按其出现的概率大小依次排列。NPP21（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。5信源符号所对应的码字即为费诺码。对表21中信源消息进行费诺编码，则编码过程如表22。则该费诺编码的平均码长（27）信息传输速率（28）表22费诺编码过程消息符号AI消息概率P（AI）第一次分组第二次分组第三次分组第四次分组二元码字码长KIA10200002A201900103A30180110113A40170102A501501103A6010011104A7001111111114显然费诺码要比上述香农码的平均码长小，消息传输速率大，说明编码效率高。223哈夫曼编码方法码元BIT953074261KXHR符号码元/742IAP71I哈夫曼编码是一种常见的压缩方法。它的基本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。哈夫曼编码步骤（1）首先把信源中的消息出现的频率从小到大排列。（2）每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。（3）重复2，直到最后得到和为1的根节点。（4）将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。对表21中的信源数据进行哈夫曼编码，编码过程如表23。表23哈夫曼编码过程信源符号AI概率PAI编码过程码字WI码长KIA102002603503906101102A201902002603500391112A3018019020002610003A4017018001910013A5015001710103A60100101104A7001101114该哈夫曼码的平均码长为（29）符号码元/27KIAP71I信息传输速率（210）码元/BIT960721KXHR由此可见，哈夫曼编码的平均码长最小，消息传输速率最大，编码效率最高。哈夫曼编码是用概率匹配方法进行信源编码。他有两个明显的特点一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码6。哈弗曼编码几乎是所有压缩算法的基础，其实这个算法并不复杂，简单的理解就是，如何用更短的BIT来编码数据。我们知道普通的编码都是定长的，比如常用的ASCII编码,每个字符都是8个BIT字符编码A00101001B00101010C00101011这样，计算机就能很方便的把由0和1组成的数据流解析成原始信息，但我们知道，在很多情况下，数据文件中的字符出现的概率是不均匀的，比如在一篇英语文章中，字母“E”出现的频率最高，“Z”最低，如果我们使用不定长的BIT编码，频率高的字母用比较短的编码表示，频率低的字母用长的编码表示，岂不是可以大大缩小文件的空间吗但这就要求编码要符合“前缀编码”的要求，即较短的编码不能是任何较长的编码的前缀，这样解析的时候才不会混淆，比如下面的编码方法就符合前缀原则字符编码A0B10C110D1110E11110根据这个码表，下面一段数据就可以唯一解析成原始信息了1110010101110110111100010DABBDCEAAB要生成这种编码，最方便的就是用二叉树，考察一下下面这个树图22二叉树图把要编码的字符放在二叉树的叶子上，所有的左节点是0，右节点是1，从根浏览到叶子上，因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合前缀原则编码就可以得到字符编码A00B010C011D10E11现在我们可以开始考虑压缩的问题，如果有一篇只包含这五个字符的文章，而这几个字符的出现的次数如下A6次B15次C2次D9次E1次用过用定长的编码，每个字符3BIT，这篇文章总长度为3631532393199（211）而用上面用二叉树生成的编码，总长度为2631522292180（212）显然，这颗树还可以进一步优化，使得编码更短，比如下面的编码图23二叉树图生成的数据长度为3611542294163213可以看出，构造更优的二叉树，原则就是权重越大的叶子，距离根应该越近，而我们的终级目标是生成“最优”的二叉树，最优二叉树必须符合下面两个条件所有上层节点都大于等于下层节点。某节点，设其较大的子节点为，较小的子节点为，下的任一层的所有节点都应大于等于下的该层的所有节点。上面这个例子是比较简单的，实际的文件中，一个字节有256种可能的取值，所以二叉树的叶子节点多达256个，最终的树形可能非常复杂，但有一种非常精巧的算法可以快速地建起一棵最优二叉树，这种算法由DHUFFMAN（戴哈夫曼）提出，下面我们先来介绍哈弗曼算法的步骤，然后再来证明通过这么简单的步骤得出的树形确实是一棵最优二叉树。哈夫曼算法的步骤是这样的从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。然后从节点序列中去除这两个节点，加入它们的父节点到序列中。重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。比如上面的例子，哈弗曼树建立的过程如下1列出原始的节点数据图24原始节点2将最小的两个节点C和E结合起来图25C和E结合3再将新的节点和A组合起来图26新节点结合图4再将D节点加入图27新节点结合图5如此循环，最终得到一个最优二叉树图28最优二叉树图生成的数据文件长度为3611542294163下面我们用逆推法来证明对于各种不同的节点序列，用哈弗曼算法建立起来的树总是一棵最优二叉树当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为按照哈弗曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。这样一步步逆推下去，在这个过程中哈弗曼树每一步都始终保持着是一棵最优二叉树。23游程编码231游程长度游程长度RLRUNLENGTH，简称游程或游长，指的是由字符或信号取样值构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度以及串的位置，就能恢复出原来的数据流，游程长度编码RLC就是用二进制码字给出这些信息的一类方法。232游程编码算法游程编码的基本原理是用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“游程”，游程编码因此而得名），使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L0和LL。“0”游程和“L”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，直到无限。将任何二元序列变换成一一对应的游程长度序列，再按哈夫曼编码或其他方法处理以达到压缩码率的目的9。233游程编码特点游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。此外，编程长度可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改进。一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。再按哈夫曼编码或其他方法处理以达到压缩码率的目的。234几种基于游程相关性的数据压缩方案1）共前缀码共前缀码编码时也是按照一定规律用尽量短的码字来表示游程形式的初始测试数据，但该编码压缩方案进一步考虑了相邻游程之间存在的联系。如果相邻游程的长度在同一组，则它们对应码字的前缀是相同的即共前缀，可以用一个标志位来表示这些相邻游程除第一个游程以外的其他游程的前缀，这样数据压缩率得以进一步提高。同组共前缀码的前缀和后缀的位数相同，前缀和后缀相加对应的十进制数比对应的游程长度多2，也就是说跟FDR码相比，相同的码字所表示的游程长度少2，使压缩效果受到一些影响，因此对初始测试数据进行无关位DONTCARESBIT填充时，要尽量时这种影响降到最低。所谓无关位是指无论它们的取值是0还是1都不会影响测试结果。不过由此也可看出待测试数据的游程长度加上2所对应的FDR码就是相应的共前缀码，若这两个相差为2的游程长度在同一组内，则码字长度并没有增加，不会影响压缩效果。共前缀码的前缀都是以1开始，以0结束的数字串，所以当相邻游程长度在同一组时，可以用数字0来表示后面游程的码字前缀，后缀则不变，这样码字的长度进一步缩短。下面给出一个共前缀编码的实例编码前的初始测试数据00000000110000001000000000000010000000000000001（47位）；编码后的码字11010010001100101110000100011（29位）。可见数据串00000000000001和0000000000000001的游程长度分别为13和15，都在第三组，前缀都为1110，所以后一游程的码字前缀用标志位0表示，其码字为00011。2）共游程码前面介绍的共前缀码是利用游程长度同组的前缀相同，用标志位0加码字后缀来表示后面的游程，从而进一步压缩初始测试数据。共游程码（SHARINGRUNLENGTHCODE，SRLC）与共前缀码的编码方案类似，该方案注意到初始测试数据中有的相邻游程是相同的，于是就用一个标志位来表示后面的相同游程，所以该方案被称为共游程码。显然该编码方案的数据压缩率比共前缀码高一些，不考虑相邻游程的长度相同的前提下，编码方法与共前缀码相同。对共游程码编码方案，如果有若干相邻游程相同，则后面的一个或多个相同游程都可以用唯一的标志位来代替，从而大大减少了编码码字的长度，即进一步提高了测试数据压缩率。共游程码的前缀都是以“1”开头以“0”结尾的数字串，没有以“0”开头的前缀，所以可以用数字0来作为相邻相同游程的标志位，即后面相邻相同游程的码字只有1位。显然相邻相同游程的长度越长，测试数据压缩率就越高。由于初始测试数据中存在着大量的无关位，可以有意识的对它们进行赋值填充，以增加长度相同的相邻游程的数量，从而降低码字的长度。例如数据串00000000000X000000000001，其中的X是无关位，如果把它填充为0则该数据串是一个长度为23的0游程，由编码码表可知其对应的码字为11101011（8位）；如果把无关位赋值为1，则数据串变成了两个长度都为11的相邻0游程，其对应的码字为1101110（7位），使码字的长度减少了1位，提高了数据压缩效果。3）共前缀连续长度码共前缀连续长度码（COPREFIXALRUNLENGTHCODES，CPRL）也考虑了相邻游程的相关性。如果相邻游程的长度在同一组内，则同组的后面的相邻游程的前缀可以省略，则编码后码字的前缀越长，则压缩效果越明显。由于初始测试数据集中存在大量的无关位，可以适当的对这些无关位进行赋值填充，增加0游程的长度，这些游程长度在同组的概率很高。该编码方案为了增加0游程的长度，对填充后的测试数据采取了差分处理，即把测试数据等长划分并进行异或逻辑运算。通过对ISCAS89基准电路硬故障测试集的分析对不同的电路各组共前缀次数的分布不均匀，因此CPRL码引入了一个参变量M,M表示确定的组号，M取值不同，编码结果就不同。但对于具体的编码，M是事先确定好的常数，显然M的取值范围在1和最大组号之间。CPRL码的具体编码方法如下若待编码的0游程长度所在的组号M,则直接用FDR码字表示CPRL码字，原因是组号小的码字前缀位数也短；若待编码的0游程长度所在的组号M，且相邻游程长度在同一组内，则后面的游程CPRL码字由该游程长度对应的FDR码字省略前缀，并在剩下的码字后缀后面加上一个标志位0组成，同组相邻的第一个游程的CPRL码字由对应的FDR码字加上标志位1组成；若待编码的0游程长度所在的组号M，且相邻游程长度不在同一组内，则各游程的CPRL码字由对应的FDR码字加一位标志位组成。下面给出一个CPRL码的编码实例（参变量M1）编码前的初始测试数据00000010000001000011100101111010010；对应的差分测试数据00000010000000000011000100001000101（35位）；差分后的测试数据对应的FDR码1100001101010010011010100101（28位）；对应的CPRL码字11000011010001001110101001（26位）。24本章小结本章主要介绍了信源编码中的几种最佳信源变长编码香农（SHANNON）、费诺（FANO）、哈夫曼（HUFFMAN）编码，以及这几种编码的编码过程,然后主要介绍了哈夫曼树的构成步骤，以及游程编码的算法和编码特点。第3章游程编码以及哈夫曼编31游程编码游程编码是针对于二元序列的压缩编码方法，在二元序列中，只有两种符号，即“0”游程和“1”游程，“0”游程和“L”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。而对二元序列游程编码主要是针对于每个游程长度以及总共有多少个游程。我在C语言编码过程中主要针对这两方面进行编码，即通过对“0”、“1”的变换次数来确定二元序列中总共有多少个游程；然后在确定每一个游程中游程的长度。两者综合即实现对于二元序列的游程编码。用游程编码压缩数据时，首先要计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来。这种压缩数据的方法,连续相同的字符及出现连续相同的次数越多，压缩比就越大，反之，压缩比就越小。数据压缩算法流程如下1打开源数据文件和压缩后的数据文件；2从源数据文件中读取字符,并把它放入一个寄存器中，然后再循环读取后面的字符，并与寄存器中的字符相比较。如果相等，则计数器加1，否则，把寄存器中的字符和计数器中数写入压缩数据文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把计数器置1。游程编码数据压缩算法流程图如图31数据解码算法流程如下1打开压缩数据文件和恢复文件；2从压缩文件中循环读出字符和该字符连续的个数,在恢复文件中连续写入从压缩文件中读出的字符,写的次数等于该字符连续的个数。游程编码数据解压缩算法流程图32图31游程编码数据压缩算法游程图打开源数据文件与压缩后的数据文件从元数据文件中读取一个字符将字符放入寄存器计数器COUNT1是否读到文件尾在源数据文件中读下一个字符读取的字符与寄存器中的字符是否相等计数器加1COUNTCOUNT1关闭源数据文件和压缩文件将寄存器字符和计数器中的数写入数据压缩文件将最后读取的字符放入寄存器计数器置1COUNT1YESNOYES图32游程编码数据解码流程图打开源数据文件与恢复后的数据文件判断是否为文件尾从压缩文件中读取字符以及该字符的连续的个数读取的字符及连续个数是否写完在恢复文件中写入从压缩文件中读取的字符关闭恢复数据文件和数据压缩文件YESNONOYES32哈夫曼编码过程哈夫曼编码是一种常见的压缩方法。它的基本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。要完成哈夫曼的编码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码。建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2N1就为最终根节点）为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。对于哈夫曼编码树来说，由于哈夫曼编码是前缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。建立哈夫曼树的流程图如图33图33构建哈夫曼树流程图构建完哈夫曼树后，根据建立哈夫曼树建立哈夫曼码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码0，如果当前节点为右子则对其编码1。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。构建哈夫曼编码表的算法流程图如图34图33构建哈夫曼编码表的算法流程图有了码表就可以进行编码了。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件打开，将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。编码流程图如图34图34编码算法流程图在解码时先打开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是0的时候，则索引走向左子节点；当是1的时候，则走向右子节点。以此类推，一直走到叶子节点为止，则当前叶子节点所代表的字符即为前一段密文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕，并将解码结果存入到新的解码文件当中。在解码之前，还应该先确认之前是否建立了哈夫曼树并且是否构建了编码表。不过由于本次将A到Z都进行了编码，所以此步省略了，因为编码表是唯一的。需要的时候可以在ENCODER函数中先进行判定。图35解码算法流程图33运行结果对于二元序列00011100001111100011111111110000000000000111110000000000000即（3,0）（3,1（4,0）（5,1）3,010,113,05,113,0编码图解码图进行完编码后的平均码长为（31信息传输速率（32）压缩前二元序列长度为49，进行游程编码后序列长度为36，再进行哈夫曼编码后序列长度为29。即总的压缩效率为59，而游程压缩效率为80。所以进行两次编码后的压缩效率比单一一次的游程编码的压缩效率高很多。这次的仿真只是对于一段很短的二元序列，而且各游程长度也很短，所以还不能过很好的体现出游程编码的压缩效率。但对于二值图像序列的就能够很好的体现出游程编码的压缩效率，然后在进行哈夫曼编码就能够很好的体现出这种方法的压缩效率。34本章小结游程编码是一种简单的快捷的编码方法，能够有效的对二元序列进行无损压缩，一般情况下，游程长度越大，其概率越小，而且随着长度的增大逐渐趋向零。对于小概率的码字，其长度未达到概率匹配或较长，损失不会太大，也就对平均码字长度影响较小，这样就可以对长游程不严格按哈夫曼码步骤进行。哈夫曼码是用概率匹配方法进行信源编码。它有两明显的个特点一是哈夫曼编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；一是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码。哈夫曼变长码的效率是相当高的，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说符号码元/4PIK91码元/14HRBITKX也简单的多。但应当注意要达到很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。结论游程编码是图像压缩的基本算法，因此对于二元相关信源数据编码研究变得尤为重要。为此，本人对游程编码压缩原理做了深入的学习，并结合哈夫曼编码把其应用到二元相关信源数据的压缩。经过这段时间的学习与实践，我对二元相关信源游程编码与信号编码的发展及现状有了更深刻的认识，意识到数据压缩与解压对于信息时代的巨大影响及其潜在的经济效益，并对MICROCSOFTVISUALC软件有了进一步的了解。经过这一段的学习，我想我对于知识的猎取是有限的，关键是我学会了如何用认真、严谨的学习态度去面对工作，如何用自学的方法来处理问题，如何把书籍和网上查找到的信息运用到实践中去。二元相关游程编码一般不直接应用与多灰度图像，但比较适于二值图像的编码，例如传真图像的编码等。为了达到较好的压缩效果，二值图像游程编码需和其它一些编码混合使用。本文中我才用游程编码和哈夫曼编码混合使用。游程压缩作为数据压缩技术的一个分支，理论浅显，走过半个多世纪的离散余弦变换理论在数据压缩领域至今不衰；近来，小波变换理论更使数据压缩技术登峰造极，图像压缩的JPEG2000标准是小波理论傲视群雄。可以预见，新的数学理论将不断为数据压缩技术输入新鲜血液，因此数学理论决不可偏废。最后，给出一点使用无损压缩算法的建议。由于每种无损压缩都有自己的适用范围，压缩比受不失真要求的限制，真正意义上高压缩比的通用无损压缩算法目前哈有待继续研究。因此在选用算法之前需要对图像数据进行分析，使用时根据数据表现出的特点，利用算法的思想，灵活使用算法是提高压缩比的有效手段。参考文献1王增辉，雷加一种变游程编码的测试数据压缩方法理论与方法200952许川佩，董祥健一种交替游程编码的SOC测试数据压缩方法计算机工程与应用2010，46（25）3刘娟，詹文法，黄忠基于交替变游程编码的测试数据压缩方法安庆师范学院学报201154詹文法，梁华国，时峰，黄正峰，欧阳一鸣一种共游程的测试数据压缩方案计算机研究与发展20085彭喜元，俞洋基于变游程编码的测试数据压缩算法电子学报200726于翔。数据压缩技术分析。青海大学学报200287祝本明，刘桂华。一种改进的游程编码算法西南科技大学学报200798MICHALSTABNO，ROBERTWREMBELRHLBITMAPCOMPRESSIONTECHNIQUEBASEDONRUNLENGTHANDHUFFMANENCODINGINFORMATIONSYSTEMS20099CRISTIANOMAGULHARI,IVANILSBONATTI,PEDROLDPERESANADAPTIVERUNLENGTHENCODINGMETHODFORTHECOMPRESSIONOFELECTROCARDIOGRAMSMEDICALENGINEERING这些字符ISTICS测定（1）行无序，部分有序，并下令由一个索引值属性，（2）索引的属性不同的枢机主教伊蒂埃斯（多达20,000个不同的值），和（3）的数据集由100,000,000股行相对于比较RLHN和RLH效率压缩位图的修改。本文的结构如下。第2部分介绍了基本本文中使用的定义和概念。第3节提出RLH和RLHN压缩技术。第4节讨论的实验结果RLH的，RLHN和华的评价。最后，第5节总结，并得出结论的文件。12造纸重点，贡献和轮廓在本文中，我们提出了一个替代的位图压缩技术，提供精确的编码（1）良好的查询响应时间和（2）的尺寸小压缩的位图。位图压缩技术我们开发被称为运行长度霍夫曼（RLH），的。同样，在英国广播公司（BBC）和华，建议技术基于游程长度编码。然而，它不同于英国广播公司（BBC）和华就以下。首先，RLH计数位的值之间的距离1，而不是相同的值的连续位的长度。该距离成为接下来编码的符号哈夫曼编码技术10。其次，RLH确实将位图转换为字提高了一个位图的压缩比。为了更好地支持位图更新中，我们提出的一个变种的RLH压缩的技术，称为RLHN。RLHN一个位图压缩被分成N比特的长度的话，则每个N位的字被压缩RLH。RLH和RLHN压缩技术实施和华实验比较。作为一个参考我们选择华，因为压缩位图华提供更好的查询响应时间比位图压缩与BBC26,32。本文扩展了我们以前的工作25就到RLHN的压缩技术的发展接受字的长度等于256，512，1024，2048位比较RLH，RLHN，和华就CPU时间和I/O处理时间这些字符ISTICS测定（1）行无序，部分有序，并下令由一个索引值属性，（2）索引的属性不同的枢机主教伊蒂埃斯（多达20,000个不同的值），和（3）的数据集由100,000,000股行相对于比较RLHN和RLH效率压缩位图的修改。本文的结构如下。第2部分介绍了基本本文中使用的定义和概念。第3节提出RLH和RLHN压缩技术。第4节讨论的实验结果RLH的，RLHN和华的评价。最后，第5节总结，并得出结论的文件。2基本定义21位图索引位图索引是基于所谓的位图。一位图是一个位向量。从域的每一个值索引的属性相关已自己的位图。该每个位图中的位的数目的数目等于行存储了表T中。创建一个位图值V索引属性，A介绍了这些在T的行A值是V。在该位图中，位编号N设置为“1”，如果A的第N行的价值等于V。否则位设置为0。位图索引的概念说明一个例子。让我们考虑表的客户和创建位图索引其性别属性，如图所示。1。由于域索引的属性只包含两个不同的价值观，指数是由两个位图。例如，第一位图描述值女位设置为0，因为的属性性的第一行中的值是不是一个女性22华BBC压缩如前所述，华和BBC压缩SION技术都是基于运行长度编码。该运行长度编码的基本思想包括编码连续的比特具有相同的值的向量（无论是0或1）为（1）中的所有位共同的价值矢量（即，无论是“0”由零组成的一个矢量或1的向量组成的）和（2）的长度矢量（即，具有相同值的位的数量）在编码之前，位图被分成词。接着，词语被分组为所谓的运行。运行组成的话，可以是填充或尾巴。填充代表一系列的比特组成的字相同的值。字表示序列的尾部两个“0”和“1”比特组成。填充被压缩因为他们同质化的内容，而尾巴没有。英国广播公司（BBC）和华之间的主要区别是英国广播公司（BBC）划分成8位字位向量，而华将其划分为31位字。此外，英国广播公司（BBC）使用四个不同类型的运行时，根据填充的长度和结构的尾巴。议员只使用一个不同的运行。说明的WAH压缩的总体思路一个例子。为了简单起见，让我们假设使用一个32位的处理器。位图的COM压制是由5456位组成的，如图中所示。2一26。华压缩的位图被执行三个下面的步骤。在第一步骤中，位图被分为若干组由31位组成的，如图中所示。2湾在该示例中176创建组。在第二步骤中，相邻的被合并成一个组含有相同位基，如图中所示。2。由于第1组是异类，即，它是由“0”和“1”的位，它是不被合并与一组。组2175是同质（0位组成），他们合并成一个大基，中图表示。2C为2175组。本组包括174了31位。最后一组176，类似于第1组，是异质的，它不能被与合并前组。作为结果合并组，三最终组被创建，如图中所示。2三。在第三步骤中，被编码的最后三个组如下所示（参见图2中的32BIT字D）。第一组代表在第一次运行的尾部。的最重要的位（最左边）有值“0”表示一个尾巴。31下一页位1组的原始位。第二组（A组2175）表示第二次运行的填充。的最显着位（位置31）被设置为“1”表示填充。在位置2的位30设置为0表示所有位原组2175值“0”，即填充用于压缩组的所有位具有价值0。该其余的30位被用于编码数字同质群体充满0在这个例子中，有174组。均质的数量组所表示的二进制值等于000000000000000000000010101110，存储上在其余30位。最后31位，记为176组，代表第二次运行的尾巴。的最在这组有显着位值“0”表示一个尾巴。其余31位是原组176位。23霍夫曼编码在霍夫曼编码10，原始符号从压缩的文件被替换的位串。更多一个给定的符号经常出现在压缩文件用于表示符号的较短的比特串。编码后的符号和它们的相应的位串表示为所谓哈夫曼树。哈夫曼树用于压缩和解压。霍夫曼编码算法，用一个例子说明。3RLH压缩RLH技术中提出的压缩位图本文是根据游程长度编码和HUFFMAN编码。有两个特点RLH区别于其竞争对手（英国广播公司（BBC）和WAH）。首先，RLH计数的价值位之间的距离“1”，而比位向量的长度相同的值，这是类似于增量编码。其次，RLH不划分位图转换为字，即整个位图被压缩。两位值1之间的距离代表数位值“0”这两个位之间。为在RLH，例如，位载体000011110100编码以下的数字序列400012。我们假设的开始和结束的位向量被解释为位值“1”这种假设没有任何影响的RLH压缩技术的概念。代码400012应解释如下。第一明确1中的编码比特矢量000011110100处于隐式地从“1”（位）的四个位置的距离开始的矢量在最左边的位置，第二个“1”是在距离为0位，距离最近的1的左侧第三1是在距离为0的位，从最近的“1”到左边，等这样的解决方案可以保证，当密度减小，则位图使用的符号的数编码位图降低过。运行长度编码用距离将进一步被称为游程长度编码。修改后的运行长度编码所编码的位图接下来HUFFMAN编码压缩。的输入值霍夫曼编码算法的频率所有所有编码位值“1”之间的距离位图。一个常见的哈夫曼树建频率，它是进一步用于编码的距离。哈夫曼树的大小影响的性能位图的压缩和解压。从每形成的实验事实证明，霍夫曼的大小树是小。例如，对于一个测试表，存储100,000,000行和索引的基数属性等于20000，哈