数据压缩大作业

《数据压缩大作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据压缩大作业——算数编码压缩与解压缩程序目录一、试验背景及目的3二、试验内容32.1试验步骤32.2试验原理3三、算法流程63.1编码器算法63.2解码器算法四、程序设计说明7五、程序压缩性能评价85.1data,txt文件的测试结果85.2textdata,txt文件的测试结果115.3程序压缩性能评价13六、程序源代码14七、测试数据文件22试验背景及目的霍夫曼方法比香农-费诺方法更有效，但这两种方法都很少能产生最佳变长编码，仅当符号概率等于2的负整数次幕时，这些方法才能产生最佳结果（码字的平均长度等于嫡）

2、。算数编码克服了这个问题，它是把一个码字（通常较长）分配给整个输入流，而不是给各符号分别分配码字。它可以为特定序列指定码字,而又不需要为所有同一长度的序列生成代码。算术编码逐个符号读输入流，每输入和处理一个符号，就在码字后面加上几位，因此，在算数编码中，当前区间的下限和上限随着码流长度的增大，将变得无限长。而实际上，双精度的实数也只有16位有效数字，更长精度的数无法表示，除此Z外，即使有一种方法能够表示足够长的数据精度，两个很长的数进行运算，花费的时间也无法承受。因此，一个实用的方案应当采用有限长度的整数运算，利

3、用有限字长寄存器来实现算数编码，该方法即为整数算数编码。本实验的目的即根据算数编码的原理，利用二进制定点数法编写算数编码压缩及解压缩程序，实现对*・txt文件的压缩及解压缩，并对程序压缩性能进行评价，从而加深对算数编码原理的理解，掌握相关算法的设计方法以及进一步提高程序编写的能力。二、试验内容2.1试验步骤根据试验目的，本次试验的具体步骤如下：①参考相关资料对算数编码的原理进行分析与理解，②根据其原理，利用二进制定点数法设计符合要求的算法，③根据所设计的算法，利用C语言编写相关程序，④利用测试数据文件对程序进行测

4、试，并对程序的压缩性能进行评价。2.2试验原理2.2.1编码器的实现给定一个字长加，将［0,1）区间中的重要值映射到2〃个二进制字的范围。点0被映射为:加次00---0点1被映射为：加次r八111・・1点0.5被映射为：〃山次100^6以耳表示符号i出现的次数，定义CumCount(k)=,编码下限/和上限u/=!可以用下式迭代：(%-/+1)*CumCountx-TotalCount1—1+("一/+1)*CumCountx)TotalCountu—/+具体编码规则如下：•如果/和M的最咼位都是弘①将方输出

5、到码流，②将Z左移1位，最低位补0,③将u左移1位，最低位补1④如果Scale>0,输出b的补，scale减1•如果Scale条件成立:①将I左移1位，最低位补0②将u左移1位，最低位补1③Z和m最高位取反，scale加1上述规则用表格表示如下：LOW.HIGHp输出"OXqox「输岀sX1X^输岀仆OOP10^正常区间卩01p正常区间卩00.11^正常区间卩01p10^Scale区卩2.2.2解码器的实现解码过程与编码过程相反，有了编码器的实现，解码器实现就很好描述了。解码过程一旦启动，剩下的就是模拟编码器算法

6、了。其原理如下：初始化/和腺从压缩码流读入加个比特作为人以Index解码符号x,其表达式如下：Index=(f一/+1)*TotalCount-1(w—/+1)MM解码下限/和上限u可以用下式迭代:(%-/+1)*CumCountx-}TotalCount〜“(w-/+l)(兀)]TotalCount具体解码规则如下：•如果/和m的最咼位都是庆①将r左移1位，最低位从压缩码流补1个比特，②将/左移1位，最低位补0,③将m左移1位，最低位补1。•如果Scale条件成立:①将/左移1位，最低位从压缩码流补1个比特

7、，②将/左移1位，最三、低位补0,③将m左移1位，最低位补1,CD将厶码/最高位取反。算法流程根据上述编码器与解码器的原理，设计相关的算法。2.1编码器算法初始化/和U取得符号Total_Count(w-/+l)xCum_Count(x-I)(w-/+l)xCum_Count(x)1TotalCountWhile（u和l的最高位都等于b或满足Scale条件）If（u和/的最高位都等于b）{发送b将/左移一个比特，并将0移入最低位将u左移一个比特，并将1移入最低位While（ScaIe>0）{发送b的补码递减Sca

8、le}}（满足Scale条件）{将/左移一个比特，并将0移入最低位将u左移一个比特，并将1移入最低位对/和况的（新）最高位求反递增Scale}2.2解码器算法初始化Z和u将接收到的比特流中的前加个比特读入标签rk=Owhile[t-l+)xTotal_Count-w—+1>Cum_Count(Z:)丿k〜k+对符号兀进行解码(w-/+l)xCum_Count(x-