《0023算法笔记——【贪心算法】哈夫曼编码问题（9月11日）.pptx》由会员分享，可在线阅读，更多相关《0023算法笔记——【贪心算法】哈夫曼编码问题（9月11日）.pptx（16页珍藏版）》请在金锄头文库上搜索。
1、0023 算法笔记【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。 其压缩率通常在 20%90%之间。哈夫曼编码算法用字符在文件中出 现的频率表来建立一个用 0，1 串表示各字符的最优表示方式。一个包 含 100,000 个字符的文件，各字符出现频率不同，如下表所示。,有多种方式表示文件中的信息，若用 0,1 码表示字符的方法，即每 个字符用唯一的一个 0,1 串表示。若采用定长编码表示，则需要 3 位表 示一个字符，整个文件编码需要 300,000 位；若采用变长编码表示，给 频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的
2、目的，则整 个文件编码需要（451+133+123+163+94+54） 1000=224,000 位，由此可见，变长码比定长码方案好，总码长减小 约 25%。 前缀码：对每一个字符规定一个 0,1 串作为其代码，并要求任一字 符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的 前缀性质可以使译码方法非常简单；例如 001011101 可以唯一的分解 为 0,0,101,1101，因而其译码为 aabe。,1,译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合 适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表 示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中
3、每一 位的 0 或 1 分别作为指示某节点到左儿子或右儿子的“路标”。,从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉 树，即树中任意节点都有 2 个儿子。图 a 表示定长编码方案不是最优 的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若 C 是编 码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对 应于字符集中的一个字符，该二叉树有|C|-1 个内部节点。 给定编码字符集 C 及频率分布 f,即C 中任一字符 c 以频率f(c)在 数据文件中出现。C 的一个前缀码编码方案对应于一棵二叉树 T。字 符 c 在树T 中的深度记为 dT(c)。dT(c)也是字符 c 的
4、前缀码长。则平均,2,码长定义为：,使平均码长达到最小的前缀码编码方,案称为 C 的最优前缀码。 2、构造哈弗曼编码 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称 为哈夫曼编码。其构造步骤如下： 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T。 算法以|C|个叶结点开始，执行|C|1 次的“合并”运算后产生最 终所要求的树 T。 假设编码字符集中每一字符 c 的频率是 f(c)。以 f 为键值的优先 队列 Q 用在贪心选择时有效地确定算法当前要合并的 2 棵具有最小频 率的树。一旦 2 棵具有最小频率的树合并后，产生一棵新的树，其频 率为合并的 2 棵树的频率之和，并将新
5、树插入优先队列 Q。经过n1 次的合并后，优先队列中只剩下一棵树，即所要求的树 T。 构造过程如图所示：,3,具体代码实现如下： (1)4d4.cpp，程序主文件,cpp view plain copy,1. /4d4 贪心算法 哈夫曼算法,2. #include stdafx.h,3. #include BinaryTree.h,4. #include MinHeap.h,5. #include ,6. using namespace std;,7.,8. const int N = 6;,9.,10. template class Huffman;,11.,12. template,13.
6、 BinaryTree HuffmanTree(Type f,int n);,14.,15. template,16. class Huffman,17. ,18.friend BinaryTree HuffmanTree(Type,int);,19.public:,20.operator Type() const,21.,4,5,22.return weight;,23.,24./private:,25.BinaryTree tree;,26.Type weight;,27. ;,28.,29. int main(),30. ,31.char c = 0,a,b,c,d,e,f;,32.in
7、t f = 0,45,13,12,16,9,5;/下标从 1 开始,33.BinaryTree t = HuffmanTree(f,N);,34.,35.cout各字符出现的对应频率分别为：endl;,36.for(int i=1; i=N; i+),37.,38.coutci:fi ;,39.,40.coutendl;,41.,42.cout生成二叉树的前序遍历结果为：endl;,43.t.Pre_Order();,44.coutendl;,45.,46.cout生成二叉树的中序遍历结果为：endl;,47.t.In_Order();,48.coutendl;,49.,50.t.Destro
8、yTree();,51.return 0;,52. ,53.,54. template,55. BinaryTree HuffmanTree(Type f,int n),56. ,57./生成单节点树,58.Huffman *w = new Huffmann+1;,59.BinaryTree z,zero;,60.,61.for(int i=1; i=n; i+),62.,63.z.MakeTree(i,zero,zero);,64.wi.weight = fi;,65.wi.tree = z;,6,66.,67.,68./建优先队列,69.MinHeap Q(n);,70.for(int i
9、=1; i=n; i+) Q.Insert(wi);,71.,72./反复合并最小频率树,73.Huffman x,y;,74.for(int i=1; in; i+),75.,76.x = Q.RemoveMin();,77.y = Q.RemoveMin();,78.z.MakeTree(0,x.tree,y.tree);,79.x.weight += y.weight;,80.x.tree = z;,81.Q.Insert(x);,82.,83.,84.x = Q.RemoveMin();,85.,86.delete w;,87.,88.return x.tree;,89. (2)Bin
10、aryTree.h 二叉树实现,cpp view plain copy,1. #include,2. using namespace std;,3.,4. template,5. struct BTNode,6. ,7.T data;,8.BTNode *lChild,*rChild;,9.,10.BTNode(),11.,12.lChild=rChild=NULL;,13.,14.,15.BTNode(const T ,7,18.lChild=Childl;,19.rChild=Childr;,20.,21.,22.BTNode* CopyTree(),23.,24.BTNode *nl,*
11、nr,*nn;,25.,26.if(,28.,29.nl=lChild-CopyTree();,30.nr=rChild-CopyTree();,31.,32.nn=new BTNode(data,nl,nr);,33.return nn;,34.,35. ;,36.,37.,38. template,39. class BinaryTree,8,61.void PostOrder(BTNode *r);,62.,63.int Height(const BTNode *r)const;,64.int NodeCount(const BTNode *r)const;,65. ;,66.,67.
12、template,68. BinaryTree:BinaryTree(),69. ,70.root=NULL;,71. ,72.,73. template,74. BinaryTree:BinaryTree(),75. ,76.,77. ,78.,79. template,80. void BinaryTree:Pre_Order(),81. ,82.PreOrder(root);,83. ,84.,85. template,86. void BinaryTree:In_Order(),87. ,88.InOrder(root);,89. ,90.,91. template,92. void
13、BinaryTree:Post_Order(),93. ,94.PostOrder(root);,95. ,96.,97. template,98. int BinaryTree:TreeHeight()const,99. ,100.return Height(root);,101. ,102.,103. template,104. int BinaryTree:TreeNodeCount()const,9,105. ,106.return NodeCount(root);,107. ,108.,109. template,110. void BinaryTree:DestroyTree(),
14、111. ,112.Destroy(root);,113. ,114.,115. template,116. void BinaryTree:PreOrder(BTNode *r),117. ,118.if(r!=NULL),119.,120.coutdata ;,121.PreOrder(r-lChild);,122.PreOrder(r-rChild);,123.,124. ,125.,126. template,127. void BinaryTree:InOrder(BTNode *r),128. ,129.if(r!=NULL),130.,131.InOrder(r-lChild);
15、,132.coutdata ;,133.InOrder(r-rChild);,134.,135. ,136.,137. template,138. void BinaryTree:PostOrder(BTNode *r),139. ,140.if(r!=NULL),141.,142.PostOrder(r-lChild);,143.PostOrder(r-rChild);,144.coutdata ;,145.,146. ,147.,148. template,10,149. int BinaryTree:NodeCount(const BTNode *r)const,150. ,151.if
16、(r=NULL),152.return 0;,153.else,154.return 1+NodeCount(r-lChild)+NodeCount(r-rChild);,155. ,156.,157. template,158. int BinaryTree:Height(const BTNode *r)const,159. ,160.if(r=NULL),161.return 0;,162.else,163.,164.int lh,rh;,165.lh=Height(r-lChild);,166.rh=Height(r-rChild);,167.return 1+(lhrh?lh:rh);,168.,169. ,170.,171. template,172. void BinaryTree:Destroy(BTNode *,177.Destroy(r-rChild);,178.delete r;,179.r=NULL;,180.,181. ,182.,
