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

本科毕业设计〔论文〕基于游程编码数据压缩算法的设计与实现2023年6月本科毕业设计〔论文〕基于游程编码数据压缩算法的设计与实现燕山大学毕业设计〔论文〕任务书学院：里仁学院系级教学单位：学号学生姓名专业班级题目题目名称基于游程编码数据压缩算法的设计与实现题目性质1.理工类：工程设计〔√〕；工程技术实验研究型〔〕；理论研究型〔〕；计算机软件型〔〕；综合型〔〕〔〕；3.外语类〔〕；4.艺术类〔〕题目类型1.毕业设计〔√〕2.论文〔〕题目来源科研课题〔〕生产实际〔〕自选题目〔√〕主要内容是基于游程编码数据压缩算法的设计与实现基本要求用c语言完成游程编码，完成哈夫曼编码；并画出流程图和结果图，得出相应结论。参考资料周次第1～4周第5～8周第9～13周第14～15周第16～17周应完成的内容熟悉课题，查阅、搜集相关资料，并完成开题报告学习游程编码、哈夫曼编码方法，以及进一步学习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-lengthcodingHuffmanencodingThecompression目录TOC\o"1-3"\h\u摘要IAbstractII第1章绪论11.1课题背景1选题目的、意义22第2章信源编码分类32.1信源编码32.1.1信源编码简介3344567151515161619第3章游程编码以及哈夫曼编20游程编码20232830结论31参考文献33致谢35附录136附录241附录345附录450绪论1.1课题背景信息时代人们对使用计算机获取信息、处理信息的依赖性越来越高。多媒体计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体承载的由模拟量转化成数字量信息的吞吐、存储和传输的问题。数字化了的视频和音频信号的数量之大是惊人的，与硬件技术所能提供的计算机存储资源和网络带宽之间有很大差距[1]。这样，对多媒体信息的存储和传输造成了很大困难，成为阻碍人们有效获取和利用信息的一个瓶颈问题。多媒体信息使用的前提是进行有效的压缩。例如一段时间长度为1min，图像尺寸为640×480pixete，每秒播放30帧的非压缩彩色24位真彩色视频的信息量为：640×480×3×30×60：1658880000Bytes，约为1.6GB(未含音频信息的容量)，如果用650MB的CD-R来存放，需要3张。由此可见，在视频信息的处理及应用过程中压缩及解压缩技术是十分必要的[2]。数据压缩技术主要采用两种方法：一种是“保真率〞较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是很高，但复原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(Hufman)编码、算术编码(AC)和游程长度编码(RLC)[2]。其中，游程长度编码是一种十分简单的压缩方法，编码／解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMP，.TIF及.AVI等，都采用了这种压缩方法，尤其适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以到达减少数据文件所占的存储空间的目的[6]。飞速开展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据平安性要求比拟苛刻的领域，现在比拟流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比拟差或者算法实现比拟困难，因此十分有必要对无损压缩算法进行研究[4]。通过对游程编码(RunLengthEncoding,RLE)进行研究,结合哈夫曼编码。最后找到一种实现相对简单、压缩效果比拟好的方法，即对游程编码后的数据在进一步的进行哈夫曼编码，采用该方法可以收到比拟理想的效果。选题目的、意义飞速开展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据平安性要求比拟苛刻的领域，现在比拟流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比拟差或者算法实现比拟困难，而游程编码却是一种是一种非常简单，且编码、解码速度很快编码方法。所以通过对于游程编码的研究能够比拟快捷语简单的实现对于数据的无损压缩。本文主要介绍了信源编码中的几种最正确变长编码方法：香农〔Shannon〕、费诺〔Fano〕、哈夫曼〔Huffman〕编码，以及这几种编码的编码过程。然后主要描述了哈夫曼编码方法以及如何构造哈夫曼树。然后详细的介绍了游程编码的编码算法以及游程编码的特点。画出游程编码哈夫曼编码的流程图，以及得出的结果图，最后做出总结。第2章信源编码分类2.1信源编码2.1.1信源编码简介编码实质上就是对信源的原始符号按一定规那么进行的一种变换。编码可分为信源编码和信道编码。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体的说就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短码字序列的方法。信源编码的根本途径有两个：使序列中的各个符号尽可能地相互独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性[3]。信源编码就是从信源符号到码符号的一种映射f，它把信源输出的符号ui变换成码元序列wi。信源编码定义如图2-1：图2-1信源编码定义图信源编码理论是信息论的一个重要分支,其理论根底是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的根底；限失真信源编码定理：是连续信源/模拟信号编码的根底。信源编码的分类：离散信源编码：独立信源编码,可做到无失真编码；连续信源编码：独立信源编码,只能做到限失真信源编码；相关信源编码：非独立信源编码。编码的作用：信源编码的作用之一是设法减少码元数目和降低码元速率，即通常所说的数据压缩：作用之二是将信源的模拟信号转化成数字信号，以实现模拟信号的数字化传输。2.1.4信源编码的历史最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：Huffman编码、算术编码、L-Z编码，这三种都是无损编码，另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余，更加有效、经济地传输，最常见的应用形式就是压缩。另外，在数字电视领域，信源编码包括通用的MPEG—2编码和H.264〔MPEG—Part10AVC〕编码等相应地，信道编码是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力[4]。但凡能载荷一定的信息量，且码字的平均长度最短，可别离的变长码的码字称为最正确变长码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最正确编码的方法主要有：香农〔Shannon〕、费诺〔Fano〕、哈夫曼〔Huffman〕编码等。香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长到达极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度Ki满足下式I(xi)≤K﹤I(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码字A1A2A3A4A5A6A70333334700000101110010111101111110费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率大，编码效率高，但它属于概率匹配编码它不是最正确的编码方法。费诺编码步骤：将信源消息符号按其出现的概率大小依次排列：。〔2〕将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0〞和“1〞。〔3〕将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0〞和“1〞。〔4〕如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。对表2-1中信源消息进行费诺编码，那么编码过程如表2-2。那么该费诺编码的平均码长：〔2-7〕信息传输速率〔2-8〕表2-2费诺编码过程消息符号Ai消息概率P〔Ai〕第一次分组第二次分组第三次分组第四次分组二元码字码长KiA100002A2100103A310113A410102A5101103A61011104A7111114显然费诺码要比上述香农码的平均码长小，消息传输速率大，说明编码效率高。哈夫曼编码是一种常见的压缩方法。它的根本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。哈夫曼编码步骤：首先把信源中的消息出现的频率从小到大排列。每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比拟，新的根节点参与比拟。重复(2)，直到最后得到和为1的根节点。将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。对表2-1中的信源数据进行哈夫曼编码，编码过程如表2-3。表2-3哈夫曼编码过程信源符号Ai概率p(Ai)编码过程码字Wi码长KiA1 0.260.350.390.6101102A2 0.260.3500.391112A3 0.2000.2610003A40.1800.1910013A500.1710103A60101104A7101114该哈夫曼码的平均码长为〔2-9〕信息传输速率〔2-10〕由此可见，哈夫曼编码的平均码长最小，消息传输速率最大，编码效率最高。哈夫曼编码是用概率匹配方法进行信源编码。他有两个明显的特点：一是哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码[6]。哈弗曼编码几乎是所有压缩算法的根底，其实这个算法并不复杂，简单的理解就是，如何用更短的bit来编码数据。

我们知道普通的编码都是定长的，比方常用的ASCII编码,每个字符都是8个bit:字符编码A00101001B00101010C00101011这样，计算机就能很方便的把由0和1组成的数据流解析成原始信息，但我们知道，在很多情况下，数据文件中的字符出现的概率是不均匀的，比方在一篇英语文章中，字母“E〞出现的频率最高，“Z〞最低，如果我们使用不定长的bit编码，频率高的字母用比拟短的编码表示，频率低的字母用长的编码表示，岂不是可以大大缩小文件的空间吗?

但这就要求编码要符合“前缀编码〞的要求，即较短的编码不能是任何较长的编码的前缀，这样解析的时候才不会混淆，比方下面的编码方法就符合前缀原那么：字符编码A0B10C110D1110E11110根据这个码表，下面一段数据就可以唯一解析成原始信息了：

要生成这种编码，最方便的就是用二叉树，考察一下下面这个树

图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，无法再进一步优化。然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为:按照哈弗曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于〔或等于〕这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。这样一步步逆推下去，在这个过程中哈弗曼树每一步都始终保持着是一棵最优二叉树。游程长度RL(Run-Length)，简称游程或游长，指的是由字符(或信号取样值)构成的数据流中各个字符重复出现而形成的字符的长度。如果给出了形成串的字符，串的长度以及串的位置，就能恢复出原来的数据流，游程长度编码(RLC)就是用二进制码字给出这些信息的一类方法。游程编码的根本原理是：用一个符号值或串长代替具有相同值的连续符号〔连续符号构成了一段连续的“游程〞，游程编码因此而得名〕，使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时，一次记录该代码及相同代码重复的个数，从而实现数据的压缩。在二元序列中，只有两种符号，即“0〞和“1〞，这些符号可连续出现，连“0〞这一段称为“0〞游程，连“1〞这一段称为“1〞游程。它们的长度分别称为游程长度L(0)和L(l)。“0〞游程和“l〞游程总是交替出现的。如果规定二元序列是以“0〞开始，第一个游程是“0〞游程，第二个必为“1〞游程，第三个又是“0〞游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，…，直到无限。将任何(二元)序列变换成一一对应的游程长度序列，再按哈夫曼编码或其他方法处理以到达压缩码率的目的[9]。游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。此外，编程长度可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改良。一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为到达概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。再按哈夫曼编码或其他方法处理以到达压缩码率的目的。1〕共前缀码共前缀码编码时也是按照一定规律用尽量短的码字来表示游程形式的初始测试数据，但该编码压缩方案进一步考虑了相邻游程之间存在的联系。如果相邻游程的长度在同一组，那么它们对应码字的前缀是相同的即共前缀，可以用一个标志位来表示这些相邻游程除第一个游程以外的其他游程的前缀，这样数据压缩率得以进一步提高。同组共前缀码的前缀和后缀的位数相同，前缀和后缀相加对应的十进制数比对应的游程长度多2，也就是说跟FDR码相比，相同的码字所表示的游程长度少2，使压缩效果受到一些影响，因此对初始测试数据进行无关位(don’tcaresbit)填充时，要尽量时这种影响降到最低。所谓无关位是指无论它们的取值是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〕共前缀连续长度码共前缀连续长度码〔Co-PrefixalRunLengthcodes，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〕编码前的初始测试数据：00000010000001000011100101111010010；对应的差分测试数据：00000010000000000011000100001000101〔35位〕；差分后的测试数据对应的FDR码：1100001101010010011010100101〔28位〕；对应的CPRL码字：11000011010001001110101001〔26位〕。本章主要介绍了信源编码中的几种最正确信源变长编码:香农〔Shannon〕、费诺〔Fano〕、哈夫曼〔Huffman〕编码，以及这几种编码的编码过程,然后主要介绍了哈夫曼树的构成步骤，以及游程编码的算法和编码特点。第3章游程编码以及哈夫曼编游程编码游程编码是针对于二元序列的压缩编码方法，在二元序列中，只有两种符号，即“0〞游程和“1〞游程，“0〞游程和“l〞游程总是交替出现的。如果规定二元序列是以“0〞开始，第一个游程是“0〞游程，第二个必为“1〞游程，第三个又是“0〞游程等等。而对二元序列游程编码主要是针对于每个游程长度以及总共有多少个游程。我在c语言编码过程中主要针对这两方面进行编码，即通过对“0〞、“1〞的变换次数来确定二元序列中总共有多少个游程；然后在确定每一个游程中游程的长度。两者综合即实现对于二元序列的游程编码。用游程编码压缩数据时，首先要计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来。这种压缩数据的方法,连续相同的字符及出现连续相同的次数越多，压缩比就越大，反之，压缩比就越小。数据压缩算法流程如下：1)翻开源数据文件和压缩后的数据文件；2)从源数据文件中读取字符,并把它放入一个存放器中，然后再循环读取后面的字符，并与存放器中的字符相比拟。如果相等，那么计数器加1，否那么，把存放器中的字符和计数器中数写入压缩数据文件中，然后再把存放器中字符不相等的字符放入存放器中，并把计数器置1。游程编码数据压缩算法流程图如图3-1：数据解码算法流程如下：1)翻开压缩数据文件和恢复文件；2)从压缩文件中循环读出字符和该字符连续的个数,在恢复文件中连续写入从压缩文件中读出的字符,写的次数等于该字符连续的个数:。游程编码数据解压缩算法流程图3-2图3-1游程编码数据压缩算法游程图图3-2游程编码数据解码流程图哈夫曼编码是一种常见的压缩方法。它的根本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的。要完成哈夫曼的编码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码。建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点〔如果编码表共有N个字符，那么2*N-1就为最终根节点〕为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。对于哈夫曼编码树来说，由于哈夫曼编码是前缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。建立哈夫曼树的流程图如图3-3：图3-3构建哈夫曼树流程图构建完哈夫曼树后，根据建立哈夫曼树建立哈夫曼码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子那么对其编码‘0’，如果当前节点为右子那么对其编码‘1’。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。构建哈夫曼编码表的算法流程图如图3-4：有了码表就可以进行编码了。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件翻开，将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比拟，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。编码流程图如图3.4：在解码时先翻开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是‘0’的时候，那么索引走向左子节点；当是‘1’的时候，那么走向右子节点。以此类推，一直走到叶子节点为止，那么当前叶子节点所代表的字符即为前一段密文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕，并将解码结果存入到新的解码文件当中。在解码之前，还应该先确认之前是否建立了哈夫曼树并且是否构建了编码表。不过由于本次将‘a’到‘z’都进行了编码，所以此步省略了，因为编码表是唯一的。需要的时候可以在Encoder函数中先进行判定。解码图：进行完编码后的平均码长为：〔3-1)信息传输速率：〔3-2〕压缩前二元序列长度为49，进行游程编码后序列长度为36，再进行哈夫曼编码后序列长度为29。即总的压缩效率为59%，而游程压缩效率为80%。所以进行两次编码后的压缩效率比单一一次的游程编码的压缩效率高很多。这次的仿真只是对于一段很短的二元序列，而且各游程长度也很短，所以还不能过很好的表达出游程编码的压缩效率。但对于二值图像序列的就能够很好的表达出游程编码的压缩效率，然后在进行哈夫曼编码就能够很好的表达出这种方法的压缩效率。游程编码是一种简单的快捷的编码方法，能够有效的对二元序列进行无损压缩，一般情况下，游程长度越大，其概率越小，而且随着长度的增大逐渐趋向零。对于小概率的码字，其长度未到达概率匹配或较长，损失不会太大，也就对平均码字长度影响较小，这样就可以对长游程不严格按哈夫曼码步骤进行。哈夫曼码是用概率匹配方法进行信源编码。它有两明显的个特点：一是哈夫曼编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；一是缩减信源的最后两个码字总是最后一位不同，从而保证哈夫曼编码是即时码。哈夫曼变长码的效率是相当高的，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也简单的多。但应当注意要到达很高的效率仍然需要按长序列来计算，这样才能使平均码字长度降低。结论游程编码是图像压缩的根本算法，因此对于二元相关信源数据编码研究变得尤为重要。为此，本人对游程编码压缩原理做了深入的学习，并结合哈夫曼编码把其应用到二元相关信源数据的压缩。经过这段时间的学习与实践，我对二元相关信源游程编码与信号编码的开展及现状有了更深刻的认识，意识到数据压缩与解压对于信息时代的巨大影响及其潜在的经济效益，并对MicrocsoftVisualC++软件有了进一步的了解。经过这一段的学习，我想我对于知识的猎取是有限的，关键是我学会了如何用认真、严谨的学习态度去面对工作，如何用自学的方法来处理问题，如何把书籍和网上查找到的信息运用到实践中去。二元相关游程编码一般不直接应用与多灰度图像，但比拟适于二值图像的编码，例如图像的编码等。为了到达较好的压缩效果，二值图像游程编码需和其它一些编码混合使用。本文中我才用游程编码和哈夫曼编码混合使用。游程压缩作为数据压缩技术的一个分支，理论浅显，走过半个多世纪的离散余弦变换理论在数据压缩领域至今不衰；近来，小波变换理论更使数据压缩技术登峰造极，图像压缩的JPEG2000标准是小波理论傲视群雄。可以预见，新的数学理论将不断为数据压缩技术输入新鲜血液，因此数学理论决不可偏废。最后，给出一点使用无损压缩算法的建议。由于每种无损压缩都有自己的适用范围，压缩比受不失真要求的限制，真正意义上高压缩比的通用无损压缩算法目前哈有待继续研究。因此在选用算法之前需要对图像数据进行分析，使用时根据数据表现出的特点，利用算法的思想，灵活使用算法是提高压缩比的有效手段。参考文献SOC测试数据压缩方法.计算机工程与应用.2023，46〔25〕[12]BoYe,QianZhao,DuoZhou,XiaohuaWang,MinLuo.Testdatacompressionusingalternatingvariablerun-lengthcode.INTEGRATION,theVLSIjournal.2023[14]方建平,郝跃,刘红侠,SOC致谢本设计的完成是在我们的导师许成谦老师的细心指导下进行的。在每次设计遇到问题时老师不辞辛苦的讲解才使得我的设计顺利的进行。从设计的选题到资料的搜集直至最后设计的修改的整个过程中，花费了许老师很多的珍贵时间和精力，在此向导师表示衷心地感谢！导师严谨的治学态度，开拓进取的精神和高度的责任心都将使学生受益终生！

