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

1、0023算法笔记一一【贪心算法】哈夫曼编码问题1、问题描述哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码 算法用字符在文件中出现的 频率表来建立一个用0, 1串表示各字符的最优表示方式。一个包含 100,000个字符的文件，各字符出现频率不同，如下表所示。abCdef频率(千次)4513121695定长码000001010Oil100101变长码010110011111011100有多种方式表示文件中的信息，若用 0,1码表示字符的方法，即每 个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示 一个字符，整个文件编码需要 30

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

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

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

5、新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列 Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树To构造过程如图所示：3 / 16f * 工3具体代码实现如下:(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。 / 下标从 1 开始BinaryTree t = HuffmanTree(f,N) 。cout各字符出现的对应频率分别为：e

7、ndl。for ( int i=1 。 i=N 。 i+) TOC o 1-5 h z coutci: fi。coutendl。cout生成二叉树的前序遍历结果为：endl。t.Pre_Order() 。coutendl 。cout生成二叉树的中序遍历结果为：endl。t.In_Order() 。coutendl 。t.DestroyTree() 。return 0。template BinaryTree HuffmanTree(Type f口，int 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/建优先队列MinHeapHuffman Q(n) 。for ( int i=1 。 i=n 。 i+) Q.Insert(wi)/反复合并最小频率树 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 二叉树实现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 所有结点的左右子树交换BTNode *p 。 if (r) p=r-lChild。r-lChild=r-rChild。r-rChild=p。 /左右子女交换Change(r-lChild)。/交换左子树上所有结点的左右子树Chan

17、ge(r-rChild)。/交换右子树上所有结点的左右子树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 最小堆实现cpp view plain copy1.#include 2.using namespace std 。3.template 4.

18、class MinHeap5.6.private7.T *heap/元素数组，0号位置也储存元素8.intCurrentSMaxSize/目前元素个数可容纳的最多元素个数10.11.void FilterDown(字小的节点在上const intstart, const int end) 。 /自上往下调整，使关键12.void FilterUp(int start)/自下往上调整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/元素数组，0号位置也储存元素8.intCurrentSMaxSize/目前元素个数可容纳的最多元素个数10.11.void FilterDown(字小的节点在上const intstart, const int end) 。 /自上往下调整，使关键12.void FilterUp(int start)/自下往上调整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) / 自下往上调整int j=start,i=(j-1)/2。 /i 指向 j 的双亲节点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) / 自上往下调整，使关 键字小的节点在上 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/调整新的