0023算法筆記——【貪心算法】哈夫曼編碼問題

1、0023算法筆記一一【貪心算法】哈夫曼編碼問題1、問題描述哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0,1串表示各字符的最優(yōu)表示方式。 一個(gè)包含100,000個(gè)字符的文件，各字符出現(xiàn)頻率不同，如下表所示。a ab bC Cd de ef f頻率(千次)45451313121216169 95 5定 3000000001001010010anan: :100100101101變長碼0 0101101100100ininnainai11001100有多種方式表示文件中的信息，若用0,1碼表示字符的方法

2、，即每個(gè)字符用唯一的一個(gè)0,1串表示。若采用定長編碼表示，則需要3位表示一個(gè)字符，整個(gè)文件編碼需要300,000位；若采用變長編碼表示，給頻率高的字符較短的編碼；頻率低的字符較長的編碼，達(dá)到整體編碼減少的目的，則整個(gè)文件編碼需要(45X1+13X3+12X3+16X3+9X4+5X4)X1000=224,000位，由此可見，變長碼比定長碼方案好，總碼長減小約25%。前綴碼：對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡單；例如001011101可以唯一的分解為0,0,101,1101,因而其譯碼為aa

3、be。譯碼過程需要方便的取出編碼的前綴，因此需要表示前綴碼的合適的數(shù)據(jù)結(jié)構(gòu)。為此，可以用二叉樹作為前綴碼的數(shù)據(jù)結(jié)構(gòu)：樹葉表示給定字符；從樹根到樹葉的路徑當(dāng)作該字符的前綴碼；代碼中每一位的0或1分別作為指示某節(jié)點(diǎn)到左兒子或右兒子的路標(biāo)”。從上圖可以看出，表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹,即樹中任意節(jié)點(diǎn)都有2個(gè)兒子。 圖a表示定長編碼方案不是最優(yōu)的， 其編碼的二叉樹不是一棵完全二叉樹。在一般情況下，若C是編碼字符集,表示其最優(yōu)前綴碼的二叉樹中恰有|C|個(gè)葉子。每個(gè)葉子對(duì)應(yīng)于字符集中的一個(gè)字符，該二叉樹有|C|-1個(gè)內(nèi)部節(jié)點(diǎn)。給定編碼字符集C及頻率分布f,即C中任一字符c以頻率f(c)在數(shù)據(jù)

4、文件中出現(xiàn)。C的一個(gè)前綴碼編碼方案對(duì)應(yīng)于一棵二叉樹T。字符c在樹T中的深度記為dT(c)。dT(c)也是字符c的前綴碼長。則平均碼長定居義為：亡三C使平均碼長達(dá)到最小的前綴碼編碼方案稱為C的最優(yōu)前綴碼。2、構(gòu)造哈弗曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。其構(gòu)造步驟如下：(1)哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹To(2)算法以|C|個(gè)葉結(jié)點(diǎn)開始， 執(zhí)行|C|1次的合并”運(yùn)算后產(chǎn)生最終所要求的樹To(3)假設(shè)編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最

5、小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列Q。經(jīng)過n1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹To構(gòu)造過程如圖所示：具體代碼實(shí)現(xiàn)如下：(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;下標(biāo)從1開始33.BinaryTreet=HuffmanTree

7、(f,N);34.35.cout各字符出現(xiàn)的對(duì)應(yīng)頻率分別為：endl;36.for(inti=1;i=N;i+)37.38.coutci:fi;39.40.coutendl;41.42.cout生成二叉樹的前序遍歷結(jié)果為：endl;43.t.Pre_Order();44.coutendl;45.46.cout生成二叉樹的中序遍歷結(jié)果為：endl;47.t.In_Order();48.coutendl;49.50.t.DestroyTree();51.return0;52.53.54.template55.BinaryTreeHuffmanTree(Typef口，intn)56.57./生成單節(jié)

8、點(diǎn)樹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./建優(yōu)先隊(duì)列69.MinHeapHuffmanQ(n);70.for(inti=1;i=n;i+)Q.Insert(wi);71.72./反復(fù)合并最小頻率樹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二叉樹實(shí)現(xiàn)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所有結(jié)點(diǎn)的左右子樹交換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);/交換左子樹上所有結(jié)點(diǎn)的左右子樹192.Change(r-rChild);/交換右子樹上所有結(jié)點(diǎn)的左右子樹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最小堆實(shí)現(xiàn)cppviewplaincopy1.#include2.usingnamespacestd;3.template4.classMinHeap5.6.private:7.T*heap;/元素?cái)?shù)組，0號(hào)位置也儲(chǔ)存元素8.intCurrentSize;/目前元素個(gè)數(shù)9.intMaxSize;/可容納的最多元素個(gè)數(shù)10.11.voidFilterDown(constintstart,constintend);/自上往下調(diào)整，使關(guān)鍵字小的節(jié)點(diǎn)在上12.voidFilterUp(intstart);/自下往上調(diào)整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(鍵字小的節(jié)點(diǎn)在上intstart)/自下往上調(diào)整/i指向j的雙親節(jié)點(diǎn)constintsta

22、rt,constintend)/自上往下調(diào)整，使關(guān)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);/調(diào)整新的根節(jié)點(diǎn)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.