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

1、0023算法筆記一一【貪心算法】哈夫曼編碼問題1、問題描述哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼 算法用字符在文件中出現(xiàn)的 頻率表來建立一個用0, 1串表示各字符的最優(yōu)表示方式。一個包含 100,000個字符的文件，各字符出現(xiàn)頻率不同，如下表所示。abCdef頻率(千次)4513121695定長碼000001010Oil100101變長碼010110011111011100有多種方式表示文件中的信息，若用 0,1碼表示字符的方法，即每 個字符用唯一的一個0,1串表示。若采用定長編碼表示，則需要3位表示 一個字符，整個文件編碼需要 30

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

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

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

5、新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列 Q。經(jīng)過n1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹To構(gòu)造過程如圖所示：3 / 16f * 工3具體代碼實現(xiàn)如下:(1)4d4.cpp ,程序主文件cpp view plain copy/4d4貪心算法哈夫曼算法#include stdafx.h#include BinaryTree.h#include MinHeap.h#include usingnamespace std 。constint N = 6 。template class Huffman 。template BinaryTree HuffmanTree(T

6、ype f, int n)template class Huffmanint )friend BinaryTree HuffmanTree(Type,int )public :operator Type()const4 / 16return weight 。/private:BinaryTree tree 。Type weight。 oint main()char c口 = 0 , a ,b ,c ,d , e，甲。int f口 = 0,45,13,12,16,9,5。 / 下標(biāo)從 1 開始BinaryTree t = HuffmanTree(f,N) 。cout各字符出現(xiàn)的對應(yīng)頻率分別為：e

7、ndl。for ( int i=1 。 i=N 。 i+) TOC o 1-5 h z coutci: fi。coutendl。cout生成二叉樹的前序遍歷結(jié)果為：endl。t.Pre_Order() 。coutendl 。cout生成二叉樹的中序遍歷結(jié)果為：endl。t.In_Order() 。coutendl 。t.DestroyTree() 。return 0。template BinaryTree HuffmanTree(Type f口，int n)/生成單節(jié)點(diǎn)樹Huffman *w = new Huffmann+1 。BinaryTree z,zero 。for ( int i=1

8、。 i=n 。 i+) TOC o 1-5 h z z.MakeTree(i,zero,zero)。wi.weight = fi。wi.tree = z。5 / 16/建優(yōu)先隊列MinHeapHuffman Q(n) 。for ( int i=1 。 i=n 。 i+) Q.Insert(wi)/反復(fù)合并最小頻率樹 TOC o 1-5 h z Huffman x,y。for ( int i=1 。 in 。 i+)x = Q.RemoveMin()。y = Q.RemoveMin()。z.MakeTree(0,x.tree,y.tree)。x.weight += y.weight。x.tree

9、 = z。Q.Insert(x)。x = Q.RemoveMin() 。delete w 。returnx.tree。(2)BinaryTree.h 二叉樹實現(xiàn)cpp view plain copy#includeusing namespace std 。template struct BTNode TOC o 1-5 h z T data。BTNode *lChild,*rChild。BTNode()lChild=rChild=NULL。BTNode( const T &val,BTNode *Childl=NULL,BTNode *Childr=NULL) HYPERLINK l book

10、mark6 o Current Document 17.data=val17.data=val6 / 16 TOC o 1-5 h z lChild=Childl。rChild=Childr。BTNode* CopyTree()BTNode *nl,*nr,*nn。if (&data=NULL)return NULL。 TOC o 1-5 h z nl=lChild-CopyTree()。nr=rChild-CopyTree()。nn= new BTNode(data,nl,nr) 。return nn 。 otemplate class BinaryTreepublic :BTNode *r

11、oot 。 TOC o 1-5 h z BinaryTree()。BinaryTree()。void Pre_Order()。void In_Order() 。void Post_Order() 。int TreeHeight() const 。int TreeNodeCount() const 。void DestroyTree() 。void MakeTree(T pData,BinaryTree leftTree,BinaryTree rightTree)55.voidChange(BTNode *r)56.57.private :58.voidDestroy(BTNode *&r)59

12、.voidPreOrder(BTNode *r)60.voidInOrder(BTNode *r)7 / 16void PostOrder(BTNode *r)。int Height( const BTNode *r) const 。int NodeCount( const BTNode *r) const otemplate BinaryTree:BinaryTree()root=NULL 。template BinaryTree:BinaryTree()template void BinaryTree:Pre_Order()PreOrder(root) 。template void Bin

13、aryTree:In_Order()InOrder(root) 。template void BinaryTree:Post_Order()PostOrder(root) 。template int BinaryTree:TreeHeight() constreturn Height(root) 。template int BinaryTree:TreeNodeCount() const8 / 16return NodeCount(root) 。template void BinaryTree:DestroyTree()Destroy(root) 。template void BinaryTr

