哈夫曼编码算法.doc

《算法设计与分析》上机报告 姓名： 学号： 日期： 上机题目： 哈夫曼编码算法 实验环境： CPU: 2.10GHz ; 内存: 6G ; 操作系统：Win7 64位 ;软件平台：Visual Studio2008 ; 一、算法设计与分析： 题目: 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在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(node C[],int n) { BuildMaxHeap(C,n); for(int i=1;in;i++) { node* z = new node; 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 using namespace std; #define LEFT(i) (2*i) #define RIGHT(i) (2*i+1) struct node { char c; int freq; node* left; node* right; }; void Exchange( node x, node y ) { node temp = x; x = y; y = temp; } void MaxHeapify( node a[], int i, int n ) { while( 1 ) { int l = LEFT( i ); int r = RIGHT( i ); int smallest; if( l=n a[l].freq a[i].freq ) smallest = l; else smallest = i; if( r=n a[r].freq a[smallest].freq ) smallest = r; if( smallest != i ) { Exchange( a[i], a[smallest] ); i = smallest; } else break; } } void BuildMaxHeap( node a[], int n ) { for(int i=n/2;i0;i--) M