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

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

2、碼需要 300,000位；假設采用變長編碼表示,給頻 率高的字符較短的編碼；頻率低的字符較長的編碼,到達整體編碼減少的目的,那么整個文件編碼需要(45X1 + 13X3+12X3+16X 3+9X4+5X4) X 1000=224,000 位,由此可見,變長碼比定長碼方案好,總碼長減小約25%前綴碼：對每一個字符規(guī)定一個0,1串作為其代碼,并要求任 一字符的代碼都不是其他字符代碼的前綴.這種編碼稱為前綴碼.編碼的前綴性質可以使譯碼方法非常簡單；例如001011101可以唯一的分解為0,0,101,1101 ,因而其譯碼為 aabe.文檔大全實用標準文案譯碼過程需要方便的取出編碼的前綴,因此需要

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

4、于一棵二叉樹T.字 符c在樹T中的深度記為dT(c) o dT(c)也是字符c的前綴碼長.那么平均碼文檔大全實用標準文案笈(丁)江/(叫(.)長定義為：亡三口使平均碼長到達最小的前綴碼編碼方案稱為C的最優(yōu)前綴碼.2、構造哈弗曼編碼哈夫曼提出構造最優(yōu)前綴碼的貪心算法,由此產(chǎn)生的編碼方案稱為哈夫曼編碼.其構造步驟如下：(1)哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹To(2)算法以|C|個葉結點開始,執(zhí)行|C| 1次的“合并運算后 產(chǎn)生最終所要求的樹To(3)假設編碼字符集中每一字符 c的頻率是f(c).以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹.

5、一旦2棵具有最小頻率的樹合并后,產(chǎn)生一棵新的樹,其 頻率為合并的2棵樹的頻率之和,并將新樹插入優(yōu)先隊列 Q經(jīng)過n-1 次的合并后,優(yōu)先隊列中只剩下一棵樹,即所要求的樹 To構造過程如下圖：文檔大全實用標準文案f * 工3具體代碼實現(xiàn)如下:4d4.cpp ,程序主文件1.4d4貪心算法哈夫曼算法..3.#include "stdafx.h"#include "BinaryTree.h"#include "MinHeap.h"#include <iostream> using n

6、amespace std;const int N = 6;template <class Type> class Huffman;template <class Type>BinaryTree< int > HuffmanTree(Type f, int n);0.21.template class<classHuffmanfriendpublic :Type>BinaryTree< int > HuffmanTree(Type,operator Type() constcpp view plai

7、n copyint );文檔大全實用標準文案22. .23. .3.64.65.return weight; ) /private:BinaryTree< int > tree; Type weight;);int main() charc口= '0' , 'a' , 'b' , 'c'

8、 ,'d' , 'e' , 'f' );int f= 0,45,13,12,16,9,5);/ 下標從 1 開始BinaryTree< int > t = HuffmanTree(f,N);cout<<"各字符出現(xiàn)的對應頻率分別為："<<endl;for (int i=1;i<=N;i+)cout<<ci<< ":" <<fi<< "") cout<<endl;cout<<&

9、quot;生成二叉樹的前序遍歷結果為："<<endl;t.Pre_Order();cout<<endl;cout<<"生成二叉樹的中序遍歷結果為："<<endl;t.In_Order(); cout<<endl;t.DestroyTree();return)0;template <classType>BinaryTree< int >HuffmanTree(Type f, int n)/生成單節(jié)點樹Huffman<Type> *w = new Huffman<Ty

10、pe>n+1; BinaryTree< int > z,zero;for (int i=1;i<=n;i+)z.MakeTree(i,zero,zero); wi.weight = fi; wi.tree = z;文檔大全實用標準文案7.88.89. )/建優(yōu)先隊列MinHeap<Huffman<Type>> Q(n);for (int i=1;i<=n;i+) Q.Insert(wi);/反復合并最小頻率樹Huf

