搜索
计算机与信息学院信息论与编码实验报告专业班级信息安全13-1班学生姓名及学号马骏2013211869课程教学班号任课教师苏兆品实验指导教师苏兆品实验地点逸夫楼2014~2015学年第一学期实验1霍夫曼编码一、基本要求通对任意输入的字符串序列进行3元霍夫曼编码，给出编码结果、编码效率；并实现相应的译码操作。二、提升要求对一幅BMP格式的灰度图像进行二元霍夫曼编码。三、问题描述1、三元霍夫曼编码首先需要考虑的是如何表示三元2、三元霍夫曼编码需要对不满足2n+3的情况做处理3、使用什么数据结构建立霍夫曼树四、算法思想1、使用两个二进制位表示一个三元变量，即00表示a、01表示b、11表示c。2、出现不满足2n+3情况即需要加入一个出现次数为0次的字符，遍历已经出现的字符，找到一种八位二进制组合作为新字符。3、建立霍夫曼树的算法，使用数组的结构作为整棵树的空间，其中每个数组元素是一个类的实例。在这各类里封装了他所代表的字符（如果不是叶子节点则为null）、出现的次数（非叶子结点则为子节点的此项加和）。承载整棵树的数组也是封装在一个类里的，这个类同时封装了对这棵树的操作，如添加节点、树节点排序等，这样就可以使从添加叶子节点后建立整棵霍夫曼树。五、模块划分charhuancun[max];//从文件中读入的字符charyasuohuancun[max];//压缩后可以写进文件中的字符串longintyasuohuancunnumber=0;//准备写入文件中的个数longinthuancunnumber=0;//从文件中读出字符个数classtree{voidset(inta,intb,intc,intd,inte)//次数为a，左孩子为b，中孩子为c，右孩子为d，自己的编号eintmynumber;//次数intleftsonnumber;//数组编号intmiddlesonnumber;intrightsonnumber;//数组编号控制时没有儿子节点则儿子都是负数intmyzifunumber;//作为叶子节点在数组中的编号};classtable//压缩对照表{public:table()voidcutrealfile()//将缓存中一样的字符区别开voiduncheck(charhuancun)//检查是否出现过字符boolcheck(charhuancun)//检查源文件字符是否出现过intcheckhuancun(inti)//读缓存数组的字符，返回yasuozifu数组中的地址voidcount(treefun[],intbegin,intend)//begin~end区间内排序charh3setonechar(charn1,charn2,charn3,charn4)//三元霍夫曼给进一个char位操作使用内联汇编语言d是不会被译码的为了补齐余码voidlinshih3manage(charptr)//进来字符存起来每四个存一个voidwritesign(treefun[],intpermitnumber,chark,intfuthernumber)//先给sign的值递归构建霍夫曼树voidhafuman3()//三元霍夫曼编码函数voidcodemanage()//对整个缓存进行编码boolcheckh3code(stringptr)//对解压缩后的码串译码voidjiemah3code(charptr)//对一个char型8位进行解码为4个char型voiddiscodemanage()//解压缩程序使用huancun[]放密文，解压后原文放在yasuohuancun[]中charlinshih3[4];//临时三元霍夫曼intlinshih3number;//记录临时三元霍夫曼个数intnumber;//未压缩字符的数量inteveryzifunumber[max];//每个字符出现的次数stringsign[max];//压缩后的字符(先用数字表示)stringpaixusign[max];//编码后与paxu字符数组对应的编码charpaixuzifu[max];//和字符数组一样，顺序对应paixusigncharzifu[max];//未压缩的字符(互不相同)};voidreadfile(constchar*realfile)//文件读入缓存voidwritefile(constchar*yasuofile)//缓存写入文件intmain()//主函数{readfile(realfile);tablemytable;mytable.cutrealfile();mytable.hafuman3();mytable.codemanage();writefile(yasuofile);readfile(yasuofile);mytable.discodemanage();writefile(jieyasuofile);return0;}六、测试数据2.txt文件n999.bmp文件1、2.txt文件hellomarkchalse,thisisasecretnumber6424155pleaseputthisinancode小刀司令压缩后：將埼绩髱釜#?庩宏壕ǔ券?€:,焕?0鼜?姾嫧偪瘞旰??3??飶卡8*解压缩后（最后多了一字节空格）：hellomarkchalse,thisisasecretnumber6424155pleaseputthisinancode压缩情况：源文件：压缩文件：解压缩文件：编码分析：无损压缩压缩率：74.16%2、n999.bmp压缩后：解压缩无失真压缩七、源程序（见附录）实验2算术编码一、基本要求对任意输入的字符串序列进行自适应编码，并设计相应的译码二、提升要求对一幅bmp格式的灰度图像进行自适应算术编码，并设计相应的译码三、问题描述1、算术编码的过程实际就是对两个小数确定的取区间，划分区间，再取区间不断重复的过程，将采用什么数据结构。2、自适应编码如何确定小数的误差以保证无误差即零失真3、Longdouble只有二十几位如何压缩更多的内容四、算法思想1、将上边界，下边界分别记录，并封装在一个类中。类中还封装了对区间选择、改变上界下界值的函数等。2、区计算后的各字符概率的小数后八位保证无误差3、为保证压缩足够多的量，不采用longdouble记录上下界的值，而是采用int型数组来记录上下界的值，每个longint取七位十进制数。这样初始max值为10000，所以整个算法可以进行小数点后70000位的小数加减乘除取对数等运算，保证了可压缩量五、模块划分因为要进行长数位计算所以用一个longint[]的数组将每个单元表示7位十进制数按max=10000的初始可以达小数点后70000位在存储大数时数组按距离小数点越近越靠左的顺序码放用一个类封装数据和操作方便对数据的掉用，省得一会形参一会实参下边界为准注意length[]中是按照小数的格式如果某一元组其不满7位则前面为0将length[]连起来表示数时一定要注意步骤：1、将原文件读入缓存2、统计原文件字符的种类有多少频率分别是多少(自适应)提示：计算频率doublec=double(a)/double(b);3、接下来在arithmetic_coding中根据缓存中每个字符获得最后的概率getposible(char)得到给定字符的概率区间getlength()计算区间长度intgetint(double)将概率小数转化成整数classposible_8::set(int)lowposiblehighposible在这里先通过getint()转化为8位整数再变成4个2位的整数方便计算接下来用posible_8的每一个数组元素(两位)从length[]最后开始乘并向前进位mathmatic::intgetreallength()//得到length[]数字的准确位数classposible_8::intgetlong()//得到every2bit[]的小数位长mathmatic::intgetbeginlength()//得到length[]数字的从开始到最后一个数字的准确位数mathmatic::voiddealhigh()//high=low+lowposible*length=low+length(已处理)mathmatic::voidcuthigh()//high后面不需要的为零的元组要约去mathmatic::voiddeallow()//low=low+lowposible*length=low+length(已处理)mathmatic::voidcutlow()//low后面不需要的为零的元组要约去4、mathmatic::voidcode()将最后的low[]进行二进制编码存入yasuohuancun[]中#includemath.h之后就可以直接使用log了以2为底的对数可以用换底公式表示log(n)/log(2)不能用log()求一个数组表示的大数的原因是log(a+b)根本无法拆解啊不要说把a+b分解成c*d*.......但我们可以使用简单粗暴的0.5*0.5*0.5.......迭代进行直到找到那个整数部分mathmatic::intgetlog()//返回log(length)mathmatic::intchecksize(longintgoal[max],intgoalnumber,longintlow[max],intlownumber)//比较两个正规小数大小goal小返回1大0相等2mathmatic::voiddealmycode()//将mycode中的十进制表示的二进制转化为二进制存入yasuohuancun[]中5、mathmatic::voiddiscode()//解压缩压缩文件已读入huancun[]第一个是以前的huancunnumbermathmatic::voiddeal8bit(charkp,intoverbit)//计算nowlowmathmatic::voidaddnowlow()//low+nowlowdiscode()现在low已经有了，接下来需要比较yasuohuancunnumber次就可以还原以前的huancun[]了不过需要重用nowlow[]作为目标小数low[]每次需要做运算intgetzifu()函数中代码重用：重用arithmetic_coding()代码直接用checksize()BUG:discode()不知道为什么要减1最后一个字符11111111这个bug还没有修复这个bug非常严重导致如原文件内容为abc无法六、测试数据2.txt文件n77.bmp文件1、2.txt文件hellomarkchalse,thisisasecretnumber6424155pleaseputthisinancode小刀司令压缩后：稬??睖?反.媹录?缶m郜緕k?.?=X杛楞璩tm?桶程序过程：解压缩后：hellomarkchalse,thisisasecretnumber6424155pleaseputthisinancode小刀司令压缩情况：源文件：压缩文件：解压缩文件：编码分析：无损压缩压缩率：65.17%2、n77.bmp压缩文件：傝?靯[左m鮏.=W噀~Z鐢?霑楞壗YO?濖?痦畝?湍叚?\Jz?V摮|_p濔?褺S??老z7?tJ?料c鶻H娀止程序过程：解压缩后：压缩情况：源文件：压缩文件：解压缩文件：编码分析：无损压缩压缩率：32.96%七、源程序（见附录）八、总结通过此次实验，我在学习编码原理的进一步学习了各种无失真信源编码的编程方法，使我对信息论与编码有了更深的了解。程序中还存在很多的不足，希望在以后的学习中可以做到更加完善。附录Hafuman.cpp/*基本要求：对任意输入字符串进行三元哈弗曼编码*/#includeiostream#includestring#includefstream#inc