Huffman编码及译码

Huffman编码及译码 1.题目 Huffman编码及译码 2. 使用文件保存初始的文本数据及最终的结果。 , 文件名为inputfile1.txt的文件保存的是一段英文短文; , 文件名为inputfile2.txt的文件保存01形式的编码段; , 文件名为outputfile1.txt的文件保存各字符的出现次数和对应的编码; , 文件名为outputfile2.txt的文件保存对应于inputfile2.txt的译码结果。 统计inputfile1.txt中各字符的出现频率，并据此构造Huffman树，编制Huffman编码;根据已经得到的编码，对01形式的编码段进行译码。 具体的要求: 1(将给定字符文件编码:生成编码，输出每个字符出现的次数和编码; 2(将给定编码文件译码:生成字符，输出编码及其对应字符。 3.程序实现 3.1程序运行及编译环境 操作系统:windows，编译环境，vc++ 6.0 3.2程序描述 程序一方面实现了对inputfile1文本文件进行霍夫曼编码，输出字符编码文件outputfile1(字符和它的二进制编码)和整个文件编码后的文件inputfile2。另一方面，程序可以将这个编码后的文件inputfile2进行译码，输出outputfile2。Inputfile1和outputfile2中的内容是一样的。 3.3实现功能 3.3.1子功能模块 为了程序主函数的简洁，我将各个步骤分成模块。 #include #include #include #include #include "FreqPair.h" #include "Huffnode.h" #include "HuffCode.h" #include "Hufftree.h" #include "SLList.h" #include "FileAnalysis.h" #include "buildSLList.h" #include "buildHufftree.h" #include "HuffEncode.h" #include "HuffCodetoFile.h" #include "HuffDecode.h" void main(){ //进行文件分析，找出所用的字符个数，并形成有用的频率对 char * inputfile1="inputfile1.txt"; FreqPair *letter=new FreqPair[128]; int lettercount=0; FileAnalysis(letter,lettercount); cout<<"-----------------读入文件inputfile1.txt-------------------\n"; //利用文件分析得到的频率对生成链

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

。 SLList *alist=new SLList; alist=buildlist(letter,lettercount); cout<<"-----------------建立链表alist完成------------------------\n"; //从链表生成霍夫曼树。 HuffTree *htree; htree=buildHufftree(alist); cout<<"-----------------建立霍夫曼树htree完成--------------------\n"; //从霍夫曼树进行编码，存到hcode[]中,并保存到一个文件中。 huffcode *hcode=new huffcode[lettercount]; 第1页 char * outputfile1="outfile1.txt"; HuffEncode(htree,hcode,letter,outputfile1); cout<<"-----------------编码完成---------------------------------\n"; //将一个文件进行编码，并输入到另一个文件中 char*f_in="inputfile1.txt"; char*f_out="inputfile2.txt"; HuffCodetoFile(f_in,f_out,hcode,lettercount); cout<<"-----------------写入编码文件完成-------------------------\n"; //用霍夫曼树从一个文件进行译码，输出到另一个文件。 char*fin="inputfile2.txt"; char*fout="outputfile2.txt"; HuffDecode(htree,fin,fout); cout<<"-----------------译码完成---------------------------------\n"; } 3.3.1.2算法及程序说明 首先，定义一个霍夫曼树的基类结点为一个抽象类，树的叶结点和内结点继承此基类结点，具体的叶结点和内结点的数据及功能自己再扩展。这样便于用基类的指针来指向叶结点和内结点的对象并访问它们的成员。 霍夫曼树的构造，是用一个权有序的链表来实现的。 第一步，从文件生成需要编码的lettercount个频率对，并由此生成lettercount个霍夫曼树(此时的树只有一个叶结点)。如图-1所示。 A，8 B，3 C，1 D，4 E，1 。。。。。。 Lettercount个 图-1 第二步，把这些树插到链表当中。注意插入的时候是按树的权值大小插入的。小的插在前面，大的就往后找，直到找到合适的位置。保证整个链表按结点(树)的权值有序(从小 第2页 到大)排列。如图-2所示。 相关代码如下所示: bool insert(HuffTree *htreein){ node *tmp=new node; tmp->htree=*htreein; for(node *nptmp=head;nptmp->next!=NULL&&(nptmp->next->htree.weight())<(htreein->weight() );nptmp=nptmp->next); tmp->next=nptmp->next; nptmp->next=tmp; listcount++; return true; }; Head A，8 Head A，8 B，3 图-2 第三步，构造霍夫曼树。每次新生成一棵树，再从链表的头读出两个树，新树的左右孩子分别是刚才取出的两棵树。再将这棵新树插到链表中。仍然保持链表有序。重复这个步骤直到链表只剩下一棵树。这样霍夫曼树就构造好了。如图-3所示。 相关代码如下: HuffTree* buildHufftree(SLList* fl){ HuffTree*temp1,*temp2,*temp3; 第3页 temp1=new HuffTree; temp2=new HuffTree; while(fl->Listcount()>1){ fl->remove(temp1); fl->remove(temp2); temp3=new HuffTree(temp1,temp2); fl->insert(temp3); } delete temp1; delete temp2; return temp3; }; Head C，1 E，1 B，3 D，4 A，8 left right Weight =2 Head WeightB,3 D , 4 A , 8 =2 图-3 第四步。编码。递归遍历整个霍夫曼树，因为递归函数带一个char*型数据path及它的脚标pathcount。(1)如果读到叶子(用isleaf()判断)则得到一个字符的编码。(2)字符串在原来字符串的基础上加‘0’， 相应地pathcount加1，然后调用左走的函数，出了左走的函数，pathcount减1。(3)字符串在原来字符串的基础上加‘1’， 相应地pathcount 第4页 加1，出了左走的函数，pathcount减1。这样遍历完整个树，就得到了所有叶子中的字符的编码。结果如如图-4所示。 相关代码如下: void encode(HuffNode *subroot,huffcode *hcode,int& hcodecount,char*path,int &pathcount){ if(subroot->isLeaf()){ path[pathcount]=NULL; strcpy(hcode[hcodecount].code,path); hcode[hcodecount++].letter=((LeafNode*)subroot)->val(); return; } path[pathcount++]='0'; encode(subroot->left(),hcode,hcodecount,path,pathcount); pathcount--; path[pathcount++]='1'; encode(subroot->right(),hcode,hcodecount,path,pathcount); pathcount--; } 17 1 7 9 8 A,0 11 4 5 D,10 110 B,111 2 3 1 1 C,1100 E,1101 图-4 第5页 第五步。译码。从文件读二进制序列，在霍夫曼树根的基础上，如果是0则往左走，如果是1则右走。直到走到叶子，输出该叶子中存的字符。如图-5所示。 相关代码如图所示: void HuffDecode(HuffTree *htree,char*f_in,char*f_out){ HuffNode *subroot=htree->root(); ifstream fin(f_in); ofstream fout(f_out); char ch; while(!fin.eof()){ fin.get(ch); if(ch=='0') subroot=subroot->left(); else subroot=subroot->right(); if(subroot->isLeaf()){ fout<<((LeafNode*)subroot)->val(); subroot=htree->root(); } } fout.close(); fin.close(); } 17 7 9 8 A,0 4 5 D,10 B,111 2 3 1 1 C,1100 E,1101 图-5 第6页 第六步。最后需要做的是将这些功能模块组织起来，为了防止头文件插入多次，每个头文 件都需要条件编译。 如下所示: #ifndef ABC_H #define ABC_H …… #endif 3.4运行结果 运行结果及译码生成文件/原文件的对比如图-7所示。 图-7 第7页 3.5尚未解决的问题 1.压缩效率。实际上一个文件通过编码译码之后生成的霍夫曼压缩文件并不是真正的压缩文件。因为很明显文件大小增长了7~8倍。这是因为写入的并不是二进制数，而是二进制数0，1的ascii值。所以一个改进的地方就是通过写入和读出二进制文件实现真正的霍夫曼压缩和解压缩。 2(通用性。我们输入一个文件，程序就生成一棵霍夫曼树，将其编码实现压缩。但是由于输入文件的不同，程序没有一棵通用的霍夫曼树。考虑到这点，程序可以改进的另一个地方是内置一棵通用树，做一个接口函数以实现不同文件之间压缩与解压缩的一致性。 3(压缩对象。程序只处理字符的编码，译码。对于其他非文本文件，就无法处理。所以程序可以扩展的另一个功能是对非文本文件的支持。 第8页 第9页