0023算法笔记——哈夫曼编码问题

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

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

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

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

5、率之和，并将新树插入优先队列Q。经过n - 1次的合并后，优先队列中只剩下一棵树，即所要求的树T。构造过程如图所示:f * M©具体代码实现如下：(1)4d4.cpp，程序主文件cpp view pla in copy1./4d4 贪心算法哈夫曼算法2.#include "stdafx.h"3.#include "BinaryTree.h"4.#include "MinHeap.h"5.#include <iostream>6.using namespace std;7.8.const int N = 69.10

6、.template <classType> class Huffman;11.12.template <classType>13.BinaryTreev int> HuffmanTree(Type f,int n);14.15.template vclassType>16.class Huffman17.18.friend BinaryTreev int > HuffmanTree(Type,int );19.public :20.operator Type()const21.22.return weight;23.24./private:25.Bin

7、aryTreevint > tree;26.Type weight;27.；28.29.int main()30.31.char c = 'O' , 'a' , 'b' , 'c' ,'d','e' ,'f' ;32.int f = 0,45,13,12,16,9,5;/下标从1开始33.BinaryTreevint > t = HuffmanTree(f,N);34.35.coutvv"各字符出现的对应频率分别为："vvendl;36.for ( i

8、nt i=1; iv=N; i+)37.38.coutvvcivv":" vvfivv ""39.40.coutvvendl;41.42.coutvv"生成二叉树的前序遍历结果为："vvendl;43.t.Pre_Order();44.coutvvendl;45.46.coutvv"生成二叉树的中序遍历结果为："vvendl;47.t.In_Order();48.coutvvendl;49.50.t.DestroyTree();51.return 0;52.53.54.template vclass Type55.

9、BinaryTreev int > HuffmanTree(Type n)56.57./生成单节点树58.HuffmanvType> *w =new HuffmanvType>n+1;59.BinaryTreevint > z,zero;60.61.for ( int i=1; iv=n; i+)62.63.z.MakeTree(i,zero,zero);64.wi.weight = fi;65.wi.tree = z;66.67.68./建优先队列69.MinHeap<Huffman<Type>> Q(n);70.for ( int

10、 i=1; i<=n; i+) Qnsert(wi);71.72./反复合并最小频率树73.Huffman<Type> x,y;74.for ( int i=1; i<n; i+)75.76.x = Q.RemoveMin();77.y = Q.RemoveMin();78.z.MakeTree(O,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.delete w;87.88.return x.tree;89.(2)B

11、i naryTree.h二叉树实现cpp view pla incopy1.#include<iostream>2.using namespace std;3.4.template <class T>5.struct BTNode6.7.T data;8.BTNode<T> *IChild,*rChild;9.10.BTNode()11.12.IChild=rChild=NULL;13.14.15.BTNode( const T &val,BTNode<T> *Childl=NULL,BTNode<T> *Childr=NUL

12、L)16.17.data=val;6 / 160.IChild=Childl;rChild=Childr;BTNode<T>* CopyTree()BTNode<T> *nl,*nr,*nn;if (&data=NULL)return NULL;nl=IChild->CopyTree();nr=rChild

13、->CopyTree();nn= new BTNode<T>(data,nl,nr); return nn;template vclass T>class BinaryTreepublic :BTNode<T> *root;BinaryTree();BinaryTree();void Pre_Order();void In_Order();void Post_Order();int TreeHeight() const ;int TreeNodeCount() const void DestroyTree();void MakeTree(T pData,Bi

14、naryTree<T> leftTree,BinaryTree<T> rightTree);void Change(BTNode<T> *r);privatevoid Destroy(BTNode<T> *&r);void PreOrder(BTNode<T> *r);void lnOrder(BTNode<T> *r);61.void PostOrder(BTNode<T> *r);62.63.int Height( const BTNode<T> *r)const ;64.int Nod

15、eCount( const BTNode<T>*r) const ;65.;66.67.template vclass T>68.BinaryTree<T>:BinaryTree()69.70.root=NULL;71.72.73.template vclass T>74.BinaryTree<T>:BinaryTree()8.79.template vclass T>80.void BinaryTree<T>:Pre_Order()81.82.PreOrder(root);83.84.85.template

16、 vclass T>86.void BinaryTree<T>:ln_Order()87.88.InOrder(root);89.90.91.template vclass T>92.void BinaryTreevT>:Post_Order()93.94.PostOrder(root);95.96.97.template vclass T>98.int BinaryTreevT>:TreeHeight()const99.100.return Height(root);101.102.103.template vclass T>104.int B

