合肥工业大学 信息论与编码 实验报告 完整代码版

1、计算机与信息学院 信息论与编码 实验报告专 业 班 级 信息安全13-1班 学生姓名及学号 马骏 2013211869 课程教学班号 任 课 教 师 苏兆品 实验指导教师 苏兆品 实验地点 逸夫楼 2014 2015 学年第 一 学期实验1 霍夫曼编码一、 基本要求 通对任意输入的字符串序列进行3元霍夫曼编码，给出编码结果、编码效率；并实现相应的译码操作。二、 提升要求对一幅BMP格式的灰度图像进行二元霍夫曼编码。三、 问题描述1、 三元霍夫曼编码首先需要考虑的是如何表示三元2、 三元霍夫曼编码需要对不满足2n+3的情况做处理3、 使用什么数据结构建立霍夫曼树四、算法思想 1、使用两个二进制位

2、表示一个三元变量，即00表示a、01表示b、11表示c。 2、出现不满足2n+3情况即需要加入一个出现次数为0次的字符，遍历已经出现的字符，找到一种八位二进制组合作为新字符。 3、建立霍夫曼树的算法，使用数组的结构作为整棵树的空间，其中每个数组元素是一个类的实例。 在这各类里封装了他所代表的字符（如果不是叶子节点则为null）、出现的次数（非叶子结点则为子节点的此项加和）。 承载整棵树的数组也是封装在一个类里的，这个类同时封装了对这棵树的操作，如添加节点、树节点排序等，这样就可以使从添加叶子节点后建立整棵霍夫曼树。5、 模块划分char huancunmax;/从文件中读入的字符char ya

3、suohuancunmax;/压缩后可以写进文件中的字符串 long int yasuohuancunnumber=0;/准备写入文件中的个数long int huancunnumber=0;/从文件中读出字符个数class treevoid set(int a,int b,int c,int d,int e)/次数为a，左孩子为b，中孩子为c，右孩子为d，自己的编号eint mynumber;/次数int leftsonnumber;/数组编号int middlesonnumber;int rightsonnumber;/数组编号 控制时没有儿子节点则儿子都是负数int myzifunumb

4、er;/作为叶子节点在数组中的编号;class table/压缩对照表public:table()void cutrealfile()/将缓存中一样的字符区别开void uncheck(char huancun)/检查是否出现过字符bool check(char huancun)/检查源文件字符是否出现过int checkhuancun(int i)/读缓存数组的字符，返回yasuozifu数组中的地址void count(tree fun,int begin,int end)/beginend区间内排序char h3setonechar(char n1,char n2,char n3,cha

5、r n4)/三元霍夫曼给进一个char 位操作使用内联汇编语言 d 是不会被译码的 为了补齐余码void linshih3manage(char ptr)/进来字符存起来 每四个存一个void writesign(tree fun,int permitnumber,char k,int futhernumber)/先给sign的值 递归构建霍夫曼树void hafuman3()/三元霍夫曼编码函数void codemanage()/对整个缓存进行编码 bool checkh3code(string ptr)/对解压缩后的码串译码void jiemah3code(char ptr)/对一个cha

6、r型8位进行解码为4个char型 void discodemanage()/解压缩程序 使用huancun放密文，解压后原文放在yasuohuancun中 char linshih34;/临时三元霍夫曼 int linshih3number;/记录临时三元霍夫曼个数 int number;/未压缩字符的数量 int everyzifunumbermax;/每个字符出现的次数 string signmax;/压缩后的字符(先用数字表示) string paixusignmax;/编码后与paxu字符数组对应的编码 char paixuzifumax;/和字符数组一样，顺序对应paixusign

7、char zifumax;/未压缩的字符(互不相同);void readfile(const char* realfile) /文件读入缓存void writefile(const char*yasuofile)/缓存写入文件int main()/主函数 readfile(realfile); table mytable; mytable.cutrealfile(); mytable.hafuman3(); mytable.codemanage(); writefile(yasuofile); readfile(yasuofile); mytable.discodemanage(); writ

8、efile(jieyasuofile); return 0; 6、 测试数据 2.txt文件 n999.bmp文件1、 2.txt文件hello markchalse,this is a secretnumber 6424155please put this in an code小刀司令压缩后：將埼绩髱釜#?庩宏壕券? :,焕?0鼜>?姾嫧偪瘞旰?3?飶卡8*解压缩后（最后多了一字节空格）：hello markchalse,this is a secretnumber 6424155please put this in an code小刀司令压缩情况：源文件：压缩文件：解压缩文件：编码分

