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

基于游程编码数据压缩算法设计与实现1812020年4月19日文档仅供参考本科毕业设计（论文）基于游程编码数据压缩算法的设计与实现 6月 本科毕业设计（论文）基于游程编码数据压缩算法的设计与实现燕山大学毕业设计（论文）任务书学院：里仁学院 系级教学单位： 学号学生姓名专 业班 级题目题目名称基于游程编码数据压缩算法的设计与实现题目性质1.理工类：工程设计 （ ）；工程技术实验研究型（ ）；理论研究型（ ）；计算机软件型（ ）；综合型（ ）2.文管理类（ ）；3.外语类（ ）；4.艺术类（ ）题目类型1.毕业设计（ ） 2.论文（ ）题目来源科研课题（ ） 生产实际（ ）自选题目（ ） 主要内容 是基于游程编码数据压缩算法的设计与实现基本要求用c语言完成游程编码，完成哈夫曼编码；并画出流程图和结果图，得出相应结论 。参考资料彭喜元，俞洋.基于变游程编码的测试数据压缩算法.电子学报. .8王增辉， 雷加.一种变游程编码的测试数据压缩方法.理论与方法. .5商进，张礼勇.一种双游程编码的测试数据压缩方案.哈尔滨理工大学学报. .8周 次第14周第58周第913周第14 15周第1617周应完成的内容熟悉课题，查阅、搜集相关资料，并完成开题报告学习游程编码、哈夫曼编码方法，以及进一步学习c语言编码编写c语言程序实现对数据的游程压缩进一步完善程序，并开始撰写毕业论文总结毕设，完成论文，准备答辩指导教师：职称：教授 2月4日系级教学单位审批： 年 月 日摘要 本次毕业设计主要是针对于游程编码数据压缩算法的设计与实现，游程编码非常简单，编码、解码速度快，应用广泛。游程编码是针对于二元序列的一种编码方法，对于二值图像而言是一种编码方法，对连续的黑、白像素数(游程)以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法，其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之，其缺点是对于不重复的资料反而加大容量。游程编码即需大量的缓冲和优质信道，因此对数据游程编码后在进一步的进行哈夫曼编码已达到更完善的数据压缩。哈夫曼编码使用变长编码表对源符号进行编码，其中变长编码表是经过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 本文主要介绍了信源编码的分类、获得最佳编码的方法、哈夫曼树的构建方法以及游程编码的原理和实现技术，对游程长度编码技术做了较为全面地研究。包括游程数据压缩、解压缩过程，并给出了流程图；哈夫曼数据压缩、解压缩过程，并给出流程图和结果图。 关键词游程编码 哈夫曼编码 压缩AbstractThis graduation design is mainly based on run-length coding data compression algorithm design and implementation of run-length coding is very simple, encoding and decoding speed, wide application. Run-length coding is a coding method for binary sequence, is a kind of coding method for binary image, the black and white pixels of continuous (run) in different code code word. Run-length coding is a kind of simple nondestructive data compression method, the advantage is that of compression and decompression are very fast. Its method is to calculate a continuous length of data compression, the downside is to not repeat data instead of increasing capacity. Run-length coding is need a lot of buffer and channel, so the data after the run-length coding in further Huffman encoding has reached more .Source coding is mainly introduced in this paper the classification, the optimal method of coding, Huffman tree, construction methods, and the run-length coding principle and implementation technology, the length of the run-length encoding technology is done more comprehensive research. Including the run-length data compression and decompression process, and gives the flow chart; Huffman data compression and decompression process, chart and flow chart is given and the results.KeywordsRun-length coding Huffman encoding The compression 目 录摘要IAbstractII第1章 绪论11.1 课题背景11.2选题目的、意义21.3主要内容2第2章 信源编码分类32.1 信源编码3 2.1.1信源编码简介3 2.1.2信源编码的理论基础3 2.1.3信源编码的分类及作用42.2最佳变长编码4 2.2.1香农编码方法5 2.2.2费诺编码方法6 2.2.3哈夫曼编码方法72.3游程编码15 2.3.1游程长度15 2.3.2游程编码算法15 2.3.3游程编码特点16 2.3.4几种基于游程相关性的数据压缩方案162.4本章小结19第3章 游程编码以及哈夫曼编203.1 游程编码203.2哈夫曼编码过程233.3运行结果283.4本章小结30结论31参考文献33致谢35附录136附录241附录345附录450第1章 绪论1.1 课题背景信息时代人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大差距1。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为1 min，图像尺寸为640480 pixete，每秒播放30帧的非压缩彩色24位真彩色视频的信息量为：64048033060：Bytes，约为1.6GB(未含音频信息的容量)，如果用650 MB的CD-R来存放，需要3张。由此可见，在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的2。 数据压缩技术主要采用两种方法：一种是“保真率”较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是很高，但还原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常见的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(Hufman)编码、算术编码(AC)和游程长度编码(RLC)2。其中，游程长度编码是一种十分简单的压缩方法，编码解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMP，.TIF及.AVI等，都采用了这种压缩方法，特别适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以达到减少数据文件所占的存储空间的目的6。飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ 系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，因此十分有必要对无损压缩算法进行研究4。经过对游程编码(Run LengthEncoding,RLE)进行研究,结合哈夫曼编码。最后找到一种实现相对简单、压缩效果比较好的方法，即对游程编码后的数据在进一步的进行哈夫曼编码，采用该方法能够收到比较理想的效果。1.2选题目的、意义飞速发展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据安全性要求比较苛刻的领域，现在比较流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ 系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比较差或者算法实现比较困难，而游程编码却是一种是一种非常简单，且编码、解码速度很快编码方法。因此经过对于游程编码的研究能够比较快捷语简单的实现对于数据的无损压缩。1.3主要内容 本文主要介绍了信源编码中的几种最佳变长编码方法：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码，以及这几种编码的编码过程。然后主要描述了哈夫曼编码方法以及如何构造哈夫曼树。然后详细的介绍了游程编码的编码算法以及游程编码的特点。画出游程编码哈夫曼编码的流程图，以及得出的结果图，最后做出总结。 第2章 信源编码分类2.1 信源编码 2.1.1信源编码简介 编码实质上就是对信源的原始符号按一定规则进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的基本途径有两个：使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性3。 2.1.2信源编码的理论基础信源编码就是从信源符号到码符号的一种映射f，它把信源输出的符号ui变换成码元序列wi。 信源编码定义如图2-1：图2-1信源编码定义图信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 2.1.3信源编码的分类及作用信源编码的分类： 离散信源编码：独立信源编码,可做到无失真编码； 连续信源编码：独立信源编码,只能做到限失真信源编码； 相关信源编码：非独立信源编码。 编码的作用： 信源编码的作用之一是设法减少码元数目和降低码元速率，即一般所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。 2.1.4信源编码的历史 最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。另外，在数字电视领域，信源编码包括 通用的MPEG2编码和H.264（MPEGPart10 AVC）编码等 相应地，信道编码是为了对抗信道中的噪音和衰减，经过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力4。2.2最佳变长编码凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字称为最佳变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳编码的方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。2.2.1香农编码方法 香农第一定理指出了平均码长与信源之间的关系，同时也指出了能够经过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度Ki满足下式 I(xi)KI(xi)+1, （2-1）就能够得到这种码。这种编码方法就是香农编码。 香农编码法冗余度稍大，实用性不大，但有重要的理论意义。编码步骤如下：1）将信源消息符号按其出现的概率大小依次排列 p（x1）p（x2）p（xn） （2-2）2）确定满足下列不等式整数码长Ki： -log2p(xi)Ki-log2p(xi)+1 （2-3）3)为了编成唯一可译码，计算第i个消息的累加概率 Pi=p(xk) （2-4）4)将累加概率Pi变成二进制数。5)取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。设信源共7个符号消息，其概率和累加概率如表2-1，则其香农编码过程如表2-1。因此信源符号的平均码长为： （2-5） 平均信息传输率即编码效率为： （2-6） 表2-1 香农编码过程信源消息符号Ai符号概率P(Ai）累加概率Pi-logp(Ai)码字长度Ki码字A1A2A3A4A5A6A70.200.190.180.170.150.100.0100.20.390.570.740.890.992.342.412.482.562.743.346.663333347000001011100101111011111102.2.2费诺编码方法费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高，但它属于概率匹配编码它不是最佳的编码方法。费诺编码步骤：（1） 将信源消息符号按其出现的概率大小依次排列： 。（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。 (5) 信源符号所对应的码字即为费诺码。对表2-1中信源消息进行费诺编码，则编码过程如表2-2。则该费诺编码的平均码长：（2-7）信息传输速率（2-8）表2-2费诺编码过程消息符号Ai消息概率P（Ai）第一次分组第二次分组第三次分组第四次分组二元码字码长KiA10.2000002A20.19100103A30.1810113A40.1710102A50.15101103A60.101011104A70.01111114显然费诺码要比上述香农码的平均码长小，消息传输速率大，说明编码效率高。2.2.3哈夫曼编码方法 哈夫曼编码是一种常见的压缩方法。它的基本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。哈夫曼编码步骤：（1） 首先把信源中的消息出现的频率从小到大排列。（2） 每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。（3） 重复(2)，直到最后得到和为1的根节点。（4） 将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。对表2-1中的信源数据进行哈夫曼编码，编码过程如表2-3。表2-3哈夫曼编码过程信源符号Ai概率p(Ai)编码过程码字Wi码长KiA10.20 0.26 0.35 0.39 0.61 0 1 102A20.19 0.20 0.26 0.35 0 0.39 1112A30.18 0.19 0.20 0 0.26 10003A40.17 0.18 0 0.19 10013A50.15 0 0.17 10103A60.100 101104A70.01101114该哈夫曼码的平均码长为（2-9）信息传输速率 （2-10） 由此可见，哈夫曼编码的平均码长最小，消息传输速率最大，编码效率最高。哈夫曼编码是用概率匹配方法进行信源编码。她有两个明显的特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码6。 哈弗曼编码几乎是所有压缩算法的基础，其实这个算法并不复杂，简单的理解就是，如何用更短的bit来编码数据。 我们知道普通的编码都是定长的，比如常见的ASCII编码,每个字符都是8个bit:字符编码A00101001B00101010C00101011.这样，计算机就能很方便的把由0和1组成的数据流解析成原始信息，但我们知道，在很多情况下，数据文件中的字符出现的概率是不均匀的，比如在一篇英语文章中，字母“E”出现的频率最高，“Z”最低，如果我们使用不定长的bit编码，频率高的字母用比较短的编码表示，频率低的字母用长的编码表示，岂不是能够大大缩小文件的空间吗? 但这就要求编码要符合“前缀编码”的要求，即较短的编码不能是任何较长的编码的前缀，这样解析的时候才不会混淆，比如下面的编码方法就符合前缀原则：字符编码A0B10C110D1110E11110.根据这个码表，下面一段数据就能够唯一解析成原始信息了： 0 DABBDCEAAB要生成这种编码，最方便的就是用二叉树，考察一下下面这个树图2-2二叉树图 把要编码的字符放在二叉树的叶子上，所有的左节点是0，右节点是1，从根浏览到叶子上，因为字符只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，符合前缀原则编码就能够得到字符编码A00B010C011D10E11 现在我们能够开始考虑压缩的问题，如果有一篇只包含这五个字符的文章，而这几个字符的出现的次数如下： 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）显然，这颗树还能够进一步优化，使得编码更短，比如下面的编码 图2-3二叉树图 生成的数据长度为： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 (2-13) 能够看出，构造更优的二叉树，原则就是权重越大的叶子，距离根应该越近，而我们的终级目标是生成“最优”的二叉树，最优二叉树必须符合下面两个条件：所有上层节点都大于等于下层节点。某节点，设其较大的子节点为，较小的子节点为，下的任一层的所有节点都应大于等于下的该层的所有节点。 上面这个例子是比较简单的，实际的文件中，一个字节有256种可能的取值，因此二叉树的叶子节点多达256个，最终的树形可能非常复杂，但有一种非常精巧的算法能够快速地建起一棵最优二叉树，这种算法由D.Huffman（戴?哈夫曼）提出，下面我们先来介绍哈弗曼算法的步骤，然后再来证明经过这么简单的步骤得出的树形确实是一棵最优二叉树。 哈夫曼算法的步骤是这样的：从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。然后从节点序列中去除这两个节点，加入它们的父节点到序列中。重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。 比如上面的例子，哈弗曼树建立的过程如下:1) 列出原始的节点数据： 图2-4原始节点2) 将最小的两个节点C和E结合起来：图2-5C和E结合3) 再将新的节点和A组合起来 图2-6新节点结合图 4) 再将D节点加入 图2-7新节点结合图5) 如此循环，最终得到一个最优二叉树 图2-8最优二叉树图生成的数据文件长度为： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 下面我们用逆推法来证明对于各种不同的节点序列，用哈弗曼算法建立起来的树总是一棵最优二叉树：当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为:按照哈弗曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其它的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其它的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，因此这两个节点一定处在当前二叉树的最低一层。这两个新增的节点是最小的，因此无法和其它上层节点对换。符合我们前面说的最优二叉树的第一个条件。只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其它节点，也无法和同层其它节点重新结合，产生比它们的父节点更小的上层节点来和同层的其它节点对换。它们的父节点小于其它节点的父节点，它们又小于其它所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。 这样一步步逆推下去，在这个过程中哈弗曼树每一步都始终保持着是一棵最优二叉树。2.3游程编码2.3.1游程长度 游程长度RL(Run-Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度以及串的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。2.3.2游程编码算法 游程编码的基本原理是：用一个符号值或串长代替具有相同值的连续符号（连续符号构成了一段连续的“游程”，游程编码因此而得名），使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。 在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(l)。“0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，直到无限。 将任何(二元)序列变换成一一对应的游程长度序列，再按哈夫曼编码或其它方法处理以达到压缩码率的目的9。2.3.3游程编码特点 游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。另外，编程长度能够从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改进。 一般情况下游程长度越长，其概率越小，这在以前的计算中也能够看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为达到概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。再按哈夫曼编码或其它方法处理以达到压缩码率的目的。2.3.4几种基于游程相关性的数据压缩方案1）共前缀码 共前缀码编码时也是按照一定规律用尽量短的码字来表示游程形式的初始测试数据，但该编码压缩方案进一步考虑了相邻游程之间存在的联系。如果相邻游程的长度在同一组，则它们对应码字的前缀是相同的即共前缀，能够用一个标志位来表示这些相邻游程除第一个游程以外的其它游程的前缀，这样数据压缩率得以进一步提高。同组共前缀码的前缀和后缀的位数相同，前缀和后缀相加对应的十进制数比对应的游程长度多2，也就是说跟FDR 码相比，相同的码字所表示的游程长度少2，使压缩效果受到一些影响，因此对初始测试数据进行无关位(dont cares bit)填充时，要尽量时这种影响降到最低。所谓无关位是指无论它们的取值是0 还是1 都不会影响测试结果。不过由此也可看出待测试数据的游程长度加上2 所对应的FDR 码就是相应的共前缀码，若这两个相差为2 的游程长度在同一组内，则码字长度并没有增加，不会影响压缩效果。 共前缀码的前缀都是以1 开始，以0 结束的数字串，因此当相邻游程长度在同一组时，能够用数字0 来表示后面游程的码字前缀，后缀则不变，这样码字的长度进一步缩短。下面给出一个共前缀编码的实例：编码前的初始测试数据： 1 0000001 010001（47 位）；编码后的码字：110100 1000 110010 11100001 00011（29 位）。可见数据串01 和0001 的游程长度分别为13 和15，都在第三组，前缀都为1110，因此后一游程的码字前缀用标志位0 表示，其码字为0 0011。2）共游程码 前面介绍的共前缀码是利用游程长度同组的前缀相同，用标志位0 加码字后缀来表示后面的游程，从而进一步压缩初始测试数据。共游程码（Sharing Run Length Code，SRLC）与共前缀码的编码方案类似，该方案注意到初始测试数据中有的相邻游程是相同的，于是就用一个标志位来表示后面的相同游程，因此该方案被称为共游程码。显然该编码方案的数据压缩率比共前缀码高一些，不考虑相邻游程的长度相同的前提下，编码方法与共前缀码相同。对共游程码编码方案，如果有若干相邻游程相同，则后面的一个或多个相同游程都能够用唯一的标志位来代替，从而大大减少了编码码字的长度，即进一步提高了测试数据压缩率。共游程码的前缀都是以“1”开头以“0”结尾的数字串，没有以“0”开头的前缀，因此能够用数字0 来作为相邻相同游程的标志位，即后面相邻相同游程的码字只有1 位。显然相邻相同游程的长度越长，测试数据压缩率就越高。由于初始测试数据中存在着大量的无关位，能够有意识的对它们进行赋值填充，以增加长度相同的相邻游程的数量，从而降低码字的长度。例如数据串x ，其中的x 是无关位，如果把它填充为0则该数据串是一个长度为23 的0 游程，由编码码表可知其对应的码字为11101011（8 位）；如果把无关位赋值为1，则数据串变成了两个长度都为11的相邻0 游程，其对应的码字为110111 0（7 位），使码字的长度减少了1 位，提高了数据压缩效果。3）共前缀连续长度码共前缀连续长度码（Co- Prefixal Run Length codes，CPRL）也考虑了相邻游程的相关性。如果相邻游程的长度在同一组内，则同组的后面的相邻游程的前缀能够省略，则编码后码字的前缀越长，则压缩效果越明显。由于初始测试数据集中存在大量的无关位，能够适当的对这些无关位进行赋值填充，增加0 游程的长度，这些游程长度在同组的概率很高。该编码方案为了增加0 游程的长度，对填充后的测试数据采取了差分处理，即把测试数据等长划分并进行异或逻辑运算。经过对ISCAS- 89 基准电路硬故障测试集的分析对不同的电路各组共前缀次数的分布不均匀，因此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 码的编码实例：（参变量M=1）编码前的初始测试数据：0000001 0000001 0000111 0010111 1010010；对应的差分测试数据： 0000001 0000000 0000110 0010000 1000101（35位）；差分后的测试数据对应的FDR 码：110000 110101 00 1001 1010 1001 01（28 位）；对应的CPRL 码字：1100001 1010 00 10011 101 010 01（26 位）。2.4本章小结 本章主要介绍了信源编码中的几种最佳信源变长编码:香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码，以及这几种编码的编码过程,然后主要介绍了哈夫曼树的构成步骤，以及游程编码的算法和编码特点。第3章 游程编码以及哈夫曼编3.1 游程编码 游程编码是针对于二元序列的压缩编码方法，在二元序列中，只有两种符号，即“0”游程和“1”游程，“0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。而对二元序列游程编码主要是针对于每个游程长度以及总共有多少个游程。我在c语言编码过程中主要针对这两方面进行编码，即经过对“0”、“1”的变换次数来确定二元序列中总共有多少个游程；然后在确定每一个游程中游程的长度。两者综合即实现对于二元序列的游程编码。 用游程编码压缩数据时，首先要计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来。这种压缩数据的方法, 连续相同的字符及出现连续相同的次数越多，压缩比就越大，反之，压缩比就越小。数据压缩算法流程如下： 1) 打开源数据文件和压缩后的数据文件； 2) 从源数据文件中读取字符, 并把它放入一个寄存器中，然后再循环读取后面的字符，并与寄存器中的字符相比较。如果相等，则计数器加1，否则，把寄存器中的字符和计数器中数写入压缩数据文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把计数器置1。游程编码数据压缩算法流程图如图3-1：数据解码算法流程如下： 1) 打开压缩数据文件和恢复文件； 2) 从压缩文件中循环读出字符和该字符连续的个数, 在恢复文件中连续写入从压缩文件中读出的字符, 写的次数等于该字符连续的个数:。游程编码数据解压缩算法流程图3-2