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

1、0023算法笔记一一【贪心算法】哈夫曼编码问题1、问题描述哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。 一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。a ab bC Cd de ef f频率(千次)45451313121216169 95 5定 3000000001001010010anan: :100100101101变长码0 0101101100100ininnainai11001100有多种方式表示文件中的信息，若用0,1码表示字符的方法

2、，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要(45X1+13X3+12X3+16X3+9X4+5X4)X1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101,因而其译码为aa

3、be。译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的路标”。从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树,即树中任意节点都有2个儿子。 图a表示定长编码方案不是最优的， 其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集,表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据

4、文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)。dT(c)也是字符c的前缀码长。则平均码长定居义为：亡三C使平均码长达到最小的前缀码编码方案称为C的最优前缀码。2、构造哈弗曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下：(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树To(2)算法以|C|个叶结点开始， 执行|C|1次的合并”运算后产生最终所要求的树To(3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最

5、小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树To构造过程如图所示：具体代码实现如下：(1)4d4.cpp,程序主文件cppviewplaincopy1./4d4贪心算法哈夫曼算法2.#includestdafx.h3.#includeBinaryTree.h4.#includeMinHeap.h5.#include6.usingnamespacestd;7.8.constintN=6;9.10.templateclassHuffman;11.12.template13.BinaryTreeHu

6、ffmanTree(Typef,intn);14.15.template16.classHuffman17.18.friendBinaryTreeHuffmanTree(Type,19.public:20.operatorType()const21.史52:3int);returnweight;23.24./private:25.BinaryTreetree;26.Typeweight;27.;28.29.intmain()30.31.charc口=0,a,b,c,d,e，甲;32.intf口=0,45,13,12,16,9,5;下标从1开始33.BinaryTreet=HuffmanTree

7、(f,N);34.35.cout各字符出现的对应频率分别为：endl;36.for(inti=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.DestroyTree();51.return0;52.53.54.template55.BinaryTreeHuffmanTree(Typef口，intn)56.57./生成单节

8、点树58.Huffman*w=newHuffmann+1;59.BinaryTreez,zero;60.61.for(inti=1;i=n;i+)62.63.z.MakeTree(i,zero,zero);64.wi.weight=fi;65.wi.tree=z;22.17.data=val;66.67.68./建优先队列69.MinHeapHuffmanQ(n);70.for(inti=1;i=n;i+)Q.Insert(wi);71.72./反复合并最小频率树73.Huffmanx,y;74.for(inti=1;in;i+)75.76.x=Q.RemoveMin();77.y=Q.Rem

9、oveMin();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.deletew;87.88.returnx.tree;89.(2)BinaryTree.h二叉树实现cppviewplaincopy1.#include2.usingnamespacestd;3.4.template5.structBTNode6.7.Tdata;8.BTNode*lChild,*rChild;9.10.BTNode()11.12.lChil

10、d=rChild=NULL;13.14.15.BTNode(constT&val,BTNode*Childl=NULL,BTNode*Childr=NULL)16.18.lChild=Childl;19.rChild=Childr;20.21.22.BTNode*CopyTree()23.24.BTNode*nl,*nr,*nn;25.26.if(&data=NULL)27.returnNULL;28.29.nl=lChild-CopyTree();30.nr=rChild-CopyTree();31.32.nn=newBTNode(data,nl,nr);33.returnn

11、n;34.35.;36.37.38.template39.classBinaryTree40.41.public:42.BTNode*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,BinaryTreeleftTree,BinaryTreerightT

12、ree);voidChange(BTNode*r);56.57.private58.voidDestroy(BTNode*&r);59.voidPreOrder(BTNode*r);60.voidInOrder(BTNode*r);voidPostOrder(BTNode*r);62.63.intHeight(constBTNode*r)const;64.intNodeCount(constBTNode*r)const65.;66.67.template68.BinaryTree:BinaryTree()69.70.root=NULL;71.72.73.template74.Binar

13、yTree:BinaryTree()8.79.template80.voidBinaryTree:Pre_Order()81.82.PreOrder(root);83.84.85.template86.voidBinaryTree:In_Order()87.88.InOrder(root);89.90.91.template92.voidBinaryTree:Post_Order()93.94.PostOrder(root);95.96.97.BinaryTree:TreeHeight()const99.100.returnHeight(root

14、);101.102.103.BinaryTree:TreeNodeCount()const61.105.106.returnNodeCount(root);107.108.109.template110.voidBinaryTree:DestroyTree()111.112.Destroy(root);113.114.115.template116.voidBinaryTree:PreOrder(BTNode*r)117.118.if(r!=NULL)119.120.coutdatalChild);122.PreOrder(r-rChild);123.124.12

15、5.126.template127.voidBinaryTree:InOrder(BTNode*r)128.129.if(r!=NULL)130.131.InOrder(r-lChild);132.coutdatarChild);37.template138.voidBinaryTree:PostOrder(BTNode*r)139.140.if(r!=NULL)141.142.PostOrder(r-lChild);143.PostOrder(r-rChild);144.coutdata;48.BinaryTr