9、析：无损压缩 压缩率：74.16%2、 n999.bmp压缩后：解压缩无失真压缩7、 源程序 （见附录）实验2算术编码一、基本要求对任意输入的字符串序列进行自适应编码，并设计相应的译码二、提升要求对一幅bmp格式的灰度图像进行自适应算术编码，并设计相应的译码三、问题描述1、算术编码的过程实际就是对两个小数确定的取区间，划分区间，再取区间不断重复的过程，将采用什么数据结构。2、自适应编码如何确定小数的误差以保证无误差即零失真3、Long double只有二十几位 如何压缩更多的内容四、算法思想1、将上边界，下边界分别记录，并封装在一个类中。类中还封装了对区间选择、改变上界下界值的函数等。2、区计

10、算后的各字符概率的小数后八位保证无误差3、为保证压缩足够多的量，不采用long double记录上下界的值，而是采用int型数组来记录上下界的值，每个long int 取七位十进制数。这样初始max值为10000，所以整个算法可以进行小数点后70000位的小数加减乘除取对数等运算，保证了可压缩量五、模块划分因为要进行长数位计算 所以用一个long int的数组将每个单元表示7位十进制数 按max=10000 的初始 可以达小数点后70000位在存储大数时数组按距离小数点越近越靠左的顺序码放用一个类封装数据和操作方便对数据的掉用，省得一会形参一会实参下边界为准注意length中是按照小数的格式

11、如果某一元组其不满7位则前面为0 将length连起来表示数时 一定要注意步骤：1、将原文件读入缓存 2、统计原文件字符的种类有多少 频率分别是多少(自适应) 提示：计算频率 double c=double(a)/double(b); 3、接下来 在arithmetic_coding中 根据缓存中每个字符 获得最后的概率 getposible(char)得到给定字符的概率区间 getlength()计算区间长度 int getint(double)将概率小数转化成整数 class posible_8:set(int) lowposible highposible 在这里先通过getint()转

12、化为8位整数再变成4个2位的整数方便计算 接下来用posible_8 的每一个数组元素(两位)从length最后开始乘并向前进位 mathmatic:int getreallength()/得到length数字的准确位数 class posible_8:int getlong()/得到every2bit的小数位长 mathmatic:int getbeginlength()/得到length数字的从开始到最后一个数字的准确位数 mathmatic:void dealhigh()/high=low+lowposible*length=low+length(已处理) mathmatic:void

13、cuthigh()/high 后面不需要的为零的元组要约去 mathmatic:void deallow()/low=low+lowposible*length=low+length(已处理) mathmatic:void cutlow()/low 后面不需要的为零的元组要约去 4、mathmatic:void code()将最后的low进行二进制编码存入yasuohuancun中 #include<math.h>之后就可以直接使用log了 以2为底的对数可以用换底公式表示 log(n)/log(2) 不能用log()求一个数组表示的大数的原因是 log(a+b)根本无法拆解啊 不

14、要说把a+b分解成c*d*. 但我们可以使用简单粗暴的0.5*0.5*0.5.迭代进行直到找到那个整数部分 mathmatic:int getlog()/返回log(length) mathmatic:int checksize(long int goalmax,int goalnumber,long int lowmax,int lownumber)/比较两个正规小数大小 goal小返回1 大0 相等2 mathmatic:void dealmycode()/将mycode中的十进制表示的二进制转化为二进制存入yasuohuancun中 5、mathmatic:void discode()/

15、解压缩 压缩文件已读入huancun 第一个是 以前的huancunnumber mathmatic:void deal8bit(char kp,int overbit)/计算nowlowmathmatic:void addnowlow()/low+nowlowdiscode()现在low已经有了，接下来需要比较yasuohuancunnumber次就可以还原以前的huancun了 不过需要重用nowlow作为目标小数 low每次需要做运算 int getzifu() 函数中代码重用：重用arithmetic_coding()代码 直接用checksize()BUG: discode()不知道

