0023算法笔记——【贪心算法】哈夫曼编码问题.docx

0023算法笔记——【贪心算法】哈夫曼编码问题
   1、问题描述
      哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。

    有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。
     前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。
     译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。

     从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。
     给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)。dT(c)也是字符c的前缀码长。则平均码长定义为：使平均码长达到最小的前缀码编码方案称为C的最优前缀码。     
     2、构造哈弗曼编码
     哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下：
     (1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
     (2)算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。
     (3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。
      构造过程如图所示：

     具体代码实现如下：
     (1)4d4.cpp，程序主文件
[cpp] view plain copy
1. //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 = 6;  
9.   
10. template<class Type> class Huffman;  
11.   
12. template<class Type>   
13. BinaryTree<int> HuffmanTree(Type f[],int n);  
14.   
15. template<class Type>   
16. class Huffman  
17. {  
18.     friend BinaryTree<int> HuffmanTree(Type[],int);  
19.     public:  
20.         operator Type() const   
21.         {  
22.             return weight;  
23.         }  
24.     //private:  
25.         BinaryTree<int> tree;  
26.         Type weight;  
27. };  
28.   
29. int main()  
30. {  
31.     char c[] = {'0','a','b','c','d','e','f'};  
32.     int f[] = {0,45,13,12,16,9,5};//下标从1开始  
33.     BinaryTree<int> t = HuffmanTree(f,N);  
34.   
35.     cout<<"各字符出现的对应频率分别为："<<endl;  
36.     for(int i=1; i<=N; i++)  
37.     {  
38.         cout<<c[i]<<":"<<f[i]<<" ";  
39.     }  
40.     cout<<endl;  
41.   
42.     cout<<"生成二叉树的前序遍历结果为："<<endl;  
43.     t.Pre_Order();  
44.     cout<<endl;  
45.   
46.     cout<<"生成二叉树的中序遍历结果为："<<endl;  
47.     t.In_Order();  
48.     cout<<endl;  
49.   
50.     t.DestroyTree();  
51.     return 0;  
52. }  
53.   
54. template<class Type>  
55. BinaryTree<int> HuffmanTree(Type f[],int n)  
56. {  
57.     //生成单节点树  
58.     Huffman<Type> *w = new Huffman<Type>[n+1];  
59.     BinaryTree<int> z,zero;  
60.   
61.     for(int i=1; i<=n; i++)  
62.     {  
63.         z.MakeTree(i,zero,zero);  
64.         w[i].weight = f[i];  
65.         w[i].tree = z;  
66.     }  
67.   
68.     //建优先队列  
69.     MinHeap<Huffman<Type>> Q(n);  
70.     for(int i=1; i<=n; i++) Q.Insert(w[i]);  
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(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.     delete[] w;  
87.   
88.     return x.tree;  
89. }  
     (2)BinaryTree.h 二叉树实现
[cpp] view plain copy
1. #include<iostream>  
2. using namespace std;  
3.   
4. template<class T>  
5. struct BTNode  
6. {  
7.     T data;  
8.     BTNode<T> *lChild,*rChild;  
9.   
10.     BTNode()  
11.     {  
12.         lChild=rChild=NULL;  
13.     }  
14.   
15.     BTNode(const T &val,BTNode<T> *Childl=NULL,BTNode<T> *Childr=NULL)  
16.     {  
17.         data=val;  
18.         lChild=Childl;  
19.         rChild=Childr;  
20.     }  
21.   
22.     BTNode<T>* CopyTree()  
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<class T>  
39. class BinaryTree  
40. {  
41.     public:  
42.         BTNode<T> *root;  
43.         BinaryTree();  
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> leftTree,BinaryTree<T> rightTree);  
55.         void Change(BTNode<T> *r);  
56.   
57.     private:  
58.         void Destroy(BTNode<T> *&r);  
59.         void PreOrder(BTNode<T> *r);  
60.         void InOrder(BTNode<T> *r);  
61.         void PostOrder(BTNode<T> *r);  
62.   
63.         int Height(const BTNode<T> *r)const;  
64.         int NodeCount(const BTNode<T> *r)const;  
65. };  
66.   
67. template<class 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>::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()const  
99. {  
100.     return Height(root);  
101. }  
102.   
103. template<class T>  
104. int BinaryTree<T>::TreeNodeCount()const  
105. {  
106.     return NodeCount(root);  
107. }  
108.   
109. template<class T>  
110. void BinaryTree<T>::DestroyTree()  
111. {  
112.     Destroy(root);  
113. }  
114.   
115. template<class T>  
116. void BinaryTree<T>::PreOrder(BTNode<T> *r)  
117. {  
118.     if(r!=NULL)  
119.     {  
120.         cout<<r->data<<' ';  
121.         PreOrder(r->lChild);  
122.         PreOrder(r->rChild);  
123.     }  
124. }  
125.   
126. template<class T>  
127. void BinaryTree<T>::InOrder(BTNode<T> *r)  
128. {  
129.     if(r!=NULL)  
130.     {  
131.         InOrder(r->lChild);  
132.         cout<<r->data<<' ';  
133.         InOrder(r->rChild);  
134.     }  
135. }  
136.   
137. template<class T>  
138. void BinaryTree<T>::PostOrder(BTNode<T> *r)  
139. {  
140.     if(r!=NULL)  
141.     {  
142.         PostOrder(r->lChild);  
143.         PostOrder(r->rChild);  
144.         cout<<r->data<<' ';  
145.     }  
146. }  
147.   
148. template<class T>  
149. int BinaryTree<T>::NodeCount(const BTNode<T> *r)const  
150. {  
151.     if(r==NULL)  
152.         return 0;  
153.     else  
154.         return 1+NodeCount(r->lChild)+NodeCount(r->rChild);  
155. }  
156.   
157. template<class T>  
158. int BinaryTree<T>::Height(const BTNode<T> *r)const  
159. {  
160.     if(r==NULL)  
161.         return 0;  
162.     else  
163.     {  
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);  
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);  //交换左子树上所有结点的左右子树  
192.         Change(r->rChild);  //交换右子树上所有结点的左右子树  
193.     }  
194. }  
195.   
196. template<class T>  
197. void BinaryTree<T>::MakeTree(T 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)MinHeap.h 最小堆实现
[cpp] view plain copy
1. #include <iostream>  
2. using namespace std;  
3. template<class T>  
4. class MinHeap  
5. {  
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(int n=1000);  
16.         ~MinHeap();  
17.         bool Insert(const T &x); //插入元素  
18.   
19.         T RemoveMin(); //删除最小元素  
20.         T GetMin(); //取最小元素  
21.   
22.         bool IsEmpty() const;  
23.         bool IsFull() const;  
24.         void Clear();  
25. };  
26.   
27. template<class T>  
28. MinHeap<T>::MinHeap(int n)  
29. {  
30.     MaxSize=n;  
31.     heap=new T[MaxSize];  
32.     CurrentSize=0;  
33. }  
34.   
35. template<class T>  
36. MinHeap<T>::~MinHeap()  
37. {  
38.     delete []heap;  
39. }  
40.   
41. template<class T>  
42. void MinHeap<T>::FilterUp(int start) //自下往上调整  
43. {  
44.     int j=start,i=(j-1)/2; //i指向j的双亲节点  
45.     T temp=heap[j];  
46.   
47.     while(j>0)  
48.     {  
49.         if(heap[i]<=temp)  
50.             break;  
51.         else  
52.         {  
53.             heap[j]=heap[i];  
54.             j=i;  
55.             i=(i-1)/2;  
56.         }  
57.     }  
58.     heap[j]=temp;  
59. }  
60.   
61. template<class T>  
62. void MinHeap<T>::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上  
63. {  
64.     int i=start,j=2*i+1;  
65.     T temp=heap[i];  
66.     while(j<=end)  
67.     {  
68.         if( (j<end) && (heap[j]>heap[j+1]) )  
69.             j++;  
70.         if(temp<=heap[j])  
71.             break;  
72.         else  
73.         {  
74.             heap[i]=heap[j];  
75.             i=j;  
76.             j=2*j+1;  
77.         }  
78.     }  
79.     heap[i]=temp;  
80. }  
81.   
82. template<class T>  
83. bool MinHeap<T>::Insert(const T &x)  
84. {  
85.     if(CurrentSize==MaxSize)  
86.         return false;  
87.   
88.     heap[CurrentSize]=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=heap[0];  
99.     heap[0]=heap[CurrentSize-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 heap[0];  
111. }  
112.   
113. template<class T>  
114. bool MinHeap<T>::IsEmpty() const  
115. {  
116.     return CurrentSize==0;  
117. }  
118.   
119. template<class T>  
120. bool MinHeap<T>::IsFull() const  
121. {  
122.     return CurrentSize==MaxSize;  
123. }  
124.   
125. template<class T>  
126. void MinHeap<T>::Clear()  
127. {  
128.     CurrentSize=0;  
129. }  
     3、贪心选择性质
     二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码。设b和c是二叉树T的最深叶子，且为兄弟。设f(b)<=f(c)，f(x)<=f(y)。由于x和y是C中具有最小频率的两个字符，有f(x)<=f(b)，f(y)<=f(c)。首先，在树T中交换叶子b和x的位置得到T'，然后再树T'中交换叶子c和y的位置，得到树T''。如图所示：

    由此可知，树T和T'的前缀码的平均码长之差为：

     因此，T''表示的前缀码也是最优前缀码，且x,y具有相同的码长，同时，仅最优一位编码不同。
     4、最优子结构性质
     二叉树T表示字符集C的一个最优前缀码，x和y是树T中的两个叶子且为兄弟，z是它们的父亲。若将z当作是具有频率f(z)=f(x)+f(y)的字符，则树T’=T-{x,y}表示字符集C’=C-{x, y} ∪ { z}的一个最优前缀码。因此，有：

     如果T’不是C’的最优前缀码，假定T”是C’的最优前缀码，那么有，显然T”’是比T更优的前缀码，跟前提矛盾！故T'所表示的C'的前缀码是最优的。
     由贪心选择性质和最优子结构性质可以推出哈夫曼算法是正确的，即HuffmanTree产生的一棵最优前缀编码树。
     程序运行结果如图：