哈夫曼编码算法.doc

《算法设计与分析》上机报告姓名: 学号: 日期: 上机题目: 哈夫曼编码算法实验环境: CPU : ;内存:6G ;操作系统: Win7 64位;软件平台: Visual Studio 2008 ; 一、算法设计与分析: 题目:哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在 20% ~90% 之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用 0,1 串表示各字符的最优表示方式。一个包含 100,000 个字符的文件,各字符出现频率不同,如下表所示。有多种方式表示文件中的信息,若用 0,1 码表示字符的方法,即每个字符用唯一的一个0,1串表示。若采用定长编码表示,则需要3位表示一个字符,整个文件编码需要300,00 0 位;若采用变长编码表示,给频率高的字符较短的编码;频率低的字符较长的编码,达到整体编码减少的目的,则整个文件编码需要( 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;i<n;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) #defi