哈夫曼编码算法

《算法设计与分析》上机报告姓名：学号：日期：上机题目：哈夫曼编码算法实验环境：CPU:2.10GHz;内存: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;in;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++描述）#includeiostreamusingnamespacestd;#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;}voidMaxHeapify(nodea[],inti,intn){while(1){intl=LEFT(i);intr=RIGHT(i);intsmallest;if(l=n&&a[l].freqa[i].freq)smallest=l;elsesmallest=i;if(r=n&&a[r].freqa[smallest].freq)smallest=r;if(smallest!=i){Exchange(a[i],a[smallest]);i=smallest;}elsebreak;}}voidBuildMaxHeap(nodea[],intn){for(inti=n/2;i0;i--)MaxHeapify(a,i,n);}node*extract_min(nodea[],intn){node*temp=newnode;*temp=a[1];a[1]=a[n];MaxHeapify(a,1,n-1);returntemp;}node*huffman(nodeC[],intn){BuildMaxHeap(C,n);for(inti=1;in;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];}voidprint(node*pRes){if(pRes!=NULL){coutpRes-c'-'pRes-freq',';print(pRes-left);print(pRes-right);}}intmain(){nodea[7]={{'',0},{'e',9},{'f',5},{'c',12},{'a',45},{'d',16},{'b',13}};cout输入的表为：endl;for(inti=1;i7;i++)couta[i].c'-'a[i].freq',';node*pRes=huffman(a,6);coutendl生成的Huffman树为a(前序遍括历)：endl;print(pRes);coutendl;system(pause);return0;}