还要感谢和我同一设计小组的几位同学，是你们在我平时设计中和我一起探讨问题，并指出我设计上的误区，使我能及时的发现问题把设计顺利的进行下去，没有你们的帮助我不可能这样顺利地结稿，在此表示深深谢意。附录1燕山大学本科毕业设计〔论文〕开题报告课题名称：基于游程编码数据压缩算法设计与实现年级专业：09通信工程学生姓名：李悦指导教师：许成谦完成日期：2023年3月27日选题的依据：飞速开展的数据压缩和图像编码技术，给多媒体数据传输和数据存储带来极大的快捷和便利。但在某些数据平安性要求比拟苛刻的领域，现在比拟流行和压缩效果好的压缩算法几乎都属于有损范畴，对原始数据压缩处理后有不同程度的损伤，无法完全恢复，以至于不能满足技术要求，现有的无损压缩方法，如Huffman、LZ系列、算术编码等压缩方法尽管在某些方面各有优点，但压缩效果比拟差或者算法实现比拟困难，因此十分有必要对无损压缩算法进行研究。通过对游程编码(RunLengthEncoding,RLE)进行研究,最后提出一种实现相对简单、压缩效果比拟好的算法，采用该算法可以收到比拟理想的效果，根本克服由于RLE自身特点而引起的数据扩张的现象。目前已提出的比拟有效的测试压缩编码算法主要有3大类：〔1〕基于统计的编码压缩算法，如哈夫曼〔Huffman〕编码、VIHC编码；〔2〕基于游程〔run-lengthcoding〕的编码压缩算法，如Golomb编码、FDR〔Frequency-directedrun-length〕编码算法、Variable-Tail算法、交替游程算法〔alternatingrun-length〕；〔3〕基于字典的编码算法，如Fixed-Length-Index-Dictionary算法、CDCR〔combiningdictionarycodingandLFSRreseeding〕。在以上编码方法中，基于游程的编码压缩算法的效果是较好的，而且这种压缩算法的解压电路是不依赖于测试向量集的，这一点在待测电路重新设计或测试向量集合发生修改的情况下特别有用[1]。基于游程编码中的各种编码:〔1〕Golomb码和FDR码都是基于测试集中0个数多于1个数的事实而对连续的0进行编码，并未把连续的0和1都进行编码，因此存在一定的缺陷。(2)交替游程编码〔AlternativeRun-LengthEncoding〕，这种编码算法既考虑测试数据中连续出现的“0〞，也考虑连续出现的“1〞，可以大大减少长度较短的游程数量，提高了编码效率，硬件开销也小，取得了比拟好的效果[2][3]。(3)共游程编码，这种编码除了像传统的变长到变长的编码方案使用较短的代码字来表示整个游程,还同时利用连续游程之间的相关性,对于连续的两个或多个相同游程,后续每个游程仅用一位就可以表示。理论分析和实验结果证明本方案相对于传统的游程编码具有更好的数据压缩效果[4]。〔4〕变游程编码，这种编码算法既考虑测试数据中连续出现的“0〞，也考虑连续出现的“1〞，大大减小了长度较短游程的数量，提高了编码效率[5]。另外，将测试集中的无关位〔don’t-cares〕用特定的方法指定后，这种变游程编码可以直接对原始测试集操作，因此解码不需要CSR，降低了解码器的硬件开销。总之，游程编码压缩数据的方法就是通过对连续出现的“0〞、“1〞进行进行相应的压缩来减小信源大小，以实现数据压缩。选题意义：通过本次的毕业设计，使我进一步的了解与掌握了游程编码技术以及相关的压缩编码方面的知识，使我在课题的实施过程中学会已有知识的应用，培养自己自主学习和发现问题、解决问题的能力。主要的研究内容、研究思路：设计内容游程编码是一种是一种相比照拟简单而且比拟容易实现的无损压缩编码，在二元序列中，只有两种符号，即“0〞和“1〞，这些符号可连续出现，连“0〞这一段称为“0〞游程，连“1〞这一段称为“1〞游程。它们的长度分别称为游程长度L(0)和L(l)。“0〞游程和“l〞游程总是交替出现的。如果规定二元序列是以“0〞开始，第一个游程是“0〞游程，第二个必为“1〞游程，第三个又是“0〞游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，…，直到无限。将任何(二元)序列变换成一一对应的游程长度序列，再按哈夫曼编码或其他方法处理以到达压缩码率的目的。本次课设主要是编写一款c程序来完成游程的数据压缩。设计思路1、熟悉游程编码完成，能够完成信源数据的游程压缩，然后按照哈夫曼编码方法处理数据已到达压缩码率的目的。2、熟悉vc++的应用方法，能够比拟熟悉的编写读懂程序。3、编写c程序来实现游程压缩以及相应的解压缩。毕业设计工作进度安排〔1〕1-4周熟悉课题，查阅、搜集相关资料，并认真学习研究并撰写开题报告。〔2〕5-10周学会运用游程编码压缩/解压信源数据的算法，并计算相应数据；准备中期报告〔3〕11-13周学习并编写相对应的c语言程序已到达数据压缩与解压。〔4)14-15周进一步完善程序，并开始撰写论文。〔5〕16-17周总结毕设，完成论文，准备辩论。参考文献SOC测试数据压缩方法.计算机工程与应用.2023，46〔25〕[12]BoYe,QianZhao,DuoZhou,XiaohuaWang,MinLuo.Testdatacompressionusingalternatingvariablerun-lengthcode.INTEGRATION,theVLSIjournal.2023[14]方建平,郝跃,刘红侠,SOC附录2燕山大学本科毕业设计〔论文〕文献综述课题名称：基于游程编码数据压缩算法设计与实现年级专业：09通信工程学生姓名：李悦指导教师：许成谦完成日期：2023年3月20日一、课题国内外现状数据压缩技术主要采用两种方法：一种是“保真率〞较高的无损压缩法；另一种是以损失信息细节而换取较高压缩比的有损压缩法。无损压缩虽然压缩比不是很高，但复原后的文件与原数据文件完全相同，从而保证了信息细节的不失真，常用的方法有统计式压缩法和字典式压缩法，统计式压缩法的编码方案主要是霍夫曼(Hufman)编码、算术编码(AC)和游程长度编码(RLC)。其中，游程长度编码是一种十分简单的压缩方法，编码／解码的速度也非常快，因此得到了广泛的应用。许多图形和视频文件，如BMP，.TIF及.AVI等，都采用了这种压缩方法，尤其适用于文本(文件)数据压缩，它主要是去除文本中的冗余字符或字节中的冗余位以到达减少数据文件所占的存储空间的目的。研究主要成果基于游程编码中的各种编码:〔1〕Golomb码和FDR码都是基于测试集中0个数多于1个数的事实而对连续的0进行编码，并未把连续的0和1都进行编码，因此存在一定的缺陷[1]。(2)交替游程编码〔AlternativeRun-LengthEncoding〕，这种编码算法既考虑测试数据中连续出现的“0〞，也考虑连续出现的“1〞，可以大大减少长度较短的游程数量，提高了编码效率，硬件开销也小，取得了比拟好的效果[2][3]。(3)共游程编码，这种编码除了像传统的变长到变长的编码方案使用较短的代码字来表示整个游程,还同时利用连续游程之间的相关性,对于连续的两个或多个相同游程,后续每个游程仅用一位就可以表示。理论分析和实验结果证明本方案相对于传统的游程编码具有更好的数据压缩效果[4]。〔4〕变游程编码，这种编码算法既考虑测试数据中连续出现的“0〞，也考虑连续出现的“1〞，大大减小了长度较短游程的数量，提高了编码效率[5]。另外，将测试集中的无关位〔don’t-cares〕用特定的方法指定后，这种变游程编码可以直接对原始测试集操作，因此解码不需要CSR，降低了解码器的硬件开销。三、开展趋势：游程压缩作为数据压缩技术的一个分支，理论浅显，压缩比之高已经让人刮目相看，走过半个多世纪的离散余弦变换理论在数据压缩领域至今不衰；近来，小波变换理论更使数据压缩技术登峰造极，图像压缩的JPEG2000标准是小波理论傲视群雄。可以预见，新的数学理论将不断为数据压缩技术输入新鲜血液，因此数学理论决不可偏废[7]。四、存在问题游程编码仍是变长码，有其固有的缺点，及需要大量的缓冲和优质的信道。此外，编程长度可以从一直到无限，这在码字的选择和码表的建立方面都有困难，实际应用是尚需采用某些措施来改良。一般情况下游程长度越长，其概率越小，这在以前的计算中也可以看见，而且将随着长度的增大渐进向零。对于小概率的码字，其长度为到达概率匹配或较长，损失不会太大，也就是对平均码字长度影响较小。五、主要参考文献SOC测试数据压缩方法.计算机工程与应用.2023，46〔25〕[12]BoYe,QianZhao,DuoZhou,XiaohuaWang,MinLuo.Testdatacompressionusingalternatingvariablerun-lengthcode.INTEGRATION,theVLSIjournal.2023[14]方建平,郝跃,刘红侠,SOC附录3燕山大学本科毕业设计〔论文〕中期报告课题名称：基于游程编码数据压缩算法设计与实现年级专业：09通信工程学生姓名：李悦指导教师：许成谦完成日期：2023年3月20日任务书中本阶段工作目标与任务要求任务书中本阶段工作目标是设计与完成c语言的游程编码然后在进行哈夫曼编码，实现二元数据的无失真的压缩编码。本阶段的任务要求：了解并掌握c语言的一些编码算法；对二元数据进行游程编码并把编码结果保存到指定位置；对进行完游程编码的二元序列在进行哈夫曼编码，得到压缩数据，并保存到指定文件。目前已完成任务情况1、学习并掌握了更多的c语言程序设计方法，比方结构体struct、c文件的读写；2、游程编码的程序流程图如图1；3、游程编码又称“运行长度编码〞或“行程编码〞，是一种统计编码，该编码属于无损压缩编码，是栅格数据压缩的重要编码方法。对于二值图有效。在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号，可大幅度减少数据量。游程编码记录方式有两种：①逐行记录每个游程的终点列号：②逐行记录每个游程的长度〔像元数〕第一种方式：AAABBACCCA图1游程编码流程图这个栅格图形就记为：A,3，B,5A,1，C,4，A,5第二种就记作：A,3，B,2A,1，C,3，A,1；4、利用c语言读写方式来实现对二元序列游程编码后在进行哈夫曼编码；5、哈夫曼编码是一种常见的压缩方法。它的根本原理是按照信号出现概率大小顺序排列信源信号，并设法按逆序分配码字字长，使编码的码字是可辨识的；6、哈夫曼编码步骤：1〕将信号源的符号按照出现概率递减的顺序排列。〔注意，一定要递减〕2〕将最下面的两个最小出现概率入行合并相加，得到的霍夫曼编码压缩结果作为新符号的出现概率。3〕重复进行步骤1和2直到概率相加的结果等于1为止。4〕在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。5)记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。三、存在的问题和拟解决方法1、进行游程编码时不能确定首位游程是“0〞游程还是“1〞游程解决方法：编码时直接规定首位是“1〞游程或是“0〞游程，即首位添加一个“1〞或一个“0〞，这样有利于相应的解码；我假定首位游程为“1〞游程。如何运用c语言进行游程编码解决方法：先记录二元序列中游程个数，然后确定每个游程长度，最后两者结合求出结果及游程编码结果，在求出每个游程在二元序列中所占百分比，以便于之后的哈夫曼编码。如何对文件进行哈夫曼编码构造出一个完整的哈夫曼树，能够很好的实现编码和译码之间的互换过程，使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。在算法执行中，哈夫曼树是由假设干棵树组成的森林，通过不断地合作树，最后得到一棵哈夫曼树。附录4燕山大学本科毕业设计〔论文〕外文翻译课题名称：基于游程编码数据压缩算法设计与实现年级专业：09通信工程学生姓名：李悦指导教师：许成谦完成日期：2023年3月20日译文：RLH：位图压缩技术基于游程长度和Huffman编码的原始研究文章关键词：位图索引位图压缩霍夫曼编码运行长度编码摘要在本文中，我们提出了一个应用在压缩位图索引技术数据仓库。这种技术被称为运行长霍夫曼〔RLH〕，是基于运行长度编码和Huffman编码。此外，我们提出了一个变种的RLH叫RLH-N。RLH-N的N位字压缩位图被分成RLH。RLH和实施RLH-N和实验比拟良好的字对齐混合〔WAH〕位图压缩技术，一直据报道，提供最短的查询执行时间。实验中讨论本文说明：〔1〕，RLH压缩位图小于相应议员压缩的位图，而不管该索引的属性的基数，〔2〕RLH-N压缩位图是小于相应的华压缩位图一定范围内的基数，该索引的属性，〔3〕RLH和RLH-N-压缩位图，提供更短的查询响应时间比华压缩位图，对于某些索引属性的基数范围，以及〔4〕RLH-N确保更短的更新时间的压缩比RLH位图。1介绍数据仓库〔DW〕是一个庞大的数据库，集成来自多个存储系统的数据企业内的。通过这些数据的分析所谓的联机分析处理〔OLAP〕应用，系统蒸发散，基于复杂的查询。OLAP查询加盟多级表和过滤数据的事实表查询谓词的手段。通常情况下，分析数据存储在事实数据表中，通过国外的参考尺寸钥匙。其结果是，有许多事实记录具有相同值的给定的外键。位图索引[14,17]的根本数据之一衍生权证查询优化结构。根本上，在最简单的形式中，位图索引所谓的位图组成的，其中每一个是一个位向量〔见第2局部〕。每个位被映射到一个排在索引表。如果一个位的值等于1，那么然后此位对应的行具有一定的索引属性值。查询谓词涉及的属性可以通过位图索引索引通过执行按位AND，OR，或不快速答复位图上的操作，这是一个很大的优势，位图索引。一个位图索引的大小在很大程度上依赖于的基数〔域宽〕索引属性，即，一个位图索引的大小增加时的基数索引的属性增加。因此，属性高基数〔宽域〕成为位图索引非常大。因此，他们无法适应主存储器和访问数据的效率与支持等指标恶化。1.1相关工作为了提高数据访问的效率支持位图索引定义属性高基数，以下两种方法在研究文献中已被提出，即：〔1〕扩展的根本的位图索引的结构〔2〕位图索引的压缩技术。在第一种方法中，两种主要的技术，一般所谓的分级，以及位切片，可以区分的。索引属性的值是被分割成范围。位图的构建代表一个给定的范围内的值，而不是一个独特的值。一个位图中的位表示的值是否一个给定的属性的一排是在一个特定的范围之内。这技术也可以应用于一个索引值时属性被分成套。在文献[12]中提出的技术可以被归类为分级更一般的形式。[12]套属性值代表一起在一个位图索引。这样的技术减少存储空间的高属性基数。选择的属性值表示的这种索引是基于查询模式频率上的分布，以及属性值。在[5]中，提出了另一种形式的分箱。这技术，称为属性映射，专注于管理箱分配到所有的索引属性的总数。一属性映射定义每个属性的属性，如使用该属性的查询的集合，分配值的属性或属性的编码值。的属性被表示为位向量。一个查询处理器需要扩展，以便使用属性映射。物业地图支持多属性查询，不平等查询或高选择性查询，它们更小于位图索引。第二种方法是基于所谓的位切片指数[4,17,37]。的有序列表，它被定义每一个索引值属性上的相同数量的n个比特来表示。作为一个因此，编码值表中的格式为n位图。该位图被称为位片。数据检索和计算重刑支持的位分片索引算术metic[20]或通过一个专用的检索功能[37]。另外，映射的数据结构所需的编码值映射到他们的真实值[37]。在第二种方法中，以提高工作效率位图索引的高基数上定义的属性，使用不同的位图的压缩技术。二在主无损耗的技术可以区分，即字节对齐的位图压缩锡永〔BBC〕[2]和字对齐混合〔WAH〕[26,33-35]。英国播送公司〔BBC〕和华是基于所谓的运行长度编码。根本上，在这种编码中，连续的向量。位相同的位值〔无论是''0''或''1''〕的一个实例的值〔例如，''1''〕，表示为计数的值。BBC英国播送公司〔BBC〕和华的根本区别是位图划分成8位字，而华分位图到31位的话。更详细的描述华第2.2节中给出。英国播送公司〔BBC〕和华提供最好的压缩比位图描述行有序索引属性的值。否那么，压缩比为恶化。对于密集均匀分布分布式数据位的值“1〞是密集的，但他们别离与比特值“0〞，因此，它可能是很难找到连续位向量的值''0''或''1''长度为n的有8位，为英国播送公司〔BBC〕和N个31位华。然而，另一种技术，称为近似编码〔AE〕，用于压缩位图索引，提出了在[3]。AE提供近似查询结果。假命中保证不会发生，即，满足查询的所有行谓词纳入查询结果。此外，本误报〔即准确性，行不满足有时包含在查询查询谓词结果集〕的范围从90％到100％。AE是基于Bloom过滤器。在AE，设置位图被视为一个布尔值矩阵。的矩阵表示中以压缩格式所谓的近似位图〔AB〕。为了压缩的布尔矩阵，它的编码分为AB多个哈希函数，基于布鲁姆过滤器。对于每一个向量在矩阵位，散列字符串HS是作为一个行号的功能构造和矩阵中的列数。接下来，K独立的哈希功能应用了HS。所指出的位置哈希值被设置为''1''AB。在[11,18]，重新排序的列或行讨论矩阵可以提高集群的相关细胞。这样技术也可以适用于位图索引被看作是矩阵。主要的想法是重新排列位图矩阵，以获得更好的聚类''0''和''1''细胞，然后压缩矩阵。由于采用了重新排序时，压缩比可以得到改善。不幸的是，在重组问题是NP-hard的[11]位图索引，实施了重大市售CIAL数据库管理系统中，可以是明确由用户定义的，例如，甲骨文，SybaseIQ中，模型204，可以隐式地由系统使用，例如，MSSQL效劳器，IBMDB2。高级研究实现位图索引表示由FastBit[24,15,19]RIDBit[15]。FastBit实现根本的位图索引，分级，华位图压缩技术。在RIDBit，密集位图存储在B-树的叶子。位图替换的行ID，原本存储在B树叶子。稀疏将自动转换成位图行ID。另一个研究领域相关的位图索引COM的是文本PRESSION压缩和倒排文件压缩锡永在文本数据库。几个压缩技术压缩文本已经提出，例如，[1,8,6]他们要么是基于哈夫曼编码[10]或谢夫的Lempel编码[38]。几项技术也提出了用于压缩倒排文件，例如，[7,13,23,29,30,39]。在[13,39]的作者提出了一种倒排索引列表中出现的压缩技术项t为代表的数据文件中块差距〔整数〕，而不是块编号。差距进一步由埃利亚斯编码克编码[7]。埃利亚斯克编码正整数x由一个一元局部和二进制的一局部。一元局部指定的比特数必须代表X，而二进制码X位。编码延伸埃利亚斯-克编码。在编码的x，一元局部被替换为克代码。寿等人[23]的报告性能测试的压缩唱倒名单〔偏移，文件的不同元素号〕，不同的编码技术〔埃利亚斯克和编码[7]以及哥伦布编码[9]〕。Vo和莫法特[29]提出了一种压缩技术，倒列表是基于一元编码[31]。它是用于压缩文件号码。[30]比拟不同的方法来压缩整数，包括埃利亚斯克和编码，哥伦布编码，和可变字节整数编码。开发的压缩技术的倒立文件，压缩整数，可能代表增量〔不同分配方法〕之间的值的序列。在RLH和RLHN压榨技术，我们提出，距离位之间的值“1〞对应这样的增量。然而，RLH和RLH-N编码这些三角洲哈夫曼编码，而不是通过克或编码。比拟RLH，RLH-N，和华就CPU时间和I/O处理时间;这些字符ISTICS测定：〔1〕行无序，局部有序，并下令由一个索引值属性，〔2〕索引的属性不同的枢机主教伊蒂埃斯〔多达20,000个不同的值〕，和〔3〕的数据集由100,000,000股行;相对于比拟RLH-N和RLH效率压缩位图的修改。本文的结构如下。第2局部介绍了根本本文中使用的定义和概念。第3节提出RLH和RLH-N压缩技术。第4节讨论的实验结果RLH的，RLH-N和华的评价。最后，第5节总结，并得出结论的文件。1.2造纸重点，奉献和轮廓在本文中，我们提出了一个替代的位图压缩技术，提供精确的编码：〔1〕良好的查询响应时间和〔2〕的尺寸小压缩的位图。位图压缩技术我们开发被称为运行长度霍夫曼〔RLH〕，的。同样，在英国播送公司〔BBC〕和华，建议技术基于游程长度编码。然而，它不同于英国播送公司〔BBC〕和华就以下。首先，RLH计数位的值之间的距离''1''，而不是相同的值的连续位的长度。该距离成为接下来编码的符号哈夫曼编码技术[10]。其次，RLH确实将位图转换为字提高了一个位图的压缩比。为了更好地支持位图更新中，我们提出的一个变种的RLH压缩的技术，称为RLH-N。RLH-N一个位图压缩被分成N比特的长度的话，那么每个N位的字被压缩RLH。RLH和RLH-N压缩技术实施和华实验比拟。作为一个参考我们选择华，因为压缩位图华提供更好的查询响应时间比位图压缩与BBC[26,32]。本文扩展了我们以前的工作[25]就到：RLH-N的压缩技术的开展接受字的长度等于256，512，1024，2048位;比拟RLH，RLH-N，和华就CPU时间和I/O处理时间;这些字符ISTICS测定：〔1〕行无序，局部有序，并下令由一个索引值属性，〔2〕索引的属性不同的枢机主教伊蒂埃斯〔多达20,000个不同的值〕，和〔3〕的数据集由100,000,000股行;相对于比拟RLH-N和RLH效率压缩位图的修改。本文的结构如下。第2局部介绍了根本本文中使用的定义和概念。第3节提出RLH和RLH-N压缩技术。第4节讨论的实验结果RLH的，RLH-N和华的评价。最后，第5节总结，并得出结论的文件。2根本定义位图索引是基于所谓的位图。一位图是一个位向量。从域的每一个值索引的属性相关已自己的位图。该每个位图中的位的数目的数目等于行存储了表T中。创立一个位图值v索引属性，A介绍了这些在T的行A值是v。在该位图中，位编号n设置为“1〞，如果A的第n行的价值等于V。否那么位设置为0。位图索引的概念说明一个例子。让我们考虑表的客户和创立位图索引其性别属性，如下图。1。由于域索引的属性只包含两个不同的价值观，指数是由两个位图。例如，第一位图描述值'女'位设置为0，因为的属性性的第一行中的值是不是一个女性如前所述，华和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〞的位，它是不被合并与一组。组2-175是同质〔''0''位组成〕，他们合并成一个大基，中图表示。2c为2-175组。本组包括174了31位。最后一组176，类似于第1组，是异质的，它不能被与合并前组。作为结果合并组，三最终组被创立，如图中所示。2三。在第三步骤中，被编码的最后三个组如下所示〔参见图2中的32-bit字D〕。第一组代表在第一次运行的尾部。的最重要的位〔最左边〕有值“0〞表示一个尾巴。31下一页位1组的原始位。第二组〔A组2-175〕表示第二次运行的填充。的最显着位〔位置31〕被设置为“1〞表示填充。在位置2的位30设置为''0''表示所有位原组2-175值“0〞，即填充用于压缩组的所有位具有价值''0''。该其余的30位被用于编码数字同质群体充满''0''在这个例子中，有174组。均质的数量组所表示的二进制值等于000000000000000000000010101110，存储上在其余30位。最后31位，记为176组，代表第二次运行的尾巴。的最在这组有显着位值“0〞表示一个尾巴。其余31位是原组176位。2.3霍夫曼编码在霍夫曼编码[10]，原始符号从压缩的文件被替换的位串。更多一个给定的符号经常出现在压缩文件用于表示符号的较短的比特串。编码后的符号和它们的相应的位串表示为所谓哈夫曼树。哈夫曼树用