数据压缩1大作业

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

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

3、理，利用二进制定点数法编写算数编码压缩及解压缩程序，实现对*.txt文件的压缩及解压缩，并对程序压缩性能进行评价，从而加深对算数编码原理的理解，掌握相关算法的设计方法以及进一步提高程序编写的能力。二、 试验内容2.1 试验步骤根据试验目的，本次试验的具体步骤如下：参考相关资料对算数编码的原理进行分析与理解，根据其原理，利用二进制定点数法设计符合要求的算法，根据所设计的算法，利用C语言编写相关程序，利用测试数据文件对程序进行测试，并对程序的压缩性能进行评价。2.2 试验原理2.2.1 编码器的实现给定一个字长，将0，1）区间中的重要值映射到个二进制字的范围。点0被映射为：点1被映射为：点0.5被

4、映射为：以表示符号出现的次数，定义，编码下限和上限可以用下式迭代：具体编码规则如下：l 如果l和u的最高位都是b：将b输出到码流，将l左移1位，最低位补0，将u左移1位，最低位补1如果Scale>0，输出b的补，scale减1l 如果Scale条件成立：将l左移1位，最低位补0将u左移1位，最低位补1l 和u最高位取反，scale加1上述规则用表格表示如下：2.2.2 解码器的实现解码过程与编码过程相反，有了编码器的实现，解码器实现就很好描述了。解码过程一旦启动，剩下的就是模拟编码器算法了。其原理如下：初始化l和u。从压缩码流读入m个比特作为t。以Index解码符号x，其表达式如下：解码

5、下限和上限可以用下式迭代：具体解码规则如下：l 如果l和u的最高位都是b：将t左移1位，最低位从压缩码流补1个比特，将l左移1位，最低位补0，将u左移1位，最低位补1。l 如果Scale条件成立：将t左移1位，最低位从压缩码流补1个比特，将l左移1位，最低位补0，将u左移1位，最低位补1，将l,u,t最高位取反。三、 算法流程根据上述编码器与解码器的原理，设计相关的算法。3.1 编码器算法初始化l和u取得符号While (u和l的最高位都等于b或满足Scale条件)If (u和l的最高位都等于b) 发送b将l左移一个比特，并将0移入最低位将u左移一个比特，并将1移入最低位While (Scal

6、e>0) 发送b的补码 递减Scale If (满足Scale条件)将l左移一个比特，并将0移入最低位将u左移一个比特，并将1移入最低位对l和u的（新）最高位求反递增Scale 3.2解码器算法初始化l和u将接收到的比特流中的前m个比特读入标签tk=0对符号x进行解码While (u和l的最高位都等于b或满足Scale条件)If (u和l的最高位都等于b) 将l左移一个比特，并将0移入最低位将u左移一个比特，并将1移入最低位将t左移一个比特，并将接收到的比特流中的下一个比特读入最低位 If (满足Scale条件)将l左移一个比特，并将0移入最低位将u左移一个比特，并将1移入最低位 将t左

7、移一个比特，并将接收到的比特流中的下一个比特读入最低位对l、u和t的（新）最高位求反 四、 程序设计说明在上交的作业压缩包中共包含两个部分：pdf格式的试验报告，程序压缩包Arith。在程序压缩包Arith中，算数编码的实现程序文件为Arith.cpp ,可在visual c+ 6.0 环境中运行成功。data.txt文件为待压缩文件。程序成功运行后，data_Code.txt文件为编码文件，用于存储压缩结果。data_Decode.txt文件为解压缩文件，用于存储恢复结果。程序压缩包Arith中的textdata.txt文件为测试文件，用于对编写的算数编码压缩及解压缩程序的测试。为了方便起见

8、，在使用测试文件对程序进行测试时，可以直接将textdata.txt文件中的内容复制到待压缩文件data.txt中，并将data.txt文件中原来的数据覆盖掉，再次运行算数编码的实现程序文件Arith.cpp即可得到测试结果，从而完成对程序压缩性能的评价。五、 程序压缩性能评价本次试验共采用两个txt文件对算数编码压缩与解压缩程序进行测试，并利用两个文件的测试结果分别从两个方面对程序的压缩性能进行评价：原文件与解压缩后的文件内容的差异，压缩比。5.1 data.txt文件的测试结果在visual c+ 6.0 环境中运行程序文件夹中的Arith.cpp文件，得到运行结果如下所示：5.2 tex

