《合肥工业大学 信息论与编码 实验报告 完整代码版讲解》由会员分享，可在线阅读，更多相关《合肥工业大学 信息论与编码 实验报告 完整代码版讲解（65页珍藏版）》请在金锄头文库上搜索。
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()转化为8位
12、整数再变成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 cuth
13、igh()/high 后面不需要的为零的元组要约去 mathmatic:void deallow()/low=low+lowposible*length=low+length(已处理) mathmatic:void cutlow()/low 后面不需要的为零的元组要约去 4、mathmatic:void code()将最后的low进行二进制编码存入yasuohuancun中 #include之后就可以直接使用log了 以2为底的对数可以用换底公式表示 log(n)/log(2) 不能用log()求一个数组表示的大数的原因是 log(a+b)根本无法拆解啊 不要说把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