11、fman<Type> x,y;for (int i=1; i<n; i+)x = Q.RemoveMin();y = Q.RemoveMin();z.MakeTree(0,x.tree,y.tree);x.weight += y.weight;x.tree = z;Q.Insert(x);x = Q.RemoveMin();delete w;return x.tree;(2)BinaryTree.h 二叉樹實現(xiàn)cpp view plain copy1. #include<iostream>2. using namespace std;3.4. template&l

12、t;classT>5. structBTNode6. 7. T data;8. BTNode<T> *lChild,*rChild;9.10. BTNode()11. 12. lChild=rChild=NULL;13. 14.15. BTNode(constT &val,BTNode<T> *Childl=NULL,BTNode<T>*Childr=NULL)16. 17. data=val;文檔大全實用標準文案18.lChild=Childl;19.rChild=Childr;20.21.22.BTNode<T>* CopyTr

13、ee()23.24.BTNode<T> *nl,*nr,*nn;25.26.if (&data=NULL)27.return NULL;28.29.nl=lChild->CopyTree();30.nr=rChild->CopyTree();31.32.nn=new BTNode<T>(data,nl,nr);33.return nn;34.35. ;36.37.38. template <classT>39. class BinaryTree40. 41.public :42.BTNode<T> *root;43.Binar

14、yTree();44.BinaryTree();45.46.void Pre_Order();47.void In_Order();48.void Post_Order();49.50.int TreeHeight() const ;51.int TreeNodeCount() const ;52.53.void DestroyTree();54.void MakeTree(T pData,BinaryTree<T>Tree);55.void Change(BTNode<T> *r);56.57.private :58.void Destroy(BTNode<T&

15、gt; *&r);59.void PreOrder(BTNode<T> *r);60.void InOrder(BTNode<T> *r);leftTree,BinaryTree<T>right文檔大全實用標準文案61.62. .63. .64.65. ;66.void PostOrder(BTNode<T> *r);int Height( const BTNode<T> *r) const ;int NodeCount(const BTNode<T> *r) const ;67. template <cla

16、ss T>68. BinaryTree<T>:BinaryTree()69. 70. root=NULL;71. 72.73. template <class T>74. BinaryTree<T>:BinaryTree()75. 76.77. 78.79. template <class T>80. void BinaryTree<T>:Pre_Order()81. 82. PreOrder(root);83. 84.85. template <class T>86. void BinaryTree<T>

17、;:In_Order()87. 88. InOrder(root);89. 90.91. template <class T>92. void BinaryTree<T>:Post_Order()93. 94. PostOrder(root);95. 96.97. template <class T>98. int BinaryTree<T>:TreeHeight()const99. 100. return Height(root);101. 102.103. template <class T>104. int BinaryTree

18、<T>:TreeNodeCount() const文檔大全實用標準文案105. 106.returnNodeCount(root);107. 108.109. template <classT>110. voidBinaryTree<T>:DestroyTree()111. 112.Destroy(root);113.114.115. template <classT>116. voidBinaryTree<T>:PreOrder(BTNode<T>117. 118.if (r!=NULL)119.120.cout<

19、<r->data<< ''121.PreOrder(r->lChild);122.PreOrder(r->rChild);123.124. 125.126. template <classT>127. voidBinaryTree<T>:InOrder(BTNode<T>128. 129.if (r!=NULL)130.131.InOrder(r->lChild);132.cout<<r->data<< ''133.InOrder(r->rChild

20、);134.135. 136.137. template <classT>138. voidBinaryTree<T>:PostOrder(BTNode<T>139. 140.if (r!=NULL)141.142.PostOrder(r->lChild);143.PostOrder(r->rChild);144.cout<<r->data<< ''145.146. 147.148. template <classT>*r)*r)*r)文檔大全實用標準文案149. int BinaryTr

21、ee<T>:NodeCount( const BTNode<T> *r) const150. 151. if (r=NULL)152. return0;153. else154. return1+NodeCount(r->lChild)+NodeCount(r->rChild);155. 156.157. template <class T>158. int BinaryTree<T>:Height( const BTNode<T> *r) const159. 160. if (r=NULL)161. return 0;1

