哈夫曼编码算法.doc

哈夫曼编码算法《算法设计与分析》上机报告姓名:学号:日期:上机题目:哈夫曼编码算法实验环境:CPU:;内存:6G;操作系统:Win764位;软件平台:VisualStudio2008;一、算法设计与分析,题目:哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%,90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。一个包含100,000个字符的文件,各字符出现频率不同,如下表所示。有多种方式表示文件中的信息,若用0,1码表示字符的方法,即每个字符用唯一的一个0,1串表示。若采用定长编码表示,则需要3位表示一个字符,整个文件编码需要300,000位;若采用变长编码表示,给频率高的字符较短的编码;频率低的字符较长的编码,达到整体编码减少的目的,则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224,000位,由此可见,变长码比定长码方案好,总码长减小约25%。哈夫曼编码步骤:一、对给定的n个权值{W1,W2,W3,...,Wi,‎‎...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算法,一般还要求以Ti的权值Wi的升序排列。)二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步,直到集合F中只有一棵二叉树为止。二、核心代码,node*huffman(nodeC[],intn){BuildMaxHeap(C,n);for(inti=1;i<n;i++){node*z=newnode;z->left=extract_min(C,n-i+1);z->right=extract_min(C,n-i);z->freq=z->left->freq+z->right->freq;C[n-i]=*z;MaxHeapify(C,n-i,n-i);}return&C[1];}三、结果与分析,其中“,”表示该结点没有字符最优性:二叉树T表示字符集C的一个最优前缀码,x和y是树T中的两个叶子且为兄弟,z是它们的父亲。若将z当作是具有频率f(z)=f(x)+f(y)的字符,则树T’=T-{x,y}表示字符集C’=C-{x,y}?{z}的一个最优前缀码。因此,有:如果T’不是C’的最优前缀码,假定T”是C’的最优前缀码,那么有,显然T”’是比T更优的前缀码,跟前提矛盾~故T'所表示的C'的前缀码是最优的。由贪心选择性质和最优子结构性质可以推出哈夫曼算法是正确的,即HuffmanTree产生的一棵最优前缀编码树。算法源代码(C++描述)#include<iostream>usingnamespacestd;#defineLEFT(i)(2*i)#defineRIGHT(i)(2*i+1)structnode{charc;intfreq;node*left;node*right;};voidExchange(node&x,node&y){nodetemp=x;x=y;y=temp