16、为什么要减1 最后一个字符11111111 这个bug还没有修复 这个bug非常严重 导致如原文件内容为abc 无法六、测试数据 2.txt文件 n77.bmp文件1、 2.txt文件hello markchalse,this is a secretnumber 6424155please put this in an code小刀司令压缩后： 稬?睖?反.媹录? 缶m郜緕k?.?=X杛楞璩tm?桶程序过程：解压缩后：hello markchalse,this is a secretnumber 6424155please put this in an code小刀司令压缩情况：源文件：压缩文

17、件：解压缩文件：编码分析：无损压缩 压缩率：65.17%2、 n77.bmp压缩文件： 傝?靯左m鮏.=W噀Z鐢?霑楞壗YO?濖?痦畝?湍叚?Jz?V摮|_p濔?褺S?老z7?tJ?料c鶻H娀止程序过程：解压缩后：压缩情况：源文件：压缩文件：解压缩文件：编码分析：无损压缩 压缩率：32.96%7、 源程序 （见附录）8、 总结 通过此次实验，我在学习编码原理的进一步学习了各种无失真信源编码的编程方法，使我对信息论与编码有了更深的了解。程序中还存在很多的不足，希望在以后的学习中可以做到更加完善。附录Hafuman.cpp/*基本要求：对任意输入字符串进行三元哈弗曼编码*/#include<

18、iostream>#include<string>#include<fstream>#include <sstream>using namespace std;const char* realfile="n77.bmp"const char* yasuofile="n3.txt"const char* jieyasuofile="n4.bmp"const int max=10000;char huancunmax;/从文件中读入的字符char yasuohuancunmax;/压缩后可以写进文

19、件中的字符串long int yasuohuancunnumber=0;/准备写入文件中的个数long int huancunnumber=0;/从文件中读出字符个数class treepublic:tree();void set(int a,int b,int c,int d,int e)/次数为a，左孩子为b，中孩子为c，右孩子为d，自己的编号emynumber=a;leftsonnumber=b;middlesonnumber=c;rightsonnumber=d;myzifunumber=e;int mynumber;/次数int leftsonnumber;/数组编号int midd