22、62. else163. 164. int lh,rh;165. lh=Height(r->lChild);166. rh=Height(r->rChild);167. return 1+(lh>rh?lh:rh);168. 169. 170.171. template <class T>172. void BinaryTree<T>:Destroy(BTNode<T> *&r)173. 174. if(r!=NULL)175. 176. Destroy(r->lChild);177. Destroy(r->rChild

23、);178. delete r;179. r=NULL;180. 181. 182.183. template <class T>184. void BinaryTree<T>:Change(BTNode<T> *r) / 將二叉樹 bt 所有結點的左右子樹交換185. 186. BTNode<T> *p;187. if (r)188. p=r->lChild;189. r->lChild=r->rChild;190. r->rChild=p; /左右子女交換191. Change(r->lChild);/交換左子樹

24、上所有結點的左右子樹192. Change(r->rChild);/交換右子樹上所有結點的左右子樹文檔大全實用標準文案193. 194. 195.196. template <class T>197. void BinaryTree<T>:MakeTree(TpData,BinaryTree<T> leftTree,BinaryTree<T> rightTree)198. 199. root = newBTNode<T>();200. root->data = pData;201. root->lChild= lef

25、tTree.root;202. root->rChild= rightTree.root;203. cpp(3)MinHeap.h 最小堆實現(xiàn)view plain copy2.usingnamespace std;.8.template <class T>class MinHeapprivate :T *heap;元素數(shù)組,0號位置也儲存元素int CurrentSize; /目前元素個數(shù)int MaxSize; /可容納的最多元素個數(shù)voi

26、d FilterDown( const int start, const int 使關鍵字小的節(jié)點在上void FilterUp( int start);/ 自下往上調整public :MinHeap(int n=1000);MinHeap();bool Insert( const T &x);/ 插入元素T RemoveMin(); /刪除最小元素T GetMin(); /取最小元素bool IsEmpty() const ;bool IsFull()const ;void Clear();template <class T>MinHeap<T>:MinHea

27、p( int n)1. #include <iostream>end); /自上往下調整,文檔大全實用標準文案29. . 30. MaxSize=n;31. heap=new TMaxSize;32. CurrentSize=0;33. 34.35. template <class T>36. MinHeap<T>:MinHeap()37. 38. delete heap;39. 1.template <class T>

28、void MinHeap<T>:FilterUp( int start) / 自下往上調整 int j=start,i=(j-1)/2;/i 指向 j 的雙親節(jié)點T temp=heapj;while (j>0) if (heapi<=temp)break ;elseheapj=heapi;j=i;i=(i-1)/2; heapj=temp;template <class T>62.void MinHeap<T>:FilterDown( const int start, const int鍵字小的節(jié)點在上end) /自上往下調整,使關63. 64.

29、inti=start,j=2*i+1;65.Ttemp=heapi;66.while (j<=end)67.68.if ( (j<end) &&69.j+;70.if (temp<=heapj)71.break ;(heapj>heapj+1)文檔大全72. .73. .7.78. .4.實用標準文案else(heapi=heapj;i=j； j=2*j+1;heapi=temp;template <class T>bool Min

30、Heap<T>:Insert( const T &x) (if (CurrentSize=MaxSize) return false ;heapCurrentSize=x;FilterUp(CurrentSize);CurrentSize+;return true ;95. template <class T>96. T MinHeap<T>:RemoveMin()97. (98. T x=heap0;99. heap0=heapCurrentSize-1;100.101. CurrentSize-;102. FilterDown(0,Current

31、Size-1);/調整新的根節(jié)點103.104. return x;105. 106.107. template <class T>108. T MinHeap<T>:GetMin()109. 110. return heap0;111. 112.113. template <class T>114. bool MinHeap<T>:IsEmpty() const115. 文檔大全實用標準文案116. return CurrentSize=0;117. 118.119. template <class T>120. bool MinHeap<T>:IsFull() const121. 122. return CurrentSize=MaxSize;123. 124.125. tem