17、inaryTreevT>:TreeNodeCount()const047.148.return NodeCount(root);template vclass T>void BinaryTree<T>:DestroyTree()Destro

18、y(root);template vclass T>void BinaryTree<T>:PreOrder(BTNode<T> *r)if (r!=NULL)cout<<r->datavv''PreOrder(r->IChild);PreOrder(r->rChild);template vclass T>void BinaryTreevT>:lnOrder(BTNodevT> *r)if (r!=NULL)InOrder(r->lChild);coutvvr->datavv'&#

19、39;lnOrder(r->rChild);template vclass T>void BinaryTreevT>:PostOrder(BTNodevT> *r) if (r!=NULL)PostOrder(r->IChild);PostOrder(r->rChild); coutvvr->datavv''template vclass T>70.171.172

20、.91.192.BTNode<T> *p;if (r)p=r->IChild;r->IChild=r->rChild;r->rChild=p;/左右子女交换Change(r->IChiId);/交换左子树上所有结点的左右子树Change(r->rChiId);/交换右子树上所有结点的左右子树int BinaryTree<T>:NodeCount( const BTNode<T>

21、*r) constif (r=NULL)return 0;elsereturn 1+NodeCount(r->IChild)+NodeCount(r->rChild);template vclass T>int BinaryTree<T>:Height(const BTNode<T> *r) constif (r=NULL)return 0;elseint lh,rh;lh=Height(r->IChild);rh=Height(r->rChild);return 1+(lh>rh?lh:rh);template vclass T&g

22、t;void BinaryTree<T>:Destroy(BTNode<T> *&r)if (r!=NULL)Destroy(r->IChild);Destroy(r->rChild);delete r;r=NULL;template vclass T>void BinaryTree<T>:Change(BTNode<T> *r)/ 将二叉树 bt 所有结点的左右子树交换96.template vclass T>197.void BinaryTree<T>:MakeTree(T

23、 pData,BinaryTree<T> leftTree,BinaryTree<T> rightTree)198.199.root =new BTNode<T>();200.root->data = pData;201.root->lChild = leftTree.root;202.root->rChild = rightTree.root;203.(3)Mi nH eap.h最小堆实现cppview pla incopy1.#include <iostream>2.using namespace std;3.templat

24、e vclass T>4.class MinHeap5.6.private :7.T *heap;/元素数组，0号位置也储存元素8.int CurrentSize;/目前元素个数9.int MaxSize;/可容纳的最多元素个数10.11.void FilterDown(const int start, const int end); / 自上往下调整，使关键字小的节点在上12.void FilterUp(int start);/自下往上调整13.14.public :15.MinHeap(intn=1000);16.MinHeap();17.bool Insert(const T &a

25、mp;x);/插入元素18.19.T RemoveMin();/删除最小元素20.T GetMin();/取最小元素21.22.bool lsEmpty()const ;23.bool IsFull()const ;24.void Clear();25.;26.27.template vclass T>28.MinHeap<T>:MinHeap(int n)29.30.MaxSize=n;31.heap= new TMaxSize;32.CurrentSize=0;33.34.35.template vclass T>36.MinHeapvT:MinHeap()37.3

26、8.delete heap;39.40.41.template vclass T>42.void MinHeap<T>:FilterUp(int start)/自下往上调整43.44.int j=start,i=(j-1)/2;/i指向j的双亲节点45.T temp=heapj;46.47.while (j>0)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.template vclass T>6

27、2.void MinHeap<T>:FilterDown(关键字小的节点在上const intstart, const int end) /自上往下调整，使63.64.int i=start,j=2*i+1;65.T temp=heapi;66.while (j<=end)67.68.if ( (jvend) && (heapj>heapj+1)69.j+;70.if (tempv=heapj)71.break ;72.else73.74.heapi=heapj;75.i=j；76.j=2*j+1;77.78.79.heapi=temp;80.81.82

28、.template <class T>83.bool MinHeap<T>:lnsert(constT &x)84.85.if (CurrentSize=MaxSize)86.return false ;87.88.heapCurrentSize=x;89.FilterUp(CurrentSize);90.91.CurrentSize+;92.return true ;93.94.95.template <class T>96.T MinHeap<T>:RemoveMin()97.98.T x=heap0;99.heap0=heapCur

29、rentSize-1;100.101.CurrentSize-;102.FilterDown(0,CurrentSize-1);/调整新的根节点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>:lsEmpty()const115.116. return CurrentSize=O;117. 118.118. template vclass T>119. bool MinHeap<T>:lsFull()const120. 121. return CurrentSize=MaxSize;122. 124.123. template vclass T>124. void MinHeap<T>:Clear()125. 126. CurrentSize=O