20、lesonnumber;int rightsonnumber;/数组编号 控制时没有儿子节点则儿子都是负数int myzifunumber;/作为叶子节点在数组中的编号;class table/压缩对照表public:table() number=0; linshih3number=0; ; void cutrealfile()/将缓存中一样的字符区别开 int x; for(x=0;x<huancunnumber;x+) if(check(huancunx)/如果是不一样的字符则存进zifu数组 zifunumber=huancunx; everyzifunumbernumber=1;

21、 number+; double i=number; if(i/2>number/2)/ 三元霍夫曼满足2n+3 不就是奇数吗 但1不满足 还没考虑1 以后注意维护 cout<<"right number!"<<endl; else cout<<"wrong number!"<<endl; char tmd;/寻找不可能出现的8位二进制数 tmd _asm mov tmd,01001101b; if(check(tmd) zifunumber=huancunx; everyzifunumbernumb

22、er=0; number+; else uncheck(tmd); _asm mov tmd,01101001b; if(check(tmd) zifunumber=huancunx; everyzifunumbernumber=0; number+; else uncheck(tmd); cout<<"-zifu-"<<endl; for(x=0;x<number;x+) cout<<zifux<<" 次数："<<everyzifunumberx<<endl; cout<

23、;<"number="<<number<<endl; ; void uncheck(char huancun)/检查是否出现过字符 int x; for(x=0;x<number;x+) if(zifux=huancun) everyzifunumberx-; ; bool check(char huancun)/检查源文件字符是否出现过 int x; for(x=0;x<number;x+) if(zifux=huancun) everyzifunumberx+; return false; return true; ; int

24、checkhuancun(int i)/读缓存数组的字符，返回yasuozifu数组中的地址 char a=huancuni; int x=0; for(x=0;x<number;x+) if(paixuzifux=a) return x; return -1; ; void count(tree fun,int begin,int end)/beginend区间内排序 int x,y; tree a; for(x=begin;x<end-1;x+) for(y=x+1;y<end;y+) if(funx.mynumber>funy.mynumber) a=funx;

25、funx=funy; funy=a; ; char h3setonechar(char n1,char n2,char n3,char n4)/三元霍夫曼给进一个char 位操作使用内联汇编语言 /d 是不会被译码的 为了补齐余码 char onechar; if(n1='a') _asm mov onechar,00h; if(n1='b') _asm mov onechar,11000000b; if(n1='c') _asm mov onechar,10000000b; if(n1='d') _asm mov onechar

26、,01000000b; if(n2='a') _asm or onechar,00000000b; if(n2='b') _asm or onechar,00110000b; if(n2='c') _asm or onechar,00100000b; if(n2='d') _asm or onechar,00010000b; if(n3='a') _asm or onechar,00000000b; if(n3='b') _asm or onechar,00001100b; if(n3='c

27、') _asm or onechar,00001000b; if(n3='d') _asm or onechar,00000100b; if(n4='a') _asm or onechar,00000000b; if(n4='b') _asm or onechar,00000011b; if(n4='c') _asm or onechar,00000010b; if(n4='d') _asm or onechar,00000001b; return onechar; ; void linshih3manag

28、e(char ptr)/进来字符存起来 每四个存一个 linshih3linshih3number=ptr; linshih3number+; if(linshih3number=4) yasuohuancunyasuohuancunnumber=h3setonechar(linshih30,linshih31,linshih32,linshih33); linshih3number=0; yasuohuancunnumber+; ; void writesign(tree fun,int permitnumber,char k,int futhernumber)/先给sign的值 递归构建霍

29、夫曼树 if(futhernumber=-1)signpermitnumber="" else signpermitnumber=signfuthernumber+k; / cout<<signpermitnumber<<" " if(funpermitnumber.myzifunumber<0)/父亲节点 if(funpermitnumber.rightsonnumber>=0)writesign(fun,funpermitnumber.rightsonnumber,'c',permitnumber)

30、; if(funpermitnumber.middlesonnumber>=0)writesign(fun,funpermitnumber.middlesonnumber,'b',permitnumber); if(funpermitnumber.leftsonnumber>=0)writesign(fun,funpermitnumber.leftsonnumber,'a',permitnumber); ; void hafuman3()/三元霍夫曼编码函数 cout<<"-use 3 leaves hafman tree-&q

31、uot;<<endl; /*电脑明明是0、1二元码偏偏用3元编码 只能用两位二元码表示一位三元码 但这样本来压缩效率挺高的三元霍夫曼编码竟然不如二元霍夫曼真是醉了 三元霍夫曼编码一开始 的叶子节点数 一定要满足2n+3的特点 这个最后还是要处理 三元 则sign分别用0 1 2 表示三元后的编码 */ int familynumber;/记录有多少组父亲、儿子节点记录 int x;/常规变量 int h3number=number;/初始叶子数 int begin=0; char h3zifumax; for(x=0;x<number;x+) h3zifux=zifux; t

32、ree h3treemax; for(x=0;x<h3number;x+)/初始化叶子节点 h3treex.set(everyzifunumberx,-1,-1,-1,x); / count(h3tree,0,h3number); / for(x=0;x<h3number;x+) / / cout<<h3zifuh3treex.myzifunumber<<" 次数："<<h3treex.mynumber<<endl; / while(begin<h3number-1)/这里注意 最后一次实际上begin是在里

33、面与h3number相等 count(h3tree,begin,h3number);cout<<"*排序*"<<endl; / for(x=begin;x<h3number;x+)/ / cout<<h3zifuh3treex.myzifunumber<<" 次数："<<h3treex.mynumber<<endl;/cout<<"begin: "<<begin<<" " h3treeh3number.

34、set(h3treebegin.mynumber+h3treebegin+1.mynumber+h3treebegin+2.mynumber,begin,begin+1,begin+2,-1); cout<<h3treeh3number.leftsonnumber<<" "<<h3treeh3number.middlesonnumber<<" "<<h3treeh3number.rightsonnumber<<endl; begin=begin+3; cout<<h3nu

35、mber<<endl; h3number+; / cout<<h3number<<endl; writesign(h3tree,h3number-1,'a',-1); cout<<h3number<<endl; for(x=0;x<h3number;x+) cout<<" 次数"<<h3treex.mynumber<<" "<<signx<<endl; cout<<"-原字符编码-"

36、<<endl; int t=0; for(x=0;x<h3number;x+) if(h3treex.myzifunumber>=0) cout<<h3zifuh3treex.myzifunumber<<" 次数"<<h3treex.mynumber<<" "<<signx<<endl; paixusignt=signx; paixuzifut=h3zifuh3treex.myzifunumber; t+; cout<<"number o

37、f zifu:"<<t<<endl; ; void codemanage()/对整个缓存进行编码 cout<<"-in code manage program-"<<endl; cout<<"字符 "<<" 压缩字符 "<<endl; int x,i,y; for(x=0;x<number;x+) cout<<paixuzifux<<" "<<paixusignx<<e

38、ndl; for(x=0;x<huancunnumber;x+) / cout<<"正在处理 :"<<huancunx<<" " i=checkhuancun(x);/ cout<<"paixuzifu"<<i<<"="<<paixuzifui<<" " for(y=0;y<paixusigni.length();y+) / cout<<paixusigniy; linshih

39、3manage(paixusigniy);/注意这里有点二维数组的感觉 / cout<<endl; if(linshih3number!=0)/补齐一个char型8位最后几位 int tt; for(tt=linshih3number;tt<4;tt+) linshih3tt='d' yasuohuancunyasuohuancunnumber=h3setonechar(linshih30,linshih31,linshih32,linshih33); linshih3number=0; yasuohuancunnumber+; ; bool checkh3c

40、ode(string ptr)/对解压缩后的码串译码 int x; /cout<<"i want find "<<ptr<<" " for(x=0;x<number;x+) if(ptr=paixusignx)/这里string又可以用“=”来比较了？不是.equal()吗？ cout<<"find "<<x<<" "<<paixusignx<<" "<<paixuzifux<

41、<endl; yasuohuancunyasuohuancunnumber=paixuzifux; yasuohuancunnumber+; return true; return false;/ cout<<"no find waiting."<<endl; ; void jiemah3code(char ptr)/对一个char型8位进行解码为4个char型 char pp=ptr; char n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15;/n13 n14 n15没用 _asm mov

42、 n1,00h; mov n2,11000000b; mov n3,10000000b; mov n4,00h; mov n5,00110000b; mov n6,00100000b; mov n7,00h; mov n8,00001100b; mov n9,00001000b; mov n10,00h; mov n11,00000011b; mov n12,00000010b; mov n13,00010000b; mov n14,00000100b; mov n15,00000001b; and pp,11000000b; if(pp=n1) linshih30='a' i

43、f(pp=n2) linshih30='b' if(pp=n3) linshih30='c' pp=ptr; _asm and pp,00110000b; if(pp=n4) linshih31='a' if(pp=n5) linshih31='b' if(pp=n6) linshih31='c' if(pp=n13) linshih31='d' pp=ptr; _asm and pp,00001100b; if(pp=n7) linshih32='a' if(pp=n8) lins

44、hih32='b' if(pp=n9) linshih32='c' if(pp=n14) linshih32='d' pp=ptr; _asm and pp,00000011b; if(pp=n10) linshih33='a' if(pp=n11) linshih33='b' if(pp=n12) linshih33='c' if(pp=n15) linshih33='d' ; void discodemanage()/解压缩程序 使用huancun放密文，解压后原文放在yasuo

45、huancun中 /文件开始的对应表读进paixusign和paixuzifu中 /还要使用linshih3 cout<<"-enter in discode manage program-"<<endl; yasuohuancunnumber=0; string holdptr="" int x,y; for(x=0;x<huancunnumber;x+) jiemah3code(huancunx); for(y=0;y<4;y+) holdptr=holdptr+linshih3y; if(checkh3code(

46、holdptr) holdptr="" ; char linshih34;/临时三元霍夫曼 int linshih3number;/记录临时三元霍夫曼个数 int number;/未压缩字符的数量 int everyzifunumbermax;/每个字符出现的次数 string signmax;/压缩后的字符(先用数字表示) string paixusignmax;/编码后与paxu字符数组对应的编码 char paixuzifumax;/和字符数组一样，顺序对应paixusign char zifumax;/未压缩的字符(互不相同);void readfile(const

47、 char* realfile)/文件读入缓存huancunnumber=0;ifstream inputfile;inputfile.open(realfile);if(!inputfile)cout<<"no file"<<endl; long int x=0;char a;while(!inputfile.eof() a=inputfile.get();huancunhuancunnumber=a;huancunnumber+;/cout<<huancunnumber<<" "for(x=0;x<huancunnumber;x+)cout<<huancunx;cout<<endl;inputfile.close();void writefile(co