9、tdata.txt文件的测试结果将程序文件夹下的textdata.txt文件的内容复制到data.txt文件中，并覆盖掉其原有内容，在visual c+ 6.0 环境中重新运行程序文件夹中的Arith.cpp文件，得到运行结果如下所示：5.3 程序压缩性能评价本试验算数编码程序编码的结果直接以0和1的形式输出，这样做的好处是更加直观。而对于实际应用情况，可以将八位数据组合输出（以ASCII码形式展示，但这么做会显得编码结果比较乱），因此程序成功运行后的编码文件大小除以8才是实际应用中的编码文件大小。从上述运行结果可以看出，无论是data.txt文件，还是textdata.txt文件，压缩前与解

10、压缩后的文件内容完全一致，因此本试验编写的算数编码压缩与解压缩程序是正确的，能够成功运行。此外，data.txt文件的压缩比为185.789606% ，textdata.txt文件的压缩比为146.636694% ，两个文件的压缩比均大于1。由于压缩比的定义为原始数据量与压缩数据量之比，所以压缩比大于1证明压缩后的文件数据量少于压缩前的文件数据量，该程序起到了压缩的作用。综上所述，本试验编写的算数编码压缩与解压缩程序不仅能完成各种符号（包括汉字）的压缩与解压缩，使压缩前与解压缩后的内容完全一致，而且程序的压缩比均大于1，因此本试验编写的算数编码压缩与解压缩程序具有较好的压缩性能。六、 程序源代

11、码根据上述编码器与解码器的算法，用C语言编写相关程序，具体程序如下所示：#include<stdio.h>#include<string.h>#include<math.h>#define N 20/定义相关变量并初始化unsigned char *DataBuf; /用来存储从文件中读入的字符串int FileLen; /文档中字符的个数int TotalCount; /字符总数int CKind = 0; /文档中字符的种类数int Count256 = 0; /有效字符表中对应字符出现次数int Sub_Code = 0; /CodeOut数组的下标i

12、nt CumCount256 = 0; /字符出现次数累加表int ShowingTable256 = 0; /有效字符表int i = 0;/主函数int main() void ScanFile();ScanFile();/扫描文件void Arith_Code();Arith_Code();/编码void Arith_DeCode(); Arith_DeCode();/解码return 0;/文件扫描函数void ScanFile() FILE *fp1;char filepath = "data.txt"/读入文件int ASCTable256 = 0;/按ASCI

13、I码表按序统计输入字符个数DataBuf = new unsigned char1024*1024;if(fp1 = fopen(filepath,"rb") = NULL)printf("数据加载失败!n");FileLen = fread(DataBuf,1,1024*1024,fp1);/总字符个数for(i=0; i < FileLen; i+)/实现字符扫描 ASCTable(int) *(DataBuf+i)+;/将有效字符移到新数组，同时编号for(i=0; i < 256; i+)/实现字符搬移if(ASCTablei >

14、; 0)CountCKind = ASCTablei;ShowingTableCKind = i;CKind+;CumCount0 = Count0;/构造数组CumCountx，记录字符出现次数for(i = 1; i < 256; i+)CumCounti = CumCounti-1 + Counti;TotalCount = CumCountCKind-1;for(Sub_Code=CKind; Sub_Code > 0; Sub_Code-) ShowingTableSub_Code = ShowingTableSub_Code-1;CountSub_Code = Coun

