算法笔记贪心算法哈夫曼编码问题.docx
- 文档编号:3947610
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:17
- 大小:34.67KB
算法笔记贪心算法哈夫曼编码问题.docx
《算法笔记贪心算法哈夫曼编码问题.docx》由会员分享,可在线阅读,更多相关《算法笔记贪心算法哈夫曼编码问题.docx(17页珍藏版)》请在冰点文库上搜索。
算法笔记贪心算法哈夫曼编码问题
0023算法笔记——【贪心算法】哈夫曼编码问题
令狐采学
1、问题描述
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。
其压缩率通常在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%。
前缀码:
对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀。
这种编码称为前缀码。
编码的前缀性质可以使译码方法非常简单;例如001011101可以唯一的分解为0,0,101,1101,因而其译码为aabe。
译码过程需要方便的取出编码的前缀,因此需要表示前缀码的合适的数据结构。
为此,可以用二叉树作为前缀码的数据结构:
树叶表示给定字符;从树根到树叶的路径当作该字符的前缀码;代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。
从上图可以看出,表示最优前缀码的二叉树总是一棵完全二叉树,即树中任意节点都有2个儿子。
图a表示定长编码方案不是最优的,其编码的二叉树不是一棵完全二叉树。
在一般情况下,若C是编码字符集,表示其最优前缀码的二叉树中恰有|C|个叶子。
每个叶子对应于字符集中的一个字符,该二叉树有|C|-1个内部节点。
给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。
C的一个前缀码编码方案对应于一棵二叉树T。
字符c在树T中的深度记为dT(c)。
dT(c)也是字符c的前缀码长。
则平均码长定义为:
使平均码长达到最小的前缀码编码方案称为C的最优前缀码。
2、构造哈弗曼编码
哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码。
其构造步骤如下:
(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
(2)算法以|C|个叶结点开始,执行|C|-1次的“合并”运算后产生最终所要求的树T。
(3)假设编码字符集中每一字符c的频率是f(c)。
以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。
一旦2棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的2棵树的频率之和,并将新树插入优先队列Q。
经过n-1次的合并后,优先队列中只剩下一棵树,即所要求的树T。
构造过程如图所示:
具体代码实现如下:
(1)4d4.cpp,程序主文件
[cpp] viewplain copy
1.//4d4 贪心算法 哈夫曼算法
2.#include "stdafx.h"
3.#include "BinaryTree.h"
4.#include "MinHeap.h"
5.#include
6.using namespace std;
7.const int N = 6;
8.template
9.template
10.BinaryTree
11.template
12.class Huffman
13.{
14. friend BinaryTree
15. public:
16. operator Type() const
17. {
18. return weight;
19. }
20. //private:
21. BinaryTree
22. Type weight;
23.};
24.int main()
25.{
26. char c[] = {'0','a','b','c','d','e','f'};
27. int f[] = {0,45,13,12,16,9,5};//下标从1开始
28. BinaryTree
29. cout<<"各字符出现的对应频率分别为:
"< 30. for(int i=1; i<=N; i++) 31. { 32. cout< "< 33. } 34. cout< 35. cout<<"生成二叉树的前序遍历结果为: "< 36. t.Pre_Order(); 37. cout< 38. cout<<"生成二叉树的中序遍历结果为: "< 39. t.In_Order(); 40. cout< 41. t.DestroyTree(); 42. return 0; 43.} 44.template 45.BinaryTree 46.{ 47. //生成单节点树 48. Huffman 49. BinaryTree 50. for(int i=1; i<=n; i++) 51. { 52. z.MakeTree(i,zero,zero); 53. w[i].weight = f[i]; 54. w[i].tree = z; 55. } 56. //建优先队列 57. MinHeap 58. for(int i=1; i<=n; i++) Q.Insert(w[i]); 59. //反复合并最小频率树 60. Huffman 61. for(int i=1; i 62. { 63. x = Q.RemoveMin(); 64. y = Q.RemoveMin(); 65. z.MakeTree(0,x.tree,y.tree); 66. x.weight += y.weight; 67. x.tree = z; 68. Q.Insert(x); 69. } 70. x = Q.RemoveMin(); 71. delete[] w; 72. return x.tree; 73.} (2)BinaryTree.h二叉树实现 [cpp] viewplain copy 1.#include 2.using namespace std; 3.template 4.struct BTNode 5.{ 6. T data; 7. BTNode 8. BTNode() 9. { 10. lChild=rChild=NULL; 11. } 12. BTNode(const T &val,BTNode 13. { 14. data=val; 15. lChild=Childl; 16. rChild=Childr; 17. } 18. BTNode 19. { 20. BTNode 21. if(&data==NULL) 22. return NULL; 23. nl=lChild->CopyTree(); 24. nr=rChild->CopyTree(); 25. nn=new BTNode 26. return nn; 27. } 28.}; 29.template 30.class BinaryTree 31.{ 32. public: 33. BTNode 34. BinaryTree(); 35. ~BinaryTree(); 36. void Pre_Order(); 37. void In_Order(); 38. void Post_Order(); 39. int TreeHeight()const; 40. int TreeNodeCount()const; 41. void DestroyTree(); 42. void MakeTree(T pData,BinaryTree 43. void Change(BTNode 44. private: 45. void Destroy(BTNode 46. void PreOrder(BTNode 47. void InOrder(BTNode 48. void PostOrder(BTNode 49. int Height(const BTNode 50. int NodeCount(const BTNode 51.}; 52.template 53.BinaryTree : BinaryTree() 54.{ 55. root=NULL; 56.} 57.template 58.BinaryTree : ~BinaryTree() 59.{ 60.} 61.template 62.void BinaryTree : Pre_Order() 63.{ 64. PreOrder(root); 65.} 66.template 67.void BinaryTree : In_Order() 68.{ 69. InOrder(root); 70.} 71.template 72.void BinaryTree : Post_Order() 73.{ 74. PostOrder(root); 75.} 76.template 77.int BinaryTree : TreeHeight()const 78.{ 79. return Height(root); 80.} 81.template 82.int BinaryTree : TreeNodeCount()const 83.{ 84. return NodeCount(root); 85.} 86.template 87.void BinaryTree : DestroyTree() 88.{ 89. Destroy(root); 90.} 91.template 92.void BinaryTree : PreOrder(BTNode 93.{ 94. if(r! =NULL) 95. { 96. cout< 97. PreOrder(r->lChild); 98. PreOrder(r->rChild); 99. } 100.} 101.template 102.void BinaryTree : InOrder(BTNode 103.{ 104. if(r! =NULL) 105. { 106. InOrder(r->lChild); 107. cout< 108. InOrder(r->rChild); 109. } 110.} 111.template 112.void BinaryTree : PostOrder(BTNode 113.{ 114. if(r! =NULL) 115. { 116. PostOrder(r->lChild); 117. PostOrder(r->rChild); 118. cout< 119. } 120.} 121.template 122.int BinaryTree : NodeCount(const BTNode 123.{ 124. if(r==NULL) 125. return 0; 126. else 127. return 1+NodeCount(r->lChild)+NodeCount(r->rChild); 128.} 129.template 130.int BinaryTree : Height(const BTNode 131.{ 132. if(r==NULL) 133. return 0; 134. else 135. { 136. int lh,rh; 137. lh=Height(r->lChild); 138. rh=Height(r->rChild); 139. return 1+(lh>rh? lh: rh); 140. } 141.} 142.template 143.void BinaryTree : Destroy(BTNode 144.{ 145. if(r! =NULL) 146. { 147. Destroy(r->lChild); 148. Destroy(r->rChild); 149. delete r; 150. r=NULL; 151. } 152.} 153.template 154.void BinaryTree : Change(BTNode 155.{ 156. BTNode 157. if(r){ 158. p=r->lChild; 159. r->lChild=r->rChild; 160. r->rChild=p; //左右子女交换 161. Change(r->lChild); //交换左子树上所有结点的左右子树 162. Change(r->rChild); //交换右子树上所有结点的左右子树 163. } 164.} 165.template 166.void BinaryTree : MakeTree(T pData,BinaryTree 167.{ 168. root = new BTNode 169. root->data = pData; 170. root->lChild = leftTree.root; 171. root->rChild = rightTree.root; 172.} (3)MinHeap.h最小堆实现 [cpp] viewplain copy 1.#include 2.using namespace std; 3.template 4.class MinHeap 5.{ 6. private: 7. T *heap; //元素数组,0号位置也储存元素 8. int CurrentSize; //目前元素个数 9. int MaxSize; //可容纳的最多元素个数 10. void FilterDown(const int start,const int end); //自上往下调整,使关键字小的节点在上 11. void FilterUp(int start); //自下往上调整 12. public: 13. MinHeap(int n=1000); 14. ~MinHeap(); 15. bool Insert(const T &x); //插入元素 16. T RemoveMin(); //删除最小元素 17. T GetMin(); //取最小元素 18. bool IsEmpty() const; 19. bool IsFull() const; 20. void Clear(); 21.}; 22.template 23.MinHeap : MinHeap(int n) 24.{ 25. MaxSize=n; 26. heap=new T[MaxSize]; 27. CurrentSize=0; 28.} 29.template 30.MinHeap : ~MinHeap() 31.{ 32. delete []heap; 33.} 34.template 35.void MinHeap : FilterUp(int start) //自下往上调整 36.{ 37. int j=start,i=(j-1)/2; //i指向j的双亲节点 38. T temp=heap[j]; 39. while(j>0) 40. { 41. if(heap[i]<=temp) 42. break; 43. else 44. { 45. heap[j]=heap[i]; 46. j=i; 47. i=(i-1)/2; 48. } 49. } 50. heap[j]=temp; 51.} 52.template 53.void MinHeap : FilterDown(const int start,const int end) //自上往下调整,使关键字小的节点在上 54.{ 55. int i=start,j=2*i+1; 56. T temp=heap[i]; 57. while(j<=end) 58. { 59. if( (j 60. j++; 61. if(temp<=heap[j]) 62. break; 63. else 64. { 65. heap[i]=heap[j]; 66. i=j; 67. j=2*j+1; 68. } 69. } 70. heap[i]=temp; 71.} 72.template 73.bool MinHeap : Insert(const T &x) 74.{ 75. if(CurrentSize==MaxSize)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 笔记 贪心 哈夫曼 编码 问题