国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 018-Huffman树-贪心-《算法设计技巧与分析》M.H.A学习笔记

018-Huffman树-贪心-《算法设计技巧与分析》M.H.A学习笔记

来源:程序员人生   发布时间:2016-07-28 08:43:51 阅读次数:1090次

Huffman是完全2叉树,权重较大的节点距离根较近。

Huffman编码1种编码方法,该方法完全根据字符出现几率来构造异字头的平均长度最短的码字

 

基本思路:

建立Huffman树的进程:

假定有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1w2wn,则哈夫曼树的构造规则为:

(1) w1w2wn看成是有n 棵树的森林(每棵树唯一1个结点)

(2) 在森林当选出两个根结点的权值最小的树合并,作为1棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

(3)从森林中删除选取的两棵树,并将新树加入森林;

(4)重复(2)(3)步,直到森林中只剩1棵树为止,该树即为所求得的哈夫曼树。

 

选取权值最小的结点时我们用最小堆。

需要得出各个字母的具体编码,我们只需要在所有的左儿子的边标上0,右儿子的边标上1,从根节点到目标节点的所有经过的边的码就是该字母的编码。

 

算法分析:

假定有n个字符。

把所有字符插入堆需要Θ(n),从堆中删除两个元素和新加1个元素需要O(log n)。重复n⑴次,所以总的时间复杂度是O(n log n)

 

伪代码:

 


 

 

C++代码:

//计算哈夫曼编码下的文本占的位数,并与定长编码的比较。 #include<iostream> #include<string> #include<cstring> #include<iomanip> #include<cstdio> #include<queue> //哈夫曼树,用优先队列实现 using namespace std; int main() { string s; while (cin >> s) { if (s == "END") break; int len = s.size(); int date[30] = { 0 }; //date数组记录text中各个字符的频数 priority_queue<int>q; for (int i = 0; i < len; i++) { if (s[i] == '_') date[0]++; else date[s[i] - 'A' + 1]++; } for (int i = 0; i < 27; i++) { if (date[i]!=0) q.push(-date[i]); //只把不同字符的频数加入优先队列,字符本身与题目要求无关 } //处理使小的数据的优先级别高 int ans = 0; int tem; while (!q.empty()) { tem = -q.top(); //取出最小的两个数,相加累计到ans中,并加入队列,1直处理到队列中没有数 q.pop(); if (!q.empty()) { tem = tem - q.top(); q.pop(); } ans = ans + tem; if (!q.empty()) q.push(-tem); //若队列已没有数据,则不添加(上面已取出最后两个,或1个),若没有这1步,上面whlie的判断不成立。 } int ans8 = len << 3; double bi = (double)ans8 / ans; printf("%d %d %.1lf\n", ans8, ans, bi); } }


 

 

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生