编程练习——Huffman编码

这个类的名字叫huffman Tree，但是不仅仅是生成huffman Tree，因为Huffman树的生成要使用优先队列，也就是堆。stl中其实有这个的实
现。但是我机器里的vs2005这个堆的使用有点小bug（估计是stl中使用的就是数组存储，而且数组一旦固定大小，就再也无法改变，其实这样实现失去了堆的某些特
性。 _ 所以我还是自己实现了一下 _
。顺便练习下。）。刚开始的时候
就采用int作为编码的存储单元。后来发现huffman是可变长编码。所以使用int作为编码单元就失去了huffman的特性。于是寻找bit数组。找到了bit
set这个stl类，却发现这个是不可变的。无语。只得自己实现一个可变大小的 _ bit vector _

。然后近乎重写了这个Huffman的编码和解码。不过也不是很难。在这之间又陆陆续续的发现了一系列的bug和编译错误。对以后的编程大有启发。

1. /* created by chico chen
2. *  date 2008/10/25
3. */
4. 5. 6. #ifndef HUFFMAN_TREE
5. #define HUFFMAN_TREE
6. #include “Heap.h”
7. #include “TreeNode.h”
8. #include “BinaryTree.h”
9. #include 
10. #include “…/…/ArithmeticTest/ArithmeticTest/BITVector.h”
11. using namespace std;
12. 15. // this class is used for the combin function in huffmanTree class.
13. class IntCombin
14. {
15. public :
16. static int Add( int i, int j)
17. {
18. return i+j;
19. }
20. };
21. 25. // this class for compare tree node
22. template < class T>
23. class TreeNodeCompare
24. {
25. public :
26. static bool Up(TreeNode* d1, TreeNode* d2)
27. {
28. return Lt(d1->getData(),d2->getData());
29. }
30. 35. static bool Eq(T& d1, T& d2)
31. {
32. if (d1 == d2)
33. return true ;
34. return false ;
35. }
36. 42. static bool Gt(T& d1, T& d2)
37. {
38. if (d1 > d2)
39. return true ;
40. return false ;
41. }
42. 49. static bool Lt(T& d1, T& d2)
43. {
44. if (d1 < d2)
45. return true ;
46. return false ;
47. }
48. };
49. 57. // this class is for storing huffman code.
50. // bits and the length of bits
51. class HuffmanCode
52. {
53. public :
54. BITVector bits;
55. int len;
56. HuffmanCode()
57. {
58. len = 0;
59. }
60. 69. HuffmanCode( const HuffmanCode & codes):bits(codes.bits)
61. {
62. len  = codes.len;
63. 73. }
64. 75. const HuffmanCode& operator=( const HuffmanCode & codes)
65. {
66. if ( this != &codes)
67. {
68. this ->len = codes.len;
69. this ->bits = codes.bits;
70. }
71. return * this ;
72. }
73. 85. ~HuffmanCode()
74. {
75. 88. }
76. };
77. 91. template < class T, class Cmp, class Combin>
78. class HuffmanTree: public BinaryTree
79. {
80. private :
81. // store the data, and sort it, then for building a huffman tree
82. Heap<TreeNode* ,Cmp> huffmanQueue;
83. 98. const unsigned int mask;
84. // the max number can be shifted, if it is unsigned int then it will be 32.
85. const int maxShiftNum;
86. 102. 103. TreeNode* initTree()
87. // init the huffman tree
88. {
89. TreeNode * combinNode = NULL;
90. T tempData;
91. while (! this ->huffmanQueue.IsEmpty())
92. {
93. // fetch two small data and generate a large data
94. TreeNode * node1 = this ->huffmanQueue.Top();
95. combinNode = node1;
96. this ->huffmanQueue.RemoveTop();
97. if (! this ->huffmanQueue.IsEmpty())
98. {
99. TreeNode * node2 = this ->huffmanQueue.Top();
100. this ->huffmanQueue.RemoveTop();
101. tempData =  Combin::Add(node1->getData(),node2->getData());
102. 120. 121. if (Cmp::Lt(node1->getData(),node2->getData()))
103. {
104. // here is comparing the data1 of node1 and the data2 of node2
105. //  Cmp:Lt means ‘<’ and Cmp:Gt means ‘>’
106. 126. combinNode = new TreeNode(tempData,node1,node2);
107. }
108. else
109. {
110. combinNode = new TreeNode(tempData,node2,node1);
111. }
112. this ->huffmanQueue.Insert(combinNode);
113. }
114. else
115. {
116. break ;
117. }
118. 139. }
119. return combinNode;
120. }
121. 143. 144. 145. // the final huffman code
122. map<T,HuffmanCode> huffmanTable;
123. 148. 149. void SelfEncode(TreeNode* subRoot,unsigned int bitcode, int num,map<T,HuffmanCode > &ht)
124. // encoding the data from a huffman tree.
125. // The left branch is 0, and the right branch is 1
126. {
127. 154. if (subRoot != NULL)
128. {
129. 157. if (subRoot->left == NULL && subRoot->right==NULL)
130. {
131. HuffmanCode hc;
132. hc.bits.SetInt(bitcode,0,maxShiftNum-num);
133. hc.len = maxShiftNum-num;
134. ht[subRoot->getData()] = hc;
135. return ;
136. }
137. else
138. {
139. if (num<=0)
140. {
141. throw “the huffman is too deep!” ;
142. }
143. 172. 173. SelfEncode(subRoot->left,bitcode,num-1,ht);
144. bitcode = bitcode | (0x80000000 >> (maxShiftNum-num));
145. SelfEncode(subRoot->right,bitcode,num-1,ht);
146. }
147. }
148. 179. 180. }
149. 182. 183. void DecodeFromTree(TreeNode* subRoot,BITVector& bits, int index, const int & len,vector& decode)
150. // decoding the code. use the code to search the data from the huffmanTree.
151. // here you can create you own map<code,data> deHuffmanTable.
152. // but I can not analyze the space the table will use,
153. // so I find the data by searching huffman tree
154. {
155. if (index == len)
156. {
157. if (subRoot->getLeft()==NULL && subRoot->getRight() == NULL)
158. {
159. 194. decode.push_back(subRoot->getData());
160. return ;
161. }
162. throw “code length is not match the bits length. Huffman Tree construct error.” ;
163. }
164. if (subRoot == NULL)
165. {
166. throw “decode error!” ;
167. 203. }
168. else if (subRoot->getLeft() == NULL && subRoot->getRight() == NULL)
169. {
170. 207. decode.push_back(subRoot->getData());
171. return DecodeFromTree( this ->root,bits,index,len,decode);
172. }
173. 211. if (bits.Get(index) == 0)
174. {
175. return DecodeFromTree(subRoot->getLeft(),bits,index+1,len,decode);
176. }
177. else if (bits.Get(index)==1)
178. {
179. 218. return DecodeFromTree(subRoot->getRight(),bits,index+1,len,decode);
180. }
181. else
182. {
183. throw “code error!” ;
184. }
185. 225. 226. }
186. 228. 229. unsigned int FindCodeFromTable(T& data)
187. // find the data code from huffman table
188. // may be not efficient.
189. {
190. return this ->huffmanTable[data];
191. }
192. 236. public :
193. 238. HuffmanTree(T t[], int n):
194. BinaryTree(),mask(0x80000000),maxShiftNum( sizeof (unsigned int )*8)
195. // the array t type is T, and the number is n
196. {
197. if (n == 0)
198. return ;
199. TreeNode* node;
200. for ( int i = 0; i < n; i++)
201. {
202. node = new TreeNode(t[i]);
203. this ->huffmanQueue.Insert(node);
204. }
205. this ->root = initTree();
206. }
207. 253. ~HuffmanTree()
208. {
209. // destroy
210. 257. }
211. 259. 260. void SelfEncode()
212. // convert the huffmanTree into huffmanTable
213. // unsigned int code is 32 bits, so the huffman tree has only less than 33 layer.
214. {
215. string s= “” ;
216. 266. SelfEncode( this ->root,0,maxShiftNum, this ->huffmanTable);
217. 268. }
218. 270. 271. 272. void Decode(HuffmanCode& huffmanCode,vector& decode)
219. // use bit to find the data node.
220. {
221. 276. return DecodeFromTree( this ->root,huffmanCode.bits,0,huffmanCode.len,decode);
222. 278. }
223. 280. HuffmanCode Encode(T info[], int n)
224. // n is size
225. {
226. HuffmanCode hc;
227. 285. for ( int i = 0; i < n; i++)
228. {
229. 288. hc.bits.SetBitVector(((HuffmanCode) this ->huffmanTable[info[i]]).bits,hc.len,((HuffmanCode) this ->huffmanTable[info[i]]).len);
230. hc.len +=((HuffmanCode) this ->huffmanTable[info[i]]).len;
231. }
232. 292. return hc;
233. }
234. 295. 296. void PrintHuffmanTable()
235. // print the huffman table
236. // print the pair data<->code
237. {
238. int len = this ->huffmanTable.size();
239. cout << “i/tdata/tcode/n” ;
240. int count = 0;
241. map<T,HuffmanCode>::iterator i= this ->huffmanTable.begin();
242. for (; i != this ->huffmanTable.end(); i++)
243. {
244. cout << count++<< “/t” <<(*i).first<< “/t” ;
245. (*i).second.bits.PrintfZeroOne(0,(*i).second.len);
246. cout<<endl;
247. }
248. 311. }
249. 313. };
250. 315. 316. #endif

这个类设计方面还有些不足之处。比如encode方法

测试一下：

1. int a[10] = {12,224,33,32,1,91,35,34,36,291};
2. HuffmanTree< int ,TreeNodeCompare< int >,IntCombin> ht(a,10);
3. ht.SelfEncode();
4. ht.PrintHuffmanTable();
5. ht.printTree();
6. cout << endl;
7. int info[] = {33,34,33};
8. HuffmanCode hc = ht.Encode(info,3);
9. hc.bits.PrintfZeroOne(0,hc.len);
10. vector< int > code;
11. ht.Decode(hc,code);
12. ** for ** ( int i = 0; i != code.size();i++)
13. {
14. 15. cout<<code[i]<<endl;
15. }
16. 18. ** return ** 0;