英文文件的压缩和解压缩

。 为了详细说明这个问题，特以下面例子来说明:有四个叶子结点A，B，C，D，分别 带权为9，4，5，2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL(树 的带权路径长度)不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全 二叉树不一定是最优树。权值越大的结点离根越近的二叉树才是最优二叉树(huffman 树)。按照上面的算法，则可按照下面图的构造过程生成huffman树。 Huffman树产生流程:以一例说明 A B D C C A D B A A C C D B D B 图2.哈夫曼树产生流程 Huffman编码流程: int rem,p;int count1=0; count1=0; for(int y=1;y<=count;y++) rem=y;hcode[y].c=huff[y].data; p=huffman[y].parent; while(p!=0 ) if(huffman[p] .lchild==rem) hcode[y].bits[++count1]='1' ; hcode[y].bits[++count1]='0'; 图3.huffman编码流程 Huffman解码流程: fp1>>inchar; if(inchar=='1 ') ptr=huffman[ptr].rchildptr=huffman[ptr].lchild ; ; if(huffman[ptr].lchild== 0&&huffman[ptr].lchild ==0) fp2 图4.huffman解码流程 四、上机调试 开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就是huffman编码是采用等长编码还是采用不等长问题，采用不等长编码要避免译码的二义性或多义性。假设用0表示字符D，用01表示字符C则当接受到编码串“„01„”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。 为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的huffman树的问题。 基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些变量还没有声明的错误，对遗漏的变量进行了声明后，再次调试，发现一个比较大的问题，就是字符都能读入，但是不能进行编码，也即不能构造 huffman树，最后经过检查发现原来是结点方面存在问题，最后加入sum=2*count-1;语句，问题得到解决。(该语句的作用是:例如提供了3个权值不同的结点，现在要构造huffman树，那就需要5个结点。) 五、测试结果 图5(与图6同为测试结果) 图6(与图5同为测试结果) 被编码(部分字符): 图7.被编码后的文档 被解码(部分文件): 图8.被解码后的文档 六、用户使用说明 用户运行本程序前，首先要在起工程文件下建立一个名字为Huffman.txt文本文档，再运行本程序后，第一步，按任意键来读取建立的 Huffman.txt文本文档,再据程序中提示完成第二步操作，也即是讲压缩的文件以Huffman编码放入一个由用户自己建立的文本文档中，接着再根据提示完成第三步操作，即对要压缩的文件解压后放入由用户建立的任意名的文本文档中，由此完成操作。 七、参考文献 [1] 王昆仑，李红. 数据结构与算法. 北京:中国铁道出版社，2006年5月。 [2] 郑莉等.c++语言程序设计(第三版)[M].北京:清华大学出版社，2003年12月 八、附录 #include #include #include #include using namespace std; string remfile[600000]; //存放原文件字符的数组 int remcount=0; //记录元素个数 float bitecount=0; //记录二进制码的个数 typedef struct { //存放读入字符的类 int count; //字符出现的个数 char data; //字符 }huffchar; int count=1; //记录huff数组中字符实际出现的个数 huffchar huff[1000]; //类的对象 //文件读入部分和统计字符出现的频率 bool char_judge(char c){ //判断字符出现的函数 for(int i=1;i<=count;i++) if(huff[i].data==c){ huff[i].count++; return true; } //如果出现过，出现的频数加1 return false; } void char_add(char c){ //添加新出现的字符; huff[count].data=c; huff[count++].count++; //个数增加 } //文件的读取 void read_file_count(){ char c; ifstream infile; infile.open("huffman.txt"); //打开huffman.txt文件 if(!infile){ //检查文件是否打开。 cout<<"不能打开 huffman.txt文件"; //输出文件未打开的标志 exit(0); } cout<<"读入的文件中的内容为:"<>str; fp.open(str.c_str()); if(!fp){ //检查文件是否打开 cout<<"不能打开 "<0;k--){ fp<>s1; fp2.open(s1.c_str()); if(!fp2){ //检查文件是否打开 cout<<"不能打开"<>inchar; if(inchar=='1') ptr=huffman[ptr].rchild;//查找相应编码对应huffman树中的位置 else ptr=huffman[ptr].lchild; if(huffman[ptr].lchild==0&&huffman[ptr].rchild==0){ //判断是否为叶子结点 fp2<