2022年2022年哈夫曼编码 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年2022年哈夫曼编码 .pdf》由会员分享,可在线阅读,更多相关《2022年2022年哈夫曼编码 .pdf(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、哈夫曼编码I.问题描述哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1 串表示各字符的最优表示方式。II. 问题分析对每一个字符规定一个0,1 串作为其代码, 并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。设 C 为编码字符集,则表示其最优前缀码的二叉树中恰有|C|个叶子, |C|-1 个内部结点。其中,每个叶子对应于字符集中一个字符。二叉树 T 的代价:编码文件需要二进制位数使达到最小的前缀码编码方案称为给定编码字符集C 的最优前缀码。哈夫曼提出构造最优前缀码的贪心算法,由此
2、产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以 |C|个叶结点开始,执行|C|1次的“合并”运算后产生最终所要求的树T。编码字符集中每一字符c 的频率是freq。以 freq 为键值的最小堆优先队列Q 用在贪心选择时有效地确定算法当前要合并的2 棵具有最小频率的树。 一旦 2 棵具有最小频率的树合并后,产生一棵新的树, 其频率为合并的2 棵树的频率之和, 并将新树插入最小堆优先队列Q。经过 n-1 次的合并后,优先队列中只剩下一棵树,即所要求的树T。III .算法描述:HUFFMAN(C) /哈夫曼编码算法n = |C| / 初始化最小优先队列Q
3、INITIALIZE(Q) = BUILD-MIN-HEAP(C) for i=1 to n-1 allocate a new node z z.left = x EXTRACT-MIN(Q) /提取队列 Q 中的最前列结点z.right = y EXTRACT-MIN(Q) z.freq x.freq + y.freq INSERT(Q, z) /在队列 Q 中插入结点z return EXTRACT-MIN(Q) 时间复杂度描述:INITIALIZE(Q) = BUILD-MIN-HEAP(C)的时间复杂度为O(n) ;循环for i=1 to n-1 的时间复杂度为O(n) ;其中,z.
4、left = x EXTRACT-MIN(Q) 和 z.right = y EXTRACT-MIN(Q) 的时间复杂度分别为O(nlogn) ;INSERT(Q, z) 的时间复杂度为O(nlogn) ;最后返回最前列结点return EXTRACT-MIN(Q)的时间复杂度也为O(nlogn) 。所以,这个哈弗曼算法的时间复杂度为T(n)=O(nlogn) 。( ).( )Tc CB Tc freq dc名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 6 页 - - -
5、 - - - - - - IV.程序#include #include #include typedef struct /结点结构体 unsigned int weight; /用来存放各个结点的权值 unsigned int parent,LChild,RChild; /指向双亲、孩子结点的指针 HTNode, *HuffmanTree; /动态分配数组,存储哈夫曼树typedef char *HuffmanCode; /动态分配数组,存储哈夫曼编码/ 选择两个parent为0,且 weight 最小的结点s1和 s2void Select(HuffmanTree *ht,int n,int
6、 *s1,int *s2) int i,min; for(i=1; i=n; i+) if(*ht)i.parent=0) min=i; break; for(i=1; i=n; i+) if(*ht)i.parent=0) if(*ht)i.weight(*ht)min.weight) min=i; *s1=min; for(i=1; i=n; i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 6 页 - - - - - - - - - if(*ht)i.pare
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年2022年哈夫曼编码 2022 年哈夫曼 编码
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内