14、ee:PreOrder(BTNode *r)if (r!=NULL) TOC o 1-5 h z coutdatalChild)。PreOrder(r-rChild)。template void BinaryTree:InOrder(BTNode *r)if (r!=NULL) TOC o 1-5 h z InOrder(r-lChild)。coutdatarChild)。template void BinaryTree:PostOrder(BTNode *r)if (r!=NULL) TOC o 1-5 h z PostOrder(r-lChild)。PostOrder(r-rChild)。

15、coutdata。template 9 / 16int BinaryTree:NodeCount(const BTNode *r) constconst BTNode *r) constif (r=NULL)return 0 。elsereturn 1+NodeCount(r-lChild)+NodeCount(r-rChild) template int BinaryTree:Height( const BTNode *r) const if (r=NULL)return 0 。 elseint lh,rh 。lh=Height(r-lChild)。rh=Height(r-rChild)。r

16、eturn 1+(lhrh?lh:rh) 。 template void BinaryTree:Destroy(BTNode *&r)if (r!=NULL)Destroy(r-lChild)。Destroy(r-rChild)。delete r 。r=NULL otemplate void BinaryTree:Change(BTNode *r)/ 將二叉樹 bt 所有結(jié)點(diǎn)的左右子樹交換BTNode *p 。 if (r) p=r-lChild。r-lChild=r-rChild。r-rChild=p。 /左右子女交換Change(r-lChild)。/交換左子樹上所有結(jié)點(diǎn)的左右子樹Chan

17、ge(r-rChild)。/交換右子樹上所有結(jié)點(diǎn)的左右子樹10 / 16template void BinaryTree:MakeTree(T pData,BinaryTree leftTree,BinaryTree r ightTree)root = new BTNode()。root-data = pData 。root-lChild = leftTree.root。root-rChild = rightTree.root。(3)MinHeap.h 最小堆實現(xiàn)cpp view plain copy1.#include 2.using namespace std 。3.template 4.

18、class MinHeap5.6.private7.T *heap/元素數(shù)組，0號位置也儲存元素8.intCurrentSMaxSize/目前元素個數(shù)可容納的最多元素個數(shù)10.11.void FilterDown(字小的節(jié)點(diǎn)在上const intstart, const int end) 。 /自上往下調(diào)整，使關(guān)鍵12.void FilterUp(int start)/自下往上調(diào)整13.14.public :15.MinHeap(intn=1000) o16.MinHeap()17.bool Insert(const T &x)。/插入元素18.19.T RemoveMin()

19、/刪除最小元素20.T GetMin()/取最小元素21.22.1.#include 2.using namespace std 。3.template 4.class MinHeap5.6.private7.T *heap/元素數(shù)組，0號位置也儲存元素8.intCurrentSMaxSize/目前元素個數(shù)可容納的最多元素個數(shù)10.11.void FilterDown(字小的節(jié)點(diǎn)在上const intstart, const int end) 。 /自上往下調(diào)整，使關(guān)鍵12.void FilterUp(int start)/自下往上調(diào)整13.14.public :15.MinH

20、eap(intn=1000) o16.MinHeap()17.bool Insert(const T &x)。/插入元素18.19.T RemoveMin()/刪除最小元素20.T GetMin()/取最小元素21.22.boolIsEmpty()const 。23.boolIsFull()const 。24.voidClear()25.26.27.template 28.MinHeap:MinHeap(int n)11 / 16MaxSize=n 。heap= new TMaxSize。CurrentSize=0 。template MinHeap:MinHeap()delete heap

21、。template void MinHeap:FilterUp( int start) / 自下往上調(diào)整int j=start,i=(j-1)/2。 /i 指向 j 的雙親節(jié)點(diǎn)T temp=heapj 。while (j0) TOC o 1-5 h z if (heapi=temp)break 。elseheapj=heapi。j=i。i=(i-1)/2oheapj=temp。template void MinHeap:FilterDown( const int start, const int end) / 自上往下調(diào)整，使關(guān) 鍵字小的節(jié)點(diǎn)在上 TOC o 1-5 h z int i=sta

22、rt,j=2*i+1。T temp=heapi。while (j=end)if ( (jheapj+1)j+oif (temp=heapj)break 。12 / 1672.else72. TOC o 1-5 h z (heapi=heapj。i=joj=2*j+1o)heapi=temp。template bool MinHeap:Insert( const T &x)if (CurrentSize=MaxSize)return false 。heapCurrentSize=x 。FilterUp(CurrentSize)。CurrentSize+ 。return true 。template T MinHeap:RemoveMin()T x=heap0 。heap0=heapCurrentSize-1。CurrentSize- 。FilterDown(0,CurrentSize-1)。return x 。template T MinHeap:GetMin()return heap0。template bool MinHeap:IsEmpty() const/調(diào)整新的