16、ee:NodeCount(constBTNode*r)const150.151.if(r=NULL)152.return0;153.else154.return1+NodeCount(r-lChild)+NodeCount(r-rChild);155.156.157.BinaryTree:Height(constBTNode*r)const159.160.if(r=NULL)161.return0;162.lh,rh;165.lh=Height(r-lChild);166.rh=Height(r-rChild);167.return1

17、+(lhrh?lh:rh);71.template172.voidBinaryTree:Destroy(BTNode*&r)173.174.if(r!=NULL)175.176.Destroy(r-lChild);177.Destroy(r-rChild);178.deleter;179.r=NULL;83.template184.voidBinaryTree:Change(BTNode*r)/将二叉树bt所有结点的左右子树交换185.186.BTNode*p;187.if(r)188.p=r-lChild;189.r-lChild=

18、r-rChild;190.r-rChild=p;/左右子女交换191.Change(r-lChild);/交换左子树上所有结点的左右子树192.Change(r-rChild);/交换右子树上所有结点的左右子树96.template197. voidBinaryTree:MakeTree(TpData,BinaryTreeleftTree,BinaryTreerightTree)198.199.root=newBTNode();200.root-data=pData;201.root-lChild=leftTree.root;202.root-rChild=right

19、Tree.root;203.(3)MinHeap.h最小堆实现cppviewplaincopy1.#include2.usingnamespacestd;3.template4.classMinHeap5.6.private:7.T*heap;/元素数组，0号位置也储存元素8.intCurrentSize;/目前元素个数9.intMaxSize;/可容纳的最多元素个数10.11.voidFilterDown(constintstart,constintend);/自上往下调整，使关键字小的节点在上12.voidFilterUp(intstart);/自下往上调整13.14.public:15.

20、MinHeap(intn=1000);16.MinHeap();17.boolInsert(constT&x);/插入元素18.19.TRemoveMin();/删除最小元素20.TGetMin();/取最小元素21.22.boolIsEmpty()const;23.boolIsFull()const;24.voidClear();25.;26.27.template28.MinHeap:MinHeap(intn)29.30.MaxSize=n;31.heap=newTMaxSize;32.CurrentSize=0;33.34.35.template36.MinHeap:MinHea

21、p()37.38.deleteheap;39.40.41.template42.voidMinHeap:FilterUp(43.44.intj=start,i=(j-1)/2;45.Ttemp=heapj;46.47.while(j0)48.49.if(heapi=temp)50.break;51.else52.53.heapj=heapi;54.j=i;55.i=(i-1)/2;56.57.58.heapj=temp;59.60.61.template62.voidMinHeap:FilterDown(键字小的节点在上intstart)/自下往上调整/i指向j的双亲节点constintsta

22、rt,constintend)/自上往下调整，使关63.64.inti=start,j=2*i+1;65.Ttemp=heapi;66.while(j=end)67.68.if(jheapj+1)69.j+;70.if(temp=heapj)break;71.else73.(74.heapi=heapj;75.i=j；76.j=2*j+1;77.78.79.heapi=temp;80.81.82.template83.boolMinHeap:Insert(constT&x)84.85.if(CurrentSize=MaxSize)86.returnfalse;87.88.heapCur

23、rentSize=x;89.FilterUp(CurrentSize);90.91.CurrentSize+;92.returntrue;93.94.95.template96.TMinHeap:RemoveMin()97.98.Tx=heap0;99.heap0=heapCurrentSize-1;100.101.CurrentSize-;102.FilterDown(0,CurrentSize-1);/调整新的根节点103.104.returnx;105.106.107.template108.TMinHeap:GetMin()109.110.returnheap0;111.112.113.template114.boolMinHeap:IsEmpty()const115.72.叶子b和x的位置得到T,然后再树T中交换叶子c和树T”。如图所示：Tr工言/、一EZJm口U由此可知，树T和T的前缀码的平均码长之差为：y的位置，得到117.118.119.template120.boolMinHeap:IsFull()const121.122.returnCurrentSize=MaxSize;123.124.125.template126.