实验报告-哈夫曼.docx

算法分析与设计课程设计报告题 目：利用哈夫曼编码算法实现字串最优前缀码的生成工作 专 业： 计算机科学与技术 班 级： 姓 名： 指导教师： 2016年 5 月 25日一、问题分析。哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。 哈夫曼树注意事项： 初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子 n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。 哈夫曼树是严格的二叉树，没有度数为1的分支结点。前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。带权值的结点都是叶子结点。权值越小的结点，其到根结点的路径越长。所谓前缀码是指，对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，比如常见的等长编码就是前缀码。所谓最优前缀码是指，平均码长或文件总长最小的前缀编码称为最优的前缀码（这里的平均码长相当于码长的期望值）。哈夫曼编码算法实现字串最优前缀码的生成，这是压缩的一种方式，在实际生活中应用广泛，一般采用贪心算法，二、问题的解决方案/算法选择/设计思路。(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。 (2)算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。 (3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。生成哈夫曼树（1）根据给定的n个权值w1,w2,.,wn构造n棵二叉树的集合F=T1,T2,.,Tn，其中Ti中只有一个权值为wi的根结点，左右子树为空； （2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 （3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。图1在队列中取最小的两个数，根的权值是这两个数的和，在将根的值带回队列中，在取最小的两个数，重复进行，得到哈夫曼树。记左子树为0，右子树为1，得到最优前缀数。三、算法设计/问题求解中所遇到的问题及分析解决方案。 生成树/*功能用于生成哈夫曼树*/ huffman ctrHuffmanTree(int n) int m=2*n-1;/1n存储叶子结点n+1m存储树的n-1个内部结点 huffman tree=(huffman)malloc(sizeof(huffmanNode)*(m+1);/用于存储哈夫曼树各结点 priorityqueue h;/用于存储优先队列首地址 int i; if(tree=NULL) printf(out of space); exit(-1); /*生成叶子结点*/ for(i=1;i=n;i+) printf(输入 %d 字母和权重:,i); scanf(%c%f,&treei.c,&treei.f); treei.i=i; treei.parent=treei.lchild=treei.rchild=-1; treei.code=NULL; getchar();/吸收回车 /*初始化优先队列*/ h=initializePrioQueue(n,tree); /*生成n-1个内部结点*/ for(i=n+1;i=m;i+) huffmanNode x,y,z; x=popPrioQueue(h); y=popPrioQueue(h); z.f=x.f+y.f; z.lchild=x.i; z.rchild=y.i; z.parent=-1; z.i=i; treex.i.parent=i; treey.i.parent=i; treei=z; pushPrioQueue(h,z); /*前缀码生成*/ for(i=1;ielement); free(h); return tree; 四、算法设计/问题求解特色及关键技术。 特点：随机生成权重。 贪心算法：二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。设b和c是二叉树T的最深叶子，且为兄弟。设f(b)=f(c)，f(x)=f(y)。由于x和y是C中具有最小频率的两个字符，有f(x)=f(b)，f(y)size;h-elementi/2.fx.f;i/=2) h-elementi=h-elementi/2;/父结点向下移 h-elementi=x; 五、算法测试。图3六、结论。根据各个字符的权值建立一颗哈夫曼树制作哈夫曼编码表，对数据文件的编码过程是：依次读人文件中的字符，在哈夫曼编码表中找到此字符，将字符转换为对应的哈夫曼编码。对压缩后的数据文件进行解码则必须借助于哈夫曼树，其过程是：依次读人文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向左孩子，否则走向右孩子。一旦到达某一叶子时便译出相应的字符。然后重新从根出发继续译码，直至文件结束。哈夫曼编码是动态变长编码，临时建立概率统计表和编码树。概率小的码比较长，概率小的码比较长。概率大的码短，这样把一篇文件编码后，就会压缩许多。从树的角度看，哈夫曼编码方式是尽量把短码都利用上。首先，把一阶节点全都用上，如果码字不够时，然后，再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最佳码。该代码缺少可视化，缺乏实用性，不具有成为优秀代码的资格。但该代码的构思独特，思路清晰，具有简约明了等特征，颇具使用性。用取局部最优的贪心算法，更简单的将问题清晰化，更好的解决问题。通过这次设计，我对二叉树和哈夫曼树有