0023算法笔记——【贪心算法】哈夫曼编码问题

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]viewplaincopy1.//4d4贪心算法哈夫曼算法2.#includestdafx.h3.#includeBinaryTree.h4.#includeMinHeap.h5.#includeiostream6.usingnamespacestd;7.8.constintN=6;9.10.templateclassTypeclassHuffman;11.12.templateclassType13.BinaryTreeintHuffmanTree(Typef[],intn);14.15.templateclassType16.classHuffman17.{18.friendBinaryTreeintHuffmanTree(Type[],int);19.public:20.operatorType()const21.{22.returnweight;23.}24.//private:25.BinaryTreeinttree;26.Typeweight;27.};28.29.intmain()30.{31.charc[]={'0','a','b','c','d','e','f'};32.intf[]={0,45,13,12,16,9,5};//下标从1开始33.BinaryTreeintt=HuffmanTree(f,N);34.35.cout各字符出现的对应频率分别为：endl;36.for(inti=1;i=N;i++)37.{38.coutc[i]:f[i];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.DestroyTree();51.return0;52.}53.54.templateclassType55.BinaryTreeintHuffmanTree(Typef[],intn)56.{57.//生成单节点树58.HuffmanType*w=newHuffmanType[n+1];59.BinaryTreeintz,zero;60.61.for(inti=1;i=n;i++)62.{63.z.MakeTree(i,zero,zero);64.w[i].weight=f[i];65.w[i].tree=z;66.}67.68.//建优先队列69.MinHeapHuffmanTypeQ(n);70.for(inti=1;i=n;i++)Q.Insert(w[i]);71.72.//反复合并最小频率树73.HuffmanTypex,y;74.for(inti=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.returnx.tree;89.}(2)BinaryTree.h二叉树实现[cpp]viewplaincopy1.#includeiostream2.usingnamespacestd;3.4.templateclassT5.structBTNode6.{7.Tdata;8.BTNodeT*lChild,*rChild;9.10.BTNode()11.{12.lChild=rChild=NULL;13.}14.15.BTNode(constT&val,BTNodeT*Childl=NULL,BTNodeT*Childr=NULL)16.{17.data=val;18.lChild=Childl;19.rChild=Childr;20.}21.22.BTNodeT*CopyTree()23.{24.BTNodeT*nl,*nr,*nn;25.26.if(&data==NULL)27.returnNULL;28.29.nl=lChild-CopyTree();30.nr=rChild-CopyTree();31.32.nn=newBTNodeT(data,nl,nr);33.returnnn;34.}35.};36.37.38.templateclassT39.classBinaryTree40.{41.public:42.BTNodeT*root;43.BinaryTree();44.~BinaryTree();45.46.voidPre_Order();47.voidIn_Order();48.voidPost_Order();49.50.intTreeHeight()const;51.intTreeNodeCount()const;52.53.voidDestroyTree();54.voidMakeTree(TpData,BinaryTreeTleftTree,BinaryTreeTrightTree);55.voidChange(BTNodeT*r);56.57.private:58.voidDestroy(BTNodeT*&r);59.voidPreOrder(BTNodeT*r);60.voidInOrder(BTNodeT*r);61.voidPostOrder(BTNodeT*r);62.63.intHeight(constBTNodeT*r)const;64.intNodeCount(constBTNodeT*r)const;65.};66.67.templateclassT68.BinaryTreeT::BinaryTree()69.{70.root=NULL;71.}72.73.templateclassT74.BinaryTreeT::~BinaryTree()75.{76.77.}78.79.templateclassT80.voidBinaryTreeT::Pre_Order()81.{82.PreOrder(root);83.}84.85.templateclassT86.voidBinaryTreeT::In_Order()87.{88.InOrder(root);89.}90.91.templateclassT92.voidBinaryTreeT::Post_Order()93.{94.PostOrder(root);95.}96.97.templateclassT98.intBinaryTreeT::TreeHeight()const99.{100.returnHeight(root);101.}102.103.templateclassT104.intBinaryTreeT::TreeNodeCount()const105.{106.returnNodeCount(root);107.}108.109.templateclassT110.voidBinaryTreeT::DestroyTree()111.{112.Destroy(root);113.}114.115.templateclassT116.voidBinaryTreeT::PreOrder(BTNodeT*r)117.{118.if(r!=NULL)119.{120.coutr-data'';121.PreOrder(r-lChild);122.PreOrder(r-rChild);123.}124.}125.126.templateclassT127.voidBinaryTreeT::InOrder(BTNodeT*r)128.{129.if(r!=NULL)130.{131.InOrder(r-lChild);132.coutr-data'';133.InOrder(r-rChild);134.}135.}136.137.templateclassT138.voidBinaryTreeT::PostOrder(BTNodeT*r)139.{140.if(r!=NULL)141.{142.PostOrder(r-lChild);143.PostOrder(r-rChild);144.coutr-data'';145.}146.}147.148.templateclassT149.intBinaryTreeT::NodeCount(constBTNodeT*r)const150.{151.if(r==NULL)152.return0;153.else154.return1+NodeCo