15、tSub_Code-1;CumCountSub_Code = CumCountSub_Code-1;ShowingTable0 = 0;Count0 = 0;CumCount0 = 0;fclose(fp1);/输出统计结果printf("文件中共出现 %d 种字符，字符共计为 %d 个n",CKind,TotalCount);/输出字符统计表 printf("字符 该字符出现次数 叠加次数n");for(i=1; i <= CKind; i+)/实现字符搬移printf(" %d %d %d n",ShowingTablei,

16、Counti,CumCounti); printf("n读入的文件为：n");for(i=0; i < FileLen; i+)/实现字符扫描printf("%c",*(DataBuf+i);/输出文件的各个字符printf("n");int TurnaN = 0;/十进制转二进制函数void Ten_To_Two(int x)int aN = 0;int m;for(i=0;i<N;i+) aN-1-i = (int)(x / pow(2,i)%2; for(m=0; m < N; m+)Turnam = am;i

17、nt q = 0; /Two_To_Ten()函数返回值/二进制转十进制函数void Two_To_Ten(int b) q = 0;for(i = 0;i < N;i+) q = q + pow(2,i)* bN-1-i; long int Highest = pow(2,N)-1; /上限最大值long int OldLow,OldHigh;int scale = 0; /scale判断条件long int NewLow = 0;long int NewHigh = 0;int CodeOut1024*1024; /编码输出码流int LowArrayN = 0;int HighAr

18、rayN = 0;/文件编码函数void Arith_Code()int m;int g = 0;OldLow = 0; /初始化下限OldHigh = Highest; /初始化上限FILE *fp2;if(fp2 = fopen("data_Code.txt","wb") = NULL)printf("数据加载失败!n");for(int n = 0; n < FileLen; n+ )for(int j = 1; j <= CKind; j+) /按序将输入的每一个字符与统计表中的字符进行匹配if(ShowingTa

19、blej = *(DataBuf+n)NewLow = OldLow + (OldHigh - OldLow + 1) * CumCountj-1 / TotalCount;/得到新下限Ten_To_Two(NewLow);/将十进制下限转换为12位二进制数for(m=0;m<N;m+)LowArraym = Turnam;NewHigh = OldLow - 1 + (OldHigh - OldLow + 1) * CumCountj / TotalCount;/得到新上限Ten_To_Two(NewHigh);/将十进制上限转换为12位二进制数for(m=0;m<N;m+)Hi

20、ghArraym = Turnam;while(LowArray0 = HighArray0)/当上下限最高位相同时CodeOutSub_Code = HighArray0;g = CodeOutSub_Code;Sub_Code+; fprintf(fp2,"%d",CodeOutSub_Code-1);/输出编码值 while(scale > 0)CodeOutSub_Code = (g+1) % 2;/输出上一个输出码的补码Sub_Code+;scale-; /递减scale fprintf(fp2,"%d",CodeOutSub_Code-

21、1);for(m=1;m<N;m+)/下限数组左移1位，低位补0LowArraym-1 = LowArraym;LowArrayN-1 = 0;for(m=1;m<N;m+)/上限数组左移1位，低位补1HighArraym-1 = HighArraym;HighArrayN-1 = 1;continue;while(LowArray0 = 0 && LowArray1 = 1 && HighArray0 = 1 && HighArray1 = 0)/当上下限的最高位和次高位分别为01和10时，满足scale条件for(m=1;m<

22、;N;m+)/数组左移1位LowArraym-1 = LowArraym; /下限数组低位补0HighArraym-1 = HighArraym; /上限数组低位补1LowArrayN-1 = 0;HighArrayN-1 = 1;LowArray0 = (LowArray0+1)%2; /下限的最高位取反HighArray0 = (HighArray0+1)%2; /上限的最高位取反scale+;continue;Two_To_Ten(LowArray);OldLow = q;Two_To_Ten(HighArray);OldHigh = q;/将最终的下限编码共12位添加到编码码流的最末位

23、置CodeOutSub_Code = (int)LowArray0;g = CodeOutSub_Code;Sub_Code+; fprintf(fp2,"%d",CodeOutSub_Code-1); while(scale > 0)/根据scale的值决定首项后添加项的位数 CodeOutSub_Code = (g+1)%2; Sub_Code+; scale-; fprintf(fp2,"%d",CodeOutSub_Code-1); for(i=0;i<N-1;i+)CodeOutSub_Code = (int)LowArrayi+1

24、;Sub_Code+;fprintf(fp2,"%d",CodeOutSub_Code-1);fclose(fp2);printf("n编码字符个数为: %dn",Sub_Code);/输出编码字符个数unsigned char *OutCode;unsigned char *CompressCode; /存储从文件中读入的压缩码int t = 0; /12位码流元对应的十进制数int Index = 0; /解码判断参量int Sub_Show = 0; /ShowingTable数组的下标int Sub_DeCode = 0; /DeCodeOut数

25、组的下标/文件解码函数void Arith_DeCode()FILE *fp3,*fpOut;int TransTableN = 0;int FLAG = 1;OutCode = new unsigned char1024*1024;char filepath = "data_Code.txt"CompressCode = new unsigned charSub_Code;if(fp3 = fopen(filepath,"rb") = NULL)printf("数据加载失败!n");fread(CompressCode,1,Sub_

26、Code,fp3);for(i=0;i<Sub_Code;i+)/将输入的码流转化成程序中的二进制码流*(CompressCode+i) = *(CompressCode+i) - 48;/写出编码得到的二进制码流printf("二进制编码结果为:n");for(i=0;i<Sub_Code;i+)printf("%d",*(CompressCode+i);printf("n");OldHigh = Highest;/初始化上限OldLow = 0; /初始化下限for(i=0;i<N;i+)TransTablei

27、= *(CompressCode+i);Two_To_Ten(TransTable);t = q;Index = (t - OldLow + 1) * TotalCount -1) / (OldHigh - OldLow + 1);Index = Index + 1;for(i = 1;i <= Sub_Code;i+)/判断字符if(Index > CumCounti-1 && Index <= CumCounti)Sub_Show = i;break;*(OutCode+Sub_DeCode) = ShowingTableSub_Show;printf(&

28、quot;n"); printf("解码结果为:n"); printf("%c",*(OutCode+Sub_DeCode); Sub_DeCode+;while(FLAG < FileLen)NewLow = OldLow + (OldHigh - OldLow + 1) * CumCountSub_Show-1 / TotalCount;/得到新下限Ten_To_Two(NewLow);/将十进制下限转换为12位二进制数for(i=0;i<N;i+)LowArrayi = Turnai;NewHigh = OldLow + (O

29、ldHigh - OldLow + 1) * CumCountSub_Show / TotalCount - 1;/得到新上限Ten_To_Two(NewHigh);/将十进制上限转换为12位二进制数for(i=0;i<N;i+)HighArrayi = Turnai;while(LowArray0 = HighArray0)/当上下限的最高位相同for(i=0;i<Sub_Code-1;i+)/更新t值，将输入码流左移一位*(CompressCode+i) = *(CompressCode+i+1);for(i=0;i<N;i+)TransTablei = *(Compre

30、ssCode+i);Two_To_Ten(TransTable);t = q;for(i=1;i<N;i+)/更新上下限，数组左移1位，下限低位补0，上限低位补1LowArrayi-1 = LowArrayi;HighArrayi-1 = HighArrayi;LowArrayN-1 = 0;HighArrayN-1 = 1;Two_To_Ten(LowArray);NewLow = q;Two_To_Ten(HighArray);NewHigh = q; OldLow = NewLow;/更新上下限，进行下一轮运算 OldHigh = NewHigh;continue;while(Lo

31、wArray0 = 0 && LowArray1 = 1 && HighArray0 = 1 && HighArray1 = 0)/当满足scale条件for(i=0;i<Sub_Code-1;i+)*(CompressCode+i) = *(CompressCode+i+1);for(i=0;i<N;i+)TransTablei = *(CompressCode+i);Two_To_Ten(TransTable);t = q;/实现t顺序移动一位for(i=1;i<N;i+)/更新上下限，数组左移1位，下限低位补0，上限低位补

32、1LowArrayi-1 = LowArrayi;HighArrayi-1 = HighArrayi;LowArrayN-1 = 0;HighArrayN-1 = 1;LowArray0 = (LowArray0 + 1)%2; /上下限及t的最高位取反HighArray0 = (HighArray0 + 1)%2;TransTable0 =(TransTable0 + 1)%2;Two_To_Ten(LowArray);NewLow = q;Two_To_Ten(HighArray);NewHigh = q;Two_To_Ten(TransTable);t = q;OldLow = NewL

33、ow;/更新上下限，进行下一轮运算 OldHigh = NewHigh;continue;Index = (t - NewLow + 1) * TotalCount -1) / (NewHigh - NewLow + 1);Index = Index + 1;for(i = 1;i <= Sub_Code;i+)/判断字符if(Index > CumCounti-1 && Index <= CumCounti)Sub_Show = i;break;FLAG+;*(OutCode+Sub_DeCode) = ShowingTableSub_Show;Sub_De

34、Code+; printf("%c",ShowingTableSub_Show);continue;printf("n");printf("n"); if (fpOut=fopen("data_Decode.txt","wb")=NULL)printf("数据加载失败!n");fwrite(OutCode,1,FileLen,fpOut); fclose(fpOut); printf("编码位数为：%dnn",N); printf("压缩比为：

35、%lf %nn",(double)Sub_Code/8/FileLen*100);七、 测试数据文件本次试验共采用两个文件完成对算数编码程序的测试，一个为待压缩文件data.txt, 另一个为测试文件textdata.txt。两个文件的具体内容如下：l data.txt : In accordance with the “main and collateral channels” theory in TCM, the purpose of acupuncture is to dredge the channel and regulate qi and blood, so as to

36、keep the bodys yin and yang balanced and achieve reconciliation between the internal organs. It features in traditional Chinese medicine that “internal diseases are to be treated with external therapy”. The main therapy of acupuncture involves using needles to pierce certain acupoints of the patients body, or adopting moxibustion to stimulate the patients acupoints so as to stimulate the channels and relieve pain. With its unique advantages